What did exactly Google do in simulating a random quantum circuit on a classical computer in supremacy experiment?

Question

I've been working on Google quantum supremacy paper for quite some time now and I have a problem in understanding how exactly they simulate their actual random quantum circuit on a classical computer.

To be specific, in their quantum random circuit each cycle includes a single qubit gate and a two-qubit gate. The single-qubit gate is chosen randomly from a set of three gates. To randomize the procedure of choosing the single-qubit gate there is a pseudorandom number generator which is initialized with a seed according to Supplementary information of the paper (part VII).

So my question is, when they want to run the simulation of the circuit on a classical computer, how exactly do they choose the single-qubit gate randomly?

Do they use a separate pseudorandom number generator for their code? If so, how do they compare the simulation results to the actual circuit, because the two are not related at all? Or they use the same pseudorandom number generator? Or none of them and they don't choose the single qubits randomly in the simulation but they look at the physical circuit and trace the gates that have been used in that circuit and then try to perform the exact set of gates on the exact same qubits in their simulation?

Please if you know where I can find the actual code of the simulation, mention that too. Thank you for your attention!

Answer 1

All quantum circuits can be simulated on a classical computer, but not all circuits take the same amount of time to simulate. If information about the circuit is known in advance, certain patterns may be exploited to significantly reduce time or memory consumption. The hardest type of circuit to simulate is one in which all qubits are entangled and there is no observable pattern in the applied gates to use a shortcut.

However, there are also limitations on the circuit for the quantum computer as well. Current quantum processors are noisy so: the smaller the depth, the more accurate the quantum processor is. Small errors can accumulate with each gate applied which could lead to a totally wrong answer at the end.

So to have a classical simulation compete with a quantum computer, the ideal circuit is highly entangled, contains no patterns, and has a small depth. This is why they used the circuit architecture discussed near Fig. 3 in the paper.

Every circuit has a probability distribution which it creates. Quantum computers approximate this distribution by running the same circuit many times and recording the output of each run. Google ran their circuits $5\times10^6$ times to get a close enough estimation of the distribution. Classical computers only need to simulate the circuit once since they don't collapse when measured like quantum computers.

The pseudorandom generator actually has to do with something else: experiment repeatability. If you handcraft the ideal circuit and want to run the experiment again, you'll need to create a new one by hand. So for every instance of the experiment, they generated a new circuit using a different seed for the pseudorandom generator which produces a different probability distribution.

A high level overview of the experiment looks like this:

for seed in numInstances:
    circuit = generateCircuit(seed)
    qDist = quantumExecution(circuit)
    cDist = classicalSimulation(circuit)

If qDist $\approx$ cDist then the quantum processor is accurate. For any instance of the experiment, if the quantum processor was faster than the classical simulation then quantum supremacy is declared.

As for the actual code used in the simulation, to my knowledge Google has yet to publish it. They have mentioned in the paper that they used a Schrödinger algorithm to simulate lower qubit counts and a Schrödinger/Feynman hybrid for the experiments of 43 qubits and higher because it does not used as much memory.