We construct a quantum oracle relative to which $\mathsf{BQP} = \mathsf{QMA}$ but 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 assumption is likely needed to construct pseudorandom states, by proving that pseudorandom states do not exist if $\mathsf{BQP} = \mathsf{PP}$. We discuss implications of these results for cryptography, complexity theory, and quantum tomography.
翻译:我们构建了一个量子神器, 相对于它, $\ mathsf{BQP} =\ mathsf ⁇ ma} $, 但伪随机量子状态和伪随机单一变异存在, 反直觉的结果是, 伪随机状态可能会被量子Merlin- Arthur对手“ 撕碎 ” 。 我们解释这种细微现象是如何由量子和经典输入的算法之间的区别而产生的。 另一方面, 我们证明, 建立伪随机状态可能需要某种计算假设, 如果 $\ mathsf{BQP} =\ mathsf{PP} 美元, 伪随机状态并不存在。 我们讨论这些结果对加密、 复杂理论 和量子摄影的影响 。