Quantum Supremacy: computational complexity and applications

The promise of quantum computers is that certain computational tasks might be executed exponentially faster on a quantum processor than on a classical processor.
A fundamental challenge is to build a high-fdelity processor capable of running quantum algorithms in an exponentially large computational space. Here we report the use of a processor with programmable superconducting qubits to create quantum states on 53 qubits.
We create ergodic dynamics by applying a sequence that alternates between a randomly chosen single-qubit gates and an entangling two-qubit gate. Measuring the output of these quantum circuits amounts to sampling from the underlying probability distribution and produces a set of bitstrings. We verify that the quantum processor is working properly using a method called cross-entropy benchmarking, which compares how often each bitstring is observed experimentally with its corresponding ideal probability computed via simulation on a classical computer. We discuss the computational complexity of the sampling problem and show how the results of computation in a $10^{16}$ dimensional Hilbert space can be verified. Furthermore, we demonstrate how our processor is programmable by showing how various algorithms can be implemented.