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

In Google's 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:

What do the terms simplifiable tiling and non-simplifiable (intractable) tiling mean in this context? They're calling the sequence $$\mathrm{ABCDCDAB}$$ intractable whereas they're calling $$\mathrm{EFGHEFGH}$$. It's not clear what they mean by that. What are the terms $$\mathrm{A, B, C, D}$$ and $$\mathrm{E, F, G, H}$$ anyway? I mean, I understand that they're two-qubit gates (couplers), but are the gates $$\{\mathrm{A, B, C, D}\}$$ different from the gates $$\{\mathrm{E, F, G, H}\}$$ or do they mean that they're the same gates arranged in a different sequence?

Also which exact types of 2-qubit gates can be used in this case? Can I replace all of A, B, C, D (or E, F, G, H) by CNOT gates? Or are only specific categories of two-qubit gates allowed? If yes, what are those?

Prequel(s):

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

Sequel(s):

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

• @MarkS What does "efficiently simulable" even mean for two-qubit gates? All 2-qubit gates are simply $4\times 4$ matrices and should be simulable in almost equivalent time... Sep 28, 2019 at 17:41
• @MarkS Umm, you mean all A = SWAP, B = SWAP, ..., E = SWAP, ..., H = SWAP? If so, why do they call the arrangement ABCDCDAB intractable whereas they call the EFGHEFGH simplfiable? If all the 2-qubit gates were simply swap gates there would be no difference between the two sequences, isn't it? Or perhaps not, as which two qubits they're swapping also matters...that is, that alphabets (A...D, E...H) denote which two qubits are being swapped rather than acting as labels for the 2-qubit gates themselves. Though, I should ask...why exactly do you think/feel that they're swap gates? Sep 28, 2019 at 17:50
• I am not entirely sure! Maybe it's a SWAP with a Cz... they say on page 3 "We perform two-qubit iSWAP-like entangling gates by bringing neighboring qubits on resonance and turning on a 20 MHz coupling for 12 ns, which allows the qubits to swap excitations. During this time, the qubits also ex-perience a controlled-phase (CZ) interaction, which orig-inates from the higher levels of the transmon." Sep 28, 2019 at 19:03
• @MarkS This is the supplementary material Sep 29, 2019 at 5:26

TL/DR: The two-qubit gates are going by the moniker "Sycamore gates" in the paper, and it appears that they would ideally want to explore more of the $$(\phi, \theta)$$ phase-space but for their purposes (of quantum supremacy) their current Sycamore gate is sufficient. The pattern of gates $$\mathrm{ABCDCDAB}$$ was chosen to avoid "wedges" and maximize/optimize entanglement.

The two-qubit Sycamore gates are described in the Supplementary Information paper for example on pp. 13 and 14.

See FIG. S10 above, wherein the gates are described as an $$\mathsf{iSWAP}$$ (imaginary swap) combined with a small phase for $$\mathsf{CZ}$$ (controlled Z). They put their Sycamore gates (green stars) closer to $$\mathsf{iSWAP}$$'s on their phase diagram of FIG. S10(c). I think the $$|00\rangle$$ state is unchanged, the $$|01\rangle$$ and $$|10\rangle$$ state are swapped and multiplied by $$i$$, and the state $$|11\rangle$$ will see a $$30^\circ$$ phase shift.

Further, page 26 of the Supplementary Information states "The former sequence [e.g., the $$\mathrm{ABCDCDAB}$$ sequence] makes SFA simulation harder by facilitating prompt transfer of entanglement created at promising circuit cuts into the bulk of each circuit partition." Here SFA is the Schrodinger/Feynman hybrid simulation algorithm.

The Supplementary Information paper, especially FIG. S22 above, notes that the formation of what is called a "wedge" of gates acting on qubits that are separated/partitioned with the SFA algorithm may not efficiently increase entanglement, and may be more efficiently simulatable.

Reviewing FIG. S21's illustration of the qubits toggled with the $$\mathrm{ABCDCDAB}$$ pattern and comparing them to the $$\mathrm{EFGH}$$ sequence above, the $$\mathrm{EFGH}$$ pattern includes a number of these "wedges" for less entanglement/more efficient simulation. That is, I think we can say that the $$\mathrm{EFGH}$$ pattern of gates has a simpler Schmidt decomposition. The $$\mathrm{ABCD}$$ gates have a different wallpaper group/packing density than the $$\mathrm{EFGH}$$ gates. (I'm sorry I forgot the right group-theoretical way to say what I mean).

EDIT

Comment #39 from Craig Gidney on this SO blog post provides more context on the $$\mathrm{ABCD}$$ vs. $$\mathrm{EFGH}$$ circuits.

From Craig:

The supremacy paper mentions “verification circuits” [i.e., $$\mathrm{EFGH}$$ circuits], which are circuits that are identical to the supremacy circuits [i.e., $$\mathrm{ABCD}$$ circuits] except the verification circuits use a slightly different ordering of the two qubit gates. This ordering introduces a weakness that can be exploited to perform simulation much more efficiently.

The verification circuits were not originally intended to be verification circuits. They were intended to be the actual supremacy circuits. We didn’t know the ordering was so important; someone just picked something that looked reasonable. It was only after we collected the experimental data for these circuits that the weakness was noticed.

To me, the claim of supremacy is made stronger by having switched over to the $$ABCD$$ circuits during the experiment, at least because more confidence is achieved when the fidelity of the verification circuits were actually verified to be on-line in FIG. 4.