January 28, 2023

How many qubits for quantum supremacy?

This is a very interesting paper published by well-known people of the Quantum Community.

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 (non-collapse conjecture). 

The team assumed that the runtime of a hypothetical quantum circuit simulation algorithm would scale linearly with the number of gates/constraints/optical elements.

They have concluded 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.

Without the assumption of linearly increasing simulation time, they have made analogous statements for circuits with slightly fewer qubits but requiring 104 to 107 gates.

The original paper can be found here.