What exactly is "Random Circuit Sampling"?

Question

Many people have suggested using "Random Circuit Sampling" to demonstrate quantum supremacy. But what is the precise definition of the "Random Circuit Sampling" problem? I've seen statements like "the task is to take a random (efficient) quantum circuit of a specific form and generate samples from its output distribution". But it is not clear to me what the terms "random (efficient) quantum circuit" mean precisely. Also, do we know anything about the classical computational complexity of this problem?

Answer 1

There are a continuous set of possible states for $n$ qubits, each of which can be expressed as a superposition of the $2^n$ basis states.

Mostly of these states are highly entangled, and would require highly complex circuits to create (assuming the standard gate set of single qubit rotations and two or three qubit entangling gates).

These circuits would have to be implemented very cleanly to be able to reach these states. Noise causes decoherence, which essentially drives your qubits to an unentangled state (like all qubits $|0\rangle$ due to relaxation, or the maximally mixed state due to constantly rotated relaxation and dephasing).

The set of unentangled states is just a tiny corner of the total set of all possible states, but it is a corner that is hard to leave for long. So implementing circuits capable of fully exploring the $n$ qubit Hilbert space will be very hard. But taking advantage of the full Hilbert space is what quantum computing is all about. So we have to show that we can overcome this hurdle.

One way to see how well we do this is to focus on just randomly producing $n$ qubit states. These should be picked uniformly from all possible states, and not be biased towards the tiny set of states that it is easy for us to produce or write down. This can be done by running a random circuits of sufficient circuit depth. The number of gates for this thought to be efficient (i.e. polynomial in $n$), though I'm not sure if this is proven or is just a widely held conjecture.

The randomness of the process ensures that there are no nice properties that could be exploited by a classical simulation. So the task of simulating arbitrary random circuits will require a full simulation of the $n$ qubits, the required classical resources for which scale exponentially with $n$.

The details of how exactly to go about creating the random circuit, and what to look for in the results to declare success, depend on the proposal (such as Google's). It is also not yet clear how many qubits are needed before current supercomputers cannot reproduce the result.