Complexity-Theoretic Foundations of Quantum Supremacy Experiments

By Scott Aaronson, Lijie Chen. Cybersecurity and Cyberforensics Conference, 2016

393 citations recorded by the source corpus.

In the near future, there will likely be special-purpose quantum computers with 40--50 high-quality qubits. This paper lays general theoretical foundations for how to use such devices to demonstrate "quantum supremacy": that is, a clear quantum speedup for some task, motivated by the goal of overturning the Extended Church-Turing Thesis as confidently as possible. First, we study the hardness of sampling the output distribution of a random quantum circuit, along the lines of a recent proposal by the Quantum AI group at Google. We show that there's a natural average-case hardness assumption, which has nothing to do with sampling, yet implies that no polynomial-time classical algorithm can pass a statistical test that the quantum sampling procedure's outputs do pass. Compared to previous work -- for example, on BosonSampling and IQP -- the central advantage is that we can now talk directly about the observed outputs, rather than about the distribution being sampled. Second, in an attempt to refute our hardness assumption, we give a new algorithm, inspired by Savitch's Theorem, for simulating a general quantum circuit with n qubits and depth d in polynomial space and dO(n) time. We then discuss why this and other known algorithms fail to refute our assumption. Third, resolving an open problem of Aaronson and Arkhipov, we show that any strong quantum supremacy theorem -- of the form "if approximate quantum sampling is classically easy, then the polynomial hierarchy collapses"-- must be non-relativizing. This sharply contrasts with the situation for exact sampling. Fourth, refuting a conjecture by Aaronson and Ambainis, we show that there is a sampling task, namely Fourier Sampling, with a 1 versus linear separation between its quantum and classical query complexities. Fifth, in search of a "happy medium" between black-box and non-black-box arguments, we study quantum supremacy relative to oracles in P/poly. Previous work implies that, if one-way functions exist, then quantum supremacy is possible relative to such oracles. We show, conversely, that some computational assumption is needed: if SampBPP = SampBQP and NP ⊆ BPP, then quantum supremacy is impossible relative to oracles with small circuits.

View Paper: https://www.semanticscholar.org/paper/5a4b237a2d381ed52bcf70c05d164e4f44e3ef47

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Quantum computational advantage using photons (2020, background): “Quantum sampling algorithms ( 3 - 6 ), based on plausible computational complexity arguments, were proposed for near-term demonstrations of quantum computational speedup in solving certain well-defined tasks compared to current supercomputers.”
Random Quantum Circuits (2022, background): “An abstract information theoretic task was chosen for the demonstration, that of sampling from the output distribution of a state evolved under a random quantum circuit (277, 124, 278, 279); the task illustrates the utility of quantum circuit dynamics for benchmarking near-term quantum devices.”
Simulation of quantum circuits by low-rank stabilizer decompositions (2018, background): “In certain special cases the memory footprint can be reduced by recasting the simulation problem as a tensor network contraction [1, 8, 40].”
Quantum supremacy using a programmable superconducting processor (2019, methodology): “For a given circuit, we collect the measured bitstrings {xi} and compute the linear XEB fidelity [11, 13, 14, 31], which is the mean of the simulated probabilities of the bitstrings we measured: FXEB = 2〈P (xi)〉i − 1 (1)”
Strawberry Fields: A Software Platform for Photonic Quantum Computing (2018, methodology): “Popular techniques include variational quantum eigensolvers [5, 6], quantum approximate optimization algorithms [7, 8], sampling from computationally hard probability distributions [9–17], and quantum annealing [18, 19].”
On the complexity and verification of quantum random circuit sampling (2018, background): “Of the numerous quantum supremacy proposals to date which are conjectured to be robust to noise [8, 9, 19, 26, 27, 28, 29, 30, 31, 32], only two have known worst-to-average-case reductions: BosonSampling and FourierSampling [8, 26].”
Quantum computational supremacy (2017, background): “It is known to hold for random circuits 4 and for IQP 13 and is conjectured to hold for boson sampling, 2 although it does not hold for constant-depth random circuits.”
Quantum advantage with shallow circuits (2017, methodology): “Our problem is more closely related to the Bernstein Vazirani problem [ 17] or, more generally, the Fourier Fishing problem introduced by Aaronson [25, 29].”
Quantum Computing in the NISQ era and beyond (2018, background): “y a bit fuzzy, in several respects. In particular, the resources needed in a classical simulation depend on the depth (number of time steps) of the quantum circuit, as well as on the number of qubits [11, 12, 13]. 5 more powerful quantum technologies we’ll develop in the future. I do think that quan”
Quantum certification and benchmarking (2019, background): “Allowing for exponential time in classical post-processing, one can also sample-efficiently verify coarse-grained versions of the target distribution [16], make use of certain complexity-theoretic assumptions [3], or assumptions on the noise in the quantum device [15, 16, 32].”