In supremacy paper and part D of section VII of supplementary information (below), it is said that there is a pseudo-random number generator that is initialized with a seed called $s$; And then the single-qubit gates are selected from the set of three gates $\sqrt{X} , \sqrt{Y},\sqrt{W}$ according to this random number.

D. Randomness

Single-qubit gates in every cycle are chosen randomly using a pseudo-random number generator (PRNG). The generator is initialized with a seed s which is the third parameter for our family of RQCs. The single-qubit gate applied to a particular qubit in a given cycle depends onlyon s. Consequently, two RQCs with the same s apply the same single-qubit gate to a given qubit in a given cycle as long as the qubit and the cycle belong in both RQCs as determined by their size n and depth m parameters.

Conversely, the choice of single-qubit gates is the sole property of our RQCs that depends on s. In particular, the same two-qubit gate is applied to a given qubit pair in a given cycle by all RQCs that contain the pair and the cycle.

and in part E:

Single-qubit gates in the first cycle are chosen independently and uniformly at random from the set of the three gates above. In subsequent cycles, each single-qubit gate is chosen independently and uniformly at random from among the gates above except the gate applied to the qubit in the preceding cycle. This prevents simplifications of some simulation paths in SFA. Consequently, there are $3^n2^{nm}$ possible random choices for a RQC with n qubits and m cycles.

What I understand from the experiment and this answer is that we have a circuit, we have an input state , and after passing this input state through the circuit, we do a measurement, and a ket consisting of zeros and ones ($e.g. |{10010101..10>}$) is obtained. Now we are repeating the experiment for many times again and again in exactly the same way and with exactly the same circuit (if I'm wrong correct me), which means that the random number you produce must again produce the same series of numbers, which is possible by initializing $s$ to the previous value.

After repeating the measurements on exactly the same circuit (for example, one million times), you can draw a bar chart (see the picture below) and get the distribution function approximately and then compared the distribution to the simulation distribution as it's mentioned in this lecture note.

enter image description here

and in the caption of this picture it's said:

Lastly, we measure the state of every qubit. The measurement is repeated many times in order to estimate the probability of each output state. Here, we plot the measured probabilities for two instances after 10 coupler pulses (cycles).

Now my question is, why do we use random numbers at all when we actually have to measure the output of the same circuit many times? Why don't we choose single-qubits gates according to a pattern like two-qubit gates?

Did Google do what I explained here for supremacy experiment or I'm missing something? That is, a specific circuit of certain single-qubit gates on a certain qubits and then two-qubit gates in each cycle and then go to the next cycle and after for example 20 cycles (for supremacy experiment) then measuring the state of each qubit and repeat the whole process with exactly the same circuit (same as I explained above) many times? If so, has Google actually do the experiment only on one circuit (I mean do the 1 million measurement on one specific circuit) or tested different circuits (with different value $s$) to verify the experiment?

If this is not the case, and each time after a measurement and obtaining a ket consisting of zeros and ones $s$ changes, and as a result, the circuit changes, and then the measurement is done, and this is repeated many times, and then from these measurements that the distribution is obtained, how is this distribution useful? because the measured kets are practically for different circuits.

What role does this randomness play in making things difficult? When it is practically pseudo-random and therefore structured, and by knowing $s$ (the seed) you can get the rest of the numbers, because according to this answer, what I understand is that the main difficulty is not because of the single-qubits gates are randomly chosen, but the main difficulty is because of the high dimension of the problem and the matrix multiplication in these dimensions are difficult to perform for a classical computer.(I've already read this answer but I don't quite understand)

And the last question is, what does instance mean in the figure above? Is the bar chart of each instance obtained by repeating a large number of measurements on a same circuit with the same value $s$?

  • $\begingroup$ What i mean by initializing s to the previous value is this: for example we are in cycle 15 and we want to determine which single gate qubit we should choose to perform for example on qubit 24 and this is the 121th time that we have repeated the experiment. So if we want to have exactly the same circuit as 120 times before in cycle 15 we should choose exactly the same set of gates to perform on each qubit and to do this because the single-qubit gates are chosen according to a pseudo-random number generator with the seed s we should set s to the same value as120 times before in cycle15.@MarkS $\endgroup$
    – Ali s.k
    Commented Apr 23, 2020 at 7:41
  • $\begingroup$ About your second question: yes input state is always $|000...>$@MarkS $\endgroup$
    – Ali s.k
    Commented Apr 23, 2020 at 7:55

1 Answer 1


It's my understanding that in Google's quantum computational supremacy experiment, they have executed exactly the same random circuit up to 1M times, e.g up to 1M instances. They must perform that many experiments in order to have a chance of proving that they would have executed the experiment perfectly, at least (greater than or equal to) the fidelity to which they quote.

Furthermore it's my understanding that the circuit is chosen randomly because they wish to show to the world that they do not have a potential back-door, which would enable them rapid simulation.

For example, I think of their random single-qubit gates as akin to 'nothing-up-my-sleeve numbers'. These are numbers used in cryptographic protocols to indicate that the protocols are unlikely to have been designed with a nefarious purpose.

If, instead of random single-qubit gates, they had applied a pattern as you suggest, then the world might be able to allege that they designed their pattern to precisely enable efficient simulation.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.