How many qubits are needed for quantum computational supremacy?

Abstract

Quantum computational supremacy arguments, which describe a way for a quantum computer to perform a task that cannot also be done by a classical computer, typically require some sort of computational assumption related to the limitations of classical computation. One common assumption is that the polynomial hierarchy (<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="sans-serif">P</mml:mi><mml:mi mathvariant="sans-serif">H</mml:mi></mml:mrow></mml:math>) does not collapse, a stronger version of the statement that<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="sans-serif">P</mml:mi></mml:mrow><mml:mo>≠</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="sans-serif">N</mml:mi><mml:mi mathvariant="sans-serif">P</mml:mi></mml:mrow></mml:math>, which leads to the conclusion that any classical simulation of certain families of quantum circuits requires time scaling worse than any polynomial in the size of the circuits. However, the asymptotic nature of this conclusion prevents us from calculating exactly how many qubits these quantum circuits must have for their classical simulation to be intractable on modern classical supercomputers. We refine these quantum computational supremacy arguments and perform such a calculation by imposing fine-grained versions of the non-collapse conjecture. Our first two conjectures poly3-NSETH(<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>a</mml:mi></mml:math>) and per-int-NSETH(<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>b</mml:mi></mml:math>) take specific classical counting problems related to the number of zeros of a degree-3 polynomial in<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>n</mml:mi></mml:math>variables over<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="double-struck">F</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub></mml:math>or the permanent of an<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>n</mml:mi><mml:mo>×</mml:mo><mml:mi>n</mml:mi></mml:math>integer-valued matrix, and assert that any non-deterministic algorithm that solves them requires<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mn>2</mml:mn><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>c</mml:mi><mml:mi>n</mml:mi></mml:mrow></mml:msup></mml:math>time steps, where<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>c</mml:mi><mml:mo>∈</mml:mo><mml:mo fence="false" stretchy="false">{</mml:mo><mml:mi>a</mml:mi><mml:mo>,</mml:mo><mml:mi>b</mml:mi><mml:mo fence="false" stretchy="false">}</mml:mo></mml:math>. A third conjecture poly3-ave-SBSETH(<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mi>a</mml:mi><mml:mo>′</mml:mo></mml:msup></mml:math>) asserts a similar statement about average-case algorithms living in the exponential-time version of the complexity class<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="sans-serif">S</mml:mi><mml:mi mathvariant="sans-serif">B</mml:mi><mml:mi mathvariant="sans-serif">P</mml:mi></mml:mrow></mml:math>. We analyze evidence for these conjectures and argue that they are plausible when<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>a</mml:mi><mml:mo>=</mml:mo><mml:mn>1</mml:mn><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mn>2</mml:mn></mml:math>,<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>b</mml:mi><mml:mo>=</mml:mo><mml:mn>0.999</mml:mn></mml:math>and<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mi>a</mml:mi><mml:mo>′</mml:mo></mml:msup><mml:mo>=</mml:mo><mml:mn>1</mml:mn><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mn>2</mml:mn></mml:math>.Imposing poly3-NSETH(1/2) and per-int-NSETH(0.999), and assuming that the runtime of a hypothetical quantum circuit simulation algorithm would scale linearly with the number of gates/constraints/optical elements, we conclude that Instantaneous Quantum Polynomial-Time (IQP) circuits with 208 qubits and 500 gates, Quantum Approximate Optimization Algorithm (QAOA) circuits with 420 qubits and 500 constraints and boson sampling circuits (i.e. linear optical networks) with 98 photons and 500 optical elements are large enough for the task of producing samples from their output distributions up to constant multiplicative error to be intractable on current technology. Imposing poly3-ave-SBSETH(1/2), we additionally rule out simulations with constant additive error for IQP and QAOA circuits of the same size. Without the assumption of linearly increasing simulation time, we can make analogous statements for circuits with slightly fewer qubits but requiring<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mn>10</mml:mn><mml:mn>4</mml:mn></mml:msup></mml:math>to<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mn>10</mml:mn><mml:mn>7</mml:mn></mml:msup></mml:math>gates.

Topics & Concepts