Quantum Supremacy Using a Programmable Superconducting Processor – Cached Google NASA Paper

Eleanor G. Rieffel

NASA Ames Research Center

Moffett Field, California

Quantum supremacy utilizing a programmable superconducting processor Google AI Quantum and collaboratorsy The tantalizing promise of quantum computer systems is that sure computational duties is perhaps executed exponentially quicker on a quantum processor than on a classical processor. A fundamen- tal problem is to construct a high- delity processor able to operating quantum algorithms in an exponentially massive computational house.

Here, we report utilizing a processor with programmable superconducting qubits to create quantum states on 53 qubits, occupying a state house 253 ˘1016. Measurements from repeated experiments pattern the corresponding chance distribution, which we confirm utilizing classical simulations. While our processor takes about 200 seconds to pattern one occasion of the quantum circuit 1 million occasions, a state-of-the-artwork supercomputer would require roughly 10,000 years to carry out the equal activity.

This dramatic speedup relative to all recognized classical algorithms supplies an experimental realization of quantum supremacy on a com- putational activity and heralds the arrival of a a lot-anticipated computing paradigm. In the early 1980s, Richard Feynman proposed that a quantum laptop could be an e ective software to unravel issues in physics and chemistry, as it’s exponentially expensive to simulate massive quantum programs with classical computer systems [1]. Realizing Feynman’s imaginative and prescient poses signi – cant experimental and theoretical challenges. First, can a quantum system be engineered to carry out a computa- tion in a massive sufficient computational (Hilbert) house and with low sufficient errors to supply a quantum speedup? Second, can we formulate a downside that’s arduous for a classical laptop however straightforward for a quantum laptop? By computing a novel benchmark activity on our superconduct- ing qubit processor[2{7], we sort out each questions. Our experiment marks a milestone in direction of full scale quantum computing: quantum supremacy[8].

In reaching this milestone, we present that quantum speedup is achievable in a actual-world system and isn’t precluded by any hidden bodily legal guidelines. Quantum supremacy additionally heralds the period of Noisy Intermediate- Scale Quantum (NISQ) applied sciences. The benchmark activity we display has a right away utility in producing certi ready random numbers[9]; different preliminary makes use of for this new computational functionality might embrace optimization optimization [10{12], machine studying[13{ 15], supplies science and chemistry [16{18]. However, realizing the total promise of quantum computing (e.g. Shor’s algorithm for factoring) nonetheless requires technical leaps to engineer fault-tolerant logical qubits[19{23].

To obtain quantum supremacy, we made a variety of technical advances which additionally pave the best way in direction of er- ror correction. We developed quick, high- delity gates that may be executed concurrently throughout a two-dimensional qubit array. We calibrated and benchmarked the pro- cessor at each the element and system stage utilizing a highly effective new software: cross-entropy benchmarking (XEB).

Finally, we used element-stage delities to precisely predict the efficiency of the entire system, additional displaying that quantum info behaves as anticipated when scaling to massive programs. A COMPUTATIONAL TASK TO DEMONSTRATE QUANTUM SUPREMACY To display quantum supremacy, we examine our quantum processor in opposition to state-of-the-artwork classical com- puters within the activity of sampling the output of a pseudo- random quantum circuit[24{26].

Random circuits are a appropriate selection for benchmarking since they don’t pos- sess construction and due to this fact permit for restricted ensures of computational hardness[24, 25, 27, 28]. We design the circuits to entangle a set of quantum bits (qubits) by re- peated utility of single-qubit and two-qubit logical operations. Sampling the quantum circuit’s output pro- duces a set of bitstrings, e.g. f0000101, 1011100, …g. Due to quantum interference, the chance distribution of the bitstrings resembles a speckled depth sample produced by gentle interference in laser scatter, such that some bitstrings are more likely to happen than oth- ers. Classically computing this chance distribution turns into exponentially extra dicult because the variety of qubits (width) and variety of gate cycles (depth) grows. We confirm that the quantum processor is working prop- erly utilizing a methodology known as cross-entropy benchmarking (XEB) [24, 26], which compares how usually every bitstring is noticed experimentally with its corresponding supreme chance computed through simulation on a classical com- puter. For a given circuit, we gather the measured bit- strings fx igand compute the linear XEB delity [24{ 26, 29], which is the imply of the simulated chances of the bitstrings we measured: F XEB = 2 nhP(x i)i i 1 (1) the place nis the variety of qubits, P(x i) is the chance of bitstring x i computed for the best quantum circuit, and the common is over the noticed bitstrings. Intu- itively, F XEB is correlated with how usually we pattern excessive chance bitstrings. When there aren’t any errors within the quantum circuit, sampling the chance distribution will produce F XEB = 1. On the opposite hand, sampling from the uniform distribution will give hP(x i)i i = 1=2n and produce F XEB = 0. Values of F XEB between Zero and a couple of Qubit Adjustable coupler a b 10 millimeters FIG. 1. The Sycamore processor. a, Layout of processor displaying a rectangular array of 54 qubits (grey), every con- nected to its 4 nearest neighbors with couplers (blue). In- operable qubit is printed. b, Optical picture of the Sycamore chip. 1 correspond to the chance that no error has oc- curred whereas operating the circuit.

The chances P(x i) should be obtained from classically simulating the quan- tum circuit, and thus computing F XEB is intractable within the regime of quantum supremacy. However, with sure circuit simpli cations, we are able to acquire quantitative delity estimates of a totally working processor operating huge and deep quantum circuits. Our objective is to realize a excessive sufficient F XEB for a circuit with sucient width and depth such that the classical computing value is prohibitively massive. This is a dicult activity as a result of our logic gates are imperfect and the quan- tum states we intend to create are delicate to errors. A single bit or section ip over the course of the algorithm will utterly shue the speckle sample and end in near Zero delity [24, 29].

Therefore, to be able to declare quantum supremacy we want a quantum processor that executes this system with suciently low error charges. BUILDING AND CHARACTERIZING A HIGH-FIDELITY PROCESSOR We designed a quantum processor named Sycamore” which consists of a two-dimensional array of 54 trans- mon qubits, the place every qubit is tunably coupled to 4 nearest-neighbors, in a rectangular lattice. The connec- tivity was chosen to be ahead suitable with error- correction utilizing the floor code [20].

A key systems- engineering advance of this machine is reaching high- delity single- and two-qubit operations, not simply in iso- lation but in addition whereas performing a life like computation with simultaneous gate operations on many qubits. We talk about the highlights beneath; prolonged particulars will be discovered within the supplementary info. In a superconducting circuit, conduction electrons con- dense into a macroscopic quantum state, such that cur- rents and voltages behave quantum mechanically [2, 30]. Our processor makes use of transmon qubits [6], which will be considered nonlinear superconducting resonators at 5 to 7 GHz.

The qubit is encoded as the 2 lowest quan- tum eigenstates of the resonant circuit. Each transmon has two controls: a microwave drive to excite the qubit, and a magnetic ux management to tune the frequency. Each qubit is related to a linear resonator used to learn out the qubit state [5]. As proven in Fig. 1, every qubit can also be related to its neighboring qubits utilizing a new ad- justable coupler [31, 32]. Our coupler design permits us to rapidly tune the qubit-qubit coupling from utterly o to 40 MHz. Since one qubit didn’t operate correctly the machine makes use of 53 qubits and 86 couplers. The processor is fabricated utilizing aluminum for metal- ization and Josephson junctions, and indium for bump- bonds between two silicon wafers. The chip is wire- bonded to a superconducting circuit board and cooled to beneath 20 mK in a dilution fridge to cut back am- bient thermal power to properly beneath the qubit power. The processor is related by lters and attenu- ators to room-temperature electronics, which synthesize the management alerts.

The state of all qubits will be learn concurrently through the use of a frequency-multiplexing tech- nique[33, 34]. We use two levels of cryogenic ampli ers to spice up the sign, which is digitized (Eight bits at 1 GS/s) and demultiplexed digitally at room temperature. In to- tal, we orchestrate 277 digital-to-analog converters (14 bits at 1 GS/s) for full management of the quantum pro- cessor. We execute single-qubit gates by driving 25 ns mi- crowave pulses resonant with the qubit frequency whereas the qubit-qubit coupling is turned o .

The pulses are formed to attenuate transitions to larger transmon states[35]. Gate efficiency varies strongly with fre- quency on account of two-stage-system (TLS) defects[36, 37], stray microwave modes, coupling to regulate traces and the readout resonator, residual stray coupling between qubits, ux noise, and pulse distortions. We due to this fact 3 Pauli and measurement errors CDF am, E ted histogr Integra e 1 e 2 e 2c e r a b Average error Single-qubit (e 1 ) Two-qubit (e 2 ) Two-qubit, cycle (e 2c ) Readout (e r ) Isolated 0.15% 0.36% 0.65% 3.1% Simultaneous 0.16% 0.62% 0.93% 3.8% Simultaneous Pauli error e 1 , e 2 10 -2 10 -3 Isolated FIG. 2. System-wide Pauli and measurement errors. a, Integrated histogram (empirical cumulative distribution func- tion, ECDF) of Pauli errors (black, inexperienced, blue) and readout errors (orange), measured on qubits in isolation (dotted traces) and when working all qubits concurrently (stable). The median of every distribution happens at 0.50 on the vertical axis. Average (imply) values are proven beneath. b, Heatmap displaying single- and two-qubit Pauli errors e 1 (crosses) and e 2 (bars) positioned within the format of the processor. Values proven for all qubits working concurrently. optimize the one-qubit operation frequencies to miti- gate these error mechanisms. We benchmark single-qubit gate efficiency through the use of the XEB protocol described above, lowered to the single- qubit stage (n= 1), to measure the chance of an error occurring throughout a single-qubit gate. On every qubit, we apply a variable quantity mof randomly chosen gates and measure F XEB averaged over many sequences; as m will increase, errors accumulate and common F XEB decays.

We mannequin this decay by [1 e 1=(1 1=D2)]m the place e 1 is the Pauli error chance. The state (Hilbert) house di- mension time period, D= 2n = 2, corrects for the depolarizing mannequin the place states with errors partially overlap with the best state. This process is just like the extra typical strategy of randomized benchmarking [21, 38, 39], however helps non-Cli ord gatesets [40] and may separate out decoherence error from coherent management error. We then repeat the experiment with all qubits executing single- qubit gates concurrently (Fig.2), which exhibits solely a small enhance within the error chances, demonstrating that our machine has low microwave crosstalk. We carry out two-qubit iSWAP-like entangling gates by bringing neighboring qubits on resonance and turning on a 20 MHz coupling for 12 ns, which permits the qubits to swap excitations. During this time, the qubits additionally ex- perience a managed-section (CZ) interplay, which orig- inates from the upper ranges of the transmon. The two- qubit gate frequency trajectories of every pair of qubits are optimized to mitigate the identical error mechanisms consid- ered in optimizing single-qubit operation frequencies. To characterize and benchmark the 2-qubit gates, we run two-qubit circuits with mcycles, the place every cy- cle accommodates a randomly chosen single-qubit gate on every of the 2 qubits adopted by a xed two-qubit gate. We study the parameters of the 2-qubit unitary (e.g. the quantity of iSWAP and CZ interplay) through the use of F XEB as a value operate. After this optimization, we extract the per-cycle error e 2c from the decay of F XEB with m, and isolate the 2-qubit error e 2 by subtracting the 2 single-qubit errors e 1. We nd a median e 2 of 0:36%.

Additionally, we repeat the identical process whereas simul- taneously operating two-qubit circuits for your entire array. After updating the unitary parameters to account for ef- fects akin to dispersive shifts and crosstalk, we nd a median e 2 of 0.62%. For the total experiment, we generate quantum circuits utilizing the 2-qubit unitaries measured for every pair dur- ing simultaneous operation, quite than a customary gate for all pairs. The typical two-qubit gate is a full iSWAP with 1=6 of a full CZ. In precept, our structure may generate unitaries with arbitrary iSWAP and CZ inter- actions, however reliably producing a goal unitary stays an lively space of analysis. Finally, we benchmark qubit readout utilizing customary dispersive measurement [41]. Measurement errors aver- aged over the Zero and 1 states are proven in Fig 2a.

We have additionally measured the error when working all qubits simul- taneously, by randomly getting ready every qubit within the Zero or 1 state after which measuring all qubits for the chance of the proper consequence. We nd that simultaneous readout incurs solely a modest enhance in per-qubit measurement errors. Having discovered the error charges of the person gates and readout, we are able to mannequin the delity of a quantum circuit because the product of the chances of error-free opera- Four single-qubit gate: 25 ns qubit XY management two-qubit gate: 12 ns qubit 1 Z management qubit 2 Z management coupler cycle: 1 2 Three Four 5 6 m time column row 7 Eight A BC D A B D C a b FIG. 3. Control operations for the quantum supremacy circuits. a, Example quantum circuit occasion utilized in our experiment. Every cycle contains a layer every of single- and two-qubit gates. The single-qubit gates are chosen randomly from f p X; p Y; p Wg. The sequence of two-qubit gates are chosen in accordance with a tiling sample, coupling every qubit sequentially to its 4 nearest-neighbor qubits.

The couplers are divided into 4 subsets (ABCD), every of which is executed concurrently throughout your entire array akin to shaded colours. Here we present an intractable sequence (repeat ABCDCDAB); we additionally use di erent coupler subsets together with a simpli ready sequence (repeat EFGHEFGH, not proven) that may be simulated on a classical laptop. b, Waveform of management alerts for single- and two-qubit gates. tion of all gates and measurements. Our largest random quantum circuits have 53 qubits, 1113 single-qubit gates, 430 two-qubit gates, and a measurement on every qubit, for which we predict a complete delity of 0:2%.

This delity ought to be resolvable with a few million measurements, because the uncertainty on F XEB is 1= p N s, the place N s is the variety of samples. Our mannequin assumes that entangling bigger and bigger programs doesn’t introduce extra error sources past the errors we measure on the single- and two-qubit stage | within the subsequent part we are going to see how properly this speculation holds. FIDELITY ESTIMATION IN THE SUPREMACY REGIME The gate sequence for our pseudo-random quantum circuit era is proven in Fig.3. One cycle of the algorithm consists of making use of single-qubit gates chosen randomly from f p X; p Y; p Wgon all qubits, adopted by two-qubit gates on pairs of qubits. The sequences of gates which kind the supremacy circuits” are designed to attenuate the circuit depth required to create a extremely entangled state, which ensures computational complexity and classical hardness. While we can’t compute F XEB within the supremacy regime, we are able to estimate it utilizing three variations to re- duce the complexity of the circuits.

In patch circuits”, we remove a slice of two-qubit gates (a small fraction of the total number of two-qubit gates), splitting the cir- cuit into two spatially isolated, non-interacting patches of qubits. We then compute the total delity as the product of the patch delities, each of which can be easily calcu- lated. In elided circuits”, we take away solely a fraction of the preliminary two-qubit gates alongside the slice, permitting for entanglement between patches, which extra intently mim- ics the total experiment whereas nonetheless sustaining simulation feasibility. Finally, we are able to additionally run full veri cation cir- cuits” with the identical gate counts as our supremacy cir- cuits, however with a di erent sample for the sequence of two- qubit gates which is far simpler to simulate classically [29]. Comparison between these variations permits track- ing of the system delity as we strategy the supremacy regime. We rst examine that the patch and elided variations of the veri cation circuits produce the identical delity as the total veri cation circuits as much as 53 qubits, as proven in Fig.4a. For every information level, we usually gather N s = 5 106 complete samples over ten circuit situations, the place situations di er solely within the decisions of single-qubit gates in every cycle.

We additionally present predicted F XEB values computed by multiplying the no-error chances of single- and two-qubit gates and measurement [29]. Patch, elided, and predicted delities all present good settlement with the delities of the corresponding full circuits, regardless of the huge di erences in computational complexity and en- tanglement. This offers us con dence that elided circuits can be utilized to precisely estimate the delity of extra complicated circuits. We proceed now to benchmark our most computa- tionally dicult circuits. In Fig.4b, we present the mea- sured F XEB for 53-qubit patch and elided variations of the total supremacy circuits with rising depth.

For the most important circuit with 53 qubits and 20 cycles, we collected N s = 30 106 samples over 10 circuit situations, acquiring F XEB = (2:24 0:21) 10 Three for the elided circuits. With 5˙con dence, we assert that the common delity of run- ning these circuits on the quantum processor is larger than no less than 0.1%. The full information for Fig.4b ought to have related delities, however are solely archived because the simula- tion occasions (crimson numbers) take too lengthy. It is thus within the quantum supremacy regime. 5 variety of qubits, n variety of cycles, m n = 53 qubits a Classically veriable b Supremacy regime idelity, XEB F

XEB m = 14 cycles Prediction from gate and measurement errors Full circuit Elided circuit Patch circuit Prediction Patch E F G H A B C D C D A B Elided (±5 error bars) 10 millennia 100 years 600 years Four years Four years 2 weeks 1 week 2 hour sC la ic mp ng @ Sycamore 5 hours Classical verication Sycamore sampling (N s = 1M): 200 seconds 10 15 20 25 30 35 40 45 50 55 12 14 16 18 20 10 -3 10 -2 10 -1 10 Zero FIG. 4. Demonstrating quantum supremacy. a, Veri cation of benchmarking strategies. F XEB values for patch, elided, and full veri cation circuits are calculated from measured bitstrings and the corresponding chances predicted by classical simulation. Here, the 2-qubit gates are utilized in a simpli ready tiling and sequence such that the total circuits will be simulated out to n= 53;m= 14 in a cheap period of time. Each information level is a median over 10 distinct quantum circuit situations that di er of their single-qubit gates (for n= 39;42;43 solely 2 situations have been simulated). For every n, every occasion is sampled with N s between 0:5M and a couple of:5M.

The black line exhibits predicted F XEB based mostly on single- and two-qubit gate and measurement errors. The shut correspondence between all 4 curves, regardless of their huge di erences in complexity, justi es using elided circuits to estimate delity within the supremacy regime. b, Estimating F XEB within the quantum supremacy regime. Here, the 2-qubit gates are utilized in a non-simpli ready tiling and sequence for which it’s a lot tougher to simulate. For the most important elided information (n= 53, m= 20, complete N s = 30M), we nd a median F XEB >0.1% with 5˙con dence, the place ˙contains each systematic and statistical uncertainties.

The corresponding full circuit information, not simulated however archived, is anticipated to point out equally signi cant delity. For m= 20, acquiring 1M samples on the quantum processor takes 200 seconds, whereas an equal delity classical sampling would take 10,000 years on 1M cores, and verifying the delity would take tens of millions of years. DETERMINING THE CLASSICAL COMPUTATIONAL COST We simulate the quantum circuits used within the exper- iment on classical computer systems for 2 functions: verify- ing our quantum processor and benchmarking strategies by computing F XEB the place doable utilizing simpli ready circuits (Fig.4a), and estimating F XEB in addition to the classical value of sampling our hardest circuits (Fig.4b).

Up to 43 qubits, we use a Schrodinger algorithm (SA) which simulates the evolution of the total quantum state; the Julich supercomputer(100okay cores, 250TB) runs the most important circumstances. Above this dimension, there may be not sufficient RAM to retailer the quantum state [42]. For bigger qubit num- bers, we use a hybrid Schrodinger-Feynman algorithm (SFA)[43] operating on Google information facilities to compute the amplitudes of particular person bitstrings. This algorithm breaks the circuit up into two patches of qubits and e- ciently simulates every patch utilizing a Schrodinger methodology, earlier than connecting them utilizing an strategy paying homage to the Feynman path-integral.

While it’s extra memory- ecient, SFA turns into exponentially extra computation- ally costly with rising circuit depth because of the exponential development of paths with the variety of gates connecting the patches. To estimate the classical computational value of the supremacy circuits (grey numbers, Fig.4b), we ran por- tions of the quantum circuit simulation on each the Sum- mit supercomputer in addition to on Google clusters and ex- trapolated to the total value. In this extrapolation, we account for the computational value scaling with F XEB, e.g. the 0.1% delity decreases the price by 1000[43, 44]. On the Summit supercomputer, which is at the moment probably the most highly effective on this planet, we used a methodology impressed by Feynman path-integrals that’s most ecient at low depth[44{47].

At m= 20 the tensors don’t moderately t in node reminiscence, so we are able to solely measure runtimes as much as m= 14, for which we estimate that sampling 3M bitstrings with 1% delity would require 1 yr. 6 On Google Cloud servers, we estimate that perform- ing the identical activity for m= 20 with 0:1% delity utilizing the SFA algorithm would value 50 trillion core-hours and eat 1 petawatt hour of power. To put this in per- spective, it took 600 seconds to pattern the circuit on the quantum processor Three million occasions, the place sampling time is restricted by management {hardware} communications; in truth, the web quantum processor time is barely about 30 seconds. The bitstring samples from this largest circuit are archived on-line. One might marvel to what extent algorithmic innova- tion can improve classical simulations. Our assumption, based mostly on insights from complexity concept, is that the price of this algorithmic activity is exponential in nas properly as m. Indeed, simulation strategies have improved steadily over the previous few years[42{50].

We anticipate that decrease simula- tion prices than reported right here will ultimately be achieved, however we additionally anticipate they are going to be persistently outpaced by {hardware} enhancements on bigger quantum processors. VERIFYING THE DIGITAL ERROR MODEL A key assumption underlying the speculation of quantum error correction is that quantum state errors could also be con- sidered digitized and localized [38, 51]. Under such a dig- ital mannequin, all errors within the evolving quantum state could also be characterised by a set of localized Pauli errors (bit- and/or phase- ips) interspersed into the circuit. Since steady amplitudes are elementary to quantum me- chanics, it must be examined whether or not errors in a quantum system could possibly be handled as discrete and probabilistic. In- deed, our experimental observations help the validity of this mannequin for our processor. Our system delity is properly predicted by a easy mannequin through which the individ- ually characterised delities of every gate are multiplied collectively (Fig

4). To be efficiently described by a digitized error mannequin, a system ought to be low in correlated errors. We obtain this in our experiment by selecting circuits that ran- domize and decorrelate errors, by optimizing management to attenuate systematic errors and leakage, and by design- ing gates that function a lot quicker than correlated noise sources, akin to 1=f ux noise [37]. Demonstrating a pre- dictive uncorrelated error mannequin as much as a Hilbert house of dimension 253 exhibits that we are able to construct a system the place quantum assets, akin to entanglement, are usually not prohibitively fragile. WHAT DOES THE FUTURE HOLD?

Quantum processors based mostly on superconducting qubits can now carry out computations in a Hilbert house of di- mension 253 ˇ9 1015, past the attain of the quickest classical supercomputers accessible at present. To our knowl- edge, this experiment marks the rst computation that may solely be carried out on a quantum processor. Quan- tum processors have thus reached the regime of quantum supremacy. We anticipate their computational energy will proceed to develop at a double exponential fee: the clas- sical value of simulating a quantum circuit will increase expo- nentially with computational quantity, and {hardware} im- provements will probably observe a quantum-processor equiv- alent of Moore’s legislation [52, 53], doubling this computational quantity each few years. To maintain the double exponen- tial development fee and to ultimately o er the computational quantity wanted to run properly-recognized quantum algorithms, such because the Shor or Grover algorithms [19, 54], the engi- neering of quantum error correction must turn into a focus of consideration. The Extended Church-Turing Thesis” formulated by Bernstein and Vazirani [55] asserts that any reasonable” mannequin of computation will be eciently simulated by a Turing machine. Our experiment means that a mannequin of computation might now be accessible that violates this assertion.

We have carried out random quantum circuit sampling in polynomial time with a bodily realized quantum processor (with suciently low error charges), but no ecient methodology is thought to exist for classical comput- ing equipment. As a results of these developments, quan- tum computing is transitioning from a analysis subject to a know-how that unlocks new computational capabilities. We are just one inventive algorithm away from invaluable close to-time period functions. Acknowledgments We are grateful to Eric Schmidt, Sergey Brin, Je Dean, and Jay Yagnik for his or her govt sponsorship of the Google AI Quantum staff, and for his or her continued engagement and help. We thank Peter Norvig for reviewing a draft of the manuscript, and Sergey Knysh for helpful discussions.

We thank Kevin Kissel, Joey Raso, Davinci Yonge-Mallo, Orion Martin, and Niranjan Sridhar for his or her assist with simulations. We thank Gina Bortoli and Lily Laws for maintaining our staff organized. This analysis used assets from the Oak Ridge Leadership Computing Facility, which is a DOE Oce of Science User Facility supported un- der Contract DE-AC05-00OR22725.

A portion of this work was carried out in the united states Nanofabrication Facility, an open entry laboratory. Author contributions The Google AI Quantum staff conceived of the experiment. The functions and algorithms staff offered the theoretical basis and the speci cs of the algorithm. The {hardware} staff carried out the experiment and picked up the info. The information evaluation was carried out collectively with exterior collaborators.

[1]Feynman, R. P. Simulating physics with computer systems. Int. J. Theor. Phys. 21, 467{488 (1982).

[2]Devoret, M. H., Martinis, J. M. & Clarke, J. Mea- surements of macroscopic quantum tunneling out of the zero-voltage state of a present-biased josephson junction. Phys. Rev. Lett 55, 1908 (1985).

[3]Nakamura, Y., Chen, C. D. & Tsai, J. S. Spectroscopy of power-stage splitting between two macroscopic quan- tum states of cost coherently superposed by josephson coupling. Phys. Rev. Lett. 79, 2328 (1997).

[4]Mooij, J. et al. Josephson persistent-present qubit. Sci- ence 285, 1036 (1999).

[5]Wallra , A. et al. Strong coupling of a single photon to a superconducting qubit utilizing circuit quantum electrody- namics. Nature 431, 162 (2004).

[6]Koch, J. et al. Charge-insensitive qubit design derived from the cooper pair field. Phys. Rev. A 76, 042319 (2007).

[7]You, J. Q. & Nori, F. Atomic physics and quantum optics utilizing superconducting circuits. Nature 474, 589 (2011).

[8]Preskill, J. Quantum computing and the entanglement frontier. Rapporteur speak on the 25th Solvay Conference on Physics, Brussels (2012).

[9]Aaronson, S. Certi ed randomness from quantum supremacy. In preparation .

[10]Hastings, M. B. Classical and Quantum Bounded Depth Approximation Algorithms. arXiv e-prints arXiv:1905.07047 (2019). 1905.07047.

[11]Kechedzhi, Ok. et al. Ecient inhabitants switch through non- ergodic prolonged states in quantum spin glass. arXiv e-prints arXiv:1807.04792 (2018). 1807.04792.

[12]Somma, R. D., Boixo, S., Barnum, H. & Knill, E. Quan- tum simulations of classical annealing processes. Phys. Rev. Lett. letters 101, 130504 (2008).

[13]McClean, J. R., Boixo, S., Smelyanskiy, V. N., Babbush, R. & Neven, H. Barren plateaus in quantum neural net- work coaching landscapes. Nat. Comm. 9, 4812 (2018).

[14]Cong, I., Choi, S. & Lukin, M. D. Quantum convolutional neural networks. arXiv:1810.03787 (2018).

[15]Bravyi, S., Gosset, D. & Okonig, R. Quantum benefit with shallow circuits. Science 362, 308{311 (2018).

[16]Aspuru-Guzik, A., Dutoi, A. D., Love, P. J. & Head- Gordon, M. Simulated quantum computation of molecu- lar energies. Science 309, 1704{1707 (2005).

[17]Peruzzo, A. et al. A variational eigenvalue solver on a photonic quantum processor. Nat. Commun. 5, 4213 (2014). [18]Hempel, C. et al. Quantum chemistry calculations on a trapped-ion quantum simulator. Phys. Rev. X 8, 031022 (2018).

[19]Shor, P. W. Algorithms for quantum computation: dis- crete logarithms and factoring proceedings. Proceedings 35th Annual Symposium on Foundations of Computer Science (1994).

[20]Fowler, A. G., Mariantoni, M., Martinis, J. M. & Cle- land, A. N. Surface codes: Towards sensible massive-scale quantum computation. Phys. Rev. A 86, 032324 (2012).

[21]Barends, R. et al. Superconducting quantum circuits on the floor code threshold for fault tolerance. Nature 508, 500{503 (2014).

[22]Corcoles, A. D. et al. Demonstration of a quantum error detection code utilizing a sq. lattice of 4 supercon- ducting qubits. Nat. Commun. 6, 6979 (2015).

[23]Ofek, N. et al. Extending the lifetime of a quantum bit with error correction in superconducting circuits. Nature 536, 441 (2016).

[24]Boixo, S. et al. Characterizing quantum supremacy in close to-time period units. Nat. Phys. 14, 595 (2018).

[25]Aaronson, S. & Chen, L. Complexity-theoretic founda- tions of quantum supremacy experiments. In 32nd Com- putational Complexity Conference (CCC 2017) (2017).

[26]Neill, C. et al. A blueprint for demonstrating quantum supremacy with superconducting qubits. Science 360, 195{199 (2018).

[27]Bremner, M. J., Montanaro, A. & Shepherd, D. J. Average-case complexity versus approximate simulation of commuting quantum computations. Phys. Rev. Lett. 117, 080501 (2016).

[28]Bouland, A., Fe erman, B., Nirkhe, C. & Vazi- rani, U. Quantum supremacy and the com- plexity of random circuit sampling. Preprint at https://arxiv.org/abs/1803.04402 (2018).

[29]See supplementary info .

[30]Vool, U. & Devoret, M. Introduction to quantum electro- magnetic circuits. Int. J. Circ. Theor. Appl. 45, 897{934 (2017). 8

[31]Chen, Y. et al. Qubit structure with excessive coherence and quick tunable coupling circuits. Phys. Rev. Lett. 113, 220502 (2014).

[32]Yan, F. et al. A tunable coupling scheme for implement- ing high- delity two-qubit gates. Phys. Rev. Applied 10, 054062 (2018).

[33]Schuster, D. I. et al. Resolving photon quantity states in a superconducting circuit. Nature 445, 515 (2007).

[34]Je rey, E. et al. Fast correct state measurement with superconducting qubits. Phys. Rev. Lett. 112, 190504 (2014).

[35]Chen, Z. et al. Measuring and suppressing quantum state leakage in a superconducting qubit. Phys. Rev. Lett. 116, 020501 (2016).

[36]Klimov, P. V. et al. Fluctuations of power-rest occasions in superconducting qubits. Phys. Rev. Lett. 121, 090502 (2018).

[37]Yan, F. et al. The ux qubit revisited to boost coher- ence and reproducibility. Nat. Commun. 7, 12964 (2016).

[38]Knill, E. et al. Randomized benchmarking of quantum gates. Phys. Rev. A 77, 012307 (2008).

[39]Magesan, E., Gambetta, J. M. & Emerson, J. Scalable and strong randomized benchmarking of quantum pro- cesses. Phys. Rev. Lett. 106, 180504 (2011).

[40]Cross, A. W., Magesan, E., Bishop, L. S., Smolin, J. A. & Gambetta, J. M. Scalable randomised benchmarking of non-cli ord gates. NPJ Quantum Information 2, 16012 (2016).

[41]Wallra , A. et al. Approaching unit visibility for management of a superconducting qubit with dispersive readout. Phys. Rev. Lett. 95, 060501 (2005).

[42]De Raedt, H. et al. Massively parallel quantum laptop simulator, eleven years later. Comput. Phys. Commun. 237, 47 { 61 (2019).

[43]Markov, I. L., Fatima, A., Isakov, S. V. & Boixo, S. Quantum supremacy is each nearer and farther than it seems. Preprint at https://arxiv.org/abs/1807.10749 (2018).

[44]Villalonga, B. et al. A exible excessive-efficiency sim- ulator for the veri cation and benchmarking of quan- tum circuits applied on actual {hardware}. Preprint at https://arxiv.org/abs/1811.09599 (2018).

[45]Boixo, S., Isakov, S. V., Smelyanskiy, V. N. & Neven, H. Simulation of low-depth quantum circuits as complicated undirected graphical fashions. Preprint at https://arxiv.org/abs/1712.05384 (2017).

[46]Chen, J., Zhang, F., Huang, C., Newman, M. & Shi, Y. Classical simulation of intermediate-dimension quantum circuits. Preprint at https://arxiv.org/abs/1805.01450 (2018).

[47]Villalonga, B. et al. Establishing the quantum supremacy frontier with a 281 p op/s simulation. Preprint at https://arxiv.org/abs/1905.00444 (2019).

[48]Pednault, E. et al. Breaking the 49-qubit barrier within the simulation of quantum circuits. Preprint at https://arxiv.org/abs/1710.05867 (2017).

[49]Chen, Z. Y. et al. 64-qubit quantum circuit simulation. Sci. Bull. 63, 964{971 (2018).

[50]Chen, M.-C. et al. Quantum teleportation-impressed al- gorithm for sampling massive random quantum circuits. Preprint at https://arxiv.org/abs/1901.05003 (2019).

[51]Shor, P. W. Scheme for lowering decoherence in quan- tum laptop reminiscence. Phys. Rev. A 52, R2493{R2496 (1995).

[52]Devoret, M. H. & Schoelkopf, R. J. Superconducting circuits for quantum info: An outlook. Science 339, 1169{1174 (2013).

[53]Mohseni, M. et al. Commercialize quantum applied sciences in ve years. Nature 543, 171 (2017).

[54]Grover, L. Ok. Quantum mechanics helps in trying to find a needle in a haystack. letters 79, 325 (1997).

[55]Bernstein, E. & Vazirani, U. Quantum complexity the- ory. Proc. 25th Annual ACM Symposium on Theory of Computing (1993).