Jump to Content

Quantum Supremacy Is Both Closer and Farther than It Appears

Igor Markov
Aneeqa Fatima
Sergei Isakov
arxiv (not yet submitted) (2018)


As quantum computers improve in the number of qubits and fidelity, the question of when they surpass state-of-the-art classical computation for a well-defined computational task is attracting much attention. The leading candidate task for this quantum computational supremacy milestone entails sampling from the output distribution defined by a random quantum circuit. We perform this task on conventional computers for larger circuits than in previous results, by trading circuit fidelity for computational resources to match the fidelity of a given quantum computer. By using publicly available Google Cloud Computing, we can price such simulations and enable comparisons by total cost across multiple hardware types. We simulate approximate sampling from the output of a circuit with 7 x 8 qubits and depth 1+40+1 by producing one million bitstring probabilities with fidelity 0.5%, at an estimated cost of $35184. The simulation costs scale linearly with fidelity, and using this scaling we estimate that extending circuit depth to 1+48+1 increases costs to one million dollars. Yet, for a quantum computer, approximate sampling would take seconds. We pay particular attention to validating simulation results. Finally, we explain why recently refined benchmarks substantially increase computation cost of leading simulators, halving the circuit depth that can be simulated within the same time.

Research Areas