A game of quantum advantage: linking verification and simulation
arXiv:2011.12173 · doi:10.22331/q-2022-06-30-753
Abstract
We present a formalism that captures the process of proving quantum superiority to skeptics as an interactive game between two agents, supervised by a referee. Bob, is sampling from a classical distribution on a quantum device that is supposed to demonstrate a quantum advantage. The other player, the skeptical Alice, is then allowed to propose mock distributions supposed to reproduce Bob's device's statistics. He then needs to provide witness functions to prove that Alice's proposed mock distributions cannot properly approximate his device. Within this framework, we establish three results. First, for random quantum circuits, Bob being able to efficiently distinguish his distribution from Alice's implies efficient approximate simulation of the distribution. Secondly, finding a polynomial time function to distinguish the output of random circuits from the uniform distribution can also spoof the heavy output generation problem in polynomial time. This pinpoints that exponential resources may be unavoidable for even the most basic verification tasks in the setting of random quantum circuits. Beyond this setting, by employing strong data processing inequalities, our framework allows us to analyse the effect of noise on classical simulability and verification of more general near-term quantum advantage proposals.
arXiv comment44 pages, to be published in Quantum. New version is substantially extended and contains new connections between previous results and the linear cross entropy
References in corpus (36)
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Quantum computational advantage using photons
- Improved Simulation of Stabilizer Circuits
- Characterizing Quantum Supremacy in Near-Term Devices
- Strong quantum computational advantage using a superconducting quantum processor
- Quantum Computational Supremacy
- Quantum annealing with more than one hundred qubits
- Exact and Approximate Unitary 2-Designs: Constructions and Applications
- A blueprint for demonstrating quantum supremacy with superconducting qubits
- Quantum Data Hiding
- Efficient experimental validation of photonic boson sampling against the uniform distribution
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
- Quantum Supremacy and the Complexity of Random Circuit Sampling
- On the experimental verification of quantum complexity in linear optics
- Achieving quantum supremacy with sparse and noisy commuting quantum computations
- Quantum Sampling Problems, BosonSampling and Quantum Supremacy
- A dissipative quantum Church-Turing theorem
- Leveraging Secondary Storage to Simulate Deep 54-qubit Sycamore Circuits
- Quantum logarithmic Sobolev inequalities and rapid mixing
- How "Quantum" is the D-Wave Machine?
- Regimes of classical simulability for noisy Gaussian boson sampling
- Classical Simulation of Quantum Supremacy Circuits
- Anticoncentration theorems for schemes showing a quantum speedup
- Limitations of Noisy Reversible Computation
- Relative Entropy Convergence for Depolarizing Channels
- Sample complexity of device-independently certified "quantum supremacy"
- Benchmarking of Gaussian boson sampling using two-point correlators
- Closing gaps of a quantum advantage with short-time Hamiltonian dynamics
- On contraction coefficients, partial orders and approximation of capacities for quantum channels
- Entropy Production of Doubly Stochastic Quantum Channels
- Comment on: "Classical signature of quantum annealing"
- Limitations of optimization algorithms on noisy quantum devices
- Quantum Brascamp-Lieb Dualities
- Efficient unitary paths and quantum computational supremacy: A proof of average-case hardness of Random Circuit Sampling
- Quantum Subdivision Capacities and Continuous-time Quantum Coding
- The Quantum Supremacy Tsirelson Inequality