Understanding Google's “Quantum supremacy using a programmable superconducting processor” (Part 1): choice of gate set

Question

I was recently going through the paper titled "Quantum supremacy using a programmable superconducting processor" by NASA Ames Research Centre and the Google Quantum AI team (note that the paper was originally posted on the NASA NTRS but later removed for unknown reasons; here's the Reddit discussion). It believe they're referring to "quantum supremacy" in the "quantum ascendency" sense.

In their 54 qubit Sycamore processor, they created a 53 qubit quantum circuit using a random selection of gates from the set $\{\sqrt{X}, \sqrt{Y}, \sqrt{W}\}$ in the following pattern:

^{FIG 3. Control operations for the quantum supremacy circuits. a, Example quantum circuit instance used in our experiment. Every cycle includes a layer each of single- and two-qubit gates. The single-qubit gates are chosen randomly from $\{\sqrt X, \sqrt Y, \sqrt W\}$. The sequence of two-qubit gates are chosen according to a tiling pattern, coupling each qubit sequentially to its four nearest-neighbor qubits. The couplers are divided into four subsets (ABCD), each of which is executed simultaneously across the entire array corresponding to shaded colors. Here we show an intractable sequence (repeat ABCDCDAB); we also use different coupler subsets along with a simplifiable sequence (repeat EFGHEFGH, not shown) that can be simulated on a classical computer. b, Waveform of control signals for single- and two-qubit gates.}

They also show some plots in FIG 4, apparently proving their claim of quantum supremacy.

^{FIG. 4. Demonstrating quantum supremacy. a, Verification of benchmarking methods. $\mathcal{F}_\mathrm{XEB}$ values for patch, elided, and full verification circuits are calculated from measured bitstrings and the corresponding probabilities predicted by classical simulation. Here, the two-qubit gates are applied in a simplifiable tiling and sequence such that the full circuits can be simulated out to $n = 53, m = 14$ in a reasonable amount of time. Each data point is an average over 10 distinct quantum circuit instances that differ in their single-qubit gates (for $n = 39, 42, 43$ only 2 instances were simulated). For each $n$, each instance is sampled with $N$s between $0.5 M$ and $2.5 M$. The black line shows predicted $\mathcal{F}_\mathrm{XEB}$ based on single- and two-qubit gate and measurement errors. The close correspondence between all four curves, despite their vast differences in complexity, justifies the use of elided circuits to estimate fidelity in the supremacy regime. b, Estimating $\mathcal{F}_\mathrm{XEB}$ in the quantum supremacy regime. Here, the two-qubit gates are applied in a non-simplifiable tiling and sequence for which it is much harder to simulate. For the largest elided data ($n = 53$, $m = 20$, total $N_s = 30 M$), we find an average $\mathcal{F}_\mathrm{XEB} > 0.1\%$ with $5\sigma$ confidence, where $\sigma$ includes both systematic and statistical uncertainties. The corresponding full circuit data, not simulated but archived, is expected to show similarly significant fidelity. For $m = 20$, obtaining $1M$ samples on the quantum processor takes 200 seconds, while an equal fidelity classical sampling would take 10,000 years on $1M$ cores, and verifying the fidelity would take millions of years.}

Question:

Why did they specifically choose the gate set $\{\sqrt{X}, \sqrt{Y}, \sqrt{W}\}$? $W$ is $(X+Y)/\sqrt 2$ as per the supplementary material. Also, why are they using randomly generated circuits?

User @Marsl says here that: "In case you are confused by the need for a random unitary, it needs to be random in order to avoid that the classical sampler trying to reproduce the right prob. distribution can adapt to the particular unitary. Basically, if I wanted build a classical sampling algorithm that solves the problem for any unitary you hand over to me (or a description of the circuit), then the randomness assures that my sampler has to be "general-purpose", I have to design it such that it works well for any instance!" It not clear to me what they mean by "adapt"-ing to some particular unitary in this context.

---

^Sequel(s):

^{Understanding Google's “Quantum supremacy using a programmable superconducting processor” (Part 2): simplifiable and intractable tilings}

^{Understanding Google's “Quantum supremacy using a programmable superconducting processor” (Part 3): sampling}

Answer 1

While a follow-up question asks for the motivation behind the two-qubit gates used in Sycamore, this question focuses on the random nature of the single qubit operations used in Sycamore, that is, the gates $\{\sqrt{X},\sqrt{Y},\sqrt{W}=(X+Y)/\sqrt{2}\}$ applied to each of the $53$ qubits between each of the two-qubit gates.

Although I agree with @Marsl that these gates were likely relatively easy to realize with the transmon qubits used in Sycamore, I suspect that there is a little more to the story.

For example, page 26 of the Supplementary Information notes that although $\sqrt{X}$ and $\sqrt{Y}$ belong to the Clifford group, $\sqrt{W}$ does not. I believe $\sqrt{W}$ was added, at least partly, because it is not a member of the Clifford group. This may help to avoid the pitfalls of the Gottesman-Knill theorem, which says that circuits consisting of only normalizers of the Pauli group $(I,X,Y,Z)$ are efficiently simulatable.

Thus, for example, if $\sqrt{Z}$ were used as opposed to $\sqrt{W}$, then the claim of quantum supremacy would have to overcome the implications of easy simulatability in view of Gottesman-Knill.

Furthermore, I believe at least three single-qubit gates are needed to help support the claim of quantum supremacy.

For example further review of page 26 of the Supplemental Information states that although the first cycle randomly chooses among the $3$ gates, subsequent cycles never use the same gates used in the immediately preceding cycle.

It's hard to scramble a Rubik's cube by giving two half-twists to the same face twice in a row. Similarly their circuit used for quantum supremacy is chosen randomly from all of the $3^n2^{nm}$ such words on $n$ qubits and $m$ cycles of single- and two-qubit gates.

Answer 2

This answer only addresses the part about the necessity of the randomness of the circuit because I am by no means familiar with the physical implementation of the qubits at Google and what kind of constraints these impose on the implementation of certain gates.

Now, for the randomness: Consider the problem of sampling from the output distribution of a quantum circuit. An instance of this problem is specified by one particular circuit. Of course, many of these instances might be extremely easy to solve for a general purpose classical sampler. Explicitly, take for example Clifford circuits for which we know we could build a poly-time sampler that could actually solve all these instances.

Edit: In fact, having thought about this a bit more, I believe that a single instance of any problem is always trivial to solve: You can just "hard-code" the right solution into your algorithm/Turing machine and it would then run in constant time (a single step) and return the right thing but of course would fail on any other instance. Thus, while we might intuitively speak about particular circuits being harder than others, this does not really make sense from a rigorous point of view. (Here, it might help to think about more conventional problems that people look at in complexity-theory like Satisfiability or whatnot.) But even for a big chunk of instances, you might still find some pattern in them, that allows you to solve all these but not all instances.

However, solving a problem means designing a general purpose algorithm/machine that solves all instances but of course asserting whether this criterion was met might be difficult. Thus, a nice way to pose the task that ought to be achieved by a sampler (be it quantum or classical) is sampling from the output distribution of a random instance.

Basically, if you cannot know which instance you will have to solve beforehand, then you have to prepare for all. To illustrate this:

Consider a competition where everyone hands in as a project their classical computer program for this task. There is simply no way you could ever exploit any particular structure in the circuit that you need to sample from because your are only told which instance you need to solve after handing in the project. Then the judges assess all submissions based on how well they do on some instance they have drawn randomly.

Facing this competition, the only thing you can do classically is just simulating the quantum circuit which of course takes exponential resources.