A foundational question in quantum computational complexity asks how much more useful a quantum state can be in a given task than a comparable, classical string. Aaronson and Kuperberg showed such a separation in the presence of a quantum oracle, a black box unitary callable during quantum computation. Their quantum oracle responds to a random, marked, quantum state, which is intractable to specify classically. We constrain the marked state in ways that make it easy to specify classically while retaining separations in task complexity. Our method replaces query by state complexity. Furthermore, assuming a widely believed separation between the difficulty of creating a random, complex state and creating a specified state, we propose an experimental demonstration of quantum witness advantage on near-term, distributed quantum computers. Finally, using the fact that a standard, classically defined oracle may enable a quantum algorithm to prepare an otherwise hard state in polynomial steps, we observe quantum-classical oracle separation in heavy output sampling.
翻译：量子计算复杂度中的基本问题询问量子状态在一项特定任务中比一个可比较的古典字符串更有用。 Aaronson 和 Kuperberg 在量子计算过程中可以使用的量子甲骨文(一个黑匣子,一个在量子计算中可以使用的统一线)中展示了这种分离。它们的量子甲骨文对一个随机的、标记的量子状态作出反应,而该质子状态在典型地难以指定。我们限制这个标志性状态的方式使得它容易以传统方式进行指定,同时保留任务复杂性中的分离。我们的方法用国家复杂性来取代查询。此外,假设在创建随机、复杂状态和创建特定状态的困难之间有广泛信仰的区分,我们提议在近期、分布的量子计算机上实验性地展示量子证人优势。 最后,我们利用一个标准,由传统定义的量子算法,可以使量子算法能够在多式步骤中准备一个本来硬的量子状态,我们在重输出抽样中观察量子级或级分离。
相关内容
微信扫码咨询专知VIP会员