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.