Quantum Pseudorandomness and Classical Complexity

arXiv:2103.09320v4 Announce Type: replace-cross
Abstract: We construct a quantum oracle relative to which $\mathsf{BQP} = \mathsf{QMA}$ but cryptographic pseudorandom quantum states and pseudorandom unitary transformations exist, a counterintuitive result in light of the fact that pseudorandom states can be "broken" by quantum Merlin-Arthur adversaries. We explain how this nuance arises as the result of a distinction between algorithms that operate on quantum and classical inputs. On the other hand, we show that some computational complexity assumption is needed to construct …

adversaries arthur arxiv can complexity cryptographic cs.cc cs.cr fact merlin nuance oracle quant-ph quantum relative result states