The Quantum Supremacy Tsirelson Inequality
share
A leading proposal for verifying near-term quantum supremacy experiments on noisy random quantum circuits is linear cross-entropy benchmarking. For a quantum circuit C on n qubits and a sample z ∈{0,1}^n, the benchmark involves computing |⟨ z|C|0^n ⟩|^2, i.e. the probability of measuring z from the output distribution of C on the all zeros input. Under a strong conjecture about the classical hardness of estimating output probabilities of quantum circuits, no polynomial-time classical algorithm given C can output a string z such that |⟨ z|C|0^n⟩|^2 is substantially larger than 1/2^n (Aaronson and Gunn, 2019). On the other hand, for a random quantum circuit C, sampling z from the output distribution of C achieves |⟨ z|C|0^n⟩|^2 ≈2/2^n on average (Arute et al., 2019). In analogy with the Tsirelson inequality from quantum nonlocal correlations, we ask: can a polynomial-time quantum algorithm do substantially better than 2/2^n? We study this question in the query (or black box) model, where the quantum algorithm is given oracle access to C. We show that, for any ε≥1/poly(n), outputting a sample z such that |⟨ z|C|0^n⟩|^2 ≥2 + ε/2^n on average requires at least Ω(2^n/4/poly(n)) queries to C, but not more than O(2^n/3) queries to C, if C is either a Haar-random n-qubit unitary, or a canonical state preparation oracle for a Haar-random n-qubit state. We also show that when C samples from the Fourier distribution of a random Boolean function, the naive algorithm that samples from C is the optimal 1-query algorithm for maximizing |⟨ z|C|0^n⟩|^2 on average.
READ FULL TEXT