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.

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.

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.

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.

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.

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 · arXiv:2012.09265 (2020)
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.

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.

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 · arXiv (2020)
Download PDF View
The use of quantum computing for machine learning is among the most exciting prospective applications of quantum technologies. At the crux of excitement is the potential for quantum computers to perform some computations exponentially faster than their classical counterparts. However, a machine learning task where some data is provided can be considerably different than more commonly studied computational tasks. In this work, we show that some problems that are classically hard to compute can be predicted easily with classical machines that learn from data. We find that classical machines can often compete or outperform existing quantum models even on data sets generated by quantum evolution, especially at large system sizes. Using rigorous prediction error bounds as a foundation, we develop a methodology for assessing the potential for quantum advantage in prediction on learning tasks. We show how the use of exponentially large quantum Hilbert space in existing quantum models can result in significantly inferior prediction performance compared to classical machines. To circumvent the observed setbacks, we propose an improvement by projecting all quantum states to an approximate classical representation. The projected quantum model provides a simple and rigorous quantum speed-up for a recently proposed learning problem in the fault-tolerant regime. For more near-term quantum models, the projected versions demonstrate a significant prediction advantage over some classical models on engineered data sets in one of the largest numerical tests for gate-based quantum machine learning to date, up to 30 qubits.

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, Murphy Yuezhen Niu, Ramin Halavati, Evan Peters, Martin Leib, Andrea Skolik, Michael Streif, David Von Dollen, Jarrod R. McClean, Sergio Boixo, Dave Bacon, Alan K. Ho, Hartmut Neven, Masoud Mohseni · (2020)
Download PDF View
We introduce TensorFlow Quantum, an open-source software platform for the rapid prototyping of hybrid quantum-classical parameterized models to learn from classical or quantum data. In particular, this framework facilitate training, inference, and testing of hybrid quantum-classical models by providing a number of features including batched circuit execution, automated expectation estimation, estimation of quantum gradients, hybrid quantum-classical autodifferentiation, and rapid model construction, all from within TensorFlow. We present an introduction to the software architecture and main building blocks through several examples and code snippets. We provide further theoretical background into the theory of hybrid quantum-classical neural-network-based models and hybrid autodifferentiation. Moreover, we provide a set of concrete quantum applications including supervised learning with quantum classifiers, adaptive layer-wise training strategies for quantum neural network training, machine learning for quantum control, meta-learning for quantum neural network training, quantum dynamics learning, and quantum-probabilistic generative modelling of mixed quantum states. We hope this library provides the necessary toolbox for quantum computing and machine learning research communities to control, verify, and better understand the state and dynamics of natural or artificial quantum systems, design novel models for quantum matter and chemical systems, and ultimately discover new quantum algorithms to observe potential quantum advantage on quantum processors.

Low Depth Mechanisms for Quantum Optimization

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.

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.

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 · arXiv:2011.03494 (2020)
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\%$.

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 · arXiv:2011.07064 (2020)
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.

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.

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 · ArXiv (2020)
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.

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.

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 · arXiv:1808.02625 (2018)
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.

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