Quantum Error Mitigation

Zhenyu Cai, Ryan Babbush, Simon Benjamin, Suguru Endo, William J. Huggins, Jarrod Ryan McClean, Ying Li, Thomas E O'Brien · arXiv (2022)
Download PDF View
For quantum computers to successfully solve real-world problems, it is necessary to tackle the challenge of noise: the errors which occur in elementary physical components due to unwanted or imperfect interactions. The theory of quantum fault tolerance can provide an answer in the long term, but in the coming era of `NISQ' machines we must seek to mitigate errors rather than completely remove them. This review surveys the diverse methods that have been proposed for quantum error mitigation, assesses their in-principle efficacy, and then describes the hardware demonstrations achieved to date. We identify the commonalities and limitations among the methods, noting how mitigation methods can be chosen according to the primary type of noise present, including algorithmic errors. Open problems in the field are identified and we discuss the prospects for realising mitigation-based devices that can deliver quantum advantage with an impact on science and business.

Matchgate Shadows for Fermionic Quantum Simulation

Kianna Wan, Bill Huggins, Joonho Lee, Ryan Babbush · arXiv:2207.13723 (2022)
Download PDF View
"Classical shadows" are estimators of an unknown quantum state, constructed from suitably distributed random measurements on copies of that state [Nature Physics 16, 1050-1057]. Here, we analyze classical shadows obtained using random matchgate circuits, which correspond to fermionic Gaussian unitaries. We prove that the first three moments of the Haar distribution over the continuous group of matchgate circuits are equal to those of the discrete uniform distribution over only the matchgate circuits that are also Clifford unitaries; thus, the latter forms a "matchgate 3-design." This implies that the classical shadows resulting from the two ensembles are functionally equivalent. We show how one can use these matchgate shadows to efficiently estimate inner products between an arbitrary quantum state and fermionic Gaussian states, as well as the expectation values of local fermionic operators and various other quantities, thus surpassing the capabilities of prior work. As a concrete application, this enables us to apply wavefunction constraints that control the fermion sign problem in the quantum-classical auxiliary-field quantum Monte Carlo algorithm (QC-AFQMC) [Nature 603, 416-420], without the exponential post-processing cost incurred by the original approach.

Noise-resilient Majorana Edge Modes on a Chain of Superconducting Qubits

Abe Asfaw, Adam Jozef Zalcman, Aditya Locharla, Alejandro Grajales Dau, Alex Crook, Alex Opremcak, Alexa Rubinov, Alexander Korotkov, Alexandre Bourassa, Alexei Kitaev, Alexis Morvan, Andre Gregory Petukhov, Andreas Bengtsson, Andrew Dunsworth, Andrey Klots, Anthony Megrant, Ashley Anne Huff, Austin Fowler, Benjamin Chiaro, Benjamin Villalonga, Bernardo Meurer Costa, Bob Benjamin Buckley, Brian Burkett, Brooks Foxen, Catherine Erickson, Catherine Vollgraff Heidweiller, Charles Neill, Chris Quintana, Christopher Schuster, Cody Jones, Craig Michael Gidney, Daniel Eppens, Daniel Sank, Dar Gilboa, Dave Bacon, Dave Landhuis, David A Buell, Dmitry Abanin, Doug Strain, Dripto M. Debroy, Dvir Kafri, Ebrahim Forati, Edward Farhi, Emily Mount, Erik Lucero, Evan Jeffrey, Fedor Kostritsa, Frank Carlton Arute, Guifre Vidal, Hartmut Neven, Igor Aleiner, Jamie Yao, Jarrod Ryan McClean, Jeremy Patterson Hilton, Joao Basso, Joe Bardin, John Mark Kreikebaum, Jonathan Arthur Gross, Joonho Lee, Juan Atalaya, Juhwan Yoo, Julian Kelly, Justin Thomas Iveland, Kannan Aryaperumal Sankaragomathi, Kenny Lee, Kevin Miao, Kevin Satzinger, Kim Ming Lau, Kostyantyn Kechedzhi, Kunal Arya, Lara Faoro, Leon Brill, Leslie Flores, Lev Ioffe, Marco Szalay, Marissa Giustina, Markus Rudolf Hoffmann, Masoud Mohseni, Matt McEwen, Matt P Harrigan, Matthew Neeley, Michael Blythe Broughton, Michael Newman, Michel Henri Devoret, Mike Shearn, Murphy Yuezhen Niu, Nicholas Bushnell, Nicholas Rubin, Ofer Naaman, Orion Martin, Paul Conner, Paul Victor Klimov, Pavel Laptev, Pedram Roushan, Ping Yeh, Rajeev Acharya, Rebecca Potter, Reza Fatemi, Roberto Collins, Ryan Babbush, Sabrina Hong, Sean Demura, Seon Kim, Sergei Isakov, Sergio Boixo, Shirin Montazeri, Steve Habegger, Tanuj Khattar, Ted White, Thomas E O'Brien, Trent Huang, Trond Ikdahl Andersen, Vadim Smelyanskiy, Vladimir Shvarts, Wayne Liu, William Courtney, William Giang, William J. Huggins, Wojtek Mruczkiewicz, Xiao Mi, Yaxing Zhang, Yu Chen, Yuan Su, Zhang Jiang, Zijun Chen · Science (2022) (to appear)
Inherent symmetry of a quantum system may protect its otherwise fragile states. Leveraging such protection requires testing its robustness against uncontrolled environmental interactions. Using 47 superconducting qubits, we implement the kicked Ising model which exhibits Majorana edge modes (MEMs) protected by a $\mathbb{Z}_2$-symmetry. Remarkably, we find that any multi-qubit Pauli operator overlapping with the MEMs exhibits a uniform decay rate comparable to single-qubit relaxation rates, irrespective of its size or composition. This finding allows us to accurately reconstruct the exponentially localized spatial profiles of the MEMs. Spectroscopic measurements further indicate exponentially suppressed hybridization between the MEMs over larger system sizes, which manifests as a strong resilience against low-frequency noise. Our work elucidates the noise sensitivity of symmetry-protected edge modes in a solid-state environment.

Quantum Computation of Molecular Structure using Data from Challenging-to-Classically-Simulate Nuclear Magnetic Resonance Experiments

Thomas E O'Brien, Lev Ioffe, Yuan Su, David Fushman, Hartmut Neven, Ryan Babbush, Vadim Smelyanskiy · PRX Quantum, vol. 3 (2022)
Download PDF View
We propose a quantum algorithm for inferring the molecular nuclear spin Hamiltonian from time-resolved measurements of spin-spin correlators, which can be obtained via nuclear magnetic resonance (NMR). We focus on learning the anisotropic dipolar term of the Hamiltonian, which generates dynamics that are challenging to classically simulate in some contexts. We demonstrate the ability to directly estimate the Jacobian and Hessian of the corresponding learning problem on a quantum computer, allowing us to learn the Hamiltonian parameters. We develop algorithms for performing this computation on both noisy near-term and future fault-tolerant quantum computers. We argue that the former is promising as an early beyond-classical quantum application since it only requires evolution of a local spin Hamiltonian. We investigate the example of a protein (ubiquitin) confined on a membrane as a benchmark of our method. We isolate small spin clusters, demonstrate the convergence of our learning algorithm on one such example, and then investigate the learnability of these clusters as we cross the ergodic to nonergodic phase transition by suppressing the dipolar interaction. We see a clear correspondence between a drop in the multifractal dimension measured across many-body eigenstates of these clusters, and a transition in the structure of the Hessian of the learning cost function (from degenerate to learnable). Our hope is that such quantum computations might enable the interpretation and development of new NMR techniques for analyzing molecular structure.

Quantifying Quantum Advantage in Topological Data Analysis

Dominic W. Berry, Yuan Su, Casper Gyurik, Robbie King, Joao Basso, Alexander Del Toro Barba, Abhishek Rajput, Nathan Wiebe, Vedran Djunko, Ryan Babbush · arXiv:2209.13581 (2022)
Download PDF View
Lloyd et al. were first to demonstrate the promise of quantum algorithms for computing Betti numbers in persistent homology (a way of characterizing topological features of data sets). Here, we propose, analyze, and optimize an improved quantum algorithm for topological data analysis (TDA) with reduced scaling, including a method for preparing Dicke states based on inequality testing, a more efficient amplitude estimation algorithm using Kaiser windows, and an optimal implementation of eigenvalue projectors based on Chebyshev polynomials. We compile our approach to a fault-tolerant gate set and estimate constant factors in the Toffoli complexity. Our analysis reveals that super-quadratic quantum speedups are only possible for this problem when targeting a multiplicative error approximation and the Betti number grows asymptotically. Further, we propose a dequantization of the quantum TDA algorithm that shows that having exponentially large dimension and Betti number are necessary, but insufficient conditions, for super-polynomial advantage. We then introduce and analyze specific problem examples for which super-polynomial advantages may be achieved, and argue that quantum circuits with tens of billions of Toffoli gates can solve some seemingly classically intractable instances.

Simulating Challenging Correlated Molecules and Materials on the Sycamore Quantum Processor

Ruslan Tazhigulov, Shi-Ning Sun, Reza Haghshenas, Huanchen Zhai, Adrian Tan, Nicholas Rubin, Ryan Babbush, Austin Minnich, Garnet Kin-Lic Chan · arXiv:2203.15291 (2022)
Download PDF View
Simulating complex molecules and materials is an anticipated application of quantum devices. With strong quantum advantage demonstrated in artificial tasks, we examine how such advantage translates into modeling physical problems, and in particular, strongly correlated electronic structure. We simulate static and dynamical electronic structure on a superconducting quantum processor derived from Google’s Sycamore architecture for two representative correlated electron problems: the nitrogenase iron-sulfur molecular clusters, and α-ruthenium trichloride, a proximate spin-liquid material. To do so, we simplify the electronic structure into low-energy spin models that fit on the device. With extensive error mitigation and assistance from classically simulated data, we achieve quantitatively meaningful results deploying about 1/5 of the gate resources used in artificial quantum advantage experiments on a similar architecture. This increases to over 1/2 of the gate resources when choosing a model that suits the hardware. Our work serves to convert artificial measures of quantum advantage into a physically relevant setting.

Direct Measurement of Nonlocal Interactions in the Many-Body Localized Phase

Adam Jozef Zalcman, Amit Vainsencher, Andrew Dunsworth, Anthony Megrant, Austin Fowler, Ben Chiaro, Brian Burkett, Brooks Foxen, Charles Neill, Chris Quintana, Craig Michael Gidney, Daniel Sank, Dave Landhuis, David A Buell, Erik Lucero, Evan Jeffrey, Fedor Kostritsa, Frank Carlton Arute, Hartmut Neven, Jimmy Chen, John Martinis, Josh Mutus, Julian Kelly, Kevin Satzinger, Kostyantyn Kechedzhi, Kunal Arya, Marissa Giustina, Matt McEwen, Matthew Neeley, Ofer Naaman, Pedram Roushan, Rami Barends, Roberto Collins, Sergio Boixo, Ted White, Trent Huang, Vadim Smelyanskiy, Yu Chen · Physical Review Research, vol. 4 (2022), pp. 013148
Download PDF View
The interplay of interactions and strong disorder can lead to an exotic quantum many-body localized (MBL) phase of matter. Beyond the absence of transport, the MBL phase has distinctive signatures, such as slow dephasing and logarithmic entanglement growth; they commonly result in slow and subtle modifications of the dynamics, rendering their measurement challenging. Here, we experimentally characterize these properties of the MBL phase in a system of coupled superconducting qubits. By implementing phase sensitive techniques, we map out the structure of local integrals of motion in the MBL phase. Tomographic reconstruction of single and two-qubit density matrices allows us to determine the spatial and temporal entanglement growth between the localized sites. In addition, we study the preservation of entanglement in the MBL phase. The interferometric protocols implemented here detect affirmative quantum correlations and exclude artifacts due to the imperfect isolation of the system. By measuring elusive MBL quantities, our work highlights the advantages of phase sensitive measurements in studying novel phases of matter.

Quantum Computing for Programmers

Robert Hundt · Cambridge University Press, Cambridge CB2 8BS, United Kingdom (2022)
Download PDF View
This introduction to quantum computing from a classical programmer's perspective is meant for students and practitioners alike. Over 25 fundamental algorithms are explained with full mathematical derivations and classical code for simulation, using an open-source code base developed from the ground up in Python and C++. After presenting the basics of quantum computing, the author focuses on algorithms and the infrastructure to simulate them efficiently, beginning with quantum teleportation, superdense coding, and Deutsch-Jozsa. Coverage of advanced algorithms includes the quantum supremacy experiment, quantum Fourier transform, phase estimation, Shor's algorithm, Grover's algorithm with derivatives, quantum random walks, and the Solovay–Kitaev algorithm for gate approximation. Quantum simulation is explored with the variational quantum eigensolver, quantum approximate optimization, and the Max-Cut and Subset-Sum algorithms. The book also discusses issues around programmer productivity, quantum noise, error correction, and challenges for quantum programming languages, compilers, and tools, with a final section on compiler techniques for transpilation.

Purification-Based Quantum Error Mitigation of Pair-Correlated Electron Simulations

Thomas E O'Brien, Gian-Luca R. Anselmetti, Fotios Gkritsis, Vincent Elfving, Stefano Polla, William J. Huggins, Oumarou Oumarou, Kostyantyn Kechedzhi, Dmitry Abanin, Rajeev Acharya, Igor Aleiner, Richard Ross Allen, Trond Ikdahl Andersen, Kyle Anderson, Markus Ansmann, Frank Carlton Arute, Kunal Arya, Juan Atalaya, Dave Bacon, Joe Bardin, Andreas Bengtsson, Sergio Boixo, Jenna Nicole Bovaird, Michael Blythe Broughton, Bob Benjamin Buckley, Alexandre Bourassa, Leon Brill, David A Buell, Tim Burger, Brian Burkett, Nicholas Bushnell, Jimmy Chen, Yu Chen, Benjamin Chiaro, Desmond Chun Fung Chik, Josh Godfrey Cogan, Roberto Collins, Paul Conner, William Courtney, Alex Crook, Ben Curtin, Dripto M. Debroy, Alexander Del Toro Barba, Sean Demura, Ilya Drozdov, Andrew Dunsworth, Daniel Eppens, Catherine Erickson, Lara Faoro, Edward Farhi, Reza Fatemi, Leslie Flores, Ebrahim Forati, Austin Fowler, Brooks Riley Foxen, William Giang, Craig Michael Gidney, Dar Gilboa, Marissa Giustina, Alejandro Grajales Dau, Jonathan Arthur Gross, Steve Habegger, Michael C. Hamilton, Matt P Harrigan, Sean Harrington, Catherine Vollgraff Heidweiller, Jeremy Patterson Hilton, Markus Rudolf Hoffmann, Sabrina Hong, Trent Huang, Ashley Anne Huff, Lev Ioffe, Sergei Isakov, Justin Thomas Iveland, Evan Jeffrey, Cody Jones, Pavol Juhas, Dvir Kafri, Julian Kelly, Tanuj Khattar, Mostafa Khezri, Marika Kieferova, Seon Kim, Paul Victor Klimov, Andrey Klots, Alexander Korotkov, Fedor Kostritsa, John Mark Kreikebaum, Dave Landhuis, Pavel Laptev, Kim Ming Lau, Lily MeeKit Laws, Joonho Lee, Kenny Lee, Brian Lester, Alexander T. Lill, Wayne Liu, Aditya Locharla, Erik Lucero, Fionn Malone, Orion Martin, Jarrod Ryan McClean, Trevor Johnathan Mccourt, Matt McEwen, Anthony Megrant, Xiao Mi, Kevin Miao, Masoud Mohseni, Shirin Montazeri, Alexis Morvan, Ramis Movassagh, Wojtek Mruczkiewicz, Ofer Naaman, Matthew Neeley, Charles Neill, Ani Nersisyan, Hartmut Neven, Michael Newman, Jiun How Ng, Anthony Hieu Nguyen, Murray Nguyen, Murphy Yuezhen Niu, Alex Opremcak, Andre Gregory Petukhov, Rebecca Potter, Chris Quintana, Pedram Roushan, Daniel Sank, Kannan Aryaperumal Sankaragomathi, Kevin Satzinger, Christopher Schuster, Mike Shearn, Aaron Shorter, Vladimir Shvarts, Jindra Skruzny, Vadim Smelyanskiy, Clarke Smith, Rolando Diego Somma, Doug Strain, Marco Szalay, Alfredo Torres, Guifre Vidal, Benjamin Villalonga, Bryan W. K. Woo, Ted White, Jamie Yao, Ping Yeh, Juhwan Yoo, Grayson Robert Young, Adam Jozef Zalcman, Yaxing Zhang, Ningfeng Zhu, Nicholas Zobrist, Christian Gogolin, Ryan Babbush, Nicholas Rubin · arXiv:2210.10799 (2022)
Download PDF View
An important measure of the development of quantum computing platforms has been the simulation of increasingly complex physical systems. Prior to fault-tolerant quantum computing, robust error mitigation strategies are necessary to continue this growth. Here, we study physical simulation within the seniority-zero electron pairing subspace, which affords both a computational stepping stone to a fully correlated model, and an opportunity to validate recently introduced ``purification-based'' error-mitigation strategies. We compare the performance of error mitigation based on doubling quantum resources in time (echo verification) or in space (virtual distillation), on up to 20 qubits of a superconducting qubit quantum processor. We observe a reduction of error by one to two orders of magnitude below less sophisticated techniques (e.g. post-selection); the gain from error mitigation is seen to increase with the system size. Employing these error mitigation strategies enables the implementation of the largest variational algorithm for a correlated chemistry system to-date. Extrapolating performance from these results allows us to estimate minimum requirements for a beyond-classical simulation of electronic structure. We find that, despite the impressive gains from purification-based error mitigation, significant hardware improvements will be required for classically intractable variational chemistry simulations.

Entanglement area law for 1D gauge theories and bosonic systems

Nilin Abrahamsen, Yuan Su, Yu Tong, Nathan Wiebe · arXiv:2203.16012 (2022)
Download PDF View
We prove an entanglement area law for a class of 1D quantum systems involving infinite-dimensional local Hilbert spaces. This class of quantum systems include bosonic models such as the Hubbard-Holstein model, and both U(1) and SU(2) lattice gauge theories in one spatial dimension. Our proof relies on new results concerning the robustness of the ground state and spectral gap to the truncation of Hilbert space, applied within the approximate ground state projector (AGSP) framework from previous work. In establishing this area law, we develop a system-size independent bound on the expectation value of local observables for Hamiltonians without translation symmetry, which may be of separate interest. Our result provides theoretical justification for using tensor network methods to study the ground state properties of quantum systems with infinite local degrees of freedom.

Compressing Many-Body Fermion Operators Under Unitary Constraints

Nicholas Rubin, Joonho Lee, Ryan Babbush · Journal of Chemical Theory and Computation (2022)
Download PDF View
The most efficient known quantum circuits for preparing unitary coupled cluster states and applying Trotter steps of the arbitrary basis electronic structure Hamiltonian involve interleaved sequences of fermionic Gaussian circuits and Ising interaction type circuits. These circuits arise from factorizing the two-body operators generating those unitaries as a sum of squared one-body operators that are simulated using product formulas. We introduce a numerical algorithm for performing this factorization that has an iteration complexity no worse than single particle basis transformations of the two-body operators and often results in many times fewer squared one-body operators in the sum of squares compared to the analytical decompositions. As an application of this numerical procedure, we demonstrate that our protocol can be used to approximate generic unitary coupled cluster operators and prepare the necessary high-quality initial states for techniques (like ADAPT-VQE) that iteratively construct approximations to the ground state.

Exploiting fermion number in factorized decompositions of the electronic structure Hamiltonian

Sam McArdle, Earl Campbell, Yuan Su · Phys. Rev. A, vol. 105 (2022), pp. 012403
Download PDF View
Achieving an accurate description of fermionic systems typically requires considerably many more orbitals than fermions. Previous resource analyses of quantum chemistry simulation often failed to exploit this low fermionic number information in the implementation of Trotter-based approach and overestimated the quantum-computer runtime as a result. They also depended on numerical procedures that are computationally too expensive to scale up to large systems of practical interest. Here we propose techniques that solve both problems by using various factorized decompositions of the electronic structure Hamiltonian. We showcase our techniques for the uniform electron gas, finding substantial (over $100\times$) improvements in Trotter error for low-filling fraction and pushing to much higher numbers of orbitals than is possible with existing methods. Finally, we calculate the $T$-count to perform phase-estimation on Jellium. In the low-filling regime, we observe improvements in gate complexity of over $10\times$ compared to the best Trotter-based approach reported to date. We also report gate counts competitive with qubitization-based approaches for Wigner-Seitz values of physical interest.

Reliably Assessing the Electronic Structure of Cytochrome P450 on Today’s Classical Computers and Tomorrow’s Quantum Computers

Joshua Goings, Alec White, Joonho Lee, Christofer Tautermann, Matthias Degroote, Craig Michael Gidney, Toru Shiozaki, Ryan Babbush, Nicholas Rubin · PNAS, vol. 119 (2022)
Download PDF View
An accurate assessment of how quantum computers can be used for chemical simulation, especially their potential computational advantages, provides important context on how to deploy these future devices. To perform this assessment reliably, quantum resource estimates must be coupled with classical computations attempting to answer relevant chemical questions and to define the classical algorithms simulation frontier. Herein, we explore the quantum computation and classical computation resources required to assess the electronic structure of cytochrome P450 enzymes (CYPs) and thus define a classical–quantum advantage boundary. This is accomplished by analyzing the convergence of density matrix renormalization group plus n-electron valence state perturbation theory (DMRG+NEVPT2) and coupled-cluster singles doubles with noniterative triples [CCSD(T)] calculations for spin gaps in models of the CYP catalytic cycle that indicate multireference character. The quantum resources required to perform phase estimation using qubitized quantum walks are calculated for the same systems. Compilation into the surface code provides runtime estimates to compare directly to DMRG runtimes and to evaluate potential quantum advantage. Both classical and quantum resource estimates suggest that simulation of CYP models at scales large enough to balance dynamic and multiconfigurational electron correlation has the potential to be a quantum advantage problem and emphasizes the important interplay between classical computations and quantum algorithms development for chemical simulation.

Optimal Scaling Quantum Linear Systems Solver via Discrete Adiabatic Theorem

Pedro C. S. Costa, Dong An, Yuval Sanders, Yuan Su, Ryan Babbush, Dominic W. Berry · PRX Quantum, vol. 3 (2022), pp. 040303
Download PDF View
Recently, several approaches to solving linear systems on a quantum computer have been formulated in terms of the quantum adiabatic theorem for a continuously varying Hamiltonian. Such approaches enabled near-linear scaling in the condition number $\kappa$ of the linear system, without requiring a complicated variable-time amplitude amplification procedure. However, the most efficient of those procedures is still asymptotically sub-optimal by a factor of $\log(\kappa)$. Here, we prove a rigorous form of the adiabatic theorem that bounds the error in terms of the spectral gap for intrinsically discrete time evolutions. We use this discrete adiabatic theorem to develop a quantum algorithm for solving linear systems that is asymptotically optimal, in the sense that the complexity is strictly linear in $\kappa$, matching a known lower bound on the complexity. Our $\mathcal{O}(\kappa\log(1/\epsilon))$ complexity is also optimal in terms of the combined scaling in $\kappa$ and the precision $\epsilon$. Compared to existing suboptimal methods, our algorithm is simpler and easier to implement. Moreover, we determine the constant factors in the algorithm, which would be suitable for determining the complexity in terms of gate counts for specific applications.

Efficient Quantum Computation of Molecular Forces and Other Energy Gradients

Thomas E O'Brien, Michael Streif, Nicholas Rubin, Raffaele Santagati, Yuan Su, William J. Huggins, Joshua Goings, Nikolaj Moll, Elica Kyoseva, Matthias Degroote, Christofer Tautermann, Joonho Lee, Dominic Berry, Nathan Wiebe, Ryan Babbush · arXiv:2111.12437 (2021)
Download PDF View
While most work on the quantum simulation of chemistry has focused on computing energy surfaces, a similarly important application requiring subtly different algorithms is the computation of energy derivatives. Almost all molecular properties can be expressed an energy derivative, including molecular forces, which are essential for applications such as molecular dynamics simulations. Here, we introduce new quantum algorithms for computing molecular energy derivatives with significantly lower complexity than prior methods. Under cost models appropriate for noisy-intermediate scale quantum devices we demonstrate how low rank factorizations and other tomography schemes can be optimized for energy derivative calculations. We perform numerics revealing that our techniques reduce the number of circuit repetitions required by many orders of magnitude for even modest systems. In the context of fault-tolerant algorithms, we develop new methods of estimating energy derivatives with Heisenberg limited scaling incorporating state-of-the-art techniques for block encoding fermionic operators. Our results suggest that the calculation of forces on a single nuclei may be of similar cost to estimating energies of chemical systems, but that further developments are needed for quantum computers to meaningfully assist with molecular dynamics simulations.

What the foundations of quantum computer science teach us about chemistry

Jarrod Ryan McClean, Nicholas Rubin, Joonho Lee, Matthew Harrigan, Thomas E O'Brien, Ryan Babbush, William J. Huggins, Hsin-Yuan Huang · Journal of Chemical Physics, vol. 155 (2021), pp. 150901
Download PDF View
With the rapid development of quantum technology, one of the leading applications that has been identified is the simulation of chemistry. Interestingly, even before full scale quantum computers are available, quantum computer science has exhibited a remarkable string of results that directly impact what is possible in chemical simulation, even with a quantum computer. Some of these results even impact our understanding of chemistry in the real world. In this perspective, we take the position that direct chemical simulation is best understood as a digital experiment. While on one hand this clarifies the power of quantum computers to extend our reach, it also shows us the limitations of taking such an approach too directly. Leveraging results that quantum computers cannot outpace the physical world, we build to the controversial stance that some chemical problems are best viewed as problems for which no algorithm can deliver their solution in general, known in computer science as undecidable problems. This has implications for the predictive power of thermodynamic models and topics like the ergodic hypothesis. However, we argue that this perspective is not defeatist, but rather helps shed light on the success of existing chemical models like transition state theory, molecular orbital theory, and thermodynamics as models that benefit from data. We contextualize recent results showing that data-augmented models are more powerful rote simulation. These results help us appreciate the success of traditional chemical theory and anticipate new models learned from experimental data. Not only can quantum computers provide data for such models, but they can extend the class and power of models that utilize data in fundamental ways. These discussions culminate in speculation on new ways for quantum computing and chemistry to interact and our perspective on the eventual roles of quantum computers in the future of chemistry.

Fast-Forwardable Quantum Evolution and Where to Find Them

Yuan Su · Quantum View, vol. 5 (2021), pp. 62
Download PDF View
This is a Perspective on "Fast-forwarding quantum evolution" by Shouzhen Gu, Rolando D. Somma, and Burak Şahinoğlu, published in Quantum 5, 577 (2021).

Resolving catastrophic error bursts from cosmic rays in large arrays of superconducting qubits

Matt McEwen, Lara Faoro, Kunal Arya, Andrew Dunsworth, Trent Huang, Seon Kim, Brian Burkett, Austin Fowler, Frank Arute, Joe Bardin, Andreas Bengtsson, Alexander Bilmes, Bob B. Buckley, Nicholas Bushnell, Jimmy Chen, Roberto Collins, Sean Demura, Alan R. Derk, Catherine Erickson, Marissa Giustina, Sean Harrington, Sabrina Hong, Evan Jeffrey, Julian Kelly, Paul V. Klimov, Fedor Kostritsa, Pavel Laptev, Aditya Locharla, Xiao Mi, Kevin C. Miao, Shirin Montazeri, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Alex Opremcak, Chris Quintana, Nicholas Redd, Pedram Roushan, Daniel Sank, Kevin Satzinger, Vladimir Shvarts, Ted White, Jamie Yao, Ping Yeh, Juhwan Yoo, Yu Chen, Vadim Smelyanskiy, John Martinis, Hartmut Neven, Anthony Megrant, Lev Ioffe, Rami Barends · Nature Physics (2021)
Download PDF View
Scalable quantum computing can become a reality with error correction, provided that coherent qubits can be constructed in large arrays. The key premise is that physical errors can remain both small and sufficiently uncorrelated as devices scale, so that logical error rates can be exponentially suppressed. However, impacts from cosmic rays and latent radioactivity violate these assumptions. An impinging particle can ionize the substrate and induce a burst of quasiparticles that destroys qubit coherence throughout the device. High-energy radiation has been identified as a source of error in pilot superconducting quantum devices, but the effect on large-scale algorithms and error correction remains an open question. Elucidating the physics involved requires operating large numbers of qubits at the same rapid timescales necessary for error correction. Here, we use space- and time-resolved measurements of a large-scale quantum processor to identify bursts of quasiparticles produced by high-energy rays. We track the events from their initial localized impact as they spread, simultaneously and severely limiting the energy coherence of all qubits and causing chip-wide failure. Our results provide direct insights into the impact of these damaging error bursts and highlight the necessity of mitigation to enable quantum computing to scale.

Unbiasing Fermionic Quantum Monte Carlo with a Quantum Computer

William J. Huggins, Bryan O'Gorman, Nicholas Rubin, David Reichman, Ryan Babbush, Joonho Lee · Nature (2021)
Download PDF View
Interacting many-electron problems pose some of the greatest computational challenges in science, with essential applications across many fields. The solutions to these problems will offer accurate predictions of chemical reactivity and kinetics, and other properties of quantum systems. Fermionic quantum Monte Carlo (QMC) methods which use a statistical sampling of the ground state, are among the most powerful approaches to these problems. Controlling the fermionic sign problem with constraints ensures the efficiency of QMC at the expense of potentially significant biases owing to the limited flexibility of classical computation. Here we propose an approach that combines constrained QMC with quantum computation to reduce such biases. We implement our scheme experimentally using up to 16 qubits to unbias constrained QMC calculations performed on chemical systems with as many as 120 orbitals. These experiments represent the largest chemistry simulations performed with the help of quantum computers, while achieving accuracy that is competitive with state-of-the-art classical methods without burdensome error mitigation. Compared with the popular variational quantum eigensolver our hybrid quantum-classical computational model offers an alternative path towards achieving a practical quantum advantage for the electronic structure problem without demanding exceedingly accurate preparation and measurement of the ground-state wavefunction.

Variational Quantum Algorithms

Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon Benjamin, Suguro Endo, Keisuke Fujii, Jarrod Ryan McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, Patrick Coles · Nature Reviews Physics (2021)
Download PDF View
Applications such as simulating large quantum systems or solving large-scale linear algebra problems are immensely challenging for classical computers due their extremely high computational cost. Quantum computers promise to unlock these applications, although fault-tolerant quantum computers will likely not be available for several years. Currently available quantum devices have serious constraints, including limited qubit numbers and noise processes that limit circuit depth. Variational Quantum Algorithms (VQAs), which employ a classical optimizer to train a parametrized quantum circuit, have emerged as a leading strategy to address these constraints. VQAs have now been proposed for essentially all applications that researchers have envisioned for quantum computers, and they appear to the best hope for obtaining quantum advantage. Nevertheless, challenges remain including the trainability, accuracy, and efficiency of VQAs. In this review article we present an overview of the field of VQAs. Furthermore, we discuss strategies to overcome their challenges as well as the exciting prospects for using them as a means to obtain quantum advantage.

Power of data in quantum machine learning

Hsin-Yuan (Robert) Huang, Michael Blythe Broughton, Masoud Mohseni, Ryan Babbush, Sergio Boixo, Hartmut Neven, Jarrod Ryan McClean · Nature Communications, vol. 12 (2021), pp. 2631
Download PDF View
The use of quantum computing for machine learning is among the most exciting prospective applications of quantum technologies. However, machine learning tasks where data is provided can be considerably different than commonly studied computational tasks. In this work, we show that some problems that are classically hard to compute can be easily predicted by classical machines learning from data. Using rigorous prediction error bounds as a foundation, we develop a methodology for assessing potential quantum advantage in learning tasks. The bounds are tight asymptotically and empirically predictive for a wide range of learning models. These constructions explain numerical results showing that with the help of data, classical machine learning models can be competitive with quantum models even if they are tailored to quantum problems. We then propose a projected quantum model that provides a simple and rigorous quantum speed-up for a learning problem in the fault-tolerant regime. For near-term implementations, we demonstrate a significant prediction advantage over some classical models on engineered data sets designed to demonstrate a maximal quantum advantage in one of the largest numerical tests for gate-based quantum machine learning to date, up to 30 qubits.

Low-Depth Mechanisms for Quantum Optimization

Jarrod Ryan McClean, Matthew P Harrigan, Masoud Mohseni, Nicholas Rubin, Zhang Jiang, Sergio Boixo, Vadim Smelyanskiy, Ryan Babbush, Hartmut Neven · PRX Quantum, vol. 3 (2021), pp. 030312
Download PDF View
One of the major application areas of interest for both near-term and fault-tolerant quantum computers is the optimization of classical objective functions. In this work, we develop intuitive constructions for a large class of these algorithms based on connections to simple dynamics of quantum systems, quantum walks, and classical continuous relaxations. We focus on developing a language and tools connected with kinetic energy on a graph for understanding the physical mechanisms of success and failure to guide algorithmic improvement. This physical language, in combination with uniqueness results related to unitarity, allow us to identify some potential pitfalls from kinetic energy fundamentally opposing the goal of optimization. This is connected to effects from wavefunction confinement, phase randomization, and shadow defects lurking in the objective far away from the ideal solution. As an example, we explore the surprising deficiency of many quantum methods in solving uncoupled spin problems and how this is both predictive of performance on some more complex systems while immediately suggesting simple resolutions. Further examination of canonical problems like the Hamming ramp or bush of implications show that entanglement can be strictly detrimental to performance results from the underlying mechanism of solution in approaches like QAOA. Kinetic energy and graph Laplacian perspectives provide new insights to common initialization and optimal solutions in QAOA as well as new methods for more effective layerwise training. Connections to classical methods of continuous extensions, homotopy methods, and iterated rounding suggest new directions for research in quantum optimization. Throughout, we unveil many pitfalls and mechanisms in quantum optimization using a physical perspective, which aim to spur the development of novel quantum optimization algorithms and refinements.

Focus Beyond Quadratic Speedups for Error-Corrected Quantum Advantage

Ryan Babbush, Jarrod Ryan McClean, Michael Newman, Craig Michael Gidney, Sergio Boixo, Hartmut Neven · PRX Quantum, vol. 2 (2021), pp. 010103
Download PDF View
In this perspective we discuss conditions under which it would be possible for a modest fault-tolerant quantum computer to realize a runtime advantage by executing a quantum algorithm with only a small polynomial speedup over the best classical alternative. The challenge is that the computation must finish within a reasonable amount of time while being difficult enough that the small quantum scaling advantage would compensate for the large constant factor overheads associated with error correction. We compute several examples of such runtimes using state-of-the-art surface code constructions under a variety of assumptions. We conclude that quadratic speedups will not enable quantum advantage on early generations of such fault-tolerant devices unless there is a significant improvement in how we realize quantum error correction. While this conclusion persists even if we were to increase the rate of logical gates in the surface code by more than an order of magnitude, we also repeat this analysis for speedups by other polynomial degrees and find that quartic speedups look significantly more practical.

Microwaves in Quantum Computing

Joseph Bardin, Daniel Slichter, David Reilly · IEEE Journal of Microwaves, vol. 1 (2021)
Download PDF View
The growing field of quantum computing relies on a broad range of microwave technologies, and has spurred development of microwave devices and methods in new operating regimes. Here we review the use of microwave signals and systems in quantum computing, with specific reference to three leading quantum computing platforms: trapped atomic ion qubits, spin qubits in semiconductors, and superconducting qubits. We highlight some key results and progress in quantum computing achieved through the use of microwave systems, and discuss how quantum computing applications have pushed the frontiers of microwave technology in some areas. We also describe open microwave engineering challenges for the construction of large-scale, fault-tolerant quantum computers.

Realizing topologically ordered states on a quantum processor

Kevin Satzinger, Y.-J. Liu, A. Smith, C. Knapp, M. Newman, N. C. Jones, Z. Chen, C. Quintana, X. Mi, A. Dunsworth, C. Gidney, I. Aleiner, F. Arute, K. Arya, J. Atalaya, R. Babbush, J. C. Bardin, R. Barends, J. Basso, A. Bengtsson, A. Bilmes, M. Broughton, B. B. Buckley, D. A. Buell, B. Burkett, N. Bushnell, B. Chiaro, R. Collins, W. Courtney, S. Demura, A. R Derk, D. Eppens, C. Erickson, L. Faoro, E. Farhi, B. Foxen, M. Giustina, A. Greene, J. A. Gross, M. P. Harrigan, S. D. Harrington, J. Hilton, S. Hong, T. Huang, W. J. Huggins, L. B. Ioffe, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, T. Khattar, S. Kim, P. V. Klimov, A. N. Korotkov, F. Kostritsa, D. Landhuis, P. Laptev, A. Locharla, E. Lucero, O. Martin, J. R. McClean, M. McEwen, K. C. Miao, M. Mohseni, S. Montazeri, W. Mruczkiewicz, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, T. E. O'Brien, A. Opremcak, B. Pato, A. Petukhov, N. C. Rubin, D. Sank, V. Shvarts, D. Strain, M. Szalay, B. Villalonga, T. C. White, Z. Yao, P. Yeh, J. Yoo, A. Zalcman, H. Neven, S. Boixo, A. Megrant, Y. Chen, J. Kelly, V. Smelyanskiy, A. Kitaev, M. Knap, F. Pollmann, Pedram Roushan · Science, vol. 374 (2021), pp. 1237-1241
Download PDF View
The discovery of topological order has revolutionized the understanding of quantum matter in modern physics and provided the theoretical foundation for many quantum error correcting codes. Realizing topologically ordered states has proven to be extremely challenging in both condensed matter and synthetic quantum systems. Here, we prepare the ground state of the emblematic toric code Hamiltonian using an efficient quantum circuit on a superconducting quantum processor. We measure a topological entanglement entropy of Stopo ≈ −0.95 × ln 2 and simulate anyon interferometry to extract the braiding statistics of the emergent excitations. Furthermore, we investigate key aspects of the surface code, including logical state injection and the decay of the non-local order parameter. Our results illustrate the topological nature of these states and demonstrate their potential for implementing the surface code.

Nearly Optimal Quantum Algorithm for Estimating Multiple Expectation Values

William J. Huggins, Kianna Wan, Jarrod Ryan McClean, Thomas E O'Brien, Nathan Wiebe, Ryan Babbush · arXiv:2110.12071 (2021)
Download PDF View
Many quantum algorithms involve the evaluation of expectation values. Optimal strategies for estimating a single expectation value are known, requiring a number of iterations that scales with the target error $\epsilon$ as $\mathcal{O}(\epsilon^{-1})$. In this paper we address the task of estimating the expectation values of \(M\) different observables, each to within an error \(\epsilon\), with the same \(\epsilon^{-1}\) dependence. We describe an approach that leverages Gily\'{e}n \emph{et al.}'s~quantum gradient estimation algorithm to achieve $\mathcal{O}\sqrt{M}\epsilon^{-1})$ scaling up to logarithmic factors, regardless of the commutation properties of the $M$ observables. We prove that this scaling is optimal in the worst case, even when the operators are mutually commuting. We highlight the flexibility of our approach by presenting several generalizations, including a strategy for accelerating the estimation of a collection of dynamic correlation functions.

Removing leakage-induced correlated errors in superconducting quantum error correction

Matt McEwen, Dvir Kafri, Jimmy Chen, Juan Atalaya, Kevin Satzinger, Chris Quintana, Paul Victor Klimov, Daniel Sank, Craig Michael Gidney, Austin Fowler, Frank Carlton Arute, Kunal Arya, Bob Benjamin Buckley, Brian Burkett, Nicholas Bushnell, Benjamin Chiaro, Roberto Collins, Sean Demura, Andrew Dunsworth, Catherine Erickson, Brooks Riley Foxen, Marissa Giustina, Trent Huang, Sabrina Hong, Evan Jeffrey, Seon Kim, Kostyantyn Kechedzhi, Fedor Kostritsa, Pavel Laptev, Anthony Megrant, Xiao Mi, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Murphy Yuezhen Niu, Alexandru Paler, Nick Redd, Pedram Roushan, Ted White, Jamie Yao, Ping Yeh, Adam Jozef Zalcman, Yu Chen, Vadim Smelyanskiy, John Martinis, Hartmut Neven, J. Kelly, Alexander Korotkov, Andre Gregory Petukhov, Rami Barends · Nature Communications, vol. 12 (2021), pp. 1761
Download PDF View
Quantum computing becomes scalable through error correction, but logical error rates only decrease with system size when physical errors are sufficiently uncorrelated. During computation, the unused high energy states of the qubits can become excited. In weakly nonlinear qubits, such as the superconducting transmon, these leakage states are long-lived and mobile, opening a path to errors that are correlated in space and time. The effects of leakage and its mitigation during quantum error correction remain an open question. Here, we report a reset protocol that returns a qubit to the ground state from all relevant higher level states. It requires no additional hardware and combines speed, fidelity, and resilience to noise. We test its performance with the bit-flip stabilizer code, a simplified version of the surface code scheme for quantum error correction. We investigate the accumulation and dynamics of leakage during the stabilizer codes. Using this protocol, we find lower rates of logical errors, and an improved scaling and stability of error suppression with qubits. This demonstration provides a key step on the path towards scalable quantum computing.

Fault-Tolerant Quantum Simulations of Chemistry in First Quantization

Yuan Su, Dominic W. Berry, Nathan Wiebe, Nicholas Rubin, Ryan Babbush · PRX Quantum, vol. 2 (2021), pp. 040332
Download PDF View
Quantum simulations of chemistry in first quantization offer important advantages over approaches in second quantization including faster convergence to the continuum limit and the opportunity for practical simulations outside the Born-Oppenheimer approximation. However, as all prior work on quantum simulation in first quantization has been limited to asymptotic analysis, it has been impossible to compare the resources required for these approaches to those for more commonly studied algorithms in second quantization. Here, we analyze and optimize the resources required to implement two first quantized quantum algorithms for chemistry from Babbush et al that realize block encodings for the qubitization and interaction picture frameworks of Low et al. The two algorithms we study enable simulation with gate complexities O(η^{8/3} N^{1/3} t+η^{4/3} N^{2/3} t) and O(η^{8/3} N^{1/3} t) where η is the number of electrons, N is the number of plane wave basis functions, and t is the duration of time-evolution (t is inverse to target precision when the goal is to estimate energies). In addition to providing the first explicit circuits and constant factors for any first quantized simulation and introducing improvements which reduce circuit complexity by about a thousandfold over naive implementations for modest sized systems, we also describe new algorithms that asymptotically achieve the same scaling in a real space representation. We assess the resources required to simulate various molecules and materials and conclude that the qubitized algorithm will often be more practical than the interaction picture algorithm. We demonstrate that our qubitized algorithm often requires much less surface code spacetime volume for simulating millions of plane waves than the best second quantized algorithms require for simulating hundreds of Gaussian orbitals.

Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor

Matthew Harrigan, Kevin Jeffery Sung, Kevin Satzinger, Matthew Neeley, Frank Carlton Arute, Kunal Arya, Juan Atalaya, Joseph Bardin, Rami Barends, Sergio Boixo, Michael Blythe Broughton, Bob Benjamin Buckley, David A Buell, Brian Burkett, Nicholas Bushnell, Jimmy Chen, Yu Chen, Ben Chiaro, Roberto Collins, William Courtney, Sean Demura, Andrew Dunsworth, Austin Fowler, Brooks Riley Foxen, Craig Michael Gidney, Marissa Giustina, Rob Graff, Steve Habegger, Sabrina Hong, Lev Ioffe, Sergei Isakov, Evan Jeffrey, Zhang Jiang, Cody Jones, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Seon Kim, Paul Klimov, Alexander Korotkov, Fedor Kostritsa, Dave Landhuis, Pavel Laptev, Martin Leib, Mike Lindmark, Orion Martin, John Martinis, Jarrod Ryan McClean, Matthew McEwen, Anthony Megrant, Xiao Mi, Masoud Mohseni, Wojtek Mruczkiewicz, Josh Mutus, Ofer Naaman, Charles Neill, Florian Neukart, Murphy Yuezhen Niu, Thomas E O'Brien, Bryan O'Gorman, A.G. Petukhov, Harry Putterman, Chris Quintana, Pedram Roushan, Nicholas Rubin, Daniel Sank, Andrea Skolik, Vadim Smelyanskiy, Doug Strain, Michael Streif, Marco Szalay, Amit Vainsencher, Ted White, Jamie Yao, Adam Zalcman, Leo Zhou, Hartmut Neven, Dave Bacon, Erik Lucero, Edward Farhi, Ryan Babbush · Nature Physics (2021)
Download PDF View
Faster algorithms for combinatorial optimization could prove transformative for diverse areas such as logistics, finance and machine learning. Accordingly, the possibility of quantum enhanced optimization has driven much interest in quantum technologies. Here we demonstrate the application of the Google Sycamore superconducting qubit quantum processor to combinatorial optimization problems with the quantum approximate optimization algorithm (QAOA). Like past QAOA experiments, we study performance for problems defined on the planar connectivity graph native to our hardware; however, we also apply the QAOA to the Sherrington–Kirkpatrick model and MaxCut, non-native problems that require extensive compilation to implement. For hardware-native problems, which are classically efficient to solve on average, we obtain an approximation ratio that is independent of problem size and observe that performance increases with circuit depth. For problems requiring compilation, performance decreases with problem size. Circuits involving several thousand gates still present an advantage over random guessing but not over some efficient classical algorithms. Our results suggest that it will be challenging to scale near-term implementations of the QAOA for problems on non-native graphs. As these graphs are closer to real-world instances, we suggest more emphasis should be placed on such problems when using the QAOA to benchmark quantum processors.

Tuning Quantum Information Scrambling on a 53-Qubit Processor

Adam Jozef Zalcman, Alan Derk, Alan Ho, Alex Opremcak, Alexander Korotkov, Alexandre Bourassa, Andre Gregory Petukhov, Andreas Bengtsson, Andrew Dunsworth, Anthony Megrant, Austin Fowler, Bálint Pató, Benjamin Chiaro, Benjamin Villalonga, Brian Burkett, Brooks Riley Foxen, Catherine Erickson, Charles Neill, Chris Quintana, Cody Jones, Craig Michael Gidney, Daniel Eppens, Daniel Sank, Dave Landhuis, David A Buell, Doug Strain, Dvir Kafri, Edward Farhi, Eric Ostby, Erik Lucero, Evan Jeffrey, Fedor Kostritsa, Frank Carlton Arute, Hartmut Neven, Igor Aleiner, Jamie Yao, Jarrod Ryan McClean, Jeffrey Marshall, Jeremy Patterson Hilton, Jimmy Chen, Jonathan Arthur Gross, Joseph Bardin, Josh Mutus, Juan Atalaya, Julian Kelly, Kevin Miao, Kevin Satzinger, Kostyantyn Kechedzhi, Kunal Arya, Marco Szalay, Marissa Giustina, Masoud Mohseni, Matt McEwen, Matt Trevithick, Matthew Neeley, Matthew P Harrigan, Michael Blythe Broughton, Michael Newman, Murphy Yuezhen Niu, Nicholas Bushnell, Nicholas Redd, Nicholas Rubin, Ofer Naaman, Orion Martin, Paul Victor Klimov, Pavel Laptev, Pedram Roushan, Ping Yeh, Rami Barends, Roberto Collins, Ryan Babbush, Sabrina Hong, Salvatore Mandra, Sean Demura, Sean Harrington, Seon Kim, Sergei Isakov, Sergio Boixo, Ted White, Thomas E O'Brien, Trent Huang, Trevor Mccourt, Vadim Smelyanskiy, Vladimir Shvarts, William Courtney, Wojtek Mruczkiewicz, Xiao Mi, Yu Chen, Zhang Jiang · arXiv (2021)
As entanglement in a quantum system grows, initially localized quantum information is spread into the exponentially many degrees of freedom of the entire system. This process, known as quantum scrambling, is computationally intensive to study classically and lies at the heart of several modern physics conundrums. Here, we characterize scrambling of different quantum circuits on a 53-qubit programmable quantum processor by measuring their out-of-time-order correlators (OTOCs). We observe that the spatiotemporal spread of OTOCs, as well as their circuit-to-circuit fluctuation, unravel in detail the time-scale and extent of quantum scrambling. Comparison with numerical results indicates a high OTOC measurement accuracy despite the large size of the quantum system. Our work establishes OTOC as an experimental tool to diagnose quantum scrambling at the threshold of being classically inaccessible.

Quantum advantage in learning from experiments

Hsin-Yuan (Robert) Huang, Michael Blythe Broughton, Jordan Cotler, Sitan Chen, Jerry Li, Masoud Mohseni, Hartmut Neven, Ryan Babbush, Richard Kueng, John Preskill, Jarrod Ryan McClean · Science, vol. 376 (2021), pp. 1182 - 1186
Download PDF View
Quantum technology has the potential to revolutionize how we acquire and process experimental data to learn about the physical world. An experimental setup that transduces data from a physical system to a stable quantum memory, and processes that data using a quantum computer, could have significant advantages over conventional experiments in which the physical system is measured and the outcomes are processed using a classical computer. We prove that, in various tasks, quantum machines can learn from exponentially fewer experiments than those required in conventional experiments. The exponential advantage holds in predicting properties of physical systems, performing quantum principal component analysis on noisy states, and learning approximate models of physical dynamics. In some tasks, the quantum processing needed to achieve the exponential advantage can be modest; for example, one can simultaneously learn about many noncommuting observables by processing only two copies of the system. Conducting experiments with up to 40 superconducting qubits and 1300 quantum gates, we demonstrate that a substantial quantum advantage can be realized using today's relatively noisy quantum processors. Our results highlight how quantum technology can enable powerful new strategies to learn about nature.

Provably accurate simulation of gauge theories and bosonic systems

Yu Tong, Victor V. Albert, Jarrod Ryan McClean, John Preskill, Yuan Su · arXiv:2110.06942 (2021)
Download PDF View
Quantum many-body systems involving bosonic modes or gauge fields have infinite-dimensional local Hilbert spaces which must be truncated to perform simulations of real-time dynamics on classical or quantum computers. To analyze errors resulting from truncation, we develop methods for bounding the rate of growth of local quantum numbers such as the occupation number of a mode at a lattice site, or the electric field at a lattice link. Our approach applies to various models of bosons interacting with spins or fermions such as the Hubbard-Holstein, Fr\"ohlich, and Dicke models, and also to both abelian and non-abelian gauge theories. We show that if states in these models are truncated by imposing an upper limit $\Lambda$ on each local quantum number, and if the initial state has low local quantum numbers, then a truncation error no worse than $\epsilon$ can be achieved by choosing $\Lambda$ to increase polylogarithmically with $\epsilon^{-1}$, an exponential improvement over previous bounds based on energy conservation. For the Hubbard-Holstein model, we numerically compute an upper bound on the value of $\Lambda$ that achieves accuracy $\epsilon$, finding significant improvement over previous estimates in various parameter regimes. We also establish a criterion for truncating the Hamiltonian with a provable guarantee on the accuracy of time evolution. Building on that result, we formulate quantum algorithms for dynamical simulation of lattice gauge theories and of models with bosonic modes; the gate complexity depends almost linearly on spacetime volume in the former case, and almost quadratically on time in the latter case. We establish a lower bound showing that there are systems involving bosons for which this quadratic scaling with time cannot be improved. By applying our results on the truncation error in time evolution, we also prove that spectrally isolated energy eigenstates can be approximated with error at most $\epsilon$ by truncating local quantum numbers at $\Lambda=\textrm{polylog}(\epsilon^{-1})$.

Exponential suppression of bit or phase flip errors with repetitive quantum error correction

Adam Jozef Zalcman, Alan Derk, Alan Ho, Alex Opremcak, Alexander Korotkov, Alexandre Bourassa, Andre Gregory Petukhov, Andreas Bengtsson, Andrew Dunsworth, Anthony Megrant, Austin Fowler, Bálint Pató, Benjamin Chiaro, Benjamin Villalonga, Brian Burkett, Brooks Riley Foxen, Catherine Erickson, Charles Neill, Chris Quintana, Cody Jones, Craig Michael Gidney, Daniel Eppens, Daniel Sank, Dave Landhuis, David A Buell, Doug Strain, Dvir Kafri, Edward Farhi, Eric Ostby, Erik Lucero, Evan Jeffrey, Fedor Kostritsa, Frank Carlton Arute, Hartmut Neven, Igor Aleiner, Jamie Yao, Jarrod Ryan McClean, Jeremy Patterson Hilton, Jimmy Chen, Jonathan Arthur Gross, Joseph Bardin, Josh Mutus, Juan Atalaya, Julian Kelly, Kevin Miao, Kevin Satzinger, Kostyantyn Kechedzhi, Kunal Arya, Marco Szalay, Marissa Giustina, Masoud Mohseni, Matt McEwen, Matt Trevithick, Matthew Neeley, Matthew P Harrigan, Michael Broughton, Michael Newman, Murphy Yuezhen Niu, Nicholas Bushnell, Nicholas Redd, Nicholas Rubin, Ofer Naaman, Orion Martin, Paul Victor Klimov, Pavel Laptev, Pedram Roushan, Ping Yeh, Rami Barends, Roberto Collins, Ryan Babbush, Sabrina Hong, Sean Demura, Sean Harrington, Seon Kim, Sergei Isakov, Sergio Boixo, Ted White, Thomas E O'Brien, Trent Huang, Trevor Mccourt, Vadim Smelyanskiy, Vladimir Shvarts, William Courtney, Wojtek Mruczkiewicz, Xiao Mi, Yu Chen, Zhang Jiang · Nature (2021)
Realizing the potential of quantum computing will require achieving sufficiently low logical error rates. Many applications call for error rates below 10^-15, but state-of-the-art quantum platforms typically have physical error rates near 10^-3. Quantum error correction (QEC) promises to bridge this divide by distributing quantum logical information across many physical qubits so that errors can be corrected. Logical errors are then exponentially suppressed as the number of physical qubits grows, provided that the physical error rates are below a certain threshold. QEC also requires that the errors are local, and that performance is maintained over many rounds of error correction, a major outstanding experimental challenge. Here, we implement 1D repetition codes embedded in a 2D grid of superconducting qubits which demonstrate exponential suppression of bit or phase-flip errors, reducing logical error per round by more than 100x when increasing the number of qubits from 5 to 21. Crucially, this error suppression is stable over 50 rounds of error correction. We also introduce a method for analyzing error correlations with high precision, and characterize the locality of errors in a device performing QEC for the first time. Finally, we perform error detection using a small 2D surface code logical qubit on the same device, and show that the results from both 1D and 2D codes agree with numerical simulations using a simple depolarizing error model. These findings demonstrate that superconducting qubits are on a viable path towards fault tolerant quantum computing.

Efficient and Noise Resilient Measurements for Quantum Chemistry on Near-Term Quantum Computers

William Huggins, Jarrod Ryan McClean, Nicholas Rubin, Zhang Jiang, Nathan Wiebe, K. Birgitta Whaley, Ryan Babbush · Nature Quantum Information, vol. 7 (2021)
Download PDF View
Variational algorithms are a promising paradigm for utilizing near-term quantum devices for modeling electronic states of molecular systems. However, previous bounds on the measurement time required have suggested that the application of these techniques to larger molecules might be infeasible. We present a measurement strategy based on a low-rank factorization of the two-electron integral tensor. Our approach provides a cubic reduction in term groupings over prior state-of-the-art and enables measurement times three orders of magnitude smaller than those suggested by commonly referenced bounds for the largest systems we consider. Although our technique requires execution of a linear-depth circuit prior to measurement, this is compensated for by eliminating challenges associated with sampling nonlocal Jordan–Wigner transformed operators in the presence of measurement error, while enabling a powerful form of error mitigation based on efficient postselection. We numerically characterize these benefits with noisy quantum circuit simulations for ground-state energies of strongly correlated electronic systems.

Even More Efficient Quantum Computations of Chemistry through Tensor Hyper-Contraction

Joonho Lee, Dominic W. Berry, Craig Michael Gidney, William J. Huggins, Jarrod Ryan McClean, Nathan Wiebe, Ryan Babbush · PRX Quantum, vol. 2 (2021), pp. 030305
Download PDF View
We describe quantum circuits with only $\widetilde{\cal O}(N)$ Toffoli complexity that block encode the spectra of quantum chemistry Hamiltonians in a basis of $N$ arbitrary (e.g., molecular) orbitals. With ${\cal O}(\lambda / \epsilon)$ repetitions of these circuits one can use phase estimation to sample in the molecular eigenbasis, where $\lambda$ is the 1-norm of Hamiltonian coefficients and $\epsilon$ is the target precision. This is the lowest complexity that has been shown for quantum computations of chemistry within an arbitrary basis. Furthermore, up to logarithmic factors, this matches the scaling of the most efficient prior block encodings that can only work with orthogonal basis functions diagonalizing the Coloumb operator (e.g., the plane wave dual basis). Our key insight is to factorize the Hamiltonian using a method known as tensor hypercontraction (THC) and then to transform the Coulomb operator into an isospectral diagonal form with a non-orthogonal basis defined by the THC factors. We then use qubitization to simulate the non-orthogonal THC Hamiltonian, in a fashion that avoids most complications of the non-orthogonal basis. We also reanalyze and reduce the cost of several of the best prior algorithms for these simulations in order to facilitate a clear comparison to the present work. In addition to having lower asymptotic scaling spacetime volume, compilation of our algorithm for challenging finite-sized molecules such as FeMoCo reveals that our method requires the least fault-tolerant resources of any known approach. By laying out and optimizing the surface code resources required of our approach we show that FeMoCo can be simulated using about four million physical qubits and under four days of runtime, assuming $1 \, \mu {\rm s}$ cycle times and physical gate error rates no worse than $0.1\%$.

\textttp$^\dagger$q: A tool for prototyping many-body methods for quantum chemistry

Nicholas Rubin, Albert Eugene DePrince III · arXiv:2106.06850 (2021)
Download PDF View
\texttt{p$^\dagger$q} is a C++ accelerated Python library designed to generate equations for many-body quantum chemistry methods and to realize proof-of-concept implementations of these equations for rapid prototyping. Central to this library is a simple interface to define strings of second-quantized creation and annihilation operators and to bring these strings to normal order with respect to either the true vacuum state or the Fermi vacuum. Tensor contractions over fully-contracted strings can then be evaluated using standard Python functions ({\em e.g.}, Numpy's einsum). Given one- and two-electron integrals these features allow for the rapid implementation and assessment of a wide array of many-body quantum quantum chemistry methods.

Virtual Distillation for Quantum Error Mitigation

William J. Huggins, Sam Connor McArdle, Thomas E O'Brien, Joonho Lee, Nicholas Rubin, Sergio Boixo, Birgitta Whaley, Ryan Babbush, Jarrod Ryan McClean · Physical Review X, vol. 11 (2021), pp. 041036
Download PDF View
Contemporary quantum computers have relatively high levels of noise, making it difficult to use them to perform useful calculations, even with a large number of qubits. Quantum error correction is expected to eventually enable fault-tolerant quantum computation at large scales, but until then it will be necessary to use alternative strategies to mitigate the impact of errors. We propose a near-term friendly strategy to mitigate errors by entangling and measuring \(M\) copies of a noisy state \(\rho\). This enables us to estimate expectation values with respect to a state with dramatically reduced error, \(\rho^M/ \tr(\rho^M)\), without explicitly preparing it, hence the name ``virtual distillation''. As \(M\) increases, this state approaches the closest pure state to \(\rho\), exponentially quickly. We analyze the effectiveness of virtual distillation and find that it is governed in many regimes by the behaviour of this pure state (corresponding to the dominant eigenvector of \(\rho\)). We numerically demonstrate that virtual distillation is capable of suppressing errors by multiple orders of magnitude and explain how this effect is enhanced as the system size grows. Finally, we show that this technique can improve the convergence of randomized quantum algorithms, even in the absence of device noise.

Low Rank Representations for Quantum Simulations of Electronic Structure

Mario Motta, Erika Ye, Jarrod Ryan McClean, Zhendong Li, Austin Minnich, Ryan Babbush, Garnet Kin-Lic Chan · NPJ Quantum Information, vol. 7 (2021)
Download PDF View
The quantum simulation of quantum chemistry is a promising application of quantum computers. However, for N molecular orbitals, the O(N^4) gate complexity of performing Hamiltonian and unitary Coupled Cluster Trotter steps makes simulation based on such primitives challenging. We substantially reduce the gate complexity of such primitives through a two-step low-rank factorization of the Hamiltonian and cluster operator, accompanied by truncation of small terms. Using truncations that incur errors below chemical accuracy, we are able to perform Trotter steps of the arbitrary basis electronic structure Hamiltonian with O(N^3) gate complexity in small simulations, which reduces to O(N^2 log N) gate complexity in the asymptotic regime, while our unitary Coupled Cluster Trotter step has O(N^3) gate complexity as a function of increasing basis size for a given molecule. In the case of the Hamiltonian Trotter step, these circuits have O(N^2) depth on a linearly connected array, an improvement over the O(N^3) scaling assuming no truncation. As a practical example, we show that a chemically accurate Hamiltonian Trotter step for a 50 qubit molecular simulation can be carried out in the molecular orbital basis with as few as 4,000 layers of parallel nearest-neighbor two-qubit gates, consisting of fewer than 100,000 non-Clifford rotations. We also apply our algorithm to iron-sulfur clusters relevant for elucidating the mode of action of metalloenzymes.

Error Mitigation via Verified Phase Estimation

Thomas E O'Brien, Stefano Polla, Nicholas Rubin, Bill Huggins, Sam Connor McArdle, Sergio Boixo, Jarrod Ryan McClean, Ryan Babbush · PRX Quantum, vol. 2 (2021)
Download PDF View
We present a novel error mitigation technique for quantum phase estimation. By post-selecting the system register to be in the starting state, we convert all single errors prior to final measurement to a time-dependent decay (up to on average exponentially small corrections), which may be accurately corrected for at the cost of additional measurement. This error migitation can be built into phase estimation techniques that do not require control qubits. By separating the observable of interest into a linear combination of fast-forwardable Hamiltonians and measuring those components individually, we can convert this decay into a constant offset. Using this technique, we demonstrate the estimation of expectation values on numerical simulations of moderately-sized quantum circuits with multiple orders of magnitude improvement over unmitigated estimation at near-term error rates. We further combine verified phase estimation with the optimization step in a variational algorithm to provide additional mitigation of control error. In many cases, our results demonstrate a clear signature that the verification technique can mitigate against any single error occurring in an instance of a quantum computation: the error $\epsilon$ in the expectation value estimation scales with $p^2$, where $p$ is the probability of an error occurring at any point in the circuit. Further numerics indicate that our scheme remains robust in the presence of sampling noise, though different classical post-processing methods may lead to up to an order of magnitude error increase in the final energy estimates.

The Fermionic Quantum Emulator

Nicholas Rubin, Klaas Gunst, Alec White, Leon Freitag, Kyle Throssell, Garnet Kin-Lic Chan, Ryan Babbush, Toru Shiozaki · Quantum, vol. 5 (2021), pp. 568
Download PDF View
The fermionic quantum emulator (FQE) is a collection of protocols for emulating quantum dynamics of fermions efficiently taking advantage of common symmetries present in chemical, materials, and condensed-matter systems. The library is fully integrated with the OpenFermion software package and serves as the simulation backend. The FQE reduces memory footprint by exploiting number and spin symmetry along with custom evolution routines for sparse and dense Hamiltonians, allowing us to study significantly larger quantum circuits at modest computational cost when compared against qubit state vector simulators. This release paper outlines the technical details of the simulation methods and key advantages.

Analog/Mixed-Signal Integrated Circuits for Quantum Computing

Joseph Bardin · Proceedings of the 2020 IEEE BiCMOS and Compound Semiconductor Integrated Circuits and Technology Symposium (BCICTS)
Future error-corrected quantum computers will require analog/mixed-signal control systems capable of providing a million or more high-precision analog waveforms. In this article, we begin by introducing the reader to superconducting transmon qubit technology and then explain how the state of a quantum processor implemented in this technology is controlled. By example, we then show how one can implement one part of the quantum control system as a cryogenic integrated circuit and review experimental results from the characterization of such an IC. The article concludes with a discussion of analog/mixed-signal design challenges that must be overcome in order to build the system required to control a million-qubit quantum computer.

Fermionic partial tomography via classical shadows

Akimasa Miyake, Andrew Zhao, Nicholas Rubin · arXiv:2010.16094 (2020)
Download PDF View
We propose a tomographic protocol for estimating any $ k $-body reduced density matrix ($ k $-RDM) of an $ n $-mode fermionic state, a ubiquitous step in near-term quantum algorithms for simulating many-body physics, chemistry, and materials. Our approach extends the framework of classical shadows, a randomized approach to learning a collection of quantum state properties, to the fermionic setting. Our sampling protocol uses randomized measurement settings generated by a discrete group of fermionic Gaussian unitaries, implementable with linear-depth circuits. We prove that estimating all $ k $-RDM elements to additive precision $ \varepsilon $ requires on the order of $ \binom{n}{k} k^{3/2} \log(n) / \varepsilon^2 $ repeated state preparations, which is optimal up to the logarithmic factor. Furthermore, numerical calculations show that our protocol offers a substantial improvement in constant overheads for $ k \geq 2 $, as compared to prior deterministic strategies. We also adapt our method to particle-number symmetry, wherein the additional circuit depth may be halved at the cost of roughly 2--5 times more repetitions.

A Low-Power CMOS Quantum Controller for Transmon Qubits

Joseph Bardin · Proceedings of the 2020 IEEE International Electron Devices Meeting (IEDM)
The development of large-scale quantum computers will require the implementation of scalable control and measurement electronics, which may have to operate at a temperature as low as 4 K. In this paper, we review a first-generation control IC that has been implemented for use with transmon qubits. We first explain the requirements which such an IC must meet and then present the circuit design. We then describe a series of quantum control experiments. The paper concludes with a discussion of future work.

The Snake Optimizer for Learning Quantum Processor Control Parameters

Paul Victor Klimov, Julian Kelly, John M. Martinis, Hartmut Neven · arXiv:2006.04594 (2020)
Download PDF View
High performance quantum computing requires a calibration system that learns optimal control parameters much faster than system drift. In some cases, the learning procedure requires solving complex optimization problems that are non-convex, high-dimensional, highly constrained, and have astronomical search spaces. Such problems pose an obstacle for scalability since traditional global optimizers are often too inefficient and slow for even small-scale processors comprising tens of qubits. In this whitepaper, we introduce the Snake optimizer for efficiently and quickly solving such optimization problems by leveraging concepts in artificial intelligence, dynamic programming, and graph optimization. In practice, the Snake has been applied to optimize the frequencies at which quantum logic gates are implemented in frequency-tunable superconducting qubits. This application enabled state-of-the-art system performance on a 53 qubit quantum processor, serving as a key component of demonstrating quantum supremacy. Furthermore, since the Snake optimizer scales favorably with qubit number, is amenable to local re-optimization, and is parallelizable, it shows promise for optimizing much larger quantum processors.

Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization

Yuval Sanders, Dominic W. Berry, Pedro C. S. Costa, Louis W. Tessler, Nathan Wiebe, Craig Michael Gidney, Hartmut Neven, Ryan Babbush · PRX Quantum, vol. 1 (2020), pp. 020312
Download PDF View
Here we explore which heuristic quantum algorithms for combinatorial optimization might be most practical to try out on a small fault-tolerant quantum computer. We compile circuits for several variants of quantum-accelerated simulated annealing including those using qubitization or Szegedy walks to quantize classical Markov chains and those simulating spectral-gap-amplified Hamiltonians encoding a Gibbs state. We also optimize fault-tolerant realizations of the adiabatic algorithm, quantum-enhanced population transfer, the quantum approximate optimization algorithm, and other approaches. Many of these methods are bottlenecked by calls to the same subroutines; thus, optimized circuits for those primitives should be of interest regardless of which heuristic is most effective in practice. We compile these bottlenecks for several families of optimization problems and report for how long and for what size systems one can perform these heuristics in the surface code given a range of resource budgets. Our results discourage the notion that any quantum optimization heuristic realizing only a quadratic speedup achieves an advantage over classical algorithms on modest superconducting qubit surface code processors without significant improvements in the implementation of the surface code. For instance, under quantum-favorable assumptions (e.g., that the quantum algorithm requires exactly quadratically fewer steps), our analysis suggests that quantum-accelerated simulated annealing requires roughly a day and a million physical qubits to optimize spin glasses that could be solved by classical simulated annealing in about 4 CPU-minutes.

Quantum Computing: An Introduction for Microwave Engineers

Joseph Bardin, Daniel Sank, Ofer Naaman, Evan Jeffrey · IEEE Microwave Magazine, vol. 21 (2020), pp. 24-44
Download PDF View
This paper is a tutorial on quantum computing designed for hardware engineers. We begin by explaining the type of computation that is carried out on a universal quantum computer then describe the requirement for hardware used to build a such system. We then explain how each of these requirements can be met using superconducting qubit technology. Connections are made throughout to familiar microwave concepts. The paper ends with a discussion of what is required of a fault-tolerant quantum computer and how the expertise of the microwave engineering community will be required to engineer such a system.

Investigating Quantum Approximate Optimization Algorithms under Bang-bang Protocols

Daniel Liang, Li Li, Stefan Leichenauer · Phys. Rev. Research, vol. 2 (2020), pp. 033402
Download PDF View
The quantum approximate optimization algorithm (QAOA) is widely seen as a possible usage of noisy intermediate-scale quantum (NISQ) devices. We analyze the algorithm as a bang-bang protocol with fixed total time and a randomized greedy optimization scheme. We investigate the performance of bang-bang QAOA on MAX-2-SAT, finding the appearance of phase transitions with respect to the total time. As the total time increases, the optimal bang-bang protocol experiences a number of jumps and plateaus in performance, which match up with an increasing number of switches in the standard QAOA formulation. At large times, it becomes more difficult to find a globally optimal bang-bang protocol and performances suffer. We also investigate the effects of changing the initial conditions of the randomized optimization algorithm and see that better local optima can be found by using an adiabatic initialization.

Improved Fault-Tolerant Quantum Simulation of Condensed-Phase Correlated Electrons via Trotterization

Ian Kivlichan, Craig Michael Gidney, Dominic Berry, Jarrod Ryan McClean, Wei Sun, Zhang Jiang, Nicholas Rubin, Austin Fowler, Alán Aspuru-Guzik, Hartmut Neven, Ryan Babbush · Quantum, vol. 4 (2020), pp. 296
Download PDF View
Recent work has deployed linear combinations of unitaries techniques to significantly reduce the cost of performing fault-tolerant quantum simulations of correlated electron models. Here, we show that one can sometimes improve over those results with optimized implementations of Trotter-Suzuki-based product formulas. We show that low-order Trotter methods perform surprisingly well when used with phase estimation to compute relative precision quantities (e.g. energy per unit cell), as is often the goal for condensed-phase (e.g. solid-state) systems. In this context, simulations of the Hubbard model and plane wave electronic structure models with $N < 10^5$ fermionic modes can be performed with roughly O(1) and O(N^2) T complexities. We also perform numerics that reveal tradeoffs between the error of a Trotter step and Trotter step gate complexity across various implementations; e.g., we show that split-operator techniques have less Trotter error than popular alternatives. By compiling to surface code fault-tolerant gates using lattice surgery and assuming error rates of one part in a thousand, we show that one can error-correct quantum simulations of interesting, classically intractable instances with only a few hundred thousand physical qubits.

Quantum Optimization with a Novel Gibbs Objective Function and Ansatz Architecture Search

Li Li, Minjie Fan, Marc Coram, Patrick Riley, Stefan Leichenauer · Phys. Rev. Research, vol. 2 (2020), pp. 023074
Download PDF View
The quantum approximate optimization algorithm (QAOA) is a standard method for combinatorial optimization with a gate-based quantum computer. The QAOA consists of a particular ansatz for the quantum circuit architecture, together with a prescription for choosing the variational parameters of the circuit. We propose modifications to both. First, we define the Gibbs objective function and show that it is superior to the energy expectation value for use as an objective function in tuning the variational parameters. Second, we describe an ansatz architecture search (AAS) algorithm for searching the discrete space of quantum circuit architectures near the QAOA to find a better ansatz. Applying these modifications for a complete graph Ising model results in a 244.7% median relative improvement in the probability of finding a low-energy state while using 33.3% fewer two-qubit gates. For Ising models on a 2d grid we similarly find 44.4% median improvement in the probability with a 20.8% reduction in the number of two-qubit gates. This opens a new research field of quantum circuit architecture design for quantum optimization algorithms.

Using Models to Improve Optimizers for Variational Quantum Algorithms

Kevin Jeffery Sung, Jiahao Yao, Matthew P Harrigan, Nicholas Rubin, Zhang Jiang, Lin Lin, Ryan Babbush, Jarrod Ryan McClean · Quantum Science and Technology, vol. 5 (2020), pp. 044008
Download PDF View
Variational quantum algorithms are a leading candidate for early applications on noisy intermediate-scale quantum computers. These algorithms depend on a classical optimization outer-loop that minimizes some function of a parameterized quantum circuit. In practice, finite sampling error and gate errors make this a stochastic optimization with unique challenges that must be addressed at the level of the optimizer. The sharp trade-off between precision and sampling time in conjunction with experimental constraints necessitates the development of new optimization strategies to minimize overall wall clock time in this setting. We introduce an optimization method and numerically compare its performance with common methods in use today. The method is a simple surrogate model-based algorithm designed to improve reuse of collected data. It does so by estimating the gradient using a least-squares quadratic fit of sampled function values within a moving trusted region. To make fair comparisons between optimization methods, we develop experimentally relevant cost models designed to balance efficiency in testing and accuracy with respect to cloud quantum computing systems. The results here underscore the need to both use relevant cost models and optimize hyperparameters of existing optimization methods for competitive performance. We compare tuned methods using cost models presented by superconducting devices accessed through cloud computing platforms. The method introduced here has several practical advantages in realistic experimental settings, and has been used successfully in a separately published experiment on Google's Sycamore device.

Accurately computing electronic properties of materials using eigenenergies

Adam Jozef Zalcman, Alan Derk, Alan Ho, Alex Opremcak, Alexander Korotkov, Andre Gregory Petukhov, Andreas Bengtsson, Andrew Dunsworth, Anthony Megrant, Austin Fowler, Bálint Pató, Benjamin Chiaro, Benjamin Villalonga, Bob Benjamin Buckley, Brian Burkett, Brooks Riley Foxen, Catherine Erickson, Charles Neill, Chris Quintana, Cody Jones, Craig Michael Gidney, Daniel Eppens, Daniel Sank, Dave Landhuis, David A Buell, Doug Strain, Dvir Kafri, Edward Farhi, Eric Ostby, Erik Lucero, Evan Jeffrey, Fedor Kostritsa, Frank Carlton Arute, Hartmut Neven, Igor Aleiner, Jamie Yao, Jarrod Ryan McClean, Jeremy Patterson Hilton, Jimmy Chen, Jonathan Arthur Gross, Joseph Bardin, Josh Mutus, Juan Atalaya, Juan Campero, Julian Kelly, Kevin Miao, Kevin Satzinger, Kostyantyn Kechedzhi, Kunal Arya, Lev Ioffe, Marco Szalay, Marissa Giustina, Masoud Mohseni, Matt Jacob-Mitos, Matt McEwen, Matt Trevithick, Matthew Neeley, Matthew P Harrigan, Michael Blythe Broughton, Michael Newman, Murphy Yuezhen Niu, Nicholas Bushnell, Nicholas Redd, Nicholas Rubin, Ofer Naaman, Orion Martin, Paul Victor Klimov, Pavel Laptev, Pedram Roushan, Ping Yeh, Rami Barends, Roberto Collins, Ryan Babbush, Sabrina Hong, Sean Demura, Sean Harrington, Seon Kim, Sergei Isakov, Sergio Boixo, Ted White, Thomas E O'Brien, Trent Huang, Trevor Mccourt, Vadim Smelyanskiy, Vladimir Shvarts, William Courtney, William J. Huggins, Wojtek Mruczkiewicz, Xiao Mi, Yu Chen, Zhang Jiang · arXiv preprint arXiv:2012.00921 (2020)
A promising approach to study quantum materials is to simulate them on an engineered quantum platform. However, achieving the accuracy needed to outperform classical methods has been an outstanding challenge. Here, using superconducting qubits, we provide an experimental blueprint for a programmable and accurate quantum matter simulator and demonstrate how to probe fundamental electronic properties. We illustrate the underlying method by reconstructing the single-particle band-structure of a one-dimensional wire. We demonstrate nearly complete mitigation of decoherence and readout errors and arrive at an accuracy in measuring energy eigenvalues of this wire with an error of ~0.01 radians, whereas typical energy scales are of order 1 radian. Insight into this unprecedented algorithm fidelity is gained by highlighting robust properties of a Fourier transform, including the ability to resolve eigenenergies with a statistical uncertainty of 1e-4 radians. Furthermore, we synthesize magnetic flux and disordered local potentials, two key tenets of a condensed-matter system. When sweeping the magnetic flux, we observe avoided level crossings in the spectrum, a detailed fingerprint of the spatial distribution of local disorder. Combining these methods, we reconstruct electronic properties of the eigenstates where we observe persistent currents and a strong suppression of conductance with added disorder. Our work describes an accurate method for quantum simulation and paves the way to study novel quantum materials with superconducting qubits.

TensorFlow Quantum: A Software Framework for Quantum Machine Learning

Michael Broughton, Guillaume Verdon, Trevor McCourt, Antonio J. Martinez, Jae Hyeon Yoo, Sergei V. Isakov, Philip Massey, Ramin Halavati, Murphy Yuezhen Niu, Alexander Zlokapa, Evan Peters, Owen Lockwood, Andrea Skolik, Sofiene Jerbi, Vedran Djunko, Martin Leib, Michael Streif, David Von Dollen, Hongxiang Chen, Chuxiang Cao, Roeland Wiersema, Hsin-Yuan Huang, Jarrod R. McClean, Ryan Babbush, Sergio Boixo, Dave Bacon, Alan K. Ho, Hartmut Neven, Masoud Mohseni · (2020)
Download PDF View
We introduce TensorFlow Quantum (TFQ), an open source library for the rapid prototyping of hybrid quantum-classical models for classical or quantum data. This framework offers high-level abstractions for the design and training of both discriminative and generative quantum models under TensorFlow and supports high-performance quantum circuit simulators. We provide an overview of the software architecture and building blocks through several examples and review the theory of hybrid quantum-classical neural networks. We illustrate TFQ functionalities via several basic applications including supervised learning for quantum classification, quantum control, simulating noisy quantum circuits, and quantum approximate optimization. Moreover, we demonstrate how one can apply TFQ to tackle advanced quantum learning tasks including meta-learning, layerwise learning, Hamiltonian learning, sampling thermal states, variational quantum eigensolvers, classification of quantum phase transitions, generative adversarial networks, and reinforcement learning. We hope this framework provides the necessary tools for the quantum computing and machine learning research communities to explore models of both natural and artificial quantum systems, and ultimately discover new quantum algorithms which could potentially yield a quantum advantage.

Learnability and Complexity of Quantum Samples

Murphy Yuezhen Niu, Andrew Mingbo Dai, Li Li, Augustus Odena, Zhengli Zhao, Vadim Smelyanskiy, Hartmut Neven, Sergio Boixo · arxiv (2020)
Download PDF View
Given a quantum circuit, a quantum computer can sample the output distribution exponentially faster in the number of bits than classical computers. A similar exponential separation has yet to be established in generative models through quantum sample learning: given samples from an n-qubit computation, can we learn the underlying quantum distribution using models with training parameters that scale polynomial in n under a fixed training time? We study four kinds of generative models: Deep Boltzmann machine (DBM), Generative Adversarial Networks (GANs), Long Short-Term Memory (LSTM) and Autoregressive GAN, on learning quantum data set generated by deep random circuits. We demonstrate the leading performance of LSTM in learning quantum samples, and thus the autoregressive structure present in the underlying quantum distribution from random quantum circuits. Both numerical experiments and a theoretical proof in the case of the DBM show exponentially growing complexity of learning-agent parameters required for achieving a fixed accuracy as n increases. Finally, we establish a connection between learnability and the complexity of generative models by benchmarking learnability against different sets of samples drawn from probability distributions of variable degrees of complexities in their quantum and classical representations.

Nearly Optimal Measurement Scheduling for Partial Tomography of Quantum States

Xavier Bonet, Ryan Babbush, Thomas O'Brien · Physical Review X, vol. 10 (2020), pp. 031064
Download PDF View
Many applications of quantum simulation require to prepare and then characterize quantum states by performing an efficient partial tomography to estimate observables corresponding to k-body reduced density matrices (k-RDMs). For instance, variational algorithms for the quantum simulation of chemistry usually require that one measure the fermionic 2-RDM. While such marginals provide a tractable description of quantum states from which many important properties can be computed, their determination often requires a prohibitively large number of circuit repetitions. Here we describe a method by which all elements of k-RDMs acting on N qubits can be sampled with a number of circuits scaling as O(3^k log^{k-1} N), an exponential improvement in N over prior art. Next, we show that if one is able to implement a linear depth circuit on a linear array prior to measurement, then one can sample all elements of the fermionic 2-RDM using only O(N^2) circuits. We prove that this result is asymptotically optimal. Finally, we demonstrate that one can estimate the expectation value of any linear combination of fermionic 2-RDM elements using O(N^4 / w) circuits, each with only O(w) gates on a linear array where w < N is a free parameter. We expect these results will improve the viability of many proposals for near-term quantum simulation.

Hartree-Fock on a Superconducting Qubit Quantum Computer

Frank Carlton Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph Bardin, Rami Barends, Sergio Boixo, Michael Blythe Broughton, Bob Benjamin Buckley, David A Buell, Brian Burkett, Nicholas Bushnell, Yu Chen, Jimmy Chen, Benjamin Chiaro, Roberto Collins, William Courtney, Sean Demura, Andrew Dunsworth, Edward Farhi, Austin Fowler, Brooks Riley Foxen, Craig Michael Gidney, Marissa Giustina, Rob Graff, Steve Habegger, Matthew P Harrigan, Alan Ho, Sabrina Hong, Trent Huang, William J. Huggins, Lev Ioffe, Sergei Isakov, Evan Jeffrey, Zhang Jiang, Cody Jones, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Seon Kim, Paul Klimov, Alexander Korotkov, Fedor Kostritsa, Dave Landhuis, Pavel Laptev, Mike Lindmark, Erik Lucero, Orion Martin, John Martinis, Jarrod Ryan McClean, Matthew McEwen, Anthony Megrant, Xiao Mi, Masoud Mohseni, Wojtek Mruczkiewicz, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Hartmut Neven, Murphy Yuezhen Niu, Thomas E O'Brien, Eric Ostby, Andre Gregory Petukhov, Harry Putterman, Chris Quintana, Pedram Roushan, Nicholas Rubin, Daniel Sank, Kevin Satzinger, Vadim Smelyanskiy, Doug Strain, Kevin Jeffery Sung, Marco Szalay, Tyler Y. Takeshita, Amit Vainsencher, Ted White, Nathan Wiebe, Jamie Yao, Ping Yeh, Adam Zalcman · Science, vol. 369 (2020), pp. 6507
Download PDF View
As the search continues for useful applications of noisy intermediate scale quantum devices, variational simulations of fermionic systems remain one of the most promising directions. Here, we perform a series of quantum simulations of chemistry which involve twice the number of qubits and more than ten times the number of gates as the largest prior experiments. We model the binding energy of ${\rm H}_6$, ${\rm H}_8$, ${\rm H}_{10}$ and ${\rm H}_{12}$ chains as well as the isomerization of diazene. We also demonstrate error-mitigation strategies based on $N$-representability which dramatically improve the effective fidelity of our experiments. Our parameterized ansatz circuits realize the Givens rotation approach to free fermion evolution, which we variationally optimize to prepare the Hartree-Fock wavefunction. This ubiquitous algorithmic primitive corresponds to a rotation of the orbital basis and is required by many proposals for correlated simulations of molecules and Hubbard models. Because free fermion evolutions are classically tractable to simulate, yet still generate highly entangled states over the computational basis, we use these experiments to benchmark the performance of our hardware while establishing a foundation for scaling up more complex correlated quantum simulations of chemistry.

Increasing the Representation Accuracy of Quantum Simulations of Chemistry without Extra Quantum Resources

Tyler Takeshita, Nicholas Rubin, Zhang Jiang, Eunseok Lee, Ryan Babbush, Jarrod Ryan McClean · Physical Review X, vol. 10 (2020), pp. 011004
Download PDF View
Proposals for near-term experiments in quantum chemistry on quantum computers leverage the ability to target a subset of degrees of freedom containing the essential quantum behavior, sometimes called the active space. This approximation allows one to treat more difficult problems using fewer qubits and lower gate depths than would otherwise be possible. However, while this approximation captures many important qualitative features, it may leave the results wanting in terms of absolute accuracy (basis error) of the representation. In traditional approaches, increasing this accuracy requires increasing the number of qubits and an appropriate increase in circuit depth as well. Here we introduce a technique requiring no additional qubits or circuit depth that is able to remove much of this approximation in favor of additional measurements. The technique is constructed and analyzed theoretically, and some numerical proof of concept calculations are shown. As an example, we show how to achieve the accuracy of a 20 qubit representation using only 4 qubits and a modest number of additional measurements for a simple hydrogen molecule. We close with an outlook on the impact this technique may have on both near-term and fault-tolerant quantum simulations.

Creating and manipulating a Laughlin-type ν=1/3 fractional quantum Hall state on a quantum computer with linear depth circuits

Armin Rahmani, Kevin J. Sung, Harald Putterman, Pedram Roushan, Pouyan Ghaemi, Zhang Jiang · PRX Quantum, vol. 1 (2020), pp. 020309
Download PDF View
Here we present an efficient quantum algorithm to generate an equivalent many-body state to Laughlin’s ν= 1/3 fractional quantum Hall state on a digitized quantum computer. Our algorithm only uses quantum gates acting on neighboring qubits in a quasi one-dimensional setting, and its circuit depth is linear in the number of qubits, i.e., the number of Landau levels in the second quantized picture. We identify correlation functions that serve as signatures of the Laughlin state and discuss how to obtain them on a quantum computer. We also discuss a generalization of the algorithm for creating quasiparticles in the Laughlin state. This paves the way for several important studies, including quantum simulation of non-equilibrium dynamics and braiding of quasiparticles in quantum Hall states.

Demonstrating a Continuous Set of Two-qubit Gates for Near-term Quantum Algorithms

Brooks Riley Foxen, Charles Neill, Andrew Dunsworth, Pedram Roushan, Ben Chiaro, Anthony Megrant, Julian Kelly, Jimmy Chen, Kevin Satzinger, Rami Barends, Frank Carlton Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph Bardin, Sergio Boixo, David A Buell, Brian Burkett, Yu Chen, Roberto Collins, Edward Farhi, Austin Fowler, Craig Michael Gidney, Marissa Giustina, Rob Graff, Matthew P Harrigan, Trent Huang, Sergei Isakov, Evan Jeffrey, Zhang Jiang, Dvir Kafri, Kostyantyn Kechedzhi, Paul Klimov, Alexander Korotkov, Fedor Kostritsa, Dave Landhuis, Erik Lucero, Jarrod McClean, Matthew McEwen, Xiao Mi, Masoud Mohseni, Josh Mutus, Ofer Naaman, Matthew Neeley, Murphy Yuezhen Niu, Chris Quintana, Nicholas Rubin, Daniel Sank, Vadim Smelyanskiy, Amit Vainsencher, Ted White, Adam Zalcman, Jamie Yao, Hartmut Neven, John Martinis · arXiv:2001.08343 (2020)
Download PDF View
Quantum algorithms offer a dramatic speedup for computational problems in machine learning, material science, and chemistry. However, any near-term realizations of these algorithms will need to be heavily optimized to fit within the finite resources offered by existing noisy quantum hardware. Here, taking advantage of the strong adjustable coupling of gmon qubits, we demonstrate a continuous two qubit gate set that can provide a 5x reduction in circuit depth. We implement two gate families: an iSWAP-like gate to attain an arbitrary swap angle, $\theta$, and a CPHASE gate that generates an arbitrary conditional phase, $\phi$. Using one of each of these gates, we can perform an arbitrary two qubit gate within the excitation-preserving subspace allowing for a complete implementation of the so-called Fermionic Simulation, or fSim, gate set. We benchmark the fidelity of the iSWAP-like and CPHASE gate families as well as 525 other fSim gates spread evenly across the entire fSim($\theta$, $\phi$) parameter space achieving purity-limited average two qubit Pauli error of $3.8 \times 10^{-3}$ per fSim gate.

Decoding Quantum Errors Using Subspace Expansions

Jarrod Ryan McClean, Zhang Jiang, Nicholas Rubin, Ryan Babbush, Hartmut Neven · Nature Communications, vol. 11 (2020), pp. 636
Download PDF View
With the rapid developments in quantum hardware comes a push towards the first practical applications on these devices. While fully fault-tolerant quantum computers may still be years away, one may ask if there exist intermediate forms of error correction or mitigation that might enable practical applications before then. In this work, we consider the idea of post-processing error decoders using existing quantum codes, which are capable of mitigating errors on encoded logical qubits using classical post-processing with no complicated syndrome measurements or additional qubits beyond those used for the logical qubits. This greatly simplifies the experimental exploration of quantum codes on near-term devices, removing the need for locality of syndromes or fast feed-forward, allowing one to study performance aspects of codes on real devices. We provide a general construction equipped with a simple stochastic sampling scheme that does not depend explicitly on a number of terms that we extend to approximate projectors within a subspace. This theory then allows one to generalize to the correction of some logical errors in the code space, correction of some physical unencoded Hamiltonians without engineered symmetries, and corrections derived from approximate symmetries. In this work, we develop the theory of the method and demonstrate it on a simple example with the perfect [[5,1,3]] code, which exhibits a pseudo-threshold of p≈0.50 under a single qubit depolarizing channel applied to all qubits. We also provide a demonstration under the application of a logical operation and performance on an unencoded hydrogen molecule, which exhibits a significant improvement over the entire range of possible errors incurred under a depolarizing channel.

Discontinuous Galerkin Discretization for Quantum Simulation of Chemistry

Jarrod Ryan McClean, Fabian M. Faulstich, Qinyi Zhu, Bryan O'Gorman, Yiheng Qiu, Steven White, Ryan Babbush, Lin Lin · New Journal of Physics, vol. 22 (2020)
Download PDF View
Methods for electronic structure based on Gaussian and molecular orbital discretizations offer a well established, compact representation that forms much of the foundation of correlated quantum chemistry calculations on both classical and quantum computers. Despite their ability to describe essential physics with relatively few basis functions, these representations can suffer from a quartic growth of the number of integrals. Recent results have shown that, for some quantum and classical algorithms, moving to representations with diagonal two-body operators can result in dramatically lower asymptotic costs, even if the number of functions required increases significantly. We introduce a way to interpolate between the two regimes in a systematic and controllable manner, such that the number of functions is minimized while maintaining a block diagonal structure of the two-body operator and desirable properties of an original, primitive basis. Techniques are analyzed for leveraging the structure of this new representation on quantum computers. Empirical results for hydrogen chains suggest a scaling improvement from O(N^4.5) in molecular orbital representations to O(N^2.6) in our representation for quantum evolution in a fault-tolerant setting, and exhibit a constant factor crossover at 15 to 20 atoms. Moreover, we test these methods using modern density matrix renormalization group methods classically, and achieve excellent accuracy with respect to the complete basis set limit with a speedup of 1-2 orders of magnitude with respect to using the primitive or Gaussian basis sets alone. These results suggest our representation provides significant cost reductions while maintaining accuracy relative to molecular orbital or strictly diagonal approaches for modest-sized systems in both classical and quantum computation for correlated systems.

Materials loss measurements using superconducting microwave resonators

Corey Rae Harrington McRae, Haozhi Wang, Jiansong Gao, Michael Vissers, Teresa Brecht, Andrew Dunsworth, David Pappas, Josh Mutus · Review of Scientific Instruments (invited) (2020)
Download PDF View
The performance of superconducting circuits for quantum computing is limited by materials losses in general, and two-level system (TLS) losses in particular, at single photon powers and millikelvin temperatures. The identification of low loss fabrication techniques, materials, and thin film dielectrics is critical to achieving scalable architectures for superconducting quantum computing. Superconducting microwave resonators provide a convenient qubit proxy for assessing loss performance and studying loss mechanisms such as TLS loss, non-equilibrium quasiparticles, and magnetic flux vortices. In this review article, we provide an overview of considerations for designing accurate resonator experiments to characterize loss including applicable types of loss, cryogenic setup, device design, and methods for extracting material and interface loss tangents, summarizing techniques that have been evolving for over two decades. Results from measurements of a variety of materials and processes are also summarized. Lastly, we present recommendations for the reporting of loss data from superconducting microwave resonators to facilitate materials comparisons across the field.

Optimal fermion-to-qubit mapping via ternary trees with applications to reduced quantum states learning

Zhang Jiang, Amir Kalev, Wojtek Mruczkiewicz, Hartmut Neven · Quantum, vol. 4 (2020), pp. 276
Download PDF View
We introduce a fermion-to-qubit mapping using ternary trees. The mapping has a simple structure where any single Majorana operator on an n-mode fermionic system is mapped to a multi-qubit Pauli operator acting nontrivially on log_3 (2n+1) qubits. We prove that the ternary-tree mapping is optimal in the sense that it is impossible to construct a Pauli operator in any fermion-to-qubit mapping which acts nontrivially on less than log_3 (2n+1) qubits. We apply this mapping to the problem of learning k-fermion reduced density matrix (RDM); a problem relevant in various quantum simulation applications. We show that using this mapping one can determine the elements of all k-fermion RDMs, to precision ε, by repeating a single quantum circuit for ~ (2n+1) k / ε^2 times. This result is based on a method we develop here that allows one to determine the elements of all k-qubit RDMs, to precision ε, by repeating a single quantum circuit for ~ 3k /ε^2 times, independent of the system size. This method improves over existing ones for determining qubit RDMs.

XY-mixers: analytical and numerical results for QAOA

Eleanor Rieffel, Jason M. Dominy, Nicholas Rubin, Zhihui Wang · Phys. Rev. A, vol. 101 (2020), pp. 012320
Download PDF View
The Quantum Alternating Operator Ansatz (QAOA) is a promising gate-model meta-heuristic for combinatorial optimization. Extending the algorithm to include hard constraints presents an implementation challenge for near-term quantum resources. This work explores strategies for enforcing hard constraints by using XY-hamiltonians as the mixer. Despite the complexity of the XY-Hamiltonian mixer, we demonstrate that for problems represented through one-hot-encoding, certain classes of the mixer Hamiltonian can be implemented without Trotter error in depth $O(\kappa)$ where $\kappa$ is the number of assignable colors. We also specify general strategies for implementing QAOA circuits on all-to-all connected graphs and linearly connected graphs inspired by fermionic simulation techniques. Performance is validated on graph coloring problems that are known to be challenging for a given classical algorithm. The general strategy of using the XY-mixers is validated numerically demonstrating a significant improvement over the general X-mixer.

Quantum Simulation of the Sachdev-Ye-Kitaev Model by Asymmetric Qubitization

Ryan Babbush, Dominic W. Berry, Hartmut Neven · Physical Review A Rapid Communication, vol. 99 (2019), 040301(R)
Download PDF View
We show that one can quantum simulate the dynamics of a Sachdev-Ye-Kitaev model with $N$ Majorana modes for time $t$ to precision $\epsilon$ with gate complexity ${\cal O}(N^{7/2} t + N^{5/2} \log(1 / \epsilon) / \log\log(1/\epsilon))$. In addition to scaling sublinearly in the number of Hamiltonian terms, this gate complexity represents an exponential improvement in $1/\epsilon$ and large polynomial improvement in $N$ and $t$ over prior state-of-the-art algorithms which scale as ${\cal O}(N^{10} t^2 / \epsilon)$. Our approach involves a variant of the qubitization technique in which we encode the Hamiltonian $H$ as an asymmetric projection of a signal oracle $U$ onto two different signal states prepared by distinct state oracles, $A\ket{0} \mapsto \ket{A}$ and $B\ket{0} \mapsto \ket{B}$, such that $H = \bra{B} U \ket{A}$. Our strategy for applying this method to the Sachdev-Ye-Kitaev model involves realizing $B$ using only Hadamard gates and realizing $A$ as a random quantum circuit.

Learning to learn with quantum neural networks via classical neural networks

Guillaume Verdon, Michael Broughton, Jarrod Ryan McClean, Kevin Jeffery Sung, Ryan Babbush, Zhang Jiang, Hartmut Neven, Masoud Mohseni · arXiv:1907.05415 (2019)
Download PDF View
Quantum Neural Networks (QNNs) are a promising variational learning paradigm with applications to near-term quantum processors, however they still face some significant challenges. One such challenge is finding good parameter initialization heuristics that ensure rapid and consistent convergence to local minima of the parameterized quantum circuit landscape. In this work, we train classical neural networks to assist in the quantum learning process, also know as meta-learning, to rapidly find approximate optima in the parameter landscape for several classes of quantum variational algorithms. Specifically, we train classical recurrent neural networks to find approximately optimal parameters within a small number of queries of the cost function for the Quantum Approximate Optimization Algorithm (QAOA) for MaxCut, QAOA for Sherrington-Kirkpatrick Ising model, and for a Variational Quantum Eigensolver for the Hubbard model. By initializing other optimizers at parameter values suggested by the classical neural network, we demonstrate a significant improvement in the total number of optimization iterations required to reach a given accuracy. We further demonstrate that the optimization strategies learned by the neural network generalize well across a range of problem instance sizes. This opens up the possibility of training on small, classically simulatable problem instances, in order to initialize larger, classically intractably simulatable problem instances on quantum devices, thereby significantly reducing the number of required quantum-classical optimization iterations.

Design and Characterization of a 28-nm Bulk-CMOS Cryogenic Quantum Controller Dissipating Less than 2 mW at 3 K

Joseph Bardin, Evan Jeffrey, Erik Lucero, Trent Huang, Sayan Das, Daniel Sank, Ofer Naaman, Anthony Megrant, Rami Barends, Ted White, Marissa Giustina, Kevin Satzinger, Kunal Arya, Pedram Roushan, Ben Chiaro, Julian Kelly, Zijun Chen, Brian Burkett, Yu Chen, Andrew Dunsworth, Austin Fowler, Brooks Foxen, Craig Michael Gidney, Rob Graff, Paul Klimov, Josh Mutus, Matthew McEwen, Matthew Neeley, Charles Neill, Chris Quintana, Amit Vainsencher, Hartmut Neven, John Martinis · IEEE Journal of Solid State Circuits, vol. 54(11) (2019), pp. 3043 - 3060
Implementation of an error corrected quantum computer is believed to require a quantum processor with on the order of a million or more physical qubits and, in order to run such a processor, a quantum control system of similar scale will be required. Such a controller will need to be integrated within the cryogenic system and in close proximity with the quantum processor in order to make such a system practical. Here, we present a prototype cryogenic CMOS quantum controller designed in a 28-nm bulk CMOS process and optimized to implement a 4-bit XY gate instruction set for transmon qubits. After introducing the transmon qubit, including a discussion of how it is controlled, design considerations are discussed, with an emphasis on error rates and scalability. The circuit design is then discussed. Cryogenic performance of the underlying technology is presented and the results of several quantum control experiments carried out using the integrated controller are described. The paper ends with a comparison to the state of the art. It has been shown that the quantum control IC achieves comparable performance with a conventional rack mount control system while dissipating less than 2mW of total AC and DC power and requiring a digital data stream of less than 500 Mb/s.

A 28nm Bulk-CMOS 4-to-8GHz <2mW Cryogenic Pulse Modulator for Scalable Quantum Computing

Joseph Bardin, Evan Jeffrey, Erik Lucero, Trent Huang, Ofer Naaman, Rami Barends, Ted White, Marissa Giustina, Daniel Sank, Pedram Roushan, Kunal Arya, Ben Chiaro, Julian Kelly, Jimmy Chen, Brian Burkett, Yu Chen, Andrew Dunsworth, Austin Fowler, Brooks Foxen, Craig Michael Gidney, Rob Graff, Paul Klimov, Josh Mutus, Matthew McEwen, Anthony Megrant, Matthew Neeley, Charles Neill, Chris Quintana, Amit Vainsencher, Hartmut Neven, John Martinis · Proceedings of the 2019 International Solid State Circuits Conference, IEEE, pp. 456-458
Future quantum computing systems will require cryogenic integrated circuits to control and measure millions of qubits. In this paper, we report design and measurement of a prototype cryogenic CMOS integrated circuit that has been optimized for the control of transmon qubits. The circuit has been integrated into a quantum measurement setup and its performance has been validated through multiple quantum control experiments.

Quantum Supremacy using a Programmable Superconducting Processor

Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando Brandao, David Buell, Brian Burkett, Yu Chen, Jimmy Chen, Ben Chiaro, Roberto Collins, William Courtney, Andrew Dunsworth, Edward Farhi, Brooks Foxen, Austin Fowler, Craig Michael Gidney, Marissa Giustina, Rob Graff, Keith Guerin, Steve Habegger, Matthew Harrigan, Michael Hartmann, Alan Ho, Markus Rudolf Hoffmann, Trent Huang, Travis Humble, Sergei Isakov, Evan Jeffrey, Zhang Jiang, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Paul Klimov, Sergey Knysh, Alexander Korotkov, Fedor Kostritsa, Dave Landhuis, Mike Lindmark, Erik Lucero, Dmitry Lyakh, Salvatore Mandrà, Jarrod Ryan McClean, Matthew McEwen, Anthony Megrant, Xiao Mi, Kristel Michielsen, Masoud Mohseni, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Murphy Yuezhen Niu, Eric Ostby, Andre Petukhov, John Platt, Chris Quintana, Eleanor G. Rieffel, Pedram Roushan, Nicholas Rubin, Daniel Sank, Kevin J. Satzinger, Vadim Smelyanskiy, Kevin Jeffery Sung, Matt Trevithick, Amit Vainsencher, Benjamin Villalonga, Ted White, Z. Jamie Yao, Ping Yeh, Adam Zalcman, Hartmut Neven, John Martinis · Nature, vol. 574 (2019), 505–510
Download PDF View
The promise of quantum computers is that certain computational tasks might be executed exponentially faster on a quantum processor than on a classical processor. A fundamental challenge is to build a high-fidelity processor capable of running quantum algorithms in an exponentially large computational space. Here we report the use of a processor with programmable superconducting qubits to create quantum states on 53 qubits, corresponding to a computational state-space of dimension 2^53 (about 10^16). Measurements from repeated experiments sample the resulting probability distribution, which we verify using classical simulations. Our Sycamore processor takes about 200 seconds to sample one instance of a quantum circuit a million times-our benchmarks currently indicate that the equivalent task for a state-of-the-art classical supercomputer would take approximately 10,000 years. This dramatic increase in speed compared to all known classical algorithms is an experimental realization of quantum supremacy for this specific computational task, heralding a much-anticipated computing paradigm.

Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization

Dominic W. Berry, Craig Michael Gidney, Mario Motta, Jarrod Ryan McClean, Ryan Babbush · Quantum, vol. 3 (2019), pp. 208
Download PDF View
Recent work has dramatically reduced the gate complexity required to quantum simulate chemistry by using linear combinations of unitaries based methods to exploit structure in the plane wave basis Coulomb operator. Here, we show that one can achieve similar scaling even for arbitrary basis sets (which can be hundreds of times more compact than plane waves) by using qubitized quantum walks in a fashion that takes advantage of structure in the Coulomb operator, either by directly exploiting sparseness, or via a low rank tensor factorization. We provide circuits for several variants of our algorithm (which all improve over the scaling of prior methods) including one with O(N^{3/2} λ) T complexity, where N is number of orbitals and λ is the 1-norm of the chemistry Hamiltonian. We deploy our algorithms to simulate the FeMoco molecule (relevant to Nitrogen fixation) and obtain circuits requiring almost one thousand times less surface code spacetime volume than prior quantum algorithms for this system, despite us using a larger and more accurate active space.

Quantum Simulation of Chemistry with Sublinear Scaling in Basis Size

Ryan Babbush, Dominic W. Berry, Jarrod Ryan McClean, Hartmut Neven · NPJ Quantum Information, vol. 5 (2019)
Download PDF View
We present a quantum algorithm for simulating quantum chemistry with gate complexity Õ(η^{8/3}N^{1/3}),where η is the number of electrons and N is the number of plane wave orbitals. In comparison, the most efficient prior algorithms for simulating electronic structure using plane waves (which are at least as efficient as algorithms using any other basis) have complexity Õ(η^{2/3}N^{8/3}). We achieve our scaling in first quantization by performing simulation in the rotating frame of the kinetic operator using interaction picture techniques. Our algorithm is far more efficient than all prior approaches when N ≫ η, as is needed to suppress discretization error when representing molecules in the plane wave basis, or when simulating without the Born-Oppenheimer approximation.

Majorana Loop Stabilizer Codes for Error Mitigation in Fermionic Quantum Simulations

Zhang Jiang, Jarrod Ryan McClean, Ryan Babbush, Hartmut Neven · Physical Review Applied, vol. 12 (2019), pp. 064041
Download PDF View
Fermion-to-qubit mappings that preserve geometric locality are especially useful for simulating lattice fermion models (e.g., the Hubbard model) on a quantum computer. They avoid the overhead associated with geometric nonlocal parity terms in mappings such as the Jordan-Wigner transformation and the Bravyi-Kitaev transformation. As a result, they often provide quantum circuits with lower depth and gate complexity. In such encodings, fermionic states are encoded in the common +1 eigenspace of a set of stabilizers, akin to stabilizer quantum error-correcting codes. Here, we discuss several known geometric locality-preserving mappings and their abilities to correct and detect single-qubit errors. We introduce a geometric locality-preserving map, whose stabilizers correspond to products of Majorana operators on closed paths of the fermionic hopping graph. We show that our code, which we refer to as the Majorana loop stabilizer code (MLSC) can correct all single-qubit errors on a two-dimensional square lattice, while previous geometric locality-preserving codes can only detect single-qubit errors on the same lattice. Compared to existing codes, the MLSC maps the relevant fermionic operators to lower-weight qubit operators despite having higher code distance. Going beyond lattice models, we demonstrate that the MLSC is compatible with state-of-the-art algorithms for simulating quantum chemistry, and can offer those simulations the same error-correction properties without additional asymptotic overhead. These properties make the MLSC a promising candidate for error-mitigated quantum simulations of fermions on near-term devices

Diabatic gates for frequency-tunable superconducting qubits

Rami Barends, Chris Quintana, A.G. Petukhov, Yu Chen, Dvir Kafri, Kostyantyn Kechedzhi, Roberto Collins, Ofer Naaman, Sergio Boixo, Frank Carlton Arute, Kunal Arya, David A Buell, Brian Burkett, Jimmy Chen, Ben Chiaro, Andrew Dunsworth, Brooks Foxen, Austin Fowler, Craig Michael Gidney, Marissa Giustina, Rob Graff, Trent Huang, Evan Jeffrey, J. Kelly, Paul Victor Klimov, Fedor Kostritsa, Dave Landhuis, Erik Lucero, Matt McEwen, Anthony Megrant, Xiao Mi, Josh Mutus, Matthew Neeley, Charles Neill, Eric Ostby, Pedram Roushan, Daniel Sank, Amit Vainsencher, Ted White, Jamie Yao, Ping Yeh, Adam Jozef Zalcman, Hartmut Neven, Vadim Smelyanskiy, John Martinis · Physical Review Letters, vol. 123 (2019), pp. 210501
Download PDF View
We demonstrate diabatic two-qubit gates with Pauli error rates down to 4.3(2)*10^{-3} in as fast as 18 ns using frequency-tunable superconducting qubits. This is achieved by synchronizing the entangling parameters with minima in the leakage channel. The synchronization shows a landscape in gate parameter space that agrees with model predictions and facilitates robust tune-up. We test both iSWAP-like and CPHASE gates with cross-entropy benchmarking. The presented approach can be extended to multibody operations as well.

Low-Depth Quantum Simulation of Materials

Ryan Babbush, Nathan Wiebe, Jarrod McClean, James McClain, Hartmut Neven, Garnet Chan · Physical Review X, vol. 8 (2018), pp. 011044
Download PDF View
Quantum simulation of the electronic structure problem is one of the most researched applications of quantum computing. The majority of quantum algorithms for this problem encode the wavefunction using $N$ molecular orbitals, leading to Hamiltonians with ${\cal O}(N^4)$ second-quantized terms. To avoid this overhead, we introduce basis functions which diagonalize the periodized Coulomb operator, providing Hamiltonians for condensed phase systems with $N^2$ second-quantized terms. Using this representation we can implement single Trotter steps of the Hamiltonians with gate depth of ${\cal O}(N)$ on a planar lattice of qubits -- a quartic improvement over prior methods. Special properties of our basis allow us to apply Trotter based simulations with planar circuit depth in $\widetilde{\cal O}(N^{7/2} / \epsilon^{1/2})$ and Taylor series methods with circuit size $\widetilde{\cal O}(N^{11/3})$, where $\epsilon$ is target precision. Variational algorithms also require significantly fewer measurements to find the mean energy using our representation, ameliorating a primary challenge of that approach. We conclude with a proposal to simulate the uniform electron gas (jellium) using a linear depth variational ansatz realizable on near-term quantum devices with planar connectivity. From these results we identify simulation of low-density jellium as an ideal first target for demonstrating quantum supremacy in electronic structure.

Strategies for Quantum Computing Molecular Energies Using the Unitary Coupled Cluster Ansatz

Jhonathan Romero Fontalvo, Ryan Babbush, Jarrod McClean, Cornelius Hempel, Peter J. Love, Alán Aspuru-Guzik · Quantum Science and Technology, vol. 4 (2018), pp. 14008
Download PDF View
The variational quantum eigensolver (VQE) algorithm combines the ability of quantum computers to efficiently compute expectations values with a classical optimization routine in order to approximate ground state energies of quantum systems. In this paper, we study the application of VQE to the simulation of molecular energies using the unitary coupled cluster (UCC) ansatz. We introduce new strategies to reduce the circuit depth for the implementation of UCC and improve the optimization of the wavefunction based on efficient classical approximations of the cluster amplitudes. Additionally, we propose a method to compute the energy gradient within the VQE approach. We illustrate our methodology with numerical simulations for a system of four hydrogen atoms that exhibit strong correlation and show that the cost of the circuit depth and execution time of VQE using a UCC ansatz can be reduced without introducing significant loss of accuracy in the final wavefunctions and energies.

Barren Plateaus in Quantum Neural Network Training Landscapes

Jarrod McClean, Sergio Boixo, Vadim Smelyanskiy, Ryan Babbush, Hartmut Neven · Nature Communications, vol. 9 (2018), pp. 4812
Download PDF View
Many experimental proposals for noisy intermediate scale quantum devices involve training a parameterized quantum circuit with a classical optimization loop. Such hybrid quantum-classical algorithms are popular for applications in quantum simulation, optimization, and machine learning. Due to its simplicity and hardware efficiency, random circuits are often proposed as initial guesses for exploring the space of quantum states. We show that the exponential dimension of Hilbert space and the gradient estimation complexity make this choice unsuitable for hybrid quantum-classical algorithms run on more than a few qubits. Specifically, we show that for a wide class of reasonable parameterized quantum circuits, the probability that the gradient along any reasonable direction is non-zero to some fixed precision is exponentially small as a function of the number of qubits. We argue that this is related to the 2-design characteristic of random circuits, and that solutions to this problem must be studied.

Quantum Chemistry Calculations on a Trapped-Ion Quantum Simulator

Cornelius Hempel, Christine Maier, Jhonathan Romero, Jarrod McClean, Thomas Monz, Heng Shen, Petar Jurcevic, Ben Lanyon, Peter J. Love, Ryan Babbush, Alán Aspuru-Guzik, Rainer Blatt, Christian Roos · Physical Review X, vol. 8 (2018), pp. 031022
Download PDF View
Quantum-classical hybrid algorithms are emerging as promising candidates for near-term practical applications of quantum information processors in a wide variety of fields ranging from chemistry to physics and materials science. We report on the experimental implementation of such an algorithm to solve a quantum chemistry problem, using a digital quantum simulator based on trapped ions. Specifically, we implement the variational quantum eigensolver algorithm to calculate the molecular ground-state energies of two simple molecules and experimentally demonstrate and compare different encoding methods using up to four qubits. Furthermore, we discuss the impact of measurement noise as well as mitigation strategies and indicate the potential for adaptive implementations focused on reaching chemical accuracy, which may serve as a cross-platform benchmark for multiqubit quantum simulators.

Postponing the Orthogonality Catastrophe: Efficient State Preparation for Electronic Structure Simulations on Quantum Devices

Norman Tubman, Carlos Mejuto Zaera, Jeffrey Epstein, Diptarka Hait, Daniel Levine, William Huggins, Zhang Jiang, Jarrod Ryan McClean, Ryan Babbush, Martin Head-Gordon, K. Birgitta Whaley · arXiv:1809.05523 (2018)
Download PDF View
Despite significant work on resource estimation for quantum simulation of electronic systems, the challenge of preparing states with sufficient ground state support has so far been largely neglected. In this work we investigate this issue in several systems of interest, including organic molecules, transition metal complexes, the uniform electron gas, Hubbard models, and quantum impurity models arising from embedding formalisms such as dynamical mean-field theory. Our approach uses a state-of-the-art classical technique for high-fidelity ground state approximation. We find that easy-to-prepare single Slater determinants such as the Hartree-Fock state often have surprisingly robust support on the ground state for many applications of interest. For the most difficult systems, single-determinant reference states may be insufficient, but low-complexity reference states may suffice. For this we introduce a method for preparation of multi-determinant states on quantum computers.

A flexible high-performance simulator for the verification and benchmarking of quantum circuits implemented on real hardware

Benjamin Villalonga, Sergio Boixo, Bron Nelson, Christopher Henze, Eleanor Rieffel, Rupak Biswas, Salvatore Mandra · arXiv:1811.09599 (2018)
Here we present a flexible tensor network based simulator for quantum circuits on different topologies, including the Google Bristlecone QPU. Our simulator can compute both exact amplitudes, a task essential for the verification of the quantum hardware, as well as low-fidelity amplitudes to mimic Noisy Intermediate-Scale Quantum (NISQ) devices. While our simulator can be used to compute amplitudes of arbitrary quantum circuits, we focus on random quantum circuits (RQCs) [Boixo et al., Nature Physics 14] in the range of sizes expected for supremacy experiments. Our simulator enables the simulation of sampling on quantum circuits that were out of reach for previous approaches. For instance, our simulator is able to output single amplitudes with depth 1+32+1 for the full Google Bristlecone QPU in less than (f · 4200) hours on a single core, where 0 < f ≤ 1 is the target fidelity, on 2 × 20-core Intel Xeon Gold 6148 processors (Skylake). We also estimate that computing 106 amplitudes (with fidelity 0.50%) needed to sample from the full Google Bristlecone QPU with depth (1+32+1) would require about 3.5 days using the NASA Pleiades and Electra supercomputers combined. In addition, we discuss the hardness of the classical simulation of RQCs, as well as give evidence for the higher complexity in the simulation of Google’s Bristlecone topology as compared to other two-dimensional grids with the same number of qubits. Our analysis is supported by extensive simulations on NASA HPC clusters Pleiades (27th in the November 2018 TOP500 list) and Electra (33rd in the November 2018 TOP500 list). For the most computationally demanding simulation we had, namely the simulation of a 60-qubit sub-lattice of Bristlecone, the two HPC clusters combined reached a peak of 20 PFLOPS (single precision), that is 64% of their maximum achievable performance. To date, this numerical computation is the largest in terms of sustained PFLOPS and number of nodes utilized ever run on NASA HPC clusters.

Application of Fermionic Marginal Constraints to Hybrid Quantum Algorithms

Nicholas Rubin, Jarrod McClean, Ryan Babbush · New Journal of Physics, vol. 20 (2018), pp. 053020
Download PDF View
Many quantum algorithms, including recently proposed hybrid classical/quantum algorithms, make use of restricted tomography of the quantum state that measures the reduced density matrices, or marginals, of the full state. The most straightforward approach to this algorithmic step estimates each component of the marginal independently without making use of the algebraic and geometric structure of the marginals. Within the field of quantum chemistry, this structure is termed the fermionic $n$-representability conditions, and is supported by a vast amount of literature on both theoretical and practical results related to their approximations. In this work, we introduce these conditions in the language of quantum computation, and utilize them to develop several techniques to accelerate and improve practical applications for quantum chemistry on quantum computers. As a general result, we demonstrate how these marginals concentrate to diagonal quantities when measured on random quantum states. We also show that one can use fermionic $n$-representability conditions to reduce the total number of measurements required by more than an order of magnitude for medium sized systems in chemistry. As a practical demonstration, we simulate an efficient restoration of the physicality of energy curves for the dilation of a four qubit diatomic hydrogen system in the presence of three distinct one qubit error channels, providing evidence these techniques are useful for pre-fault tolerant quantum chemistry experiments.

Fluctuations of Energy-Relaxation Times in Superconducting Qubits

Paul Klimov, Julian Kelly, Jimmy Chen, Matthew Neeley, Anthony Megrant, Brian Burkett, Rami Barends, Kunal Arya, Ben Chiaro, Yu Chen, Andrew Dunsworth, Austin Fowler, Brooks Foxen, Craig Michael Gidney, Marissa Giustina, Rob Graff, Trent Huang, Evan Jeffrey, Erik Lucero, Josh Mutus, Ofer Naaman, Charles Neill, Chris Quintana, Pedram Roushan, Daniel Sank, Amit Vainsencher, Jim Wenner, Ted White, Sergio Boixo, Ryan Babbush, Vadim Smelyanskiy, Hartmut Neven, John Martinis · Physical Review Letters, vol. 121 (2018), pp. 090502
Download PDF View
Superconducting qubits are an attractive platform for quantum computing since they have demonstrated high-fidelity quantum gates and extensibility to modest system sizes. Nonetheless, an outstanding challenge is stabilizing their energy-relaxation times, which can fluctuate unpredictably in frequency and time. Here, we use qubits as spectral and temporal probes of individual two-level-system defects to provide direct evidence that they are responsible for the largest fluctuations. This research lays the foundation for stabilizing qubit performance through calibration, design and fabrication.

Quantum Simulation of Electronic Structure with Linear Depth and Connectivity

Ian D. Kivlichan, Jarrod McClean, Nathan Wiebe, Craig Michael Gidney, Alán Aspuru-Guzik, Garnet Kin-Lic Chan, Ryan Babbush · Physical Review Letters, vol. 120 (2018), pp. 110501
Download PDF View
As physical implementations of quantum architectures emerge, it is increasingly important to consider the cost of algorithms for practical connectivities between qubits. We show that by using an arrangement of gates that we term the fermionic swap network, we can simulate a Trotter step of the electronic structure Hamiltonian in exactly N depth and with N^2/2 two-qubit entangling gates, and prepare arbitrary Slater determinants in at most N/2 depth, all assuming only a minimal, linearly connected architecture. We conjecture that no explicit Trotter step of the electronic structure Hamiltonian is possible with fewer entangling gates, even with arbitrary connectivities. These results represent significant practical improvements on the cost of all current proposed algorithms for both variational and phase estimation based simulation of quantum chemistry.

Physical qubit calibration on a directed acyclic graph

Hartmut Neven, John Martinis, Julian Kelly, Matthew Neeley, Peter James Joyce O'Malley · arXiv, possibly npj Quantum Information (2018)
High-fidelity control of qubits requires precisely tuned control parameters. Typically, these param- eters are found through a series of bootstrapped calibration experiments which successively acquire more accurate information about a physical qubit. However, optimal parameters are typically dif- ferent between devices and can also drift in time, which begets the need for an efficient calibration strategy. Here, we introduce a framework to understand the relationship between calibrations as a directed graph. With this approach, calibration is reduced to a graph traversal problem that is automatable and extensible.

Quantum Supremacy Is Both Closer and Farther than It Appears

Igor Markov, Aneeqa Fatima, Sergei Isakov, Sergio Boixo · arxiv (not yet submitted) (2018)
Download PDF View
As quantum computers improve in the number of qubits and fidelity, the question of when they surpass state-of-the-art classical computation for a well-defined computational task is attracting much attention. The leading candidate task for this quantum computational supremacy milestone entails sampling from the output distribution defined by a random quantum circuit. We perform this task on conventional computers for larger circuits than in previous results, by trading circuit fidelity for computational resources to match the fidelity of a given quantum computer. By using publicly available Google Cloud Computing, we can price such simulations and enable comparisons by total cost across multiple hardware types. We simulate approximate sampling from the output of a circuit with 7 x 8 qubits and depth 1+40+1 by producing one million bitstring probabilities with fidelity 0.5%, at an estimated cost of $35184. The simulation costs scale linearly with fidelity, and using this scaling we estimate that extending circuit depth to 1+48+1 increases costs to one million dollars. Yet, for a quantum computer, approximate sampling would take seconds. We pay particular attention to validating simulation results. Finally, we explain why recently refined benchmarks substantially increase computation cost of leading simulators, halving the circuit depth that can be simulated within the same time.

Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity

Ryan Babbush, Craig Michael Gidney, Dominic W. Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler, Hartmut Neven · Physical Review X, vol. 8 (2018), pp. 041015
Download PDF View
We construct quantum circuits which exactly encode the spectra of correlated electron models up to errors from rotation synthesis. By invoking these circuits as oracles within the recently introduced "qubitization" framework, one can use quantum phase estimation to sample states in the Hamiltonian eigenbasis with optimal query complexity O(lambda / epsilon) where lambda is an absolute sum of Hamiltonian coefficients and epsilon is target precision. For both the Hubbard model and electronic structure Hamiltonian in a second quantized basis diagonalizing the Coulomb operator, our circuits have T gate complexity O(N + \log (1/epsilon)) where N is number of orbitals in the basis. Compared to prior approaches, our algorithms are asymptotically more efficient in gate complexity and require fewer T gates near the classically intractable regime. Compiling to surface code fault-tolerant gates and assuming per gate error rates of one part in a thousand reveals that one can error-correct phase estimation on interesting instances of these problems beyond the current capabilities of classical methods using only a few times more qubits than would be required for magic state distillation.

Characterizing Quantum Supremacy in Near-Term Devices

Sergio Boixo, Sergei Isakov, Vadim Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J. Bremner, John Martinis, Hartmut Neven · Nature Physics, vol. 14 (2018), 595–600
Download PDF View
A critical question for quantum computing in the near future is whether quantum devices without error correction can perform a well-defined computational task beyond the capabilities of supercomputers. Such a demonstration of what is referred to as quantum supremacy requires a reliable evaluation of the resources required to solve tasks with classical approaches. Here, we propose the task of sampling from the output distribution of random quantum circuits as a demonstration of quantum supremacy. We extend previous results in computational complexity to argue that this sampling task must take exponential time in a classical computer. We introduce cross-entropy benchmarking to obtain the experimental fidelity of complex multiqubit dynamics. This can be estimated and extrapolated to give a success metric for a quantum supremacy demonstration. We study the computational cost of relevant classical algorithms and conclude that quantum supremacy can be achieved with circuits in a two-dimensional lattice of 7 × 7 qubits and around 40 clock cycles. This requires an error rate of around 0.5% for two-qubit gates (0.05% for one-qubit gates), and it would demonstrate the basic building blocks for a fault-tolerant quantum computer

Quantum Approach to the Unique Sink Orientation Problem

Dave Bacon · Physical Review A, vol. 96 (2017), pp. 012323
Download PDF View
We consider quantum algorithms for the unique sink orientation problem on cubes. This problem is widely considered to be of intermediate computational complexity. This is because there is no known polynomial algorithm (classical or quantum) for the problem and yet it arises as part of a series of problems for which it being intractable would imply complexity-theoretic collapses. We give a reduction which proves that if one can efficiently evaluate the kth power of the unique sink orientation outmap, then there exists a polynomial time quantum algorithm for the unique sink orientation problem on cubes.

Commercialize Quantum Technologies in Five Years

Masoud Mohseni, Peter Read, Hartmut Neven, Sergio Boixo, Vasil Denchev, Ryan Babbush, Austin Fowler, Vadim Smelyanskiy, John Martinis · Nature, vol. 543 (2017), 171–174
Download PDF View
Masoud Mohseni, Peter Read, Hartmut Neven and colleagues at Google's Quantum AI Laboratory set out investment opportunities on the road to the ultimate quantum machines.

Improved Techniques for Preparing Eigenstates of Fermionic Hamiltonians

Dominic W. Berry, Mária Kieferová, Artur Scherer, Yuval Sanders, Guang Hao Low, Nathan Wiebe, Craig Gidney, Ryan Babbush · npj Quantum Information, vol. 4 (2017), pp. 22
Download PDF View
Modeling low energy eigenstates of fermionic systems can provide insight into chemical reactions and material properties and is one of the most anticipated applications of quantum computing. We present three techniques for reducing the cost of preparing fermionic Hamiltonian eigenstates using phase estimation. First, we report a polylogarithmic-depth quantum algorithm for antisymmetrizing the initial states required for simulation of fermions in first quantization. This is an exponential improvement over the previous state-of-the-art. Next, we show how to reduce the overhead due to repeated state preparation in phase estimation when the goal is to prepare the ground state to high precision and one has knowledge of an upper bound on the ground state energy that is less than the excited state energy (often the case in quantum chemistry). Finally, we explain how one can perform the time evolution necessary for the phase estimation based preparation of Hamiltonian eigenstates with exactly zero error by using the recently introduced qubitization procedure.

OpenFermon: The Electronic Structure Package for Quantum Computers

Jarrod McClean, Ian D. Kivlichan, Kevin Sung, Damian Steiger, Yudong Cao, Chengyu Dai, E. Schuyler Fried, Craig Michael Gidney, Brendan Gimby, Thomas Häner, Tarini Hardikar, Vojtĕch Havlíček, Cupjin Huang, Zhang Jiang, Matthew Neeley, Thomas O'Brien, Isil Ozfidan, Jhonathan Romero, Nicholas Rubin, Nicolas Sawaya, Kanav Setia, Sukin Sim, Mark Steudtner, Wei Sun, Fang Zhang, Ryan Babbush · Quantum Science and Technology, vol. 5 (2017), pp. 034014
Download PDF View
Quantum simulation of chemistry and materials is predicted to be a key application for both near-term and fault-tolerant quantum devices. However, at present, developing and studying algorithms for these problems can be difficult due to the prohibitive amount of domain knowledge required in both the area of chemistry and quantum algorithms. To help bridge this gap and open the field to more researchers, we have developed the OpenFermion software package ( OpenFermion is an open-source software library written largely in Python under an Apache 2.0 license, aimed at enabling the simulation of fermionic models and quantum chemistry problems on quantum hardware. Beginning with an interface to common electronic structure packages, it simplifies the translation between a molecular specification and a quantum circuit for solving or studying the electronic structure problem on a quantum computer, minimizing the amount of domain expertise required to enter the field. Moreover, the package is designed to be extensible and robust, maintaining high software standards in documentation and testing. This release paper outlines the key motivations for design choices in OpenFermion and discusses some of the basic OpenFermion functionality available for the initial release of the package, which we believe will aid the community in the development of better quantum algorithms and tools for this exciting area.

Exponentially More Precise Quantum Simulation of Fermions in the Configuration Interaction Representation

Ryan Babbush, Dominic Berry, Yuval Sanders, Ian Kivlichan, Artur Scherer, Annie Wei, Peter Love, Alán Aspuru-Guzik · Quantum Science and Technology, vol. 3 (2017), pp. 015006
Download PDF View
We present a quantum algorithm for the simulation of molecular systems that is asymptotically more efficient than all previous algorithms in the literature in terms of the main problem parameters. As in previous work [Babbush et al., New Journal of Physics 18, 033032 (2016)], we employ a recently developed technique for simulating Hamiltonian evolution, using a truncated Taylor series to obtain logarithmic scaling with the inverse of the desired precision. The algorithm of this paper involves simulation under an oracle for the sparse, first-quantized representation of the molecular Hamiltonian known as the configuration interaction (CI) matrix. We construct and query the CI matrix oracle to allow for on-the-fly computation of molecular integrals in a way that is exponentially more efficient than classical numerical methods. Whereas second-quantized representations of the wavefunction require O(N) qubits, where N is the number of single-particle spin-orbitals, the CI matrix representation requires O(η) qubits where η ≪ N is the number of electrons in the molecule of interest. We show that the gate count of our algorithm scales at most as O(η^2 N^3 t).

Tunable inductive coupling of superconducting qubits in the strongly nonlinear regime

Dvir Kafri, Chris Quintana, Yu Chen, Alireza Shabani, John Martinis, Hartmut Neven · Phys. Rev. A, vol. 95 (2017), pp. 052333
Download PDF View
For a variety of superconducting qubits, tunable interactions are achieved through mutual inductive coupling to a coupler circuit containing a nonlinear Josephson element. In this paper, we derive the general interaction mediated by such a circuit under the Born-Oppenheimer approximation. This interaction naturally decomposes into a classical part, with origin in the classical circuit equations, and a quantum part, associated with the coupler's zero-point energy. Our result is nonperturbative in the qubit-coupler coupling strengths and in the coupler nonlinearity. This can lead to significant departures from previous, linear theories for the interqubit coupling, including nonstoquastic and many-body interactions. Our analysis provides explicit and efficiently computable series for any term in the interaction Hamiltonian and can be applied to any superconducting qubit type. We conclude with a numerical investigation of our theory using a case study of two coupled flux qubits, and in particular study the regime of validity of the Born-Oppenheimer approximation.

Chiral Ground-State Currents of Interacting Photons in a Synthetic Magnetic Field

Pedram Roushan, Charles Neill, Anthony Megrant, Yu Chen, Ryan Babbush, Rami Barends, Brooks Campbell, Zijun Chen, Ben Chiaro, Andrew Dunsworth, Austin Fowler, Evan Jeffrey, Julian Kelly, Erik Lucero, Josh Mutus, Peter O'Malley, Matthew Neeley, Chris Quintana, Daniel Sank, Amit Vainsencher, Jim Wenner, Ted White, Eliot Kapit, Hartmut Neven, John Martinis · Nature Physics, vol. 13 (2017), pp. 146-151
Download PDF View
The intriguing many-body phases of quantum matter arise from the interplay of particle interactions, spatial symmetries, and external fields. Generating these phases in an engineered system could provide deeper insight into their nature. Using superconducting qubits, we simultaneously realize synthetic magnetic fields and strong particle interactions, which are among the essential elements for studying quantum magnetism and fractional quantum Hall phenomena. The artificial magnetic fields are synthesized by sinusoidally modulating the qubit couplings. In a closed loop formed by the three qubits, we observe the directional circulation of photons, a signature of broken time-reversal symmetry. We demonstrate strong interactions through the creation of photon vacancies, or "holes", which circulate in the opposite direction. The combination of these key elements results in chiral ground-state currents. Our work introduces an experimental platform for engineering quantum phases of strongly interacting photons.

Bounding the Costs of Quantum Simulation of Many-Body Physics in Real Space

Ian D. Kivlichan, Nathan Wiebe, Ryan Babbush, Alán Aspuru-Guzik · Journal of Physics A: Mathematical and Theoretical, vol. 50 (2017), pp. 305301
Download PDF View
We present a quantum algorithm for simulating the dynamics of a first-quantized Hamiltonian in real space based on the truncated Taylor series algorithm. We avoid the possibility of singularities by applying various cutoffs to the system and using a high-order finite difference approximation to the kinetic energy operator. We find that our algorithm can simulate η interacting particles using a number of calculations of the pairwise interactions that scales, for a fixed spatial grid spacing, as O(η^2), versus the O(η^5) time required by previous methods (assuming the number of orbitals is proportional to η), and scales super-polynomially better with the error tolerance than algorithms based on the Lie-Trotter-Suzuki product formula. Finally, we analyze discretization errors that arise from the spatial grid and show that under some circumstances these errors can remove the exponential speedups typically afforded by quantum simulation.

Observation of classical-quantum crossover of 1/f flux noise and its paramagnetic temperature dependence

Chris Quintana, Yu Chen, Daniel Sank, Andre Petukhov, Ted White, Dvir Kafri, Ben Chiaro, Anthony Megrant, Rami Barends, Brooks Campbell, Zijun Chen, Andrew Dunsworth, Austin Fowler, Rob Graff, Evan Jeffrey, Julian Kelly, Erik Lucero, Josh Mutus, Matthew Neeley, Charles Neill, Peter O'Malley, Pedram Roushan, Alireza Shabani, Vadim Smelyanskiy, Amit Vainsencher, Jim Wenner, Hartmut Neven, John Martinis · Phys. Rev. Lett., vol. 118 (2017), pp. 057702
Download PDF View
By analyzing the dissipative dynamics of a tunable gap flux qubit, we extract both sides of its two-sided environmental flux noise spectral density over a range of frequencies around 2kT/h ≈ 1GHz, allowing for the observation of a classical-quantum crossover. Below the crossover point, the symmetric noise component follows a 1/f power law that matches the magnitude of the 1/f noise near 1 Hz. The antisymmetric component displays a 1/T dependence below 100 mK, providing dynamical evidence for a paramagnetic environment. Extrapolating the two-sided spectrum predicts the linewidth and reorganization energy of incoherent resonant tunneling between flux qubit wells.

What is the Computational Value of Finite Range Tunneling?

Vasil Denchev, Sergio Boixo, Sergei Isakov, Nan Ding, Ryan Babbush, Vadim Smelyanskiy, John Martinis, Hartmut Neven · Physical Review X, vol. 6 (2016), pp. 031015
Download PDF View
Quantum annealing (QA) has been proposed as a quantum enhanced optimization heuristic exploiting tunneling. Here, we demonstrate how finite-range tunneling can provide considerable computational advantage. For a crafted problem designed to have tall and narrow energy barriers separating local minima, the D-Wave 2X quantum annealer achieves significant runtime advantages relative to simulated annealing (SA). For instances with 945 variables, this results in a time-to-99%-success-probability that is ~1e8 times faster than SA running on a single processor core. We also compare physical QA with the quantum Monte Carlo algorithm, an algorithm that emulates quantum tunneling on classical processors. We observe a substantial constant overhead against physical QA: D-Wave 2X again runs up to ~ 1e8 times faster than an optimized implementation of the quantum Monte Carlo algorithm on a single core. We note that there exist heuristic classical algorithms that can solve most instances of Chimera structured problems in a time scale comparable to the D-Wave 2X. However, it is well known that such solvers will become ineffective for sufficiently dense connectivity graphs. To investigate whether finite-range tunneling will also confer an advantage for problems of practical interest, we conduct numerical studies on binary optimization problems that cannot yet be represented on quantum hardware. For random instances of the number partitioning problem, we find numerically that algorithms designed to simulate QA scale better than SA. We discuss the implications of these findings for the design of next-generation quantum annealers.

Computational multiqubit tunnelling in programmable quantum annealers

Sergio Boixo, Vadim N Smelyanskiy, Alireza Shabani, Sergei V Isakov, Mark Dykman, Vasil S Denchev, Mohammad H Amin, Anatoly Yu Smirnov, Masoud Mohseni, Hartmut Neven · Nature Communications, vol. 7 (2016)
Download PDF View
Quantum tunnelling is a phenomenon in which a quantum state traverses energy barriers higher than the energy of the state itself. Quantum tunnelling has been hypothesized as an advantageous physical resource for optimization in quantum annealing. However, computational multiqubit tunnelling has not yet been observed, and a theory of co-tunnelling under high- and low-frequency noises is lacking. Here we show that 8-qubit tunnelling plays a computational role in a currently available programmable quantum annealer. We devise a probe for tunnelling, a computational primitive where classical paths are trapped in a false minimum. In support of the design of quantum annealers we develop a nonperturbative theory of open quantum dynamics under realistic noise characteristics. This theory accurately predicts the rate of many-body dissipative quantum tunnelling subject to the polaron effect. Furthermore, we experimentally demonstrate that quantum tunnelling outperforms thermal hopping along classical paths for problems with up to 200 qubits containing the computational primitive.

The Theory of Variational Hybrid Quantum-Classical Algorithms

Jarrod McClean, Jonathan Romero, Ryan Babbush, Alán Aspuru-Guzik · New Journal of Physics, vol. 18 (2016), pp. 023023
Download PDF View
Many quantum algorithms have daunting resource requirements when compared to what is available today. To address this discrepancy, a quantum-classical hybrid optimization scheme known as "the quantum variational eigensolver" was developed with the philosophy that even minimal quantum resources could be made useful when used in conjunction with classical routines. In this work we extend the general theory of this algorithm and suggest algorithmic improvements for practical implementations. Specifically, we develop a variational adiabatic ansatz and explore unitary coupled cluster where we establish a connection from second order unitary coupled cluster to universal gate sets through relaxation of exponential splitting. We introduce the concept of quantum variational error suppression that allows some errors to be suppressed naturally in this algorithm on a pre-threshold quantum device. Additionally, we analyze truncation and correlated sampling in Hamiltonian averaging as ways to reduce the cost of this procedure. Finally, we show how the use of modern derivative free optimization techniques can offer dramatic computational savings of up to three orders of magnitude over previously used optimization techniques.

Scalable Quantum Simulation of Molecular Energies

Peter O'Malley, Ryan Babbush, Ian Kivlichan, Jonathan Romero, Jarrod McClean, Rami Barends, Julian Kelly, Pedram Roushan, Andrew Tranter, Nan Ding, Brooks Campbell, Yu Chen, Zijun Chen, Ben Chiaro, Andrew Dunsworth, Austin Fowler, Evan Jeffrey, Anthony Megrant, Josh Mutus, Charles Neil, Chris Quintana, Daniel Sank, Ted White, Jim Wenner, Amit Vainsencher, Peter Coveney, Peter Love, Hartmut Neven, Alán Aspuru-Guzik, John Martinis · Physical Review X, vol. 6 (2016), pp. 031007
Download PDF View
We report the first electronic structure calculation performed on a quantum computer without exponentially costly precompilation. We use a programmable array of superconducting qubits to compute the energy surface of molecular hydrogen using two distinct quantum algorithms. First, we experimentally execute the unitary coupled cluster method using the variational quantum eigensolver. Our efficient implementation predicts the correct dissociation energy to within chemical accuracy of the numerically exact result. Second, we experimentally demonstrate the canonical quantum algorithm for chemistry, which consists of Trotterization and quantum phase estimation. We compare the experimental performance of these approaches to show clear evidence that the variational quantum eigensolver is robust to certain errors. This error tolerance inspires hope that variational quantum simulations of classically intractable molecules may be viable in the near future.

Digitized Adiabatic Quantum Computing with a Superconducting Circuit

Rami Barends, Alireza Shabani, Lucas Lamata, Julian Kelly, Antonio Mezzacapo, Urtzi Las Heras, Ryan Babbush, Austin Fowler, Brooks Campbell, Yu Chen, Zijun Chen, Ben Chiaro, Andrew Dunsworth, Evan Jeffrey, Erik Lucero, Anthony Megrant, Josh Mutus, Matthew Neeley, Charles Neill, Peter O'Malley, Chris Quintana, Enrique Solano, Ted White, Jim Wenner, Amit Vainsencher, Daniel Sank, Pedram Roushan, Hartmut Neven, John Martinis · Nature, vol. 534 (2016), pp. 222-226
Download PDF View
A major challenge in quantum computing is to solve general problems with limited physical hardware. Here, we implement digitized adiabatic quantum computing, combining the generality of the adiabatic algorithm with the universality of the digital approach, using a superconducting circuit with nine qubits. We probe the adiabatic evolutions, and quantify the success of the algorithm for random spin problems. We find that the system can approximate the solutions to both frustrated Ising problems and problems with more complex interactions, with a performance that is comparable. The presented approach is compatible with small-scale systems as well as future error-corrected quantum computers.

Scalable in-situ qubit calibration during repetitive error detection

Austin Fowler, John Martinis, Julian Kelly, Rami Barends · PHYSICAL REVIEW A, vol. 94 (2016), pp. 032321
We present a method to optimize physical qubit parameters while error detection is running. We demonstrate how gate optimization can be parallelized in a large-scale qubit array. Additionally we show that the presented method can be used to simultaneously compensate for independent or correlated qubit parameter drifts. Our method is O(1) scalable to systems of arbitrary size, providing a path towards controlling the large numbers of qubits needed for a fault-tolerant quantum computer.

Exponentially More Precise Quantum Simulation of Fermions in Second Quantization

Ryan Babbush, Dominic Berry, Ian Kivlichan, Annie Wei, Peter Love, Alán Aspuru-Guzik · New Journal of Physics, vol. 18 (2016), pp. 033032
Download PDF View
We introduce novel algorithms for the quantum simulation of fermionic systems which are dramatically more efficient than those based on the Lie–Trotter–Suzuki decomposition. We present the first application of a general technique for simulating Hamiltonian evolution using a truncated Taylor series to obtain logarithmic scaling with the inverse of the desired precision. The key difficulty in applying algorithms for general sparse Hamiltonian simulation to fermionic simulation is that a query, corresponding to computation of an entry of the Hamiltonian, is costly to compute. This means that the gate complexity would be much higher than quantified by the query complexity. We solve this problem with a novel quantum algorithm for on-the-fly computation of integrals that is exponentially faster than classical sampling. While the approaches presented here are readily applicable to a wide class of fermionic models, we focus on quantum chemistry simulation in second quantization, perhaps the most studied application of Hamiltonian simulation. Our central result is an algorithm for simulating an N spin–orbital system that requires O(N^5 t) gates. This approach is exponentially faster in the inverse precision and at least cubically faster in N than all previous approaches to chemistry simulation in the literature.

Fast quantum methods for optimization

S. Boixo, G. Ortiz, R. Somma · The European Physical Journal Special Topics, vol. 224 (2015), pp. 35
Download PDF View
Discrete combinatorial optimization consists in finding the optimal configuration that minimizes a given discrete objective function. An interpretation of such a function as the energy of a classical system allows us to reduce the optimization problem into the preparation of a low-temperature thermal state of the system. Motivated by the quantum annealing method, we present three strategies to prepare the low-temperature state that exploit quantum mechanics in remarkable ways. We focus on implementations without uncontrolled errors induced by the environment. This allows us to rigorously prove a quantum advantage. The first strategy uses a classical-to-quantum mapping, where the equilibrium properties of a classical system in d spatial dimensions can be determined from the ground state properties of a quantum system also in d spatial dimensions. We show how such a ground state can be prepared by means of quantum annealing, including quantum adiabatic evolutions. This mapping also allows us to unveil some fundamental relations between simulated and quantum annealing. The second strategy builds upon the first one and introduces a technique called spectral gap amplification to reduce the time required to prepare the same quantum state adiabatically. If implemented on a quantum device that exploits quantum coherence, this strategy leads to a quadratic improvement in complexity over the well-known bound of the classical simulated annealing method. The third strategy is not purely adiabatic; instead, it exploits diabatic processes between the low-energy states of the corresponding quantum system. For some problems it results in an exponential speedup (in the oracle model) over the best classical algorithms.

Quantum Simulation of Helium Hydride Cation in a Solid-State Spin Register

Ya Wang, Florian Dolde, Jacob Biamonte, Ryan Babbush, Ville Bergholm, Sen Yang, Ingmar Jakobi, Philipp Neumann, Alán Aspuru-Guzik, James Whitfield, Jörg Wrachtrup · ACS Nano, vol. 9 (2015), 7769–7774
Download PDF View
Ab initio computation of molecular properties is one of the most promising applications of quantum computing. While this problem is widely believed to be intractable for classical computers, efficient quantum algorithms exist which have the potential to vastly accelerate research throughput in fields ranging from material science to drug discovery. Using a solid-state quantum register realized in a nitrogen-vacancy (NV) defect in diamond, we compute the bond dissociation curve of the minimal basis helium hydride cation, HeH+. Moreover, we report an energy uncertainty (given our model basis) of the order of 1e–14 hartree, which is 10 orders of magnitude below the desired chemical precision. As NV centers in diamond provide a robust and straightforward platform for quantum information processing, our work provides an important step toward a fully scalable solid-state implementation of a quantum chemistry simulator.

Quantum Algorithms for Discrete Optimization

Sergio Boixo, Rolando Somma · Quantum Optimization: Fields Institute Communications, Springer (2015) (to appear)

Computational complexity of time-dependent density functional theory

J D Whitfield, M-H Yung, D G Templ, S Boixo, A Aspuru-Guzik · New Journal of Physics, vol. 16 (2014), pp. 083035
Download PDF View
Time-dependent density functional theory (TDDFT) is rapidly emerging as a premier method for solving dynamical many-body problems in physics and chemistry. The mathematical foundations of TDDFT are established through the formal existence of a fictitious non-interacting system (known as the Kohn–Sham system), which can reproduce the one-electron reduced probability density of the actual system. We build upon these works and show that on the interior of the domain of existence, the Kohn–Sham system can be efficiently obtained given the time-dependent density. We introduce a V-representability parameter which diverges at the boundary of the existence domain and serves to quantify the numerical difficulty of constructing the Kohn–Sham potential. For bounded values of V-representability, we present a polynomial time quantum algorithm to generate the time-dependent Kohn–Sham potential with controllable error bounds.

Defining and detecting quantum speedup

Troels F. Rønnow, Zhihui Wang, Joshua Job, Sergio Boixo, Sergei V. Isakov, David Wecker, John M. Martinis, Daniel A. Lidar, Matthias Troyer · Science, vol. 345 (2014), pp. 420-424
Download PDF View
The development of small-scale quantum devices raises the question of how to fairly assess and detect quantum speedup. Here, we show how to define and measure quantum speedup and how to avoid pitfalls that might mask or fake such a speedup. We illustrate our discussion with data from tests run on a D-Wave Two device with up to 503 qubits. By using random spin glass instances as a benchmark, we found no evidence of quantum speedup when the entire data set is considered and obtained inconclusive results when comparing subsets of instances on an instance-by-instance basis. Our results do not rule out the possibility of speedup for other classes of problems and illustrate the subtle nature of the quantum speedup question. How to benchmark a quantum computer: Quantum machines offer the possibility of performing certain computations much faster than their classical counterparts. However, how to define and measure quantum speedup is a topic of debate. Rønnow et al. describe methods for fairly evaluating the difference in computational power between classical and quantum processors. They define various types of quantum speedup and consider quantum processors that are designed to solve a specific class of problems. Science, this issue p. 420

Construction of Non-Convex Polynomial Loss Functions for Training a Binary Classifier with Quantum Annealing

Ryan Babbush, Vasil Denchev, Nan Ding, Sergei Isakov, Hartmut Neven · arXiv:1406.4203 (2014)
Download PDF View
Quantum annealing is a heuristic quantum algorithm which exploits quantum resources to minimize an objective function embedded as the energy levels of a programmable physical system. To take advantage of a potential quantum advantage, one needs to be able to map the problem of interest to the native hardware with reasonably low overhead. Because experimental considerations constrain our objective function to take the form of a low degree PUBO (polynomial unconstrained binary optimization), we employ non-convex loss functions which are polynomial functions of the margin. We show that these loss functions are robust to label noise and provide a clear advantage over convex methods. These loss functions may also be useful for classical approaches as they compile to regularized risk expressions which can be evaluated in constant time with respect to the number of training examples.

Hearing the Shape of the Ising Model with a Programmable Superconducting-Flux Annealer

Walter Vinci, Klas Markström, Sergio Boixo, Aidan Roy, Federico M. Spedalieri, Paul A. Warburton, Simone Severini · Scientific Reports, vol. 4 (2014)
Download PDF View
Two objects can be distinguished if they have different measurable properties. Thus, distinguishability depends on the Physics of the objects. In considering graphs, we revisit the Ising model as a framework to define physically meaningful spectral invariants. In this context, we introduce a family of refinements of the classical spectrum and consider the quantum partition function. We demonstrate that the energy spectrum of the quantum Ising Hamiltonian is a stronger invariant than the classical one without refinements. For the purpose of implementing the related physical systems, we perform experiments on a programmable annealer with superconducting flux technology. Departing from the paradigm of adiabatic computation, we take advantage of a noisy evolution of the device to generate statistics of low energy states. The graphs considered in the experiments have the same classical partition functions, but different quantum spectra. The data obtained from the annealer distinguish non-isomorphic graphs via information contained in the classical refinements of the functions but not via the differences in the quantum spectra.

Quantum Algorithms for Simulated Annealing

Sergio Boixo, Rolando Somma · Encyclopedia of Algorithms, Springer (2014) (to appear)

Entanglement in a Quantum Annealing Processor

T. Lanting, A. J. Przybysz, A. Yu. Smirnov, F. M. Spedalieri, M. H. Amin, A. J. Berkley, R. Harris, F. Altomare, S. Boixo, P. Bunyk, N. Dickson, C. Enderud, J. P. Hilton, E. Hoskinson, M. W. Johnson, E. Ladizinsky, N. Ladizinsky, R. Neufeld, T. Oh, I. Perminov, C. Rich, M. C. Thom, E. Tolkacheva, S. Uchaikin, A. B. Wilson, G. Rose · Physical Review X, vol. 4 (2014), pp. 021041
Download PDF View
Entanglement lies at the core of quantum algorithms designed to solve problems that are intractable by classical approaches. One such algorithm, quantum annealing (QA), provides a promising path to a practical quantum processor. We have built a series of architecturally scalable QA processors consisting of networks of manufactured interacting spins (qubits). Here, we use qubit tunneling spectroscopy to measure the energy eigenspectrum of two- and eight-qubit systems within one such processor, demonstrating quantum coherence in these systems. We present experimental evidence that, during a critical portion of QA, the qubits become entangled and entanglement persists even as these systems reach equilibrium with a thermal environment. Our results provide an encouraging sign that QA is a viable technology for large-scale quantum computing.
View more