I am looking for interesting examples of complexity-theoretic and cryptographic problems where we have a significant amount of knowledge about the classical version of the problem, but we have no answers to analogous questions in the quantum case.

I can explain what I’m looking for by giving examples of cases that would have been good answers to my question, say, four years ago:

  • Garbled Circuits: Brakerski and Yuen gave a construction for Quantum Randomized Encodings with quantum encoders and decoders.
  • Zero-Knowledge Constant-Round Protocol for NP: Bitansky and Shmueli gave a classical argument which was post-quantum secure

It would also be nice to have some explanation of the main challenge to developing a quantum analog, if there are a few factors that can be easily isolated.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.