Quantum Oracle Separations from Complex but Easily Specified States

Abstract

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.

arXiv comment29 pages, 1 figure

References in corpus (14)

• Characterizing Quantum Supremacy in Near-Term Devices
• Bulk Locality and Quantum Error Correction in AdS/CFT
• Grover's quantum searching algorithm is optimal
• Random Quantum Circuits are Approximate 2-designs
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Microwave Quantum Link between Superconducting Circuits Housed in Spatially Separated Cryogenic Systems
• Average fidelity between random quantum states
• Leveraging Secondary Storage to Simulate Deep 54-qubit Sycamore Circuits
• Algorithmic complexity and entanglement of quantum states
• The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes
• Demonstration of quantum volume 64 on a superconducting quantum computing system
• Characterization of quantum states based on creation complexity
• The Quantum Supremacy Tsirelson Inequality
• Quantum Versus Classical Proofs and Advice