Years
8
44
30
26
39
18
15
22
13
11
6
7
1
Thermalization and criticality on an analogue–digital quantum simulator
Trond I Andersen, Nikita Astrakhantsev, Amir H Karamlou, Julia Berndtsson, Johannes Motruk, Aaron Szasz, Jonathan A Gross, Alexander Schuckert, Tom Westerhout, Yaxing Zhang, Ebrahim Forati, Dario Rossi, Bryce Kobrin, A Di Paolo, Andrey R Klots, Ilya Drozdov, V Kurilovich, Andre Petukhov, Lev B Ioffe, Andreas Elben, Aniket Rath, Vittorio Vitale, Benoit Vermersch, Rajeev Acharya, Laleh Aghababaie Beni, Kyle Anderson, Markus Ansmann, Frank Arute, Kunal Arya, Abraham Asfaw, Juan Atalaya, Brian Ballard, Joseph C Bardin, Andreas Bengtsson, Alexander Bilmes, Gina Bortoli, Alexandre Bourassa, Jenna Bovaird, Leon Brill, Michael Broughton, David A Browne, Brett Buchea, Bob B Buckley, David A Buell, Tim Burger, Brian Burkett, Nicholas Bushnell, Anthony Cabrera, Juan Campero, H-S Chang, Zijun Chen, Ben Chiaro, Jahan Claes, Agnetta Y Cleland, Josh Cogan, Roberto Collins, Paul Conner, William Courtney, Alexander L Crook, Sayan Das, Dripto M Debroy, L De Lorenzo, A Del Toro Barba, Sean Demura, Paul Donohoe, Andrew Dunsworth, Clint Earle, Alec Eickbusch, Aviv Moshe Elbag, Mahmoud Elzouka, Catherine Erickson, Lara Faoro, Reza Fatemi, Vinicius S Ferreira, L Flores Burgos, Austin G Fowler, Brooks Foxen, Suhas Ganjam, Robert Gasca, William Giang, Craig Gidney, Dar Gilboa, Marissa Giustina, Raja Gosula, A Grajales Dau, Dietrich Graumann, Alex Greene, Steve Habegger, Michael C Hamilton, Monica Hansen, Matthew P Harrigan, Sean D Harrington, Stephen Heslin, Paula Heu, Gordon Hill, Markus R Hoffmann, H-Y Huang, Trent Huang, Ashley Huff, William J Huggins, Sergei V Isakov, Evan Jeffrey, Zhang Jiang, Cody Jones, Stephen Jordan, Chaitali Joshi, Pavol Juhas, Dvir Kafri, Hui Kang, Kostyantyn Kechedzhi, Trupti Khaire, Tanuj Khattar, Mostafa Khezri, Mária Kieferová, Seon Kim, Alexei Kitaev, P Klimov, Alexander N Korotkov, Fedor Kostritsa, John Mark Kreikebaum, David Landhuis, Brandon W Langley, Pavel Laptev, K-M Lau, L Le Guevel, Justin Ledford, Joonho Lee, KW Lee, Yuri D Lensky, Brian J Lester, Wing Yan Li, Alexander T Lill, Wayne Liu, William P Livingston, Aditya Locharla, Daniel Lundahl, Aaron Lunt, Sid Madhuk, Ashley Maloney, Salvatore Mandrà, Leigh S Martin, Orion Martin, Steven Martin, Cameron Maxfield, Jarrod R McClean, Matt McEwen, Seneca Meeks, Kevin C Miao, Amanda Mieszala, Sebastian Molina ·  Nature 638 (8049), 79-85, 2025
Download PDF View
Understanding how interacting particles approach thermal equilibrium is a major challenge of quantum simulators,. Unlocking the full potential of such systems towards this goal requires flexible initial state preparation, precise time evolution and extensive probes for final state characterization. Here we present a quantum simulator comprising 69 superconducting qubits that supports both universal quantum gates and high-fidelity analogue evolution, with performance beyond the reach of classical simulation in cross-entropy benchmarking experiments. This hybrid platform features more versatile measurement capabilities compared with analogue-only simulators, which we leverage here to reveal a coarsening-induced breakdown of Kibble–Zurek scaling predictions in the XY model, as well as signatures of the classical Kosterlitz–Thouless phase transition. Moreover, the digital gates enable precise energy control …
Sparse blossom: correcting a million errors per core second with minimum-weight matching
Oscar Higgott, Craig Gidney ·  Quantum 9, 1600, 2025
Download PDF View
In this work, we introduce a fast implementation of the minimum-weight perfect matching (MWPM) decoder, the most widely used decoder for several important families of quantum error correcting codes, including surface codes. Our algorithm, which we call sparse blossom, is a variant of the blossom algorithm which directly solves the decoding problem relevant to quantum error correction. Sparse blossom avoids the need for all-to-all Dijkstra searches, common amongst MWPM decoder implementations. For 0.1% circuit-level depolarising noise, sparse blossom processes syndrome data in both and bases of distance-17 surface code circuits in less than one microsecond per round of syndrome extraction on a single core, which matches the rate at which syndrome data is generated by superconducting quantum computers. Our implementation is open-source, and has been released in version 2 of the PyMatching library.
Quartic quantum speedups for planted inference
Alexander Schmidhuber, Ryan O’Donnell, Robin Kothari, Ryan Babbush ·  Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms …, 2025
Download PDF View
We describe a quantum algorithm for the Planted Noisy kXOR problem (also known as sparse Learning Parity with Noise) that achieves a nearly quartic (4th power) speedup over the best known classical algorithm while also only using logarithmically many qubits. Our work generalizes and simplifies prior work of Hastings [Has20], by building on his quantum algorithm for the Tensor Principal Component Analysis (PCA) problem. We achieve our quantum speedup using a general framework based on the Kikuchi Method (recovering the quartic speedup for Tensor PCA), and we anticipate it will yield similar speedups for further planted inference problems. These speedups rely on the fact that planted inference problems naturally instantiate the Guided Sparse Hamiltonian problem. Since the Planted Noisy kXOR problem has been used as a component of certain cryptographic constructions, our work suggests that …
Triply efficient shadow tomography
Robbie King, David Gosset, Robin Kothari, Ryan Babbush ·  Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms …, 2025
Download PDF View
Given copies of a quantum state ρ, a shadow tomography protocol aims to learn all expectation values from a fixed set of observables, to within a given precision ε. We say that a shadow tomography protocol is triply efficient if it is sample- and time-efficient, and only employs measurements that entangle a constant number of copies of ρ at a time. The classical shadows protocol based on random single-copy measurements is triply efficient for the set of local Pauli observables. This and other protocols based on random singlecopy Clifford measurements can be understood as arising from fractional colorings of a graph G that encodes the commutation structure of the set of observables. Here we describe a framework for two-copy shadow tomography that uses an initial round of Bell measurements to reduce to a fractional coloring problem in an induced subgraph of G with bounded clique number. This coloring …
Efficient state preparation for the quantum simulation of molecules in first quantization
William J Huggins, Oskar Leimkuhler, Torin F Stetina, K Birgitta Whaley ·  PRX Quantum 6 (2), 020319, 2025
Download PDF View
The quantum simulation of real molecules and materials is one of the most highly anticipated applications of quantum computing. Algorithms for simulating electronic structure using a first-quantized plane-wave representation are especially promising due to their asymptotic efficiency. However, previous proposals for preparing initial states for these simulation algorithms scale poorly with the size of the basis set. We address this shortcoming by showing how to efficiently map states defined in a Gaussian-type orbital basis to a plane-wave basis with a scaling that is logarithmic in the number of plane waves. Our key technical result is a proof that molecular orbitals constructed from Gaussian-type basis functions can be compactly represented in a plane-wave basis using matrix product states. While we expect that other approaches could achieve the same logarithmic scaling with respect to basis-set size, our proposed …
Shadow hamiltonian simulation
Rolando D Somma, Robbie King, Robin Kothari, Thomas E O’Brien, Ryan Babbush ·  Nature Communications 16 (1), 2690, 2025
Download PDF View
Simulating quantum dynamics is one of the most important applications of quantum computers. Traditional approaches for quantum simulation involve preparing the full evolved state of the system and then measuring some physical quantity. Here, we present a different and novel approach to quantum simulation that uses a compressed quantum state that we call the “shadow state”. The amplitudes of this shadow state are proportional to the time-dependent expectations of a specific set of operators of interest, and it evolves according to its own Schrödinger equation. This evolution can be simulated on a quantum computer efficiently under broad conditions. Applications of this approach to quantum simulation problems include simulating the dynamics of exponentially large systems of free fermions or free bosons, the latter example recovering a recent algorithm for simulating exponentially many classical harmonic …
Uncovering local integrability in quantum many-body dynamics
Oles Shtanko, Derek S Wang, Haimeng Zhang, Nikhil Harle, Alireza Seif, Ramis Movassagh, Zlatko Minev ·  Nature Communications 16 (1), 2552, 2025
Download PDF View
Interacting many-body quantum systems and their dynamics, while fundamental to modern science and technology, are formidable to simulate and understand. However, by discovering their symmetries, conservation laws, and integrability, one can unravel their intricacies. Here, using up to 124 qubits of a fully programmable quantum computer, we uncover local conservation laws and integrability in one- and two-dimensional periodically-driven spin lattices in a regime previously inaccessible to such detailed analysis. We focus on the paradigmatic example of disorder-induced ergodicity breaking, where we first benchmark the system crossover into a localized regime through anomalies in the one-particle-density-matrix spectrum and other hallmark signatures. We then demonstrate that this regime stems from hidden local integrals of motion by faithfully reconstructing their quantum operators, thus providing a more …
Quantum error correction below the surface code threshold
Rajeev Acharya, Dmitry A Abanin, Laleh Aghababaie-Beni, Igor Aleiner, Trond I Andersen, Markus Ansmann, Frank Arute, Kunal Arya, Abraham Asfaw, Nikita Astrakhantsev, Juan Atalaya, Ryan Babbush, Dave Bacon, Brian Ballard, Joseph C Bardin, Johannes Bausch, Andreas Bengtsson, Alexander Bilmes, Sam Blackwell, Sergio Boixo, Gina Bortoli, Alexandre Bourassa, Jenna Bovaird, Leon Brill, Michael Broughton, David A Browne, Brett Buchea, Bob B Buckley, David A Buell, Tim Burger, Brian Burkett, Nicholas Bushnell, Anthony Cabrera, Juan Campero, Hung-Shen Chang, Yu Chen, Zijun Chen, Ben Chiaro, Desmond Chik, Charina Chou, Jahan Claes, Agnetta Y Cleland, Josh Cogan, Roberto Collins, Paul Conner, William Courtney, Alexander L Crook, Ben Curtin, Sayan Das, Alex Davies, Laura De Lorenzo, Dripto M Debroy, Sean Demura, Michel Devoret, Agustin Di Paolo, Paul Donohoe, Ilya Drozdov, Andrew Dunsworth, Clint Earle, Thomas Edlich, Alec Eickbusch, Aviv Moshe Elbag, Mahmoud Elzouka, Catherine Erickson, Lara Faoro, Edward Farhi, Vinicius S Ferreira, Leslie Flores Burgos, Ebrahim Forati, Austin G Fowler, Brooks Foxen, Suhas Ganjam, Gonzalo Garcia, Robert Gasca, Élie Genois, William Giang, Craig Gidney, Dar Gilboa, Raja Gosula, Alejandro Grajales Dau, Dietrich Graumann, Alex Greene, Jonathan A Gross, Steve Habegger, John Hall, Michael C Hamilton, Monica Hansen, Matthew P Harrigan, Sean D Harrington, Francisco JH Heras, Stephen Heslin, Paula Heu, Oscar Higgott, Gordon Hill, Jeremy Hilton, George Holland, Sabrina Hong, Hsin-Yuan Huang, Ashley Huff, William J Huggins, Lev B Ioffe, Sergei V Isakov, Justin Iveland, Evan Jeffrey, Zhang Jiang, Cody Jones, Stephen Jordan, Chaitali Joshi, Pavol Juhas, Dvir Kafri, Hui Kang, Amir H Karamlou, Kostyantyn Kechedzhi, Julian Kelly, Trupti Khaire, Tanuj Khattar, Mostafa Khezri, Seon Kim, Paul V Klimov, Andrey R Klots, Bryce Kobrin, Pushmeet Kohli, Alexander N Korotkov, Fedor Kostritsa, Robin Kothari, Borislav Kozlovskii, John Mark Kreikebaum, Vladislav D Kurilovich, Nathan Lacroix, David Landhuis, Tiano Lange-Dei, Brandon W Langley, Pavel Laptev, Kim-Ming Lau, Loïck Le Guevel, Justin Ledford, Joonho Lee, Kenny Lee, Yuri D Lensky, Shannon Leon, Brian J Lester, Wing Yan Li, Yin Li, Alexander T Lill, Wayne Liu, William P Livingston, Aditya Locharla, Erik Lucero, Daniel Lundahl, Aaron Lunt ·  Nature 638 (8052), 920-926, 2025
Download PDF View
Quantum error correction 1, 2, 3–4 provides a path to reach practical quantum computing by combining multiple physical qubits into a logical qubit, in which the logical error rate is suppressed exponentially as more qubits are added. However, this exponential suppression only occurs if the physical error rate is below a critical threshold. Here we present two below-threshold surface code memories on our newest generation of superconducting processors, Willow: a distance-7 code and a distance-5 code integrated with a real-time decoder. The logical error rate of our larger quantum memory is suppressed by a factor of Λ= 2.14±0.02 when increasing the code distance by 2, culminating in a 101-qubit distance-7 code with 0.143%±0.003 per cent error per cycle of error correction. This logical memory is also beyond breakeven, exceeding the lifetime of its best physical qubit by a factor of 2.4±0.3. Our system maintains …
Quantum simulation of realistic materials in first quantization using non-local pseudopotentials
Dominic W Berry, Nicholas C Rubin, Ahmed O Elnabawy, Gabriele Ahlers, A Eugene DePrince III, Joonho Lee, Christian Gogolin, Ryan Babbush ·  npj Quantum Information 10 (1), 130, 2024
Download PDF View
This paper improves and demonstrates the usefulness of the first quantized plane-wave algorithms for the quantum simulation of electronic structure. We describe our quantum algorithm for first quantized simulation that accurately includes pseudopotentials. We focus on the Goedecker-Tetter-Hutter pseudopotential, and despite its complicated form, we block encode the associated operator without significantly increasing the overall cost of quantum simulation. This is surprising since simulating the nuclear potential is much simpler without pseudopotentials, yet is still the bottleneck. We also generalize prior methods to enable the simulation of materials with non-cubic unit cells, which requires nontrivial modifications. Finally, we combine these techniques to estimate block-encoding costs for commercially relevant instances of heterogeneous catalysis (e.g. carbon monoxide adsorption) and compare to the quantum …
Scaling and logic in the color code on a superconducting quantum processor
Nathan Lacroix, Alexandre Bourassa, Francisco JH Heras, Lei M Zhang, Johannes Bausch, Andrew W Senior, Thomas Edlich, Noah Shutty, Volodymyr Sivak, Andreas Bengtsson, Matt McEwen, Oscar Higgott, Dvir Kafri, Jahan Claes, Alexis Morvan, Zijun Chen, Adam Zalcman, Sid Madhuk, Rajeev Acharya, Laleh Aghababaie Beni, Georg Aigeldinger, Ross Alcaraz, Trond I Andersen, Markus Ansmann, Frank Arute, Kunal Arya, Abraham Asfaw, Juan Atalaya, Ryan Babbush, Brian Ballard, Joseph C Bardin, Alexander Bilmes, Sam Blackwell, Jenna Bovaird, Dylan Bowers, Leon Brill, Michael Broughton, David A Browne, Brett Buchea, Bob B Buckley, Tim Burger, Brian Burkett, Nicholas Bushnell, Anthony Cabrera, Juan Campero, Hung-Shen Chang, Ben Chiaro, Liang-Ying Chih, Agnetta Y Cleland, Josh Cogan, Roberto Collins, Paul Conner, William Courtney, Alexander L Crook, Ben Curtin, Sayan Das, Sean Demura, Laura De Lorenzo, Agustin Di Paolo, Paul Donohoe, Ilya Drozdov, Andrew Dunsworth, Alec Eickbusch, Aviv Moshe Elbag, Mahmoud Elzouka, Catherine Erickson, Vinicius S Ferreira, Leslie Flores Burgos, Ebrahim Forati, Austin G Fowler, Brooks Foxen, Suhas Ganjam, Gonzalo Garcia, Robert Gasca, Élie Genois, William Giang, Dar Gilboa, Raja Gosula, Alejandro Grajales Dau, Dietrich Graumann, Alex Greene, Jonathan A Gross, Tan Ha, Steve Habegger, Monica Hansen, Matthew P Harrigan, Sean D Harrington, Stephen Heslin, Paula Heu, Reno Hiltermann, Jeremy Hilton, Sabrina Hong, Hsin-Yuan Huang, Ashley Huff, William J Huggins, Evan Jeffrey, Zhang Jiang, Xiaoxuan Jin, Chaitali Joshi, Pavol Juhas, Andreas Kabel, Hui Kang, Amir H Karamlou, Kostyantyn Kechedzhi, Trupti Khaire, Tanuj Khattar, Mostafa Khezri, Seon Kim, Paul V Klimov, Bryce Kobrin, Alexander N Korotkov, Fedor Kostritsa, John Mark Kreikebaum, Vladislav D Kurilovich, David Landhuis, Tiano Lange-Dei, Brandon W Langley, Pavel Laptev, Kim-Ming Lau, Justin Ledford, Kenny Lee, Brian J Lester, Loïck Le Guevel, Wing Yan Li, Yin Li, Alexander T Lill, William P Livingston, Aditya Locharla, Erik Lucero, Daniel Lundahl, Aaron Lunt, Ashley Maloney, Salvatore Mandrà, Leigh S Martin, Orion Martin, Cameron Maxfield, Jarrod R McClean, Seneca Meeks, Anthony Megrant, Kevin C Miao, Reza Molavi, Sebastian Molina, Shirin Montazeri, Ramis Movassagh, Charles Neill, Michael Newman, Anthony Nguyen, Murray Nguyen, Chia-Hung Ni, Murphy Y Niu ·  arXiv preprint arXiv:2412.14256, 2024
Download PDF View
Quantum error correction is essential for bridging the gap between the error rates of physical devices and the extremely low logical error rates required for quantum algorithms. Recent error-correction demonstrations on superconducting processors have focused primarily on the surface code, which offers a high error threshold but poses limitations for logical operations. In contrast, the color code enables much more efficient logic, although it requires more complex stabilizer measurements and decoding techniques. Measuring these stabilizers in planar architectures such as superconducting qubits is challenging, and so far, realizations of color codes have not addressed performance scaling with code size on any platform. Here, we present a comprehensive demonstration of the color code on a superconducting processor, achieving logical error suppression and performing logical operations. Scaling the code distance from three to five suppresses logical errors by a factor of = 1.56(4). Simulations indicate this performance is below the threshold of the color code, and furthermore that the color code may be more efficient than the surface code with modest device improvements. Using logical randomized benchmarking, we find that transversal Clifford gates add an error of only 0.0027(3), which is substantially less than the error of an idling error correction cycle. We inject magic states, a key resource for universal computation, achieving fidelities exceeding 99% with post-selection (retaining about 75% of the data). Finally, we successfully teleport logical states between distance-three color codes using lattice surgery, with teleported state fidelities …
Demonstrating dynamic surface codes
Alec Eickbusch, Matt McEwen, Volodymyr Sivak, Alexandre Bourassa, Juan Atalaya, Jahan Claes, Dvir Kafri, Craig Gidney, Christopher W Warren, Jonathan Gross, Alex Opremcak, Nicholas Zobrist Kevin C Miao, Gabrielle Roberts, Kevin J Satzinger, Andreas Bengtsson, Matthew Neeley, William P Livingston, Alex Greene, Laleh Aghababaie Beni, Georg Aigeldinger, Ross Alcaraz, Trond I Andersen, Markus Ansmann, Kunal Arya, Abraham Asfaw, Ryan Babbush, Brian Ballard, Joseph C Bardin, Alexander Bilmes, Dylan Bowers, Leon Brill, Michael Broughton, David A Browne, Brett Buchea, Bob B Buckley, Brian Burkett, Nicholas Bushnell, Anthony Cabrera, Juan Campero, Hung-Shen Chang, Ben Chiaro, Liang-Ying Chih, Agnetta Y Cleland, Josh Cogan, Roberto Collins, Paul Conner, William Courtney, L Crook, Ben Curtin, Sayan Das, Alexander Del Toro Barba, Sean Demura, Laura De Lorenzo, Agustin Di Paolo, Paul Donohoe, Ilya K Drozdov, Andrew Dunsworth, Aviv Moshe Elbag, Mahmoud Elzouka, Catherine Erickson, Vinicius S Ferreira, Leslie Flores Burgos, Ebrahim Forati, Austin G Fowler, Brooks Foxen, Suhas Ganjam, Robert Gasca, Élie Genois, William Giang, Dar Gilboa, Raja Gosula, Alejandro Grajales Dau, Tan Ha, Steve Habegger, Monica Hansen, Matthew P Harrigan, Sean D Harrington, Stephen Heslin, Paula Heu, Oscar Higgott, Reno Hiltermann, Jeremy Hilton, Hsin-Yuan Huang, Ashley Huff, William J Huggins, Evan Jeffrey, Zhang Jiang, Xiaoxuan Jin, Cody Jones, Chaitali Joshi, Pavol Juhas, Andreas Kabel, Hui Kang, H Karamlou, Kostyantyn Kechedzhi, Trupti Khaire, Tanuj Khattar, Mostafa Khezri, Seon Kim, Bryce Kobrin, Alexander N Korotkov, Fedor Kostritsa, John Mark Kreikebaum, Vladislav D Kurilovich, David Landhuis, Brandon W Langley, Kim-Ming Lau, Justin Ledford, Kenny Lee, Brian J Lester, Loïck Le Guevel, Yan Li, Alexander T Lill, Aditya Locharla, Erik Lucero, Daniel Lundahl, Aaron Lunt, Sid Madhuk, Ashley Maloney, Salvatore Mandrà, Leigh S Martin, Orion Martin, Cameron Maxfield, Jarrod R McClean, Seneca Meeks, Reza Molavi, Sebastian Molina, Shirin Montazeri, Ramis Movassagh, Michael Newman, Anthony Nguyen, Murray Nguyen, Chia-Hung Ni, Logan Oas, Raymond Orosco, Kristoffer Ottosson, Alex Pizzuto, Rebecca Potter, Orion Pritchard, Chris Quintana, Ganesh Ramachandran, Matthew J Reagor, David M Rhodes, Eliott Rosenberg, Elizabeth Rossi, Kannan Sankaragomathi, Henry F Schurkus, Michael J Shearn, Aaron Shorter, Noah Shutty ·  arXiv preprint arXiv:2412.14360, 2024
Download PDF View
A remarkable characteristic of quantum computing is the potential for reliable computation despite faulty qubits. This can be achieved through quantum error correction, which is typically implemented by repeatedly applying static syndrome checks, permitting correction of logical information. Recently, the development of time-dynamic approaches to error correction has uncovered new codes and new code implementations. In this work, we experimentally demonstrate three time-dynamic implementations of the surface code, each offering a unique solution to hardware design challenges and introducing flexibility in surface code realization. First, we embed the surface code on a hexagonal lattice, reducing the necessary couplings per qubit from four to three. Second, we walk a surface code, swapping the role of data and measure qubits each round, achieving error correction with built-in removal of accumulated non-computational errors. Finally, we realize the surface code using iSWAP gates instead of the traditional CNOT, extending the set of viable gates for error correction without additional overhead. We measure the error suppression factor when scaling from distance-3 to distance-5 codes of , , and , achieving state-of-the-art error suppression for each. With detailed error budgeting, we explore their performance trade-offs and implications for hardware design. This work demonstrates that dynamic circuit approaches satisfy the demands for fault-tolerance and opens new alternative avenues for scalable hardware design.
Entanglement-enabled advantage for learning a bosonic random displacement channel
Changhun Oh, Senrui Chen, Yat Wong, Sisi Zhou, Hsin-Yuan Huang, Jens AH Nielsen, Zheng-Hao Liu, Jonas S Neergaard-Nielsen, Ulrik L Andersen, Liang Jiang, John Preskill ·  Physical Review Letters 133 (23), 230604, 2024
Download PDF View
We show that quantum entanglement can provide an exponential advantage in learning properties of a bosonic continuous-variable (CV) system. The task we consider is estimating a probabilistic mixture of displacement operators acting on bosonic modes, called a random displacement channel. We prove that if the modes are not entangled with an ancillary quantum memory, then the channel must be sampled a number of times exponential in in order to estimate its characteristic function to reasonable precision; this lower bound on sample complexity applies even if the channel inputs and measurements performed on channel outputs are chosen adaptively or have unrestricted energy. On the other hand, we present a simple entanglement-assisted scheme that only requires a number of samples independent of in the large squeezing and noiseless limit. This establishes an exponential separation in …
The advantage of quantum control in many-body Hamiltonian learning
Alicja Dutkiewicz, Thomas E O'Brien, Thomas Schuster ·  Quantum 8, 1537, 2024
Download PDF View
We study the problem of learning the Hamiltonian of a many-body quantum system from experimental data. We show that the rate of learning depends on the amount of control available during the experiment. We consider three control models: one where time evolution can be augmented with instantaneous quantum operations, one where the Hamiltonian itself can be augmented by adding constant terms, and one where the experimentalist has no control over the system's time evolution. With continuous quantum control, we provide an adaptive algorithm for learning a many-body Hamiltonian at the Heisenberg limit: , where is the total amount of time evolution across all experiments and is the target precision. This requires only preparation of product states, time-evolution, and measurement in a product basis. In the absence of quantum control, we prove that learning is standard quantum limited, , for large classes of many-body Hamiltonians, including any Hamiltonian that thermalizes via the eigenstate thermalization hypothesis. These results establish a quadratic advantage in experimental runtime for learning with quantum control.
Kernel polynomial method for linear spin wave theory
Harry Lane, Hao Zhang, David Dahlbom, Sam Quinn, Rolando Somma, Martin Mourigal, Christian D Batista, Kipton Barros ·  SciPost Physics 17 (5), 145, 2024
Download PDF View
Calculating dynamical spin correlations is essential for matching model magnetic exchange Hamiltonians to momentum-resolved spectroscopic measurements. A major numerical bottleneck is the diagonalization of the dynamical matrix, especially in systems with large magnetic unit cells, such as those with incommensurate magnetic structures or quenched disorder. In this paper, we demonstrate an efficient scheme based on the kernel polynomial method for calculating dynamical correlations of relevance to inelastic neutron scattering experiments. This method reduces the scaling of numerical cost from cubic to linear in the magnetic unit cell size.
Quantum one-time protection of any randomized algorithm
Sam Gunn, Ramis Movassagh ·  arXiv preprint arXiv:2411.03305, 2024
Download PDF View
The meteoric rise in power and popularity of machine learning models dependent on valuable training data has reignited a basic tension between the power of running a program locally and the risk of exposing details of that program to the user. At the same time, fundamental properties of quantum states offer new solutions to data and program security that can require strikingly few quantum resources to exploit, and offer advantages outside of mere computational run time. In this work, we demonstrate such a solution with quantum one-time tokens. A quantum one-time token is a quantum state that permits a certain program to be evaluated exactly once. One-time security guarantees, roughly, that the token cannot be used to evaluate the program more than once. We propose a scheme for building quantum one-time tokens for any randomized classical program, which include generative AI models. We prove that the scheme satisfies an interesting definition of one-time security as long as outputs of the classical algorithm have high enough min-entropy, in a black box model. Importantly, the classical program being protected does not need to be implemented coherently on a quantum computer. In fact, the size and complexity of the quantum one-time token is independent of the program being protected, and additional quantum resources serve only to increase the security of the protocol. Due to this flexibility in adjusting the security, we believe that our proposal is parsimonious enough to serve as a promising candidate for a near-term useful demonstration of quantum computing in either the NISQ or early fault tolerant regime.
Certifying almost all quantum states with few single-qubit measurements
Hsin-Yuan Huang, John Preskill, Mehdi Soleimanifar ·  2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS …, 2024
Download PDF View
A fundamental challenge in quantum information science is certifying that an n-qubit state prepared in the lab closely matches a target state . Previous approaches to this problem often require deep quantum circuits, exponentially many single-qubit measurements, or are limited to specific state families. In this work, we introduce a new method that leverages a connection between state certification and the mixing time of a random walk, allowing almost all n-qubit target states, including those with exponential circuit complexity, to be certified with only single-qubit measurements. Our protocol is broadly compatible with various experimental platforms and has applications in benchmarking quantum systems, optimizing quantum circuits, and efficiently learning and verifying representations of quantum states—such as neural networks and tensor networks—using only single-qubit measurements. Moreover, these …
Phase transitions in random circuit sampling
Alexis Morvan, B Villalonga, X Mi, S Mandra, A Bengtsson, PV Klimov, Z Chen, S Hong, C Erickson, IK Drozdov, J Chau, G Laun, R Movassagh, A Asfaw, LTAN Brandão, R Peralta, D Abanin, R Acharya, R Allen, TI Andersen, K Anderson, M Ansmann, F Arute, K Arya, J Atalaya, JC Bardin, A Bilmes, G Bortoli, A Bourassa, J Bovaird, L Brill, M Broughton, BB Buckley, DA Buell, T Burger, B Burkett, N Bushnell, J Campero, H-S Chang, B Chiaro, D Chik, C Chou, J Cogan, R Collins, P Conner, W Courtney, AL Crook, B Curtin, DM Debroy, A Del Toro Barba, S Demura, A Di Paolo, A Dunsworth, L Faoro, E Farhi, R Fatemi, VS Ferreira, L Flores Burgos, E Forati, AG Fowler, B Foxen, G Garcia, E Genois, W Giang, C Gidney, D Gilboa, M Giustina, R Gosula, A Grajales Dau, JA Gross, S Habegger, MC Hamilton, M Hansen, MP Harrigan, SD Harrington, P Heu, MR Hoffmann, T Huang, A Huff, WJ Huggins, LB Ioffe, SV Isakov, J Iveland, E Jeffrey, Z Jiang, C Jones, P Juhas, D Kafri, T Khattar, M Khezri, M Kieferová, S Kim, A Kitaev, AR Klots, AN Korotkov, F Kostritsa, JM Kreikebaum, D Landhuis, P Laptev, K-M Lau, L Laws, J Lee, KW Lee, YD Lensky, BJ Lester, AT Lill, W Liu, WP Livingston, A Locharla, FD Malone, O Martin, S Martin, JR McClean, M McEwen, KC Miao, A Mieszala, S Montazeri, W Mruczkiewicz, O Naaman, M Neeley, C Neill, A Nersisyan, M Newman, JH Ng, A Nguyen, M Nguyen, M Yuezhen Niu, TE O’Brien, S Omonije, A Opremcak, A Petukhov, R Potter, LP Pryadko, C Quintana, DM Rhodes, C Rocque, E Rosenberg, NC Rubin, N Saei, D Sank, K Sankaragomathi, KJ Satzinger, HF Schurkus, C Schuster, MJ Shearn, A Shorter, N Shutty, V Shvarts, V Sivak, J Skruzny ·  Nature 634 (8033), 328-333, 2024
Download PDF View
Undesired coupling to the surrounding environment destroys long-range correlations in quantum processors and hinders coherent evolution in the nominally available computational space. This noise is an outstanding challenge when leveraging the computation power of near-term quantum processors. It has been shown that benchmarking random circuit sampling with cross-entropy benchmarking can provide an estimate of the effective size of the Hilbert space coherently available, , , , , –. Nevertheless, quantum algorithms’ outputs can be trivialized by noise, making them susceptible to classical computation spoofing. Here, by implementing an algorithm for random circuit sampling, we demonstrate experimentally that two phase transitions are observable with cross-entropy benchmarking, which we explain theoretically with a statistical model. The first is a dynamical transition as a function of the number of cycles …
Observation of disorder-free localization and efficient disorder averaging on a quantum processor
Gaurav Gyawali, Tyler Cochran, Yuri Lensky, Eliott Rosenberg, Amir H Karamlou, Kostyantyn Kechedzhi, Julia Berndtsson, Tom Westerhout, Abraham Asfaw, Dmitry Abanin, Rajeev Acharya, Laleh Aghababaie Beni, Trond I Andersen, Markus Ansmann, Frank Arute, Kunal Arya, Nikita Astrakhantsev, Juan Atalaya, Ryan Babbush, Brian Ballard, Joseph C Bardin, Andreas Bengtsson, Alexander Bilmes, Gina Bortoli, Alexandre Bourassa, Jenna Bovaird, Leon Brill, Michael Broughton, David A Browne, Brett Buchea, Bob B Buckley, David A Buell, Tim Burger, Brian Burkett, Nicholas Bushnell, Anthony Cabrera, Juan Campero, Hung-Shen Chang, Zijun Chen, Ben Chiaro, Jahan Claes, Agnetta Y Cleland, Josh Cogan, Roberto Collins, Paul Conner, William Courtney, Alexander L Crook, Sayan Das, Dripto M Debroy, Laura De Lorenzo, Alexander Del Toro Barba, Sean Demura, Agustin Di Paolo, Paul Donohoe, Ilya Drozdov, Andrew Dunsworth, Clint Earle, Alec Eickbusch, Aviv Moshe Elbag, Mahmoud Elzouka, Catherine Erickson, Lara Faoro, Reza Fatemi, Vinicius S Ferreira, Leslie Flores Burgos, Ebrahim Forati, Austin G Fowler, Brooks Foxen, Suhas Ganjam, Robert Gasca, William Giang, Craig Gidney, Dar Gilboa, Raja Gosula, Alejandro Grajales Dau, Dietrich Graumann, Alex Greene, Jonathan A Gross, Steve Habegger, Michael C Hamilton, Monica Hansen, Matthew P Harrigan, Sean D Harrington, Stephen Heslin, Paula Heu, Gordon Hill, Jeremy Hilton, Markus R Hoffmann, Hsin-Yuan Huang, Ashley Huff, William J Huggins, Lev B Ioffe, Sergei V Isakov, Evan Jeffrey, Zhang Jiang, Cody Jones, Stephen Jordan, Chaitali Joshi, Pavol Juhas, Dvir Kafri, Hui Kang, Trupti Khaire, Tanuj Khattar, Mostafa Khezri, Mária Kieferová, Seon Kim, Paul V Klimov, Andrey R Klots, Bryce Kobrin, Alexander N Korotkov, Fedor Kostritsa, John Mark Kreikebaum, Vladislav D Kurilovich, David Landhuis, Tiano Lange-Dei, Brandon W Langley, Pavel Laptev, Kim-Ming Lau, Loïck Le Guevel, Justin Ledford, Joonho Lee, Kenny Lee, Brian J Lester, Wing Yan Li, Alexander T Lill, Wayne Liu, William P Livingston, Aditya Locharla, Daniel Lundahl, Aaron Lunt, Sid Madhuk, Ashley Maloney, Salvatore Mandrà, Leigh S Martin, Steven Martin, Orion Martin, Cameron Maxfield, Jarrod R McClean, Matt McEwen, Seneca Meeks, Anthony Megrant, Xiao Mi, Kevin C Miao, Amanda Mieszala, Sebastian Molina, Shirin Montazeri, Alexis Morvan, Ramis Movassagh, Charles Neill, Ani Nersisyan ·  arXiv preprint arXiv:2410.06557, 2024
Download PDF View
One of the most challenging problems in the computational study of localization in quantum manybody systems is to capture the effects of rare events, which requires sampling over exponentially many disorder realizations. We implement an efficient procedure on a quantum processor, leveraging quantum parallelism, to efficiently sample over all disorder realizations. We observe localization without disorder in quantum many-body dynamics in one and two dimensions: perturbations do not diffuse even though both the generator of evolution and the initial states are fully translationally invariant. The disorder strength as well as its density can be readily tuned using the initial state. Furthermore, we demonstrate the versatility of our platform by measuring Renyi entropies. Our method could also be extended to higher moments of the physical observables and disorder learning.
Exponential learning advantages with conjugate states and minimal quantum memory
Robbie King, Kianna Wan, Jarrod R McClean ·  PRX Quantum 5 (4), 040301, 2024
Download PDF View
The ability of quantum computers to directly manipulate and analyze quantum states stored in quantum memory allows them to learn about aspects of our physical world that would otherwise be invisible given a modest number of measurements. Here we investigate a new learning resource, which could be available to quantum computers in the future—measurements on the unknown state accompanied by its complex conjugate . For a certain shadow tomography task, we surprisingly find that measurements on only copies of can be exponentially more powerful than measurements on , even for large . This expands the class of provable exponential advantages using only a constant overhead quantum memory, or minimal quantum memory, and we provide a number of examples where the state is naturally available in both computational and physical applications. In addition, we precisely …
Learning quantum states and unitaries of bounded gate complexity
Haimeng Zhao, Laura Lewis, Ishaan Kannan, Yihui Quek, Hsin-Yuan Huang, Matthias C Caro ·  PRX Quantum 5 (4), 040306, 2024
Download PDF View
While quantum state tomography is notoriously hard, most states hold little interest to practically minded tomographers. Given that states and unitaries appearing in nature are of bounded gate complexity, it is natural to ask if efficient learning becomes possible. In this work, we prove that to learn a state generated by a quantum circuit with two-qubit gates to a small trace distance, a sample complexity scaling linearly in is necessary and sufficient. We also prove that the optimal query complexity to learn a unitary generated by gates to a small average-case error scales linearly in . While sample-efficient learning can be achieved, we show that under reasonable cryptographic conjectures, the computational complexity for learning states and unitaries of gate complexity must scale exponentially in . We illustrate how these results establish fundamental limitations on the expressivity of quantum machine …
Visualizing Dynamics of Charges and Strings in (2+1)D Lattice Gauge Theories
Tyler A Cochran, Bernhard Jobst, Eliott Rosenberg, Yuri D Lensky, Gaurav Gyawali, Norhan Eassa, Melissa Will, Dmitry Abanin, Rajeev Acharya, Laleh Aghababaie Beni, Trond I Andersen, Markus Ansmann, Frank Arute, Kunal Arya, Abraham Asfaw, Juan Atalaya, Ryan Babbush, Brian Ballard, Joseph C Bardin, Andreas Bengtsson, Alexander Bilmes, Alexandre Bourassa, Jenna Bovaird, Michael Broughton, David A Browne, Brett Buchea, Bob B Buckley, Tim Burger, Brian Burkett, Nicholas Bushnell, Anthony Cabrera, Juan Campero, Hung-Shen Chang, Zijun Chen, Ben Chiaro, Jahan Claes, Agnetta Y Cleland, Josh Cogan, Roberto Collins, Paul Conner, William Courtney, Alexander L Crook, Ben Curtin, Sayan Das, Sean Demura, Laura De Lorenzo, Agustin Di Paolo, Paul Donohoe, Ilya Drozdov, Andrew Dunsworth, Alec Eickbusch, Aviv Moshe Elbag, Mahmoud Elzouka, Catherine Erickson, Vinicius S Ferreira, Leslie Flores Burgos, Ebrahim Forati, Austin G Fowler, Brooks Foxen ·  arXiv preprint arXiv:2409.17142, 2024
Download PDF View
Lattice gauge theories (LGTs) can be employed to understand a wide range of phenomena, from elementary particle scattering in high-energy physics to effective descriptions of many-body interactions in materials. Studying dynamical properties of emergent phases can be challenging as it requires solving many-body problems that are generally beyond perturbative limits. We investigate the dynamics of local excitations in a LGT using a two-dimensional lattice of superconducting qubits. We first construct a simple variational circuit which prepares low-energy states that have a large overlap with the ground state; then we create particles with local gates and simulate their quantum dynamics via a discretized time evolution. As the effective magnetic field is increased, our measurements show signatures of transitioning from deconfined to confined dynamics. For confined excitations, the magnetic field induces a tension in the string connecting them. Our method allows us to experimentally image string dynamics in a (2+1)D LGT from which we uncover two distinct regimes inside the confining phase: for weak confinement the string fluctuates strongly in the transverse direction, while for strong confinement transverse fluctuations are effectively frozen. In addition, we demonstrate a resonance condition at which dynamical string breaking is facilitated. Our LGT implementation on a quantum processor presents a novel set of techniques for investigating emergent particle and string dynamics.
Rapid initial state preparation for the quantum simulation of strongly correlated molecules
Dominic W Berry, Yu Tong, Tanuj Khattar, Alec White, Tae In Kim, Sergio Boixo, Lin Lin, Seunghoon Lee, Garnet Kin Chan, Ryan Babbush, Nicholas C Rubin ·  arXiv preprint arXiv:2409.11748, 2024
Download PDF View
Studies on quantum algorithms for ground state energy estimation often assume perfect ground state preparation; however, in reality the initial state will have imperfect overlap with the true ground state. Here we address that problem in two ways: by faster preparation of matrix product state (MPS) approximations, and more efficient filtering of the prepared state to find the ground state energy. We show how to achieve unitary synthesis with a Toffoli complexity about lower than that in prior work, and use that to derive a more efficient MPS preparation method. For filtering we present two different approaches: sampling and binary search. For both we use the theory of window functions to avoid large phase errors and minimise the complexity. We find that the binary search approach provides better scaling with the overlap at the cost of a larger constant factor, such that it will be preferred for overlaps less than about . Finally, we estimate the total resources to perform ground state energy estimation of Fe-S cluster systems, including the FeMo cofactor by estimating the overlap of different MPS initial states with potential ground-states of the FeMo cofactor using an extrapolation procedure. {With a modest MPS bond dimension of 4000, our procedure produces an estimate of overlap squared with a candidate ground-state of the FeMo cofactor, producing a total resource estimate of Toffoli gates; neglecting the search over candidates and assuming the accuracy of the extrapolation, this validates prior estimates that used perfect ground state overlap. This presents an example of a practical path to prepare states of high overlap in a …
Consumable Data via Quantum Communication
Dar Gilboa, Siddhartha Jain, Jarrod McClean ·  arXiv preprint arXiv:2409.08495, 2024
Download PDF View
Classical data can be copied and re-used for computation, with adverse consequences economically and in terms of data privacy. Motivated by this, we formulate problems in one-way communication complexity where Alice holds some data and Bob holds inputs, and he wants to compute instances of a bipartite relation on Alice's data and each of his inputs. We call this the asymmetric direct sum question for one-way communication. We give a number of examples where the quantum communication complexity of such problems scales polynomially with , while the classical communication complexity depends at most logarithmically on . For these examples, data behaves like a consumable resource when the owner stores and transmits it as quantum states. We show an application to a strategic data-selling game, and discuss other potential economic implications.
Expressing and analyzing quantum algorithms with qualtran
Matthew P Harrigan, Tanuj Khattar, Charles Yuan, Anurudh Peduri, Noureldin Yosri, Fionn D Malone, Ryan Babbush, Nicholas C Rubin ·  arXiv preprint arXiv:2409.04643, 2024
Download PDF View
Quantum computing's transition from theory to reality has spurred the need for novel software tools to manage the increasing complexity, sophistication, toil, and fallibility of quantum algorithm development. We present Qualtran, an open-source library for representing and analyzing quantum algorithms. Using appropriate abstractions and data structures, we can simulate and test algorithms, automatically generate information-rich diagrams, and tabulate resource requirements. Qualtran offers a standard library of algorithmic building blocks that are essential for modern cost-minimizing compilations. Its capabilities are showcased through the re-analysis of key algorithms in Hamiltonian simulation, chemistry, and cryptography. Architecture-independent resource counts output by Qualtran can be forwarded to our implementation of cost models to estimate physical costs like wall-clock time and number of physical qubits assuming a surface-code architecture. Qualtran provides a foundation for explicit constructions and reproducible analysis, fostering greater collaboration within the growing quantum algorithm development community.
Predicting quantum channels over general product distributions
Sitan Chen, Jaume de Dios Pont, Jun-Ting Hsieh, Hsin-Yuan Huang, Jane Lange, Jerry Li ·  arXiv preprint arXiv:2409.03684, 2024
Download PDF View
We investigate the problem of predicting the output behavior of unknown quantum channels. Given query access to an -qubit channel and an observable , we aim to learn the mapping \begin{equation*} \rho \mapsto \mathrm{Tr}(O E[\rho]) \end{equation*} to within a small error for most sampled from a distribution . Previously, Huang, Chen, and Preskill proved a surprising result that even if is arbitrary, this task can be solved in time roughly , where is the target prediction error. However, their guarantee applied only to input distributions invariant under all single-qubit Clifford gates, and their algorithm fails for important cases such as general product distributions over product states . In this work, we propose a new approach that achieves accurate prediction over essentially any product distribution , provided it is not "classical" in which case there is a trivial exponential lower bound. Our method employs a "biased Pauli analysis," analogous to classical biased Fourier analysis. Implementing this approach requires overcoming several challenges unique to the quantum setting, including the lack of a basis with appropriate orthogonality properties. The techniques we develop to address these issues may have broader applications in quantum information.
Classically estimating observables of noiseless quantum circuits
Armando Angrisani, Alexander Schmidhuber, Manuel S Rudolph, M Cerezo, Zoë Holmes, Hsin-Yuan Huang ·  arXiv preprint arXiv:2409.01706, 2024
Download PDF View
We present a classical algorithm for estimating expectation values of arbitrary observables on most quantum circuits across all circuit architectures and depths, including those with all-to-all connectivity. We prove that for any architecture where each circuit layer is equipped with a measure invariant under single-qubit rotations, our algorithm achieves a small error on all circuits except for a small fraction . The computational time is polynomial in qubit count and circuit depth for any small constant , and quasi-polynomial for inverse-polynomially small . For non-classically-simulable input states or observables, the expectation values can be estimated by augmenting our algorithm with classical shadows of the relevant state or observable. Our approach leverages a Pauli-path method under Heisenberg evolution. While prior works are limited to noisy quantum circuits, we establish classical simulability in noiseless regimes. Given that most quantum circuits in an architecture exhibit chaotic and locally scrambling behavior, our work demonstrates that estimating observables of such quantum dynamics is classically tractable across all geometries.
Hamiltonian simulation for low-energy states with optimal time dependence
Alexander Zlokapa, Rolando D Somma ·  Quantum 8, 1449, 2024
Download PDF View
We consider the task of simulating time evolution under a Hamiltonian within its low-energy subspace. Assuming access to a block-encoding of , for some and , the goal is to implement an -approximation to the evolution operator when the initial state is confined to the subspace corresponding to eigenvalues of , for . We present a quantum algorithm that requires queries to the block-encoding for any choice of such that . When the parameters satisfy and , this result improves over generic methods with query complexity . Our quantum algorithm leverages spectral gap amplification and the quantum singular value transform.
Quantum error correction below the surface code threshold
Rajeev Acharya, Laleh Aghababaie-Beni, Igor Aleiner, Trond I Andersen, Markus Ansmann, Frank Arute, Kunal Arya, Abraham Asfaw, Nikita Astrakhantsev, Juan Atalaya, Ryan Babbush, Dave Bacon, Brian Ballard, Joseph C Bardin, Johannes Bausch, Andreas Bengtsson, Alexander Bilmes, Sam Blackwell, Sergio Boixo, Gina Bortoli, Alexandre Bourassa, Jenna Bovaird, Leon Brill, Michael Broughton, David A Browne, Brett Buchea, Bob B Buckley, David A Buell, Tim Burger, Brian Burkett, Nicholas Bushnell, Anthony Cabrera, Juan Campero, Hung-Shen Chang, Yu Chen, Zijun Chen, Ben Chiaro, Desmond Chik, Charina Chou, Jahan Claes, Agnetta Y Cleland, Josh Cogan, Roberto Collins, Paul Conner, William Courtney, Alexander L Crook, Ben Curtin, Sayan Das, Alex Davies, Laura De Lorenzo, Dripto M Debroy, Sean Demura, Michel Devoret, Agustin Di Paolo, Paul Donohoe, Ilya Drozdov, Andrew Dunsworth, Clint Earle, Thomas Edlich, Alec Eickbusch, Aviv Moshe Elbag, Mahmoud Elzouka, Catherine Erickson, Lara Faoro, Edward Farhi, Vinicius S Ferreira, Leslie Flores Burgos, Ebrahim Forati, Austin G Fowler, Brooks Foxen, Suhas Ganjam, Gonzalo Garcia, Robert Gasca, Élie Genois, William Giang, Craig Gidney, Dar Gilboa, Raja Gosula, Alejandro Grajales Dau, Dietrich Graumann, Alex Greene, Jonathan A Gross, Steve Habegger, John Hall, Michael C Hamilton, Monica Hansen, Matthew P Harrigan, Sean D Harrington, Francisco JH Heras, Stephen Heslin, Paula Heu, Oscar Higgott, Gordon Hill, Jeremy Hilton, George Holland, Sabrina Hong, Hsin-Yuan Huang, Ashley Huff, William J Huggins, Lev B Ioffe, Sergei V Isakov, Justin Iveland, Evan Jeffrey, Zhang Jiang, Cody Jones, Stephen Jordan, Chaitali Joshi, Pavol Juhas, Dvir Kafri, Hui Kang, Amir H Karamlou, Kostyantyn Kechedzhi, Julian Kelly, Trupti Khaire, Tanuj Khattar, Mostafa Khezri, Seon Kim, Paul V Klimov, Andrey R Klots, Bryce Kobrin, Pushmeet Kohli, Alexander N Korotkov, Fedor Kostritsa, Robin Kothari, Borislav Kozlovskii, John Mark Kreikebaum, Vladislav D Kurilovich, Nathan Lacroix, David Landhuis, Tiano Lange-Dei, Brandon W Langley, Pavel Laptev, Kim-Ming Lau, Loïck Le Guevel, Justin Ledford, Kenny Lee, Yuri D Lensky, Shannon Leon, Brian J Lester, Wing Yan Li, Yin Li, Alexander T Lill, Wayne Liu, William P Livingston, Aditya Locharla, Erik Lucero, Daniel Lundahl, Aaron Lunt, Sid Madhuk, Fionn D Malone ·  arXiv preprint arXiv:2408.13687, 2024
Download PDF View
Quantum error correction provides a path to reach practical quantum computing by combining multiple physical qubits into a logical qubit, where the logical error rate is suppressed exponentially as more qubits are added. However, this exponential suppression only occurs if the physical error rate is below a critical threshold. In this work, we present two surface code memories operating below this threshold: a distance-7 code and a distance-5 code integrated with a real-time decoder. The logical error rate of our larger quantum memory is suppressed by a factor of = 2.14 0.02 when increasing the code distance by two, culminating in a 101-qubit distance-7 code with 0.143% 0.003% error per cycle of error correction. This logical memory is also beyond break-even, exceeding its best physical qubit's lifetime by a factor of 2.4 0.3. We maintain below-threshold performance when decoding in real time, achieving an average decoder latency of 63 s at distance-5 up to a million cycles, with a cycle time of 1.1 s. To probe the limits of our error-correction performance, we run repetition codes up to distance-29 and find that logical performance is limited by rare correlated error events occurring approximately once every hour, or 3 10 cycles. Our results present device performance that, if scaled, could realize the operational requirements of large scale fault-tolerant quantum algorithms.
Optimization by decoded quantum interferometry
Stephen P Jordan, Noah Shutty, Mary Wootters, Adam Zalcman, Alexander Schmidhuber, Robbie King, Sergei V Isakov, Ryan Babbush ·  arXiv preprint arXiv:2408.08292, 2024
Download PDF View
We introduce Decoded Quantum Interferometry (DQI), a quantum algorithm for reducing classical optimization problems to classical decoding problems by exploiting structure in the Fourier spectrum of the objective function. DQI reduces sparse max-XORSAT to decoding LDPC codes, which can be achieved using powerful classical algorithms such as Belief Propagation (BP). As an initial benchmark, we compare DQI using belief propagation decoding against classical optimization via simulated annealing. In this setting we present evidence that, for a certain family of max-XORSAT instances, DQI with BP decoding achieves a better approximation ratio on average than simulated annealing, although not better than specialized classical algorithms tailored to those instances. We also analyze a combinatorial optimization problem corresponding to finding polynomials that intersect the maximum number of points. There, DQI efficiently achieves a better approximation ratio than any polynomial-time classical algorithm known to us, thus realizing an apparent exponential quantum speedup. Finally, we show that the problem defined by Yamakawa and Zhandry in order to prove an exponential separation between quantum and classical query complexity is a special case of the optimization problem efficiently solved by DQI.
Measurement and feed forward induced entanglement negativity transition
Alireza Seif, Yu-Xin Wang, Ramis Movassagh, Aashish A Clerk ·  Physical Review Letters 133 (5), 050402, 2024
Download PDF View
We study the interplay between measurement-induced dynamics and conditional unitary evolution in quantum systems. We numerically and analytically investigate commuting random measurement and feed forward (MFF) processes and find a sharp transition in their ability to generate entanglement negativity as the number of MFF channels varies. We also establish a direct connection between these findings and transitions induced by random dephasing from an environment with broken time-reversal symmetry. In one variant of the problem, we employ free probability theory to rigorously prove the transition’s existence. Furthermore, these MFF processes have dynamic circuit representations that can be experimentally explored on current quantum computing platforms.
Shadow hamiltonian simulation
Rolando D Somma, Robbie King, Robin Kothari, Thomas O'Brien, Ryan Babbush ·  arXiv preprint arXiv:2407.21775, 2024
Download PDF View
We present shadow Hamiltonian simulation, a framework for simulating quantum dynamics using a compressed quantum state that we call the "shadow state". The amplitudes of this shadow state are proportional to the expectations of a set of operators of interest. The shadow state evolves according to its own Schr\"odinger equation, and under broad conditions can be simulated on a quantum computer. We analyze a number of applications of this framework to quantum simulation problems. This includes simulating the dynamics of exponentially large systems of free fermions, or exponentially large systems of free bosons, the latter example recovering a recent algorithm for simulating exponentially many classical harmonic oscillators. Shadow Hamiltonian simulation can be extended to simulate expectations of more complex operators such as two-time correlators or Green's functions, and to study the evolution of operators themselves in the Heisenberg picture.
Rise of conditionally clean ancillae for optimizing quantum circuits
Tanuj Khattar, Craig Gidney ·  arXiv preprint arXiv:2407.17966, 2024
Download PDF View
We argue by example that conditionally clean ancillae, recently described by [NZS24], should become a standard tool in the quantum circuit design kit. We use conditionally clean ancillae to reduce the gate counts and depths of several circuit constructions. In particular, we present: (a) n-controlled NOT using 2n Toffolis and O(log n) depth given 2 clean ancillae. (b) n-qubit incrementer using 3n Toffolis given log*(n) clean ancillae. (c) n-qubit quantum-classical comparator using 3n Toffolis given log*(n) clean ancillae. (d) unary iteration over [0, N) using 2.5N Toffolis given 2 clean ancillae. (e) unary iteration via skew tree over [0, N) using 1.25 N Toffolis given n dirty ancillae. We also describe a technique for laddered toggle detection to replace clean ancillae with dirty ancillae in all our constructions with a 2x Toffoli overhead. Our constructions achieve the lowest gate counts to date with sublinear ancilla requirements and should be useful building blocks to optimize circuits in the low-qubit regime of Early Fault Tolerance.
Zero and finite temperature quantum simulations powered by quantum magic
Andi Gu, Hong-Ye Hu, Di Luo, Taylor L Patti, Nicholas C Rubin, Susanne F Yelin ·  Quantum 8, 1422, 2024
Download PDF View
We introduce a quantum information theory-inspired method to improve the characterization of many-body Hamiltonians on near-term quantum devices. We design a new class of similarity transformations that, when applied as a preprocessing step, can substantially simplify a Hamiltonian for subsequent analysis on quantum hardware. By design, these transformations can be identified and applied efficiently using purely classical resources. In practice, these transformations allow us to shorten requisite physical circuit-depths, overcoming constraints imposed by imperfect near-term hardware. Importantly, the quality of our transformations is $ tunable $: we define a'ladder'of transformations that yields increasingly simple Hamiltonians at the cost of more classical computation. Using quantum chemistry as a benchmark application, we demonstrate that our protocol leads to significant performance improvements for zero and finite temperature free energy calculations on both digital and analog quantum hardware. Specifically, our energy estimates not only outperform traditional Hartree-Fock solutions, but this performance gap also consistently widens as we tune up the quality of our transformations. In short, our quantum information-based approach opens promising new pathways to realizing useful and feasible quantum chemistry algorithms on near-term hardware.
Random unitaries in extremely low depth
Thomas Schuster, Jonas Haferkamp, Hsin-Yuan Huang ·  arXiv preprint arXiv:2407.07754, 2024
Download PDF View
We prove that random quantum circuits on any geometry, including a 1D line, can form approximate unitary designs over qubits in depth. In a similar manner, we construct pseudorandom unitaries (PRUs) in 1D circuits in depth, and in all-to-all-connected circuits in depth. In all three cases, the dependence is optimal and improves exponentially over known results. These shallow quantum circuits have low complexity and create only short-range entanglement, yet are indistinguishable from unitaries with exponential complexity. Our construction glues local random unitaries on -sized or -sized patches of qubits to form a global random unitary on all qubits. In the case of designs, the local unitaries are drawn from existing constructions of approximate unitary -designs, and hence also inherit an optimal scaling in . In the case of PRUs, the local unitaries are drawn from existing unitary ensembles conjectured to form PRUs. Applications of our results include proving that classical shadows with 1D log-depth Clifford circuits are as powerful as those with deep circuits, demonstrating superpolynomial quantum advantage in learning low-complexity physical systems, and establishing quantum hardness for recognizing phases of matter with topological order.
Efficient state preparation for the quantum simulation of molecules in first quantization
William J Huggins, Oskar Leimkuhler, Torin F Stetina, K Birgitta Whaley ·  arXiv preprint arXiv:2407.00249, 2024
Download PDF View
The quantum simulation of real molecules and materials is one of the most highly anticipated applications of quantum computing. Algorithms for simulating electronic structure using a first-quantized plane wave representation are especially promising due to their asymptotic efficiency. However, previous proposals for preparing initial states for these simulation algorithms scale poorly with the size of the basis set. We address this shortcoming by showing how to efficiently map states defined in a Gaussian type orbital basis to a plane wave basis with a scaling that is logarithmic in the number of plane waves. Our key technical result is a proof that molecular orbitals constructed from Gaussian type basis functions can be compactly represented in a plane wave basis using matrix product states. While we expect that other approaches could achieve the same logarithmic scaling with respect to basis set size, our proposed state preparation technique is also highly efficient in practice. For example, in a series of numerical experiments on small molecules, we find that our approach allows us to prepare an approximation to the Hartree-Fock state using orders of magnitude fewer non-Clifford gates than a naive approach. By resolving the issue of state preparation, our work allows for the first quantum simulation of molecular systems whose end-to-end complexity is truly sublinear in the basis set size.
Quantum merkle trees
Lijie Chen, Ramis Movassagh ·  Quantum 8, 1380, 2024
Download PDF View
Committing to information is a central task in cryptography, where a party (typically called a prover) stores a piece of information (eg, a bit string) with the promise of not changing it. This information can be accessed by another party (typically called the verifier), who can later learn the information and verify that it was not meddled with. Merkle trees [1] are a well-known construction for doing so in a succinct manner, in which the verifier can learn any part of the information by receiving a short proof from the honest prover. Despite its significance in classical cryptography, there was no quantum analog of the Merkle tree. A direct generalization using the Quantum Random Oracle Model (QROM)[2] does not seem to be secure. In this work, we propose the $\textit {quantum Merkle tree} $. It is based on what we call the $\textit {Quantum Haar Random Oracle Model} $(QHROM). In QHROM, both the prover and the verifier have access to a $ Haar $ random quantum oracle $ G $ and its inverse.
Random insights into the complexity of two-dimensional tensor network calculations
Sofía González-García, Shengqi Sang, Timothy H Hsieh, Sergio Boixo, Guifré Vidal, Andrew C Potter, Romain Vasseur ·  Physical Review B 109 (23), 235102, 2024
Download PDF View
Projected entangled pair states (PEPS) offer memory-efficient representations of some quantum many-body states that obey an entanglement area law and are the basis for classical simulations of ground states in two-dimensional (2d) condensed matter systems. However, rigorous results show that exactly computing observables from a 2d PEPS state is generically a computationally hard problem. Yet approximation schemes for computing properties of 2d PEPS are regularly used, and empirically seen to succeed, for a large subclass of (“not too entangled”) condensed matter ground states. Adopting the philosophy of random matrix theory, in this work, we analyze the complexity of approximately contracting a 2d random PEPS by exploiting an analytic mapping to an effective replicated statistical mechanics model that permits a controlled analysis at a large bond dimension. Through this statistical-mechanics lens …
Learning shallow quantum circuits
Hsin-Yuan Huang, Yunchao Liu, Michael Broughton, Isaac Kim, Anurag Anshu, Zeph Landau, Jarrod R McClean ·  Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 1343-1351, 2024
Download PDF View
Despite fundamental interests in learning quantum circuits, the existence of a computationally efficient algorithm for learning shallow quantum circuits remains an open question. Because shallow quantum circuits can generate distributions that are classically hard to sample from, existing learning algorithms do not apply. In this work, we present a polynomial-time classical algorithm for learning the description of any unknown n-qubit shallow quantum circuit U (with arbitrary unknown architecture) within a small diamond distance using single-qubit measurement data on the output states of U. We also provide a polynomial-time classical algorithm for learning the description of any unknown n-qubit state | ψ ⟩ = U | 0n ⟩ prepared by a shallow quantum circuit U (on a 2D lattice) within a small trace distance using single-qubit measurements on copies of | ψ ⟩. Our approach uses a quantum circuit representation based on …
Local minima in quantum systems
Chi-Fang Chen, Hsin-Yuan Huang, John Preskill, Leo Zhou ·  Proceedings of the 56th Annual ACM Symposium On Theory Of Computing, 1323-1330, 2024
Download PDF View
Finding ground states of quantum many-body systems is known to be hard for both classical and quantum computers. As a result, when Nature cools a quantum system in a low-temperature thermal bath, the ground state cannot always be found efficiently. Instead, Nature finds a local minimum of the energy. In this work, we study the problem of finding local minima in quantum systems under thermal perturbations. While local minima are much easier to find than ground states, we show that finding a local minimum is computationally hard for classical computers, even when the task is to output a single-qubit observable at any local minimum. In contrast, we prove that a quantum computer can always find a local minimum efficiently using a thermal gradient descent algorithm that mimics the cooling process in Nature. To establish the classical hardness of finding local minima, we consider a family of two-dimensional …
Quantum computation of stopping power for inertial fusion target design
Nicholas C Rubin, Dominic W Berry, Alina Kononov, Fionn D Malone, Tanuj Khattar, Alec White, Joonho Lee, Hartmut Neven, Ryan Babbush, Andrew D Baczewski ·  Proceedings of the National Academy of Sciences 121 (23), e2317772121, 2024
Download PDF View
Stopping power is the rate at which a material absorbs the kinetic energy of a charged particle passing through it—one of many properties needed over a wide range of thermodynamic conditions in modeling inertial fusion implosions. First-principles stopping calculations are classically challenging because they involve the dynamics of large electronic systems far from equilibrium, with accuracies that are particularly difficult to constrain and assess in the warm-dense conditions preceding ignition. Here, we describe a protocol for using a fault-tolerant quantum computer to calculate stopping power from a first-quantized representation of the electrons and projectile. Our approach builds upon the electronic structure block encodings of Su et al. [PRX Quant. 2, 040332 (2021)], adapting and optimizing those algorithms to estimate observables of interest from the non-Born–Oppenheimer dynamics of multiple particle …
Tailored and externally corrected coupled cluster with quantum inputs
Maximilian Scheurer, Gian-Luca R Anselmetti, Oumarou Oumarou, Christian Gogolin, Nicholas C Rubin ·  Journal of Chemical Theory and Computation 20 (12), 5068-5093, 2024
Download PDF View
We propose to use wave function overlaps obtained from a quantum computer as inputs for the classical split-amplitude techniques, tailored and externally corrected coupled cluster, to achieve balanced treatment of static and dynamic correlation effects in molecular electronic structure simulations. By combining insights from statistical properties of matchgate shadows, which are used to measure quantum trial state overlaps, with classical correlation diagnostics, we can provide quantum resource estimates well into the classically no longer exactly solvable regime. We find that rather imperfect wave functions and remarkably low shot counts are sufficient to cure qualitative failures of plain coupled cluster singles doubles and to obtain chemically precise dynamic correlation energy corrections. We provide insights into which wave function preparation schemes have a chance of yielding quantum advantage, and we …
Efficiently constructing a quantum uniform superposition over bit strings near a binary linear code
Edward Farhi, Stephen P Jordan ·  arXiv preprint arXiv:2404.16129, 2024
Download PDF View
We demonstrate that a high fidelity approximation to , the quantum superposition over all bit strings within Hamming distance of the codewords of a dimension- linear code over , can be efficiently constructed by a quantum circuit for large values of , and which we characterize. We do numerical experiments at which back up our claims. The achievable radius is much larger than the distance out to which known classical algorithms can efficiently find the nearest codeword. Hence, these states cannot be prepared by quantum constuctions that require uncomputing to find the codeword nearest a string. Unlike the analogous states for lattices in , is not a useful resource for bounded distance decoding because the relevant overlap falls off too quickly with distance and known classical algorithms do better. Furthermore the overlap calculation can be dequantized. Perhaps these states could be used to solve other code problems. The technique used to construct these states is of interest and hopefully will have applications beyond codes.
Dynamics of magnetization at infinite temperature in a Heisenberg spin chain
Eliott Rosenberg, TI Andersen, Rhine Samajdar, Andre Petukhov, JC Hoke, Dmitry Abanin, Andreas Bengtsson, IK Drozdov, Catherine Erickson, PV Klimov, Xiao Mi, Alexis Morvan, Matthew Neeley, Charles Neill, Rajeev Acharya, Richard Allen, Kyle Anderson, Markus Ansmann, Frank Arute, Kunal Arya, Abraham Asfaw, Juan Atalaya, JC Bardin, A Bilmes, Gina Bortoli, Alexandre Bourassa, Jenna Bovaird, Leon Brill, Michael Broughton, Bob B Buckley, DA Buell, Tim Burger, Brian Burkett, Nicholas Bushnell, Juan Campero, H-S Chang, Zijun Chen, Benjamin Chiaro, Desmond Chik, Josh Cogan, Roberto Collins, Paul Conner, William Courtney, AL Crook, Ben Curtin, DM Debroy, A Del Toro Barba, Sean Demura, Agustin Di Paolo, Andrew Dunsworth, Clint Earle, L Faoro, E Farhi, Reza Fatemi, VS Ferreira, L Flores Burgos, Ebrahim Forati, AG Fowler, Brooks Foxen, Gonzalo Garcia, Élie Genois, William Giang, Craig Gidney, Dar Gilboa, Marissa Giustina, Raja Gosula, A Grajales Dau, JA Gross, Steve Habegger, MC Hamilton, Monica Hansen, MP Harrigan, SD Harrington, Paula Heu, Gordon Hill, MR Hoffmann, Sabrina Hong, Trent Huang, Ashley Huff, WJ Huggins, LB Ioffe, SV Isakov, Justin Iveland, Evan Jeffrey, Zhang Jiang, Cody Jones, Pavol Juhas, D Kafri, Tanuj Khattar, Mostafa Khezri, Mária Kieferová, Seon Kim, Alexei Kitaev, AR Klots, AN Korotkov, Fedor Kostritsa, John Mark Kreikebaum, David Landhuis, Pavel Laptev, K-M Lau, Lily Laws, Joonho Lee, KW Lee, YD Lensky, BJ Lester, AT Lill, Wayne Liu, A Locharla, Salvatore Mandrà, Orion Martin, Steven Martin, JR McClean, Matthew McEwen, Seneca Meeks, KC Miao, Amanda Mieszala, Shirin Montazeri, Ramis Movassagh, Wojciech Mruczkiewicz, Ani Nersisyan, Michael Newman, Jiun How Ng, Anthony Nguyen, Murray Nguyen, MY Niu, TE O’Brien, Seun Omonije, Alex Opremcak, Rebecca Potter, LP Pryadko, Chris Quintana, DM Rhodes, Charles Rocque, NC Rubin, Negar Saei, Daniel Sank, Kannan Sankaragomathi, KJ Satzinger, HF Schurkus, Christopher Schuster, MJ Shearn, Aaron Shorter, Noah Shutty, Vladimir Shvarts, Volodymyr Sivak, Jindra Skruzny, W Clarke Smith, RD Somma, George Sterling, Doug Strain ·  Science 384 (6691), 48-53, 2024
Download PDF View
Understanding universal aspects of quantum dynamics is an unresolved problem in statistical mechanics. In particular, the spin dynamics of the one-dimensional Heisenberg model were conjectured as to belong to the Kardar-Parisi-Zhang (KPZ) universality class based on the scaling of the infinite-temperature spin-spin correlation function. In a chain of 46 superconducting qubits, we studied the probability distribution of the magnetization transferred across the chain’s center, PM. The first two moments of PM show superdiffusive behavior, a hallmark of KPZ universality. However, the third and fourth moments ruled out the KPZ conjecture and allow for evaluating other theories. Our results highlight the importance of studying higher moments in determining dynamic universality classes and provide insights into universal behavior in quantum systems.
Drug design on quantum computers
Raffaele Santagati, Alan Aspuru-Guzik, Ryan Babbush, Matthias Degroote, Leticia González, Elica Kyoseva, Nikolaj Moll, Markus Oppel, Robert M Parrish, Nicholas C Rubin, Michael Streif, Christofer S Tautermann, Horst Weiss, Nathan Wiebe, Clemens Utschig-Utschig ·  Nature Physics 20 (4), 549-557, 2024
Download PDF View
The promised industrial applications of quantum computers often rest on their anticipated ability to perform accurate, efficient quantum chemical calculations. Computational drug discovery relies on accurate predictions of how candidate drugs interact with their targets in a cellular environment involving several thousands of atoms at finite temperatures. Although quantum computers are still far from being used as daily tools in the pharmaceutical industry, here we explore the challenges and opportunities of applying quantum computers to drug design. We discuss where these could transform industrial research and identify the substantial further developments needed to reach this goal.
Stable quantum-correlated many-body states through engineered dissipation
Xiao Mi, AA Michailidis, Sara Shabani, KC Miao, PV Klimov, J Lloyd, E Rosenberg, R Acharya, I Aleiner, TI Andersen, M Ansmann, F Arute, K Arya, A Asfaw, J Atalaya, JC Bardin, A Bengtsson, G Bortoli, A Bourassa, J Bovaird, L Brill, M Broughton, BB Buckley, DA Buell, T Burger, B Burkett, N Bushnell, Z Chen, B Chiaro, D Chik, C Chou, J Cogan, R Collins, P Conner, W Courtney, AL Crook, B Curtin, AG Dau, DM Debroy, A Del Toro Barba, S Demura, A Di Paolo, IK Drozdov, A Dunsworth, C Erickson, L Faoro, E Farhi, R Fatemi, VS Ferreira, LF Burgos, E Forati, AG Fowler, B Foxen, É Genois, W Giang, C Gidney, D Gilboa, M Giustina, R Gosula, JA Gross, S Habegger, MC Hamilton, M Hansen, MP Harrigan, SD Harrington, P Heu, MR Hoffmann, S Hong, T Huang, A Huff, WJ Huggins, LB Ioffe, SV Isakov, J Iveland, E Jeffrey, Z Jiang, C Jones, P Juhas, D Kafri, K Kechedzhi, T Khattar, M Khezri, M Kieferová, S Kim, A Kitaev, AR Klots, AN Korotkov, F Kostritsa, JM Kreikebaum, D Landhuis, P Laptev, K-M Lau, L Laws, J Lee, KW Lee, YD Lensky, BJ Lester, AT Lill, W Liu, A Locharla, FD Malone, O Martin, JR McClean, M McEwen, A Mieszala, S Montazeri, A Morvan, R Movassagh, W Mruczkiewicz, M Neeley, C Neill, A Nersisyan, M Newman, JH Ng, A Nguyen, M Nguyen, MY Niu, TE O’Brien, A Opremcak, A Petukhov, R Potter, LP Pryadko, C Quintana, C Rocque, NC Rubin, N Saei, D Sank, K Sankaragomathi, KJ Satzinger, HF Schurkus, C Schuster, MJ Shearn, A Shorter, N Shutty, V Shvarts, J Skruzny, WC Smith, R Somma, G Sterling, D Strain, M Szalay, A Torres, G Vidal, B Villalonga, CV Heidweiller, T White, BWK Woo, C Xing, ZJ Yao, P Yeh ·  Science 383 (6689), 1332-1337, 2024
Download PDF View
Engineered dissipative reservoirs have the potential to steer many-body quantum systems toward correlated steady states useful for quantum simulation of high-temperature superconductivity or quantum magnetism. Using up to 49 superconducting qubits, we prepared low-energy states of the transverse-field Ising model through coupling to dissipative auxiliary qubits. In one dimension, we observed long-range quantum correlations and a ground-state fidelity of 0.86 for 18 qubits at the critical point. In two dimensions, we found mutual information that extends beyond nearest neighbors. Lastly, by coupling the system to auxiliaries emulating reservoirs with different chemical potentials, we explored transport in the quantum Heisenberg model. Our results establish engineered dissipation as a scalable alternative to unitary evolution for preparing entangled many-body states on noisy quantum processors.
Optimizing quantum gates towards the scale of logical qubits
Paul V Klimov, Andreas Bengtsson, Chris Quintana, Alexandre Bourassa, Sabrina Hong, Andrew Dunsworth, Kevin J Satzinger, William P Livingston, Volodymyr Sivak, Murphy Yuezhen Niu, Trond I Andersen, Yaxing Zhang, Desmond Chik, Zijun Chen, Charles Neill, Catherine Erickson, Alejandro Grajales Dau, Anthony Megrant, Pedram Roushan, Alexander N Korotkov, Julian Kelly, Vadim Smelyanskiy, Yu Chen, Hartmut Neven ·  Nature Communications 15 (1), 2442, 2024
Download PDF View
A foundational assumption of quantum error correction theory is that quantum gates can be scaled to large processors without exceeding the error-threshold for fault tolerance. Two major challenges that could become fundamental roadblocks are manufacturing high-performance quantum hardware and engineering a control system that can reach its performance limits. The control challenge of scaling quantum gates from small to large processors without degrading performance often maps to non-convex, high-constraint, and time-dynamic control optimization over an exponentially expanding configuration space. Here we report on a control optimization strategy that can scalably overcome the complexity of such problems. We demonstrate it by choreographing the frequency trajectories of 68 frequency-tunable superconducting qubits to execute single- and two-qubit gates while mitigating computational errors …
Model-based optimization of superconducting qubit readout
Andreas Bengtsson, Alex Opremcak, Mostafa Khezri, Daniel Sank, Alexandre Bourassa, Kevin J Satzinger, Sabrina Hong, Catherine Erickson, Brian J Lester, Kevin C Miao, Alexander N Korotkov, Julian Kelly, Zijun Chen, Paul V Klimov ·  Physical Review Letters 132 (10), 100603, 2024
Download PDF View
Measurement is an essential component of quantum algorithms, and for superconducting qubits it is often the most error prone. Here, we demonstrate model-based readout optimization achieving low measurement errors while avoiding detrimental side effects. For simultaneous and midcircuit measurements across 17 qubits, we observe 1.5% error per qubit with a 500 ns end-to-end duration and minimal excess reset error from residual resonator photons. We also suppress measurement-induced state transitions achieving a leakage rate limited by natural heating. This technique can scale to hundreds of qubits and be used to enhance the performance of error-correcting codes and near-term applications.
Learning conservation laws in unknown quantum dynamics
Yongtao Zhan, Andreas Elben, Hsin-Yuan Huang, Yu Tong ·  PRX Quantum 5 (1), 010350, 2024
Download PDF View
We present a learning algorithm for discovering conservation laws given as sums of geometrically local observables in quantum dynamics. This includes conserved quantities that arise from local and global symmetries in closed and open quantum many-body systems. The algorithm combines the classical shadow formalism for estimating expectation values of observable and data analysis techniques based on singular value decompositions and robust polynomial interpolation to discover all such conservation laws in unknown quantum dynamics with rigorous performance guarantees. Our method can be directly realized in quantum experiments, which we illustrate with numerical simulations, using closed and open quantum system dynamics in a gauge theory and in many-body localized spin chains.
A hybrid quantum algorithm to detect conical intersections
Emiel Koridon, Joana Fraxanet, Alexandre Dauphin, Lucas Visscher, Thomas E O'Brien, Stefano Polla ·  Quantum 8, 1259, 2024
Download PDF View
Conical intersections are topologically protected crossings between the potential energy surfaces of a molecular Hamiltonian, known to play an important role in chemical processes such as photoisomerization and non-radiative relaxation. They are characterized by a non-zero Berry phase, which is a topological invariant defined on a closed path in atomic coordinate space, taking the value when the path encircles the intersection manifold. In this work, we show that for real molecular Hamiltonians, the Berry phase can be obtained by tracing a local optimum of a variational ansatz along the chosen path and estimating the overlap between the initial and final state with a control-free Hadamard test. Moreover, by discretizing the path into points, we can use single Newton-Raphson steps to update our state non-variationally. Finally, since the Berry phase can only take two discrete values (0 or ), our procedure succeeds even for a cumulative error bounded by a constant; this allows us to bound the total sampling cost and to readily verify the success of the procedure. We demonstrate numerically the application of our algorithm on small toy models of the formaldimine molecule ().
Analyzing prospects for quantum advantage in topological data analysis
Dominic W Berry, Yuan Su, Casper Gyurik, Robbie King, Joao Basso, Alexander Del Toro Barba, Abhishek Rajput, Nathan Wiebe, Vedran Dunjko, Ryan Babbush ·  PRX Quantum 5 (1), 010319, 2024
Download PDF View
Lloyd et al. [Nat. Commun. 7, 10138 (2016)] were first to demonstrate the promise of quantum algorithms for computing Betti numbers, a way to characterize topological features of data sets. Here, we propose, analyze, and optimize an improved quantum algorithm for topological data analysis (TDA) with reduced scaling, including a method for preparing Dicke states based on inequality testing, a more efficient amplitude estimation algorithm using Kaiser windows, and an optimal implementation of eigenvalue projectors based on Chebyshev polynomials. We compile our approach to a fault-tolerant gate set and estimate constant factors in the Toffoli complexity. Our analysis reveals that superquadratic quantum speedups are only possible for this problem when targeting a multiplicative error approximation and the Betti number grows asymptotically. Further, we propose a dequantization of the quantum TDA algorithm …
Improved machine learning algorithm for predicting ground state properties
Laura Lewis, Hsin-Yuan Huang, Viet T Tran, Sebastian Lehner, Richard Kueng, John Preskill ·  nature communications 15 (1), 895, 2024
Download PDF View
Finding the ground state of a quantum many-body system is a fundamental problem in quantum physics. In this work, we give a classical machine learning (ML) algorithm for predicting ground state properties with an inductive bias encoding geometric locality. The proposed ML model can efficiently predict ground state properties of an n-qubit gapped local Hamiltonian after learning from only data about other Hamiltonians in the same quantum phase of matter. This improves substantially upon previous results that require data for a large constant c. Furthermore, the training and prediction time of the proposed ML model scale as in the number of qubits n. Numerical experiments on physical systems with up to 45 qubits confirm the favorable scaling in predicting ground state properties using a small training dataset.
On quantum backpropagation, information reuse, and cheating measurement collapse
Amira Abbas, Robbie King, Hsin-Yuan Huang, William J Huggins, Ramis Movassagh, Dar Gilboa, Jarrod McClean ·  Advances in Neural Information Processing Systems 36, 44792-44819, 2023
Download PDF View
The success of modern deep learning hinges on the ability to train neural networks at scale. Through clever reuse of intermediate information, backpropagation facilitates training through gradient computation at a total cost roughly proportional to running the function, rather than incurring an additional factor proportional to the number of parameters--which can now be in the trillions. Naively, one expects that quantum measurement collapse entirely rules out the reuse of quantum information as in backpropagation. But recent developments in shadow tomography, which assumes access to multiple copies of a quantum state, have challenged that notion. Here, we investigate whether parameterized quantum models can train as efficiently as classical neural networks. We show that achieving backpropagation scaling is impossible without access to multiple copies of a state. With this added ability, we introduce an algorithm with foundations in shadow tomography that matches backpropagation scaling in quantum resources while reducing classical auxiliary computational costs to open problems in shadow tomography. These results highlight the nuance of reusing quantum information for practical purposes and clarify the unique difficulties in training large quantum models, which could alter the course of quantum machine learning.
The discrete adiabatic quantum linear system solver has lower constant factors than the randomized adiabatic solver
Pedro Costa, Dong An, Ryan Babbush, Dominic Berry ·  arXiv preprint arXiv:2312.07690, 2023
Download PDF View
The solution of linear systems of equations is the basis of many other quantum algorithms, and recent results provided an algorithm with optimal scaling in both the condition number and the allowable error [PRX Quantum \textbf{3}, 0403003 (2022)]. That work was based on the discrete adiabatic theorem, and worked out an explicit constant factor for an upper bound on the complexity. Here we show via numerical testing on random matrices that the constant factor is in practice about 1,500 times smaller than the upper bound found numerically in the previous results. That means that this approach is far more efficient than might naively be expected from the upper bound. In particular, it is over an order of magnitude more efficient than using a randomised approach from [arXiv:2305.11352] that claimed to be more efficient.
Overcoming leakage in quantum error correction
Kevin C Miao, Matt McEwen, Juan Atalaya, Dvir Kafri, Leonid P Pryadko, Andreas Bengtsson, Alex Opremcak, Kevin J Satzinger, Zijun Chen, Paul V Klimov, Chris Quintana, Rajeev Acharya, Kyle Anderson, Markus Ansmann, Frank Arute, Kunal Arya, Abraham Asfaw, Joseph C Bardin, Alexandre Bourassa, Jenna Bovaird, Leon Brill, Bob B Buckley, David A Buell, Tim Burger, Brian Burkett, Nicholas Bushnell, Juan Campero, Ben Chiaro, Roberto Collins, Paul Conner, Alexander L Crook, Ben Curtin, Dripto M Debroy, Sean Demura, Andrew Dunsworth, Catherine Erickson, Reza Fatemi, Vinicius S Ferreira, Leslie Flores Burgos, Ebrahim Forati, Austin G Fowler, Brooks Foxen, Gonzalo Garcia, William Giang, Craig Gidney, Marissa Giustina, Raja Gosula, Alejandro Grajales Dau, Jonathan A Gross, Michael C Hamilton, Sean D Harrington, Paula Heu, Jeremy Hilton, Markus R Hoffmann, Sabrina Hong, Trent Huang, Ashley Huff, Justin Iveland, Evan Jeffrey, Zhang Jiang, Cody Jones, Julian Kelly, Seon Kim, Fedor Kostritsa, John Mark Kreikebaum, David Landhuis, Pavel Laptev, Lily Laws, Kenny Lee, Brian J Lester, Alexander T Lill, Wayne Liu, Aditya Locharla, Erik Lucero, Steven Martin, Anthony Megrant, Xiao Mi, Shirin Montazeri, Alexis Morvan, Ofer Naaman, Matthew Neeley, Charles Neill, Ani Nersisyan, Michael Newman, Jiun How Ng, Anthony Nguyen, Murray Nguyen, Rebecca Potter, Charles Rocque, Pedram Roushan, Kannan Sankaragomathi, Henry F Schurkus, Christopher Schuster, Michael J Shearn, Aaron Shorter, Noah Shutty, Vladimir Shvarts, Jindra Skruzny, W Clarke Smith, George Sterling, Marco Szalay, Douglas Thor, Alfredo Torres, Theodore White, Bryan WK Woo, Z Jamie Yao, Ping Yeh, Juhwan Yoo, Grayson Young, Adam Zalcman, Ningfeng Zhu, Nicholas Zobrist, Hartmut Neven, Vadim Smelyanskiy, Andre Petukhov, Alexander N Korotkov, Daniel Sank, Yu Chen ·  Nature Physics 19 (12), 1780-1786, 2023
Download PDF View
The leakage of quantum information out of the two computational states of a qubit into other energy states represents a major challenge for quantum error correction. During the operation of an error-corrected algorithm, leakage builds over time and spreads through multi-qubit interactions. This leads to correlated errors that degrade the exponential suppression of the logical error with scale, thus challenging the feasibility of quantum error correction as a path towards fault-tolerant quantum computation. Here, we demonstrate a distance-3 surface code and distance-21 bit-flip code on a quantum processor for which leakage is removed from all qubits in each cycle. This shortens the lifetime of leakage and curtails its ability to spread and induce correlated errors. We report a tenfold reduction in the steady-state leakage population of the data qubits encoding the logical state and an average leakage population of less …
Purification-based quantum error mitigation of pair-correlated electron simulations
Thomas E O’Brien, G Anselmetti, Fotios Gkritsis, VE Elfving, Stefano Polla, William J Huggins, Oumarou Oumarou, Kostyantyn Kechedzhi, Dmitry Abanin, Rajeev Acharya, Igor Aleiner, Richard Allen, Trond Ikdahl Andersen, Kyle Anderson, Markus Ansmann, Frank Arute, Kunal Arya, Abraham Asfaw, Juan Atalaya, JC Bardin, Andreas Bengtsson, G Bortoli, A Bourassa, J Bovaird, L Brill, M Broughton, B Buckley, David A Buell, Tim Burger, Brian Burkett, Nicholas Bushnell, J Campero, Z Chen, Benjamin Chiaro, D Chik, J Cogan, Roberto Collins, Paul Conner, William Courtney, AL Crook, Ben Curtin, Dripto M Debroy, Sean Demura, Ilya Drozdov, Andrew Dunsworth, C Erickson, L Faoro, E Farhi, R Fatemi, VS Ferreira, L Flores Burgos, E Forati, AG Fowler, B Foxen, W Giang, C Gidney, D Gilboa, M Giustina, R Gosula, A Grajales Dau, Jonathan Arthur Gross, Steve Habegger, Michael C Hamilton, M Hansen, MP Harrigan, SD Harrington, P Heu, Markus Rudolf Hoffmann, Sabrina Hong, Trent Huang, A Huff, LB Ioffe, SV Isakov, J Iveland, Evan Jeffrey, Z Jiang, C Jones, P Juhas, D Kafri, Tanuj Khattar, Mostafa Khezri, Marika Kieferová, Seon Kim, Paul Victor Klimov, AR Klots, AN Korotkov, Fedor Kostritsa, John Mark Kreikebaum, Dave Landhuis, Pavel Laptev, K-M Lau, L Laws, Joonho Lee, Kenny Lee, BJ Lester, Alexander T Lill, Wayne Liu, WP Livingston, A Locharla, FD Malone, S Mandrà, O Martin, S Martin, JR McClean, T McCourt, M McEwen, X Mi, A Mieszala, KC Miao, M Mohseni, S Montazeri, A Morvan, R Movassagh, W Mruczkiewicz, O Naaman, M Neeley, C Neill, A Nersisyan, M Newman, JH Ng, A Nguyen, M Nguyen, MY Niu, S Omonije, A Opremcak, A Petukhov, R Potter, LP Pryadko, C Quintana, C Rocque, P Roushan, N Saei, D Sank, K Sankaragomathi, KJ Satzinger, HF Schurkus, C Schuster, MJ Shearn, A Shorter, N Shutty, V Shvarts, J Skruzny, WC Smith, RD Somma, G Sterling, D Strain, M Szalay, D Thor, A Torres, G Vidal ·  Nature Physics 19 (12), 1787-1792, 2023
Download PDF View
An important measure of the development of quantum computing platforms has been the simulation of increasingly complex physical systems. Before fault-tolerant quantum computing, robust error-mitigation strategies were necessary to continue this growth. Here, we validate recently introduced error-mitigation strategies that exploit the expectation that the ideal output of a quantum algorithm would be a pure state. We consider the task of simulating electron systems in the seniority-zero subspace where all electrons are paired with their opposite spin. This affords a computational stepping stone to a fully correlated model. We compare the performance of error mitigations on the basis of doubling quantum resources in time or in space on up to 20 qubits of a superconducting qubit quantum processor. We observe a reduction of error by one to two orders of magnitude below less sophisticated techniques such as …
Learning quantum systems via out-of-time-order correlators
Thomas Schuster, Murphy Niu, Jordan Cotler, Thomas O'Brien, Jarrod R McClean, Masoud Mohseni ·  Physical Review Research 5 (4), 043284, 2023
Download PDF View
Learning the properties of dynamical quantum systems underlies applications ranging from nuclear magnetic resonance spectroscopy to quantum device characterization. A central challenge in this pursuit is the learning of strongly interacting systems, where conventional observables decay quickly in time and space, limiting the information that can be learned from their measurement. In this work, we introduce a new class of observables into the context of quantum learning—the out-of-time-order correlator—which we show can substantially improve the learnability of strongly interacting systems by virtue of displaying informative physics at large times and distances. We identify two general scenarios in which out-of-time-order correlators provide a significant learning advantage: (i) when experimental access to the system is spatially restricted, for example, via a single “probe” degree of freedom, and (ii) when one …
Matchgate shadows for fermionic quantum simulation
Kianna Wan, William J Huggins, Joonho Lee, Ryan Babbush ·  Communications in Mathematical Physics 404 (2), 629-700, 2023
Download PDF View
“Classical shadows” are estimators of an unknown quantum state, constructed from suitably distributed random measurements on copies of that state (Huang et al. in Nat Phys 16:1050, 2020, https://doi.org/10.1038/s41567-020-0932-7). In this paper, we analyze classical shadows obtained using random matchgate circuits, which correspond to fermionic Gaussian unitaries. We prove that the first three moments of the Haar distribution over the continuous group of matchgate circuits are equal to those of the discrete uniform distribution over only the matchgate circuits that are also Clifford unitaries; thus, the latter forms a “matchgate 3-design.” This implies that the classical shadows resulting from the two ensembles are functionally equivalent. We show how one can use these matchgate shadows to efficiently estimate inner products between an arbitrary quantum state and fermionic Gaussian states, as well as the …
Compilation of product-formula Hamiltonian simulation via reinforcement learning
Lea M Trenkwalder, Eleanor Scerri, Thomas E O'Brien, Vedran Dunjko ·  arXiv preprint arXiv:2311.04285, 2023
Download PDF View
Hamiltonian simulation is believed to be one of the first tasks where quantum computers can yield a quantum advantage. One of the most popular methods of Hamiltonian simulation is Trotterization, which makes use of the approximation and higher-order corrections thereto. However, this leaves open the question of the order of operations (i.e. the order of the product over , which is known to affect the quality of approximation). In some cases this order is fixed by the desire to minimise the error of approximation; when it is not the case, we propose that the order can be chosen to optimize compilation to a native quantum architecture. This presents a new compilation problem -- order-agnostic quantum circuit compilation -- which we prove is NP-hard in the worst case. In lieu of an easily-computable exact solution, we turn to methods of heuristic optimization of compilation. We focus on reinforcement learning due to the sequential nature of the compilation task, comparing it to simulated annealing and Monte Carlo tree search. While two of the methods outperform a naive heuristic, reinforcement learning clearly outperforms all others, with a gain of around 12% with respect to the second-best method and of around 50% compared to the naive heuristic in terms of the gate count. We further test the ability of RL to generalize across instances of the compilation problem, and find that a single learner is able to solve entire problem families. This demonstrates the ability of machine learning techniques to provide assistance in an order-agnostic quantum compilation task.
Relaxing hardware requirements for surface code circuits using time-dynamics
Matt McEwen, Dave Bacon, Craig Gidney ·  Quantum 7, 1172, 2023
Download PDF View
The typical time-independent view of quantum error correction (QEC) codes hides significant freedom in the decomposition into circuits that are executable on hardware. Using the concept of detecting regions, we design time-dynamic QEC circuits directly instead of designing static QEC codes to decompose into circuits. In particular, we improve on the standard circuit constructions for the surface code, presenting new circuits that can embed on a hexagonal grid instead of a square grid, that can use ISWAP gates instead of CNOT or CZ gates, that can exchange qubit data and measure roles, and that move logical patches around the physical qubit grid while executing. All these constructions use no additional entangling gate layers and display essentially the same logical performance, having teraquop footprints within 25% of the standard surface code circuit. We expect these circuits to be of great interest to quantum hardware engineers, because they achieve essentially the same logical performance as standard surface code circuits while relaxing demands on hardware.
Josephson parametric amplifier with Chebyshev gain profile and high saturation
Ryan Kaufman, Theodore White, Mark I Dykman, Andrea Iorio, George Sterling, Sabrina Hong, Alex Opremcak, Andreas Bengtsson, Lara Faoro, Joseph C Bardin, Tim Burger, Robert Gasca, Ofer Naaman ·  Physical Review Applied 20 (5), 054058, 2023
Download PDF View
We demonstrate a Josephson parametric amplifier design with a band-pass impedance-matching network based on a third-order Chebyshev prototype. We measured eight amplifiers operating at 4.6 GHz that exhibit gains of 20 dB with less than 1-dB gain ripple and bandwidth up to 500 MHz. The amplifiers further achieve high-output-saturation powers around based on the use of rf superconducting quantum interference device arrays as their nonlinear element. We characterize the system readout efficiency and its signal-to-noise ratio near saturation using a Sycamore processor, finding the data consistent with near quantum limited noise performance of the amplifiers. In addition, we measure the amplifiers’ intermodulation distortion in two-tone experiments as a function of input power and intertone detuning, and observe excess distortion at small detuning with a pronounced dip as a function of signal …
Measurement-induced state transitions in a superconducting qubit: Within the rotating-wave approximation
Mostafa Khezri, Alex Opremcak, Zijun Chen, Kevin C Miao, Matt McEwen, Andreas Bengtsson, Theodore White, Ofer Naaman, Daniel Sank, Alexander N Korotkov, Yu Chen, Vadim Smelyanskiy ·  Physical Review Applied 20 (5), 054008, 2023
Download PDF View
Superconducting qubits typically use a dispersive readout scheme, where a resonator is coupled to a qubit such that its frequency is qubit-state dependent. Measurement is performed by driving the resonator, where the transmitted resonator field yields information about the resonator frequency and thus the qubit state. Ideally, we could use arbitrarily strong resonator drives to achieve a target signal-to-noise ratio in the shortest possible time. However, experiments have shown that when the average resonator photon number exceeds a certain threshold, the qubit is excited out of its computational subspace in a process we refer to as a measurement-induced state transition (MIST). These transitions degrade readout fidelity, and constitute leakage, which precludes further operation of the qubit in, for example, error correction. Here we study these transitions experimentally with a transmon qubit by measuring their …
A pair measurement surface code on pentagons
Craig Gidney ·  Quantum 7, 1156, 2023
Download PDF View
In this paper, I present a way to compile the surface code into two-body parity measurements (" pair measurements"), where the pair measurements run along the edges of a Cairo pentagonal tiling. The resulting circuit improves on prior work by Chao et al. by using fewer pair measurements per four-body stabilizer measurement (5 instead of 6) and fewer time steps per round of stabilizer measurement (6 instead of 10). Using Monte Carlo sampling, I show that these improvements increase the threshold of the surface code when compiling into pair measurements from to , and also that they improve the teraquop footprint at a physical gate error rate from qubits to qubits. However, I also show that the teraquop footprint of Chao et al's construction improves more quickly than mine as physical error rate decreases, and is likely better below a physical gate error rate of (due to bidirectional hook errors in my construction). I also compare to the planar honeycomb code, showing that although this work does noticeably reduce the gap between the surface code and the honeycomb code (when compiling into pair measurements), the honeycomb code is still more efficient (threshold , teraquop footprint at of ).
Measurement-induced entanglement and teleportation on a noisy quantum processor
Nature 622 (7983), 481-486, 2023
Download PDF View
Measurement has a special role in quantum theory: by collapsing the wavefunction, it can enable phenomena such as teleportation and thereby alter the ‘arrow of time’ that constrains unitary evolution. When integrated in many-body dynamics, measurements can lead to emergent patterns of quantum information in space–time, , , , , , – that go beyond the established paradigms for characterizing phases, either in or out of equilibrium, –. For present-day noisy intermediate-scale quantum (NISQ) processors, the experimental realization of such physics can be problematic because of hardware limitations and the stochastic nature of quantum measurement. Here we address these experimental challenges and study measurement-induced quantum information phases on up to 70 superconducting qubits. By leveraging the interchangeability of space and time, we use a duality mapping,, – to avoid mid-circuit …
Fault-tolerant quantum simulation of materials using Bloch orbitals
Nicholas C Rubin, Dominic W Berry, Fionn D Malone, Alec F White, Tanuj Khattar, A Eugene DePrince III, Sabrina Sicolo, Michael Küehn, Michael Kaicher, Joonho Lee, Ryan Babbush ·  PRX Quantum 4 (4), 040303, 2023
Download PDF View
The simulation of chemistry is among the most promising applications of quantum computing. However, most prior work exploring algorithms for block encoding, time evolving, and sampling in the eigenbasis of electronic structure Hamiltonians has either focused on modeling finite-sized systems, or has required a large number of plane-wave basis functions. In this work, we extend methods for quantum simulation with Bloch orbitals constructed from symmetry-adapted atom-centered orbitals so that one can model periodic ab initio Hamiltonians using only a modest number of basis functions. We focus on adapting existing algorithms based on combining qubitization with tensor factorizations of the Coulomb operator. Significant modifications of those algorithms are required to obtain an asymptotic speedup leveraging translational (or, more broadly, Abelian) symmetries. We implement block encodings using known …
Exponential quantum speedup in simulating coupled classical oscillators
Ryan Babbush, Dominic W Berry, Robin Kothari, Rolando D Somma, Nathan Wiebe ·  Physical Review X 13 (4), 041041, 2023
Download PDF View
We present a quantum algorithm for simulating the classical dynamics of coupled oscillators (e.g., masses coupled by springs). Our approach leverages a mapping between the Schrödinger equation and Newton’s equation for harmonic potentials such that the amplitudes of the evolved quantum state encode the momenta and displacements of the classical oscillators. When individual masses and spring constants can be efficiently queried, and when the initial state can be efficiently prepared, the complexity of our quantum algorithm is polynomial in , almost linear in the evolution time, and sublinear in the sparsity. As an example application, we apply our quantum algorithm to efficiently estimate the kinetic energy of an oscillator at any time. We show that any classical algorithm solving this same problem is inefficient and must make queries to the oracle, and when the oracles are instantiated by efficient …
Quantum error mitigation
Zhenyu Cai, Ryan Babbush, Simon C Benjamin, Suguru Endo, William J Huggins, Ying Li, Jarrod R McClean, Thomas E O’Brien ·  Reviews of Modern Physics 95 (4), 045005, 2023
Download PDF View
For quantum computers to successfully solve real-world problems, it is necessary to tackle the challenge of noise: the errors that occur in elementary physical components due to unwanted or imperfect interactions. The theory of quantum fault tolerance can provide an answer in the long term, but in the coming era of noisy intermediate-scale quantum machines one must seek to mitigate errors rather than completely eliminate them. This review surveys the diverse methods that have been proposed for quantum error mitigation, assesses their in-principle efficacy, and describes the hardware demonstrations achieved to date. Commonalities and limitations among the methods are identified, while mention is made of how mitigation methods can be chosen according to the primary type of noise present, including algorithmic errors. Open problems in the field are identified, and the prospects for realizing mitigation-based …
Simulating prethermalization using near-term quantum computers
Yilun Yang, Arthur Christianen, Sandra Coll-Vinent, Vadim Smelyanskiy, Mari Carmen Bañuls, Thomas E O’Brien, Dominik S Wild, J Ignacio Cirac ·  PRX Quantum 4 (3), 030320, 2023
Download PDF View
Quantum simulation is one of the most promising scientific applications of quantum computers. Due to decoherence and noise in current devices, it is however challenging to perform digital quantum simulation in a regime that is intractable with classical computers. In this work, we propose an experimental protocol for probing dynamics and equilibrium properties on near-term digital quantum computers. As a key ingredient of our work, we show that it is possible to study thermalization even with a relatively coarse Trotter decomposition of the Hamiltonian evolution of interest. Even though the step size is too large to permit a rigorous bound on the Trotter error, we observe that the system prethermalizes in accordance with previous results for Floquet systems. The dynamics closely resemble the thermalization of the model underlying the Trotterization up to long times. We make our approach resilient to noise by developing …
Uncovering local integrability in quantum many-body dynamics
Oles Shtanko, Derek S Wang, Haimeng Zhang, Nikhil Harle, Alireza Seif, Ramis Movassagh, Zlatko Minev ·  arXiv preprint arXiv:2307.07552, 2023
Download PDF View
Interacting many-body quantum systems and their dynamics, while fundamental to modern science and technology, are formidable to simulate and understand. However, by discovering their symmetries, conservation laws, and integrability one can unravel their intricacies. Here, using up to 124 qubits of a fully programmable quantum computer, we uncover local conservation laws and integrability in one- and two-dimensional periodically-driven spin lattices in a regime previously inaccessible to such detailed analysis. We focus on the paradigmatic example of disorder-induced ergodicity breaking, where we first benchmark the system crossover into a localized regime through anomalies in the one-particle-density-matrix spectrum and other hallmark signatures. We then demonstrate that this regime stems from hidden local integrals of motion by faithfully reconstructing their quantum operators, thus providing a detailed portrait of the system's integrable dynamics. Our results demonstrate a versatile strategy for extracting hidden dynamical structure from noisy experiments on large-scale quantum computers.
Josephson parametric circulator with same-frequency signal ports, 200 MHz bandwidth, and high dynamic range
Randy Kwende, Theodore White, Ofer Naaman ·  Applied Physics Letters 122 (22), 2023
Download PDF View
We demonstrate a 3-port Josephson parametric circulator matched to 50 Ω using second order Chebyshev networks. The device notably operates with two of its signal ports at the same frequency and uses only two out-of-phase pumps at a single frequency. As a consequence, when operated as an isolator, it does not require phase coherence between the pumps and the signal, thus simplifying the requirements for its integration into standard dispersive qubit readout setups. The device utilizes parametric couplers based on a balanced bridge of rf-superconducting quantum interference device arrays, which offer purely parametric coupling and high dynamic range. We characterize the device by measuring its full 3× 3 S-matrix as a function of frequency and the relative phase between the two pumps. We find up to 15 dB nonreciprocity over a 200 MHz signal band, port match better than 10 dB, low insertion loss of 0.6 …
Less Bacon more threshold
Craig Gidney, Dave Bacon ·  arXiv preprint arXiv:2305.12046, 2023
Download PDF View
We give the Bacon-Shor code a threshold purely by deleting gates from its circuit. Specifically: we use lattice surgery to concatenate the Bacon-Shor code with itself using local planar connectivity, and observe that the resulting circuit is a subset of the circuit that would be used by a larger Bacon-Shor code.
Accelerating quantum algorithms with precomputation
William J Huggins, Jarrod R McClean ·  arXiv preprint arXiv:2305.09638, 2023
Download PDF View
Real-world applications of computing can be extremely time-sensitive. It would be valuable if we could accelerate such tasks by performing some of the work ahead of time. Motivated by this, we propose a cost model for quantum algorithms that allows quantum precomputation; ie, for a polynomial amount of``free''computation before the input to an algorithm is fully specified, and methods for taking advantage of it. We analyze two families of unitaries that are asymptotically more efficient to implement in this cost model than in the standard one. The first example of quantum precomputation, based on density matrix exponentiation, could offer an exponential advantage under certain conditions. The second example uses a variant of gate teleportation to achieve a quadratic advantage when compared with implementing the unitaries directly. These examples hint that quantum precomputation may offer a new arena in which to seek quantum advantage.
Boundaries of quantum supremacy via random circuit sampling
Alexander Zlokapa, Benjamin Villalonga, Sergio Boixo, Daniel A Lidar ·  npj Quantum Information 9 (1), 36, 2023
Download PDF View
Google’s quantum supremacy experiment heralded a transition point where quantum computers can evaluate a computational task, random circuit sampling, faster than classical supercomputers. We examine the constraints on the region of quantum advantage for quantum circuits with a larger number of qubits and gates than experimentally implemented. At near-term gate fidelities, we demonstrate that quantum supremacy is limited to circuits with a qubit count and circuit depth of a few hundred. Larger circuits encounter two distinct boundaries: a return of a classical advantage and practically infeasible quantum runtimes. Decreasing error rates cause the region of a quantum advantage to grow rapidly. At error rates required for early implementations of the surface code, the largest circuit size within the quantum supremacy regime coincides approximately with the smallest circuit size needed to implement error …
Evaluating the evidence for exponential quantum advantage in ground-state quantum chemistry
Seunghoon Lee, Joonho Lee, Huanchen Zhai, Yu Tong, Alexander M Dalzell, Ashutosh Kumar, Phillip Helms, Johnnie Gray, Zhi-Hao Cui, Wenyuan Liu, Michael Kastoryano, Ryan Babbush, John Preskill, David R Reichman, Earl T Campbell, Edward F Valeev, Lin Lin, Garnet Kin-Lic Chan ·  Nature communications 14 (1), 1952, 2023
Download PDF View
Due to intense interest in the potential applications of quantum computing, it is critical to understand the basis for potential exponential quantum advantage in quantum chemistry. Here we gather the evidence for this case in the most common task in quantum chemistry, namely, ground-state energy estimation, for generic chemical problems where heuristic quantum state preparation might be assumed to be efficient. The availability of exponential quantum advantage then centers on whether features of the physical problem that enable efficient heuristic quantum state preparation also enable efficient solution by classical heuristics. Through numerical studies of quantum state preparation and empirical complexity analysis (including the error scaling) of classical heuristics, in both ab initio and model Hamiltonian settings, we conclude that evidence for such an exponential advantage across chemical space has yet to …
Performance comparison of optimization methods on variational quantum algorithms
Xavier Bonet-Monroig, Hao Wang, Diederick Vermetten, Bruno Senjean, Charles Moussa, Thomas Bäck, Vedran Dunjko, Thomas E O'Brien ·  Physical Review A 107 (3), 032407, 2023
Download PDF View
Variational quantum algorithms (VQAs) offer a promising path toward using near-term quantum hardware for applications in academic and industrial research. These algorithms aim to find approximate solutions to quantum problems by optimizing a parametrized quantum circuit using a classical optimization algorithm. A successful VQA requires fast and reliable classical optimization algorithms. Understanding and optimizing how off-the-shelf optimization methods perform in this context is important for the future of the field. In this work, we study the performance of four commonly used gradient-free optimization methods [sequential least-squares quadratic programming, constrained optimization by linear approximations, the covariance matrix adaptation evolutionary strategy (CMA-ES), and the simultaneous perturbation stochastic approximation (SPSA)] to find ground-state energies of a range of small chemistry and …
Parametric Amplifier Matching Using Legendre Prototypes
Ryan Kaufman, Ofer Naaman ·  arXiv preprint arXiv:2303.00184, 2023
Download PDF View
In this note we describe Josephson parametric amplifier (JPA) matching networks based on Legendre polynomials. These networks typically exhibit lower ripple and gentler roll-off than Chebyshev networks with similar parameters, and can be viewed as bridging the gap between Butterworth and Chebyshev ones. We tabulate prototype coefficients for parametric amplifiers based on Legendre polynomials with a range of gain and ripple parameters, and for a range of network orders. We also use this opportunity to further illustrate the synthesis of these networks based on methods from previous work, and synthesize a prototype JPA with 20dB gain at a center frequency of 5GHz with a bandwidth of 500MHz.
Cleaner magic states with hook injection
Craig Gidney ·  arXiv preprint arXiv:2302.12292, 2023
Download PDF View
In this paper, I show how an intentional hook error mechanism can be used as a control knob for injecting magic states into surface codes. The limitation, and benefit, of this approach is that it can only inject states in the XY or YZ plane of the Bloch sphere. This increases fidelity, because perturbations out of the target plane can be detected as errors. I use Monte Carlo sampling to show that this technique outperforms previous injection techniques, achieving lower error rates at smaller spacetime cost under digitized circuit noise.
Suppressing quantum errors by scaling a surface code logical qubit
Nature 614 (7949), 676-681, 2023
Download PDF View
Practical quantum computing will require error rates well below those achievable with physical qubits. Quantum error correction, offers a path to algorithmically relevant error rates by encoding logical qubits within many physical qubits, for which increasing the number of physical qubits enhances protection against physical errors. However, introducing more qubits also increases the number of error sources, so the density of errors must be sufficiently low for logical performance to improve with increasing code size. Here we report the measurement of logical qubit performance scaling across several code sizes, and demonstrate that our system of superconducting qubits has sufficient performance to overcome the additional errors from increasing qubit number. We find that our distance-5 surface code logical qubit modestly outperforms an ensemble of distance-3 logical qubits on average, in terms of both logical error …
Quantum simulation of exact electron dynamics can be more efficient than classical mean-field methods
Ryan Babbush, William J Huggins, Dominic W Berry, Shu Fay Ung, Andrew Zhao, David R Reichman, Hartmut Neven, Andrew D Baczewski, Joonho Lee ·  Nature Communications 14, 4058, 2023
Download PDF View
Quantum algorithms for simulating electronic ground states are slower than popular classical mean-field algorithms such as Hartree–Fock and density functional theory but offer higher accuracy. Accordingly, quantum computers have been predominantly regarded as competitors to only the most accurate and costly classical methods for treating electron correlation. However, here we tighten bounds showing that certain first-quantized quantum algorithms enable exact time evolution of electronic systems with exponentially less space and polynomially fewer operations in basis set size than conventional real-time time-dependent Hartree–Fock and density functional theory. Although the need to sample observables in the quantum algorithm reduces the speedup, we show that one can estimate all elements of the k-particle reduced density matrix with a number of samples scaling only polylogarithmically in basis set …
Readout of a quantum processor with high dynamic range Josephson parametric amplifiers
Theodore White, Alex Opremcak, George Sterling, Alexander Korotkov, Daniel Sank, Rajeev Acharya, Markus Ansmann, Frank Arute, Kunal Arya, Joseph C Bardin, Andreas Bengtsson, Alexandre Bourassa, Jenna Bovaird, Leon Brill, Bob B Buckley, David A Buell, Tim Burger, Brian Burkett, Nicholas Bushnell, Zijun Chen, Ben Chiaro, Josh Cogan, Roberto Collins, Alexander L Crook, Ben Curtin, Sean Demura, Andrew Dunsworth, Catherine Erickson, Reza Fatemi, Leslie Flores Burgos, Ebrahim Forati, Brooks Foxen, William Giang, Marissa Giustina, Alejandro Grajales Dau, Michael C Hamilton, Sean D Harrington, Jeremy Hilton, Markus Hoffmann, Sabrina Hong, Trent Huang, Ashley Huff, Justin Iveland, Evan Jeffrey, Mária Kieferová, Seon Kim, Paul V Klimov, Fedor Kostritsa, John Mark Kreikebaum, David Landhuis, Pavel Laptev, Lily Laws, Kenny Lee, Brian J Lester, Alexander Lill, Wayne Liu, Aditya Locharla, Erik Lucero, Trevor McCourt, Matt McEwen, Xiao Mi, Kevin C Miao, Shirin Montazeri, Alexis Morvan, Matthew Neeley, Charles Neill, Ani Nersisyan, Jiun How Ng, Anthony Nguyen, Murray Nguyen, Rebecca Potter, Chris Quintana, Pedram Roushan, Kannan Sankaragomathi, Kevin J Satzinger, Christopher Schuster, Michael J Shearn, Aaron Shorter, Vladimir Shvarts, Jindra Skruzny, W Clarke Smith, Marco Szalay, Alfredo Torres, Bryan WK Woo, Z Jamie Yao, Ping Yeh, Juhwan Yoo, Grayson Young, Ningfeng Zhu, Nicholas Zobrist, Yu Chen, Anthony Megrant, Julian Kelly, Ofer Naaman ·  Applied Physics Letters 122 (1), 2023
Download PDF View
We demonstrate a high dynamic range Josephson parametric amplifier (JPA) in which the active nonlinear element is implemented using an array of rf-SQUIDs. The device is matched to the 50 Ω environment with a Klopfenstein-taper impedance transformer and achieves a bandwidth of 250–300 MHz with input saturation powers up to− 95 dBm at 20 dB gain. A 54-qubit Sycamore processor was used to benchmark these devices, providing a calibration for readout power, an estimation of amplifier added noise, and a platform for comparison against standard impedance matched parametric amplifiers with a single dc-SQUID. We find that the high power rf-SQUID array design has no adverse effect on system noise, readout fidelity, or qubit dephasing, and we estimate an upper bound on amplifier added noise at 1.6 times the quantum limit. Finally, amplifiers with this design show no degradation in readout fidelity due …
Exponential quantum communication advantage in distributed learning
Dar Gilboa, Jarrod R McClean
Download PDF View
Training and inference with large machine learning models that far exceed the memory capacity of individual devices necessitates the design of distributed architectures, forcing one to contend with communication constraints. We present a framework for distributed computation over a quantum network in which data is encoded into specialized quantum states. We prove that for certain models within this framework, inference and training using gradient descent can be performed with exponentially less communication compared to their classical analogs, and with relatively modest time and space complexity overheads relative to standard gradient-based methods. To our knowledge, this is the first example of exponential quantum advantage for a generic class of machine learning problems with dense classical data that holds regardless of the data encoding cost. Moreover, we show that models in this class can encode highly nonlinear features of their inputs, and their expressivity increases exponentially with model depth. We also find that, interestingly, the communication advantage nearly vanishes for simpler linear classifiers. These results can be combined with natural privacy advantages in the communicated quantum states that limit the amount of information that can be extracted from them about the data and model parameters. Taken as a whole, these findings form a promising foundation for distributed machine learning over quantum networks.
Observation of non-Abelian exchange statistics on a superconducting processor
Trond Andersen, Yuri Lensky, Kostyantyn Kechedzhi, Ilya Drozdov, Andreas Bengtsson, Sabrina Hong, Alexis Morvan, Xiao Mi, Alexander Opremcak, Eun-Ah Kim, Igor Aleiner, Pedram Roushan, Quantum AI Team ·  APS March Meeting Abstracts 2023, G65. 002, 2023
Download PDF View
Indistinguishability of particles is a fundamental principle of quantum mechanics. For all elementary and quasiparticles observed to date-including fermions, bosons, and Abelian anyons-this principle guarantees that the braiding of identical particles leaves the system unchanged. However, in two spatial dimensions, an intriguing possibility exists: braiding of non-Abelian anyons causes rotations in a space of topologically degenerate wavefunctions. Hence, it can change the observables of the system without violating the principle of indistinguishability. Despite the well developed mathematical description of non-Abelian anyons and numerous theoretical proposals, their experimental observation has remained elusive for decades. Using a superconducting quantum processor, we prepare the ground state of the surface code and manipulate it via unitary operations to form wavefunctions that are described by non …
Nearly optimal quantum algorithm for estimating multiple expectation values
William J Huggins, Kianna Wan, Jarrod McClean, Thomas E O’Brien, Nathan Wiebe, Ryan Babbush ·  Physical Review Letters 129 (24), 240501, 2022
Download PDF View
Many quantum algorithms involve the evaluation of expectation values. Optimal strategies for estimating a single expectation value are known, requiring a number of state preparations that scales with the target error as . In this Letter, we address the task of estimating the expectation values of different observables, each to within additive error , with the same dependence. We describe an approach that leverages Gilyén et al.’s quantum gradient estimation algorithm to achieve scaling up to logarithmic factors, regardless of the commutation properties of the observables. We prove that this scaling is worst-case optimal in the high-precision regime if the state preparation is treated as a black box, even when the operators are mutually commuting. We highlight the flexibility of our approach by presenting several generalizations, including a strategy for accelerating the estimation of a …
Formation of robust bound states of interacting microwave photons
Alexis Morvan, Trond I Andersen, Xiao Mi, Charles Neill, Andre Petukhov, Kostyantyn Kechedzhi, DA Abanin, Alexios Michailidis, Rajeev Acharya, Frank Arute, K Arya, A Asfaw, J Atalaya, JC Bardin, J Basso, A Bengtsson, G Bortoli, A Bourassa, J Bovaird, L Brill, M Broughton, BB Buckley, DA Buell, T Burger, B Burkett, N Bushnell, Z Chen, B Chiaro, R Collins, P Conner, W Courtney, AL Crook, B Curtin, DM Debroy, A Del Toro Barba, S Demura, A Dunsworth, D Eppens, C Erickson, L Faoro, E Farhi, R Fatemi, L Flores Burgos, E Forati, AG Fowler, B Foxen, W Giang, C Gidney, D Gilboa, M Giustina, A Grajales Dau, JA Gross, S Habegger, MC Hamilton, MP Harrigan, SD Harrington, M Hoffmann, S Hong, T Huang, A Huff, WJ Huggins, SV Isakov, J Iveland, E Jeffrey, Z Jiang, C Jones, P Juhas, D Kafri, T Khattar, M Khezri, M Kieferová, S Kim, AY Kitaev, PV Klimov, AR Klots, AN Korotkov, F Kostritsa, JM Kreikebaum, D Landhuis, P Laptev, K-M Lau, L Laws, J Lee, KW Lee, BJ Lester, AT Lill, W Liu, A Locharla, F Malone, O Martin, JR McClean, M McEwen, B Meurer Costa, KC Miao, M Mohseni, S Montazeri, E Mount, W Mruczkiewicz, O Naaman, M Neeley, A Nersisyan, M Newman, A Nguyen, M Nguyen, MY Niu, TE O’Brien, R Olenewa, A Opremcak, R Potter, C Quintana, NC Rubin, N Saei, D Sank, K Sankaragomathi, KJ Satzinger, HF Schurkus, C Schuster, MJ Shearn, A Shorter, V Shvarts, J Skruzny, WC Smith, D Strain, G Sterling, Y Su, M Szalay, A Torres, G Vidal, B Villalonga, C Vollgraff-Heidweiller, T White, C Xing, Z Yao, P Yeh, J Yoo, A Zalcman, Y Zhang, N Zhu, H Neven, D Bacon, J Hilton, E Lucero, R Babbush, Sergio Boixo, Anthony Megrant, Julian Kelly, Yu Chen, Vadim Smelyanskiy, Igor Aleiner, Lev B Ioffe ·  Nature 612 (7939), 240-245, 2022
Download PDF View
Systems of correlated particles appear in many fields of modern science and represent some of the most intractable computational problems in nature. The computational challenge in these systems arises when interactions become comparable to other energy scales, which makes the state of each particle depend on all other particles. The lack of general solutions for the three-body problem and acceptable theory for strongly correlated electrons shows that our understanding of correlated systems fades when the particle number or the interaction strength increases. One of the hallmarks of interacting systems is the formation of multiparticle bound states, , , , , , –. Here we develop a high-fidelity parameterizable fSim gate and implement the periodic quantum circuit of the spin-½ XXZ model in a ring of 24 superconducting qubits. We study the propagation of these excitations and observe their bound nature for up to …
Efficient quantum computation of molecular forces and other energy gradients
Thomas E O'Brien, Michael Streif, Nicholas C Rubin, Raffaele Santagati, Yuan Su, William J Huggins, Joshua J Goings, Nikolaj Moll, Elica Kyoseva, Matthias Degroote, Christofer S Tautermann, Joonho Lee, Dominic W Berry, Nathan Wiebe, Ryan Babbush ·  Physical Review Research 4 (4), 043210, 2022
Download PDF View
While most work on the quantum simulation of chemistry has focused on computing energy surfaces, a similarly important application requiring subtly different algorithms is the computation of energy derivatives. Almost all molecular properties can be expressed an energy derivative, including molecular forces, which are essential for applications such as molecular dynamics simulations. Here, we introduce new quantum algorithms for computing molecular energy derivatives with significantly lower complexity than prior methods. Under cost models appropriate for noisy-intermediate scale quantum devices, we demonstrate how low-rank factorization and other tomography schemes can be optimized for energy derivative calculations. We numerically demonstrate that our techniques reduce the number of circuit repetitions required by many orders of magnitude for even modest systems, and that the cost of estimating …
Traversable wormhole dynamics on a quantum processor
Daniel Jafferis, Alexander Zlokapa, Joseph D Lykken, David K Kolchmeyer, Samantha I Davis, Nikolai Lauk, Hartmut Neven, Maria Spiropulu ·  Nature 612 (7938), 51-55, 2022
Download PDF View
The holographic principle, theorized to be a property of quantum gravity, postulates that the description of a volume of space can be encoded on a lower-dimensional boundary. The anti-de Sitter (AdS)/conformal field theory correspondence or duality is the principal example of holography. The Sachdev–Ye–Kitaev (SYK) model of N ≫ 1 Majorana fermions, has features suggesting the existence of a gravitational dual in AdS2, and is a new realization of holography, –. We invoke the holographic correspondence of the SYK many-body system and gravity to probe the conjectured ER=EPR relation between entanglement and spacetime geometry, through the traversable wormhole mechanism as implemented in the SYK model,. A qubit can be used to probe the SYK traversable wormhole dynamics through the corresponding teleportation protocol. This can be realized as a quantum circuit, equivalent to the …
Noise-resilient edge modes on a chain of superconducting qubits
Xiao Mi, Michael Sonner, M Yuezhen Niu, Kenneth W Lee, Brooks Foxen, Rajeev Acharya, Igor Aleiner, Trond I Andersen, Frank Arute, Kunal Arya, Abraham Asfaw, Juan Atalaya, JC Bardin, J Basso, A Bengtsson, G Bortoli, A Bourassa, L Brill, M Broughton, BB Buckley, DA Buell, B Burkett, N Bushnell, Z Chen, B Chiaro, R Collins, P Conner, W Courtney, AL Crook, DM Debroy, S Demura, A Dunsworth, D Eppens, C Erickson, L Faoro, E Farhi, R Fatemi, L Flores, E Forati, AG Fowler, W Giang, C Gidney, D Gilboa, M Giustina, AG Dau, JA Gross, S Habegger, MP Harrigan, M Hoffmann, S Hong, T Huang, A Huff, WJ Huggins, LB Ioffe, SV Isakov, J Iveland, E Jeffrey, Z Jiang, C Jones, D Kafri, K Kechedzhi, T Khattar, S Kim, AY Kitaev, PV Klimov, AR Klots, AN Korotkov, F Kostritsa, JM Kreikebaum, D Landhuis, P Laptev, K-M Lau, J Lee, L Laws, W Liu, A Locharla, O Martin, JR McClean, M McEwen, B Meurer Costa, KC Miao, M Mohseni, S Montazeri, A Morvan, E Mount, W Mruczkiewicz, O Naaman, M Neeley, C Neill, M Newman, TE O’Brien, A Opremcak, A Petukhov, R Potter, C Quintana, NC Rubin, N Saei, D Sank, K Sankaragomathi, KJ Satzinger, C Schuster, MJ Shearn, V Shvarts, D Strain, Y Su, M Szalay, G Vidal, B Villalonga, C Vollgraff-Heidweiller, T White, Z Yao, P Yeh, J Yoo, A Zalcman, Y Zhang, N Zhu, H Neven, D Bacon, J Hilton, E Lucero, R Babbush, Sergio Boixo, Anthony Megrant, Yu Chen, Julian Kelly, Vadim Smelyanskiy, Dmitry A Abanin, Pedram Roushan ·  Science 378 (6621), 785-790, 2022
Download PDF View
Inherent symmetry of a quantum system may protect its otherwise fragile states. Leveraging such protection requires testing its robustness against uncontrolled environmental interactions. Using 47 superconducting qubits, we implement the one-dimensional kicked Ising model, which exhibits nonlocal Majorana edge modes (MEMs) with parity symmetry. We find that any multiqubit Pauli operator overlapping with the MEMs exhibits a uniform late-time decay rate comparable to single-qubit relaxation rates, irrespective of its size or composition. This characteristic allows us to accurately reconstruct the exponentially localized spatial profiles of the MEMs. Furthermore, the MEMs are found to be resilient against certain symmetry-breaking noise owing to a prethermalization mechanism. Our work elucidates the complex interplay between noise and symmetry-protected edge modes in a solid-state environment.
Simulating models of challenging correlated molecules and materials on the sycamore quantum processor
Ruslan N Tazhigulov, Shi-Ning Sun, Reza Haghshenas, Huanchen Zhai, Adrian TK Tan, Nicholas C Rubin, Ryan Babbush, Austin J Minnich, Garnet Kin-Lic Chan ·  PRX Quantum 3 (4), 040318, 2022
Download PDF View
Simulating complex molecules and materials is an anticipated application of quantum devices. With the emergence of hardware designed to target strong quantum advantage in artificial tasks, we examine how the same hardware behaves in modeling physical problems of correlated electronic structure. We simulate static and dynamical electronic structure on a superconducting quantum processor derived from Google’s Sycamore architecture for two representative correlated electron problems: the nitrogenase iron-sulfur molecular clusters and -ruthenium trichloride, a proximate spin-liquid material. To do so, we simplify the electronic structure into low-energy spin models that fit on the device. With extensive error mitigation and assistance from classical recompilation and simulated data, we achieve quantitatively meaningful results deploying about one fifth of the gate resources used in artificial quantum …
Optimal scaling quantum linear-systems solver via discrete adiabatic theorem
Pedro CS Costa, Dong An, Yuval R Sanders, Yuan Su, Ryan Babbush, Dominic W Berry ·  PRX quantum 3 (4), 040303, 2022
Download PDF View
Recently, several approaches to solving linear systems on a quantum computer have been formulated in terms of the quantum adiabatic theorem for a continuously varying Hamiltonian. Such approaches have enabled near-linear scaling in the condition number of the linear system, without requiring a complicated variable-time amplitude amplification procedure. However, the most efficient of those procedures is still asymptotically suboptimal by a factor of log⁡(κ). Here, we prove a rigorous form of the adiabatic theorem that bounds the error in terms of the spectral gap for intrinsically discrete-time evolutions. In combination with the qubitized quantum walk, our discrete adiabatic theorem gives a speed-up for all adiabatic algorithms. Here, we use this combination to develop a quantum algorithm for solving linear systems that is asymptotically optimal, in the sense that the complexity is strictly linear in , matching a known …
Provably accurate simulation of gauge theories and bosonic systems
Yu Tong, Victor V Albert, Jarrod R McClean, John Preskill, Yuan Su ·  Quantum 6, 816, 2022
Download PDF View
Quantum many-body systems involving bosonic modes or gauge fields have infinite-dimensional local Hilbert spaces which must be truncated to perform simulations of real-time dynamics on classical or quantum computers. To analyze the truncation error, we develop methods for bounding the rate of growth of local quantum numbers such as the occupation number of a mode at a lattice site, or the electric field at a lattice link. Our approach applies to various models of bosons interacting with spins or fermions, and also to both abelian and non-abelian gauge theories. We show that if states in these models are truncated by imposing an upper limit on each local quantum number, and if the initial state has low local quantum numbers, then an error at most can be achieved by choosing to scale polylogarithmically with , an exponential improvement over previous bounds based on energy conservation. For the Hubbard-Holstein model, we numerically compute a bound on that achieves accuracy , obtaining significantly improved estimates in various parameter regimes. We also establish a criterion for truncating the Hamiltonian with a provable guarantee on the accuracy of time evolution. Building on that result, we formulate quantum algorithms for dynamical simulation of lattice gauge theories and of models with bosonic modes; the gate complexity depends almost linearly on spacetime volume in the former case, and almost quadratically on time in the latter case. We establish a lower bound showing that there are systems involving bosons for which this quadratic scaling with time cannot be improved. By applying our result on the truncation error …
Benchmarking the planar honeycomb code
Craig Gidney, Michael Newman, Matt McEwen ·  Quantum 6, 813, 2022
Download PDF View
We improve the planar honeycomb code by describing boundaries that need no additional physical connectivity, and by optimizing the shape of the qubit patch. We then benchmark the code using Monte Carlo sampling to estimate logical error rates and derive metrics including thresholds, lambdas, and teraquop qubit counts. We determine that the planar honeycomb code can create a logical qubit with one-in-a-trillion logical error rates using 7000 physical qubits at a 0.1% gate-level error rate (or 900 physical qubits given native two-qubit parity measurements). Our results cement the honeycomb code as a promising candidate for two-dimensional qubit architectures with sparse connectivity.
Reliably assessing the electronic structure of cytochrome P450 on today’s classical computers and tomorrow’s quantum computers
Joshua J Goings, Alec White, Joonho Lee, Christofer S Tautermann, Matthias Degroote, Craig Gidney, Toru Shiozaki, Ryan Babbush, Nicholas C Rubin ·  Proceedings of the National Academy of Sciences 119 (38), e2203533119, 2022
Download PDF View
An accurate assessment of how quantum computers can be used for chemical simulation, especially their potential computational advantages, provides important context on how to deploy these future devices. To perform this assessment reliably, quantum resource estimates must be coupled with classical computations attempting to answer relevant chemical questions and to define the classical algorithms simulation frontier. Herein, we explore the quantum computation and classical computation resources required to assess the electronic structure of cytochrome P450 enzymes (CYPs) and thus define a classical–quantum advantage boundary. This is accomplished by analyzing the convergence of density matrix renormalization group plus n-electron valence state perturbation theory (DMRG+NEVPT2) and coupled-cluster singles doubles with noniterative triples [CCSD(T)] calculations for spin gaps in models of …
Quantum computation of molecular structure using data from challenging-to-classically-simulate nuclear magnetic resonance experiments
Thomas E O’Brien, Lev B Ioffe, Yuan Su, David Fushman, Hartmut Neven, Ryan Babbush, Vadim Smelyanskiy ·  PRX Quantum 3 (3), 030345, 2022
Download PDF View
We propose a quantum algorithm for inferring the molecular nuclear spin Hamiltonian from time-resolved measurements of spin-spin correlators, which can be obtained via nuclear magnetic resonance (NMR). We focus on learning the anisotropic dipolar term of the Hamiltonian, which generates dynamics that are challenging to classically simulate in some contexts. We demonstrate the ability to directly estimate the Jacobian and Hessian of the corresponding learning problem on a quantum computer, allowing us to learn the Hamiltonian parameters. We develop algorithms for performing this computation on both noisy near-term and future fault-tolerant quantum computers. We argue that the former is promising as an early beyond-classical quantum application since it only requires evolution of a local spin Hamiltonian. We investigate the example of a protein (ubiquitin) confined on a membrane as a benchmark of …
Information-theoretic hardness of out-of-time-order correlators
Jordan Cotler, Thomas Schuster, Masoud Mohseni ·  arXiv preprint arXiv:2208.02256, 2022
Download PDF View
We establish that there are properties of quantum many-body dynamics which are efficiently learnable if we are given access to out-of-time-order correlators (OTOCs), but which require exponentially many operations in the system size if we can only measure time-ordered correlators. This implies that any experimental protocol which reconstructs OTOCs solely from time-ordered correlators must be, in certain cases, exponentially inefficient. Our proofs leverage and generalize recent techniques in quantum learning theory. Along the way, we elucidate a general definition of time-ordered versus out-of-time-order experimental measurement protocols, which can be considered as classes of adaptive quantum learning algorithms. Moreover, our results provide a theoretical foundation for novel applications of OTOCs in quantum simulations.
Small-world complex network generation on a digital quantum processor
Eric B Jones, Logan E Hillberry, Matthew T Jones, Mina Fasihi, Pedram Roushan, Zhang Jiang, Alan Ho, Charles Neill, Eric Ostby, Peter Graf, Eliot Kapit, Lincoln D Carr ·  Nature communications 13 (1), 4483, 2022
Download PDF View
Quantum cellular automata (QCA) evolve qubits in a quantum circuit depending only on the states of their neighborhoods and model how rich physical complexity can emerge from a simple set of underlying dynamical rules. The inability of classical computers to simulate large quantum systems hinders the elucidation of quantum cellular automata, but quantum computers offer an ideal simulation platform. Here, we experimentally realize QCA on a digital quantum processor, simulating a one-dimensional Goldilocks rule on chains of up to 23 superconducting qubits. We calculate calibrated and error-mitigated population dynamics and complex network measures, which indicate the formation of small-world mutual information networks. These networks decohere at fixed circuit depth independent of system size, the largest of which corresponding to 1,056 two-qubit gates. Such computations may enable the …
The QAOA gets stuck starting from a good classical string
Madelyn Cain, Edward Farhi, Sam Gutmann, Daniel Ranard, Eugene Tang ·  arXiv preprint arXiv:2207.05089, 2022
Download PDF View
The Quantum Approximate Optimization Algorithm (QAOA) is designed to maximize a cost function over bit strings. While the initial state is traditionally a uniform superposition over all strings, it is natural to try expediting the QAOA: first use a classical algorithm to produce some good string, and then run the standard QAOA starting in the computational basis state associated with that string. Here we report numerical experiments that show this method of initializing the QAOA fails dramatically, exhibiting little to no improvement of the cost function. We provide multiple analytical arguments for this lack of improvement, each of which can be made rigorous under different regimes or assumptions, including at nearly linear depths. We emphasize that our negative results only apply to our simple incarnation of the warm-start QAOA and may not apply to other approaches in the literature. We hope that our theoretical analysis will inform future algorithm design.
The quantum approximate optimization algorithm and the Sherrington-Kirkpatrick model at infinite size
Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Leo Zhou ·  Quantum 6, 759, 2022
Download PDF View
The Quantum Approximate Optimization Algorithm (QAOA) is a general-purpose algorithm for combinatorial optimization problems whose performance can only improve with the number of layers . While QAOA holds promise as an algorithm that can be run on near-term quantum computers, its computational power has not been fully explored. In this work, we study the QAOA applied to the Sherrington-Kirkpatrick (SK) model, which can be understood as energy minimization of spins with all-to-all random signed couplings. There is a recent classical algorithm by Montanari that, assuming a widely believed conjecture, can efficiently find an approximate solution for a typical instance of the SK model to within times the ground state energy. We hope to match its performance with the QAOA.
Quantum advantage in learning from experiments
Hsin-Yuan Huang, Michael Broughton, Jordan Cotler, Sitan Chen, Jerry Li, Masoud Mohseni, Hartmut Neven, Ryan Babbush, Richard Kueng, John Preskill, Jarrod R McClean ·  Science 376 (6598), 1182-1186, 2022
Download PDF View
Quantum technology promises to revolutionize how we learn about the physical world. An experiment that processes quantum data with a quantum computer could have substantial advantages over conventional experiments in which quantum states are measured and outcomes are processed with a classical computer. We proved that quantum machines could learn from exponentially fewer experiments than the number required by conventional experiments. This exponential advantage is shown for predicting properties of physical systems, performing quantum principal component analysis, and learning about physical dynamics. Furthermore, the quantum resources needed for achieving an exponential advantage are quite modest in some cases. Conducting experiments with 40 superconducting qubits and 1300 quantum gates, we demonstrated that a substantial quantum advantage is possible with today’s …
Entangling quantum generative adversarial networks
Murphy Yuezhen Niu, Alexander Zlokapa, Michael Broughton, Sergio Boixo, Masoud Mohseni, Vadim Smelyanskyi, Hartmut Neven ·  Physical Review Letters 128 (22), 220505, 2022
Download PDF View
Generative adversarial networks (GANs) are one of the most widely adopted machine learning methods for data generation. In this work, we propose a new type of architecture for quantum generative adversarial networks (an entangling quantum GAN, EQ-GAN) that overcomes limitations of previously proposed quantum GANs. Leveraging the entangling power of quantum circuits, the EQ-GAN converges to the Nash equilibrium by performing entangling operations between both the generator output and true quantum data. In the first multiqubit experimental demonstration of a fully quantum GAN with a provably optimal Nash equilibrium, we use the EQ-GAN on a Google Sycamore superconducting quantum processor to mitigate uncharacterized errors, and we numerically confirm successful error mitigation with simulations up to 18 qubits. Finally, we present an application of the EQ-GAN to prepare an approximate …
Synthesis of parametrically coupled networks
Ofer Naaman, José Aumentado ·  PRX Quantum 3 (2), 020201, 2022
Download PDF View
We show that a common language can be used to unify the description of parametrically coupled circuits—parametric amplifiers, frequency converters, and parametric nonreciprocal devices—with that of band-pass filter and impedance matching networks. This enables one to readily adapt network synthesis methods from microwave engineering in the design of parametrically coupled devices having prescribed transfer characteristics, e.g., gain, bandwidth, return loss, and isolation. We review basic practical aspects of coupled-mode theory and filter synthesis, and then show how to apply both, on an equal footing, to the design of multipole, broadband parametric and nonreciprocal networks. We supplement the discussion with a range of examples and reference designs.
Unbiasing fermionic quantum Monte Carlo with a quantum computer
William J Huggins, Bryan A O’Gorman, Nicholas C Rubin, David R Reichman, Ryan Babbush, Joonho Lee ·  Nature 603 (7901), 416-420, 2022
Download PDF View
Interacting many-electron problems pose some of the greatest computational challenges in science, with essential applications across many fields. The solutions to these problems will offer accurate predictions of chemical reactivity and kinetics, and other properties of quantum systems, , –. Fermionic quantum Monte Carlo (QMC) methods,, which use a statistical sampling of the ground state, are among the most powerful approaches to these problems. Controlling the fermionic sign problem with constraints ensures the efficiency of QMC at the expense of potentially significant biases owing to the limited flexibility of classical computation. Here we propose an approach that combines constrained QMC with quantum computation to reduce such biases. We implement our scheme experimentally using up to 16 qubits to unbias constrained QMC calculations performed on chemical systems with as many as 120 orbitals …
Software mitigation of coherent two-qubit gate errors
Lingling Lao, Alexander Korotkov, Zhang Jiang, Wojciech Mruczkiewicz, Thomas E O'Brien, Dan E Browne ·  Quantum Science and Technology 7 (2), 025021, 2022
Download PDF View
Two-qubit gates are important components of quantum computing. However, unwanted interactions between qubits (so-called parasitic gates) can be particularly problematic and degrade the performance of quantum applications. In this work, we present two software methods to mitigate parasitic two-qubit gate errors. The first approach is built upon the Cartan's KAK decomposition and keeps the original unitary decomposition for the error-free native two-qubit gate. It counteracts a parasitic two-qubit gate by only applying single-qubit rotations and therefore has no two-qubit gate overhead. We show the optimal choice of single-qubit mitigation gates. The second approach applies a numerical optimisation algorithm to re-compile a target unitary into the error-parasitic two-qubit gate plus single-qubit gates. We demonstrate these approaches on the CPhase-parasitic iSWAP-like gates. The KAK-based approach helps …
Precise Hamiltonian identification of a superconducting quantum processor (Part 1)
Dominik Hangleiter, Ingo Roth, Jens Eisert, Pedram Roushan ·  APS March Meeting Abstracts 2022, K35. 001, 2022
View
None
Beyond-classical computing using superconducting quantum processors
Joseph Bardin ·  2022 IEEE International Solid-State Circuits Conference (ISSCC) 65, 422-424, 2022
Download PDF View
The Google Quantum AI team's long-term goal is to realize a large-scale fault-tolerant quantum computer. Of the technologies available to implement the quantum processor at the core of such a system, solid-state superconducting circuits based on Josephson junctions (JJs) are among the strongest contenders. Recent demonstrations with this technology include computation beyond the capabilities of today's most powerful supercomputers [1] and execution of quantum error correction (QEC) codes that can detect and correct either bit or phase flip errors [2]. These exciting results were enabled by low-error-rate quantum processors with tens of qubits and the supporting infrastructure to run these devices. However, today's quantum computers still have orders of magnitude fewer qubits than is required for a useful fault-tolerant quantum computer; for this, an estimated million or more qubits will be needed and scaling …
Compressing many-body fermion operators under unitary constraints
Nicholas C Rubin, Joonho Lee, Ryan Babbush ·  Journal of Chemical Theory and Computation 18 (3), 1480-1488, 2022
Download PDF View
The most efficient known quantum circuits for preparing unitary coupled cluster states and applying Trotter steps of the arbitrary basis electronic structure Hamiltonian involve interleaved sequences of Fermionic Gaussian circuits and Ising interaction-type circuits. These circuits arise from factorizing the two-body operators generating those unitaries as a sum of squared one-body operators that are simulated using product formulas. We introduce a numerical algorithm for performing this factorization that has an iteration complexity no worse than single particle basis transformations of the two-body operators and often results in many times fewer squared one-body operators in the sum of squares, compared to the analytical decompositions. As an application of this numerical procedure, we demonstrate that our protocol can be used to approximate generic unitary coupled cluster operators and prepare the necessary …
Direct measurement of nonlocal interactions in the many-body localized phase
Benjamin Chiaro, C Neill, A Bohrdt, Michele Filippone, F Arute, K Arya, R Babbush, D Bacon, J Bardin, R Barends, S Boixo, D Buell, B Burkett, Y Chen, Z Chen, R Collins, A Dunsworth, E Farhi, A Fowler, B Foxen, C Gidney, M Giustina, M Harrigan, T Huang, S Isakov, E Jeffrey, Z Jiang, D Kafri, K Kechedzhi, J Kelly, P Klimov, A Korotkov, F Kostritsa, D Landhuis, E Lucero, J McClean, X Mi, A Megrant, M Mohseni, J Mutus, M McEwen, O Naaman, M Neeley, M Niu, A Petukhov, C Quintana, N Rubin, D Sank, K Satzinger, T White, Z Yao, P Yeh, A Zalcman, V Smelyanskiy, H Neven, S Gopalakrishnan, D Abanin, M Knap, J Martinis, P Roushan ·  Physical Review Research 4 (1), 013148, 2022
Download PDF View
The interplay of interactions and strong disorder can lead to an exotic quantum many-body localized (MBL) phase of matter. Beyond the absence of transport, the MBL phase has distinctive signatures, such as slow dephasing and logarithmic entanglement growth; they commonly result in slow and subtle modifications of the dynamics, rendering their measurement challenging. Here, we experimentally characterize these properties of the MBL phase in a system of coupled superconducting qubits. By implementing phase sensitive techniques, we map out the structure of local integrals of motion in the MBL phase. Tomographic reconstruction of single and two-qubit density matrices allows us to determine the spatial and temporal entanglement growth between the localized sites. In addition, we study the preservation of entanglement in the MBL phase. The interferometric protocols implemented here detect affirmative …
Time-crystalline eigenstate order on a quantum processor
Xiao Mi, Matteo Ippoliti, Chris Quintana, Ami Greene, Zijun Chen, Jonathan Gross, Frank Arute, Kunal Arya, Juan Atalaya, Ryan Babbush, Joseph C Bardin, Joao Basso, Andreas Bengtsson, Alexander Bilmes, Alexandre Bourassa, Leon Brill, Michael Broughton, Bob B Buckley, David A Buell, Brian Burkett, Nicholas Bushnell, Benjamin Chiaro, Roberto Collins, William Courtney, Dripto Debroy, Sean Demura, Alan R Derk, Andrew Dunsworth, Daniel Eppens, Catherine Erickson, Edward Farhi, Austin G Fowler, Brooks Foxen, Craig Gidney, Marissa Giustina, Matthew P Harrigan, Sean D Harrington, Jeremy Hilton, Alan Ho, Sabrina Hong, Trent Huang, Ashley Huff, William J Huggins, LB Ioffe, Sergei V Isakov, Justin Iveland, Evan Jeffrey, Zhang Jiang, Cody Jones, Dvir Kafri, Tanuj Khattar, Seon Kim, Alexei Kitaev, Paul V Klimov, Alexander N Korotkov, Fedor Kostritsa, David Landhuis, Pavel Laptev, Joonho Lee, Kenny Lee, Aditya Locharla, Erik Lucero, Orion Martin, Jarrod R McClean, Trevor McCourt, Matt McEwen, Kevin C Miao, Masoud Mohseni, Shirin Montazeri, Wojciech Mruczkiewicz, Ofer Naaman, Matthew Neeley, Charles Neill, Michael Newman, Murphy Yuezhen Niu, Thomas E O’Brien, Alex Opremcak, Eric Ostby, Balint Pato, Andre Petukhov, Nicholas C Rubin, Daniel Sank, Kevin J Satzinger, Vladimir Shvarts, Yuan Su, Doug Strain, Marco Szalay, Matthew D Trevithick, Benjamin Villalonga, Theodore White, Z Jamie Yao, Ping Yeh, Juhwan Yoo, Adam Zalcman, Hartmut Neven, Sergio Boixo, Vadim Smelyanskiy, Anthony Megrant, Julian Kelly, Yu Chen, SL Sondhi, Roderich Moessner, Kostyantyn Kechedzhi, Vedika Khemani, Pedram Roushan ·  Nature 601 (7894), 531-536, 2022
Download PDF View
Quantum many-body systems display rich phase structure in their low-temperature equilibrium states. However, much of nature is not in thermal equilibrium. Remarkably, it was recently predicted that out-of-equilibrium systems can exhibit novel dynamical phases, , , , , – that may otherwise be forbidden by equilibrium thermodynamics, a paradigmatic example being the discrete time crystal (DTC),, , , , , –. Concretely, dynamical phases can be defined in periodically driven many-body-localized (MBL) systems via the concept of eigenstate order,,. In eigenstate-ordered MBL phases, the entire many-body spectrum exhibits quantum correlations and long-range order, with characteristic signatures in late-time dynamics from all initial states. It is, however, challenging to experimentally distinguish such stable phases from transient phenomena, or from regimes in which the dynamics of a few select states can mask typical …
Resolving catastrophic error bursts from cosmic rays in large arrays of superconducting qubits
Matt McEwen, Lara Faoro, Kunal Arya, Andrew Dunsworth, Trent Huang, Seon Kim, Brian Burkett, Austin Fowler, Frank Arute, Joseph C Bardin, Andreas Bengtsson, Alexander Bilmes, Bob B Buckley, Nicholas Bushnell, Zijun Chen, Roberto Collins, Sean Demura, Alan R Derk, Catherine Erickson, Marissa Giustina, Sean D Harrington, Sabrina Hong, Evan Jeffrey, Julian Kelly, Paul V Klimov, Fedor Kostritsa, Pavel Laptev, Aditya Locharla, Xiao Mi, Kevin C Miao, Shirin Montazeri, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Alex Opremcak, Chris Quintana, Nicholas Redd, Pedram Roushan, Daniel Sank, Kevin J Satzinger, Vladimir Shvarts, Theodore White, Z Jamie Yao, Ping Yeh, Juhwan Yoo, Yu Chen, Vadim Smelyanskiy, John M Martinis, Hartmut Neven, Anthony Megrant, Lev Ioffe, Rami Barends ·  Nature Physics 18 (1), 107-111, 2022
Download PDF View
Scalable quantum computing can become a reality with error correction, provided that coherent qubits can be constructed in large arrays,. The key premise is that physical errors can remain both small and sufficiently uncorrelated as devices scale, so that logical error rates can be exponentially suppressed. However, impacts from cosmic rays and latent radioactivity violate these assumptions. An impinging particle can ionize the substrate and induce a burst of quasiparticles that destroys qubit coherence throughout the device. High-energy radiation has been identified as a source of error in pilot superconducting quantum devices, –, but the effect on large-scale algorithms and error correction remains an open question. Elucidating the physics involved requires operating large numbers of qubits at the same rapid timescales necessary for error correction. Here, we use space- and time-resolved measurements of a …
A fault-tolerant honeycomb memory
Craig Gidney, Michael Newman, Austin Fowler, Michael Broughton ·  Quantum 5, 605, 2021
Download PDF View
Recently, Hastings & Haah introduced a quantum memory defined on the honeycomb lattice. Remarkably, this honeycomb code assembles weight-six parity checks using only two-local measurements. The sparse connectivity and two-local measurements are desirable features for certain hardware, while the weight-six parity checks enable robust performance in the circuit model.
Information scrambling in quantum circuits
Xiao Mi, Pedram Roushan, Chris Quintana, Salvatore Mandra, Jeffrey Marshall, Charles Neill, Frank Arute, Kunal Arya, Juan Atalaya, Ryan Babbush, Joseph C Bardin, Rami Barends, Joao Basso, Andreas Bengtsson, Sergio Boixo, Alexandre Bourassa, Michael Broughton, Bob B Buckley, David A Buell, Brian Burkett, Nicholas Bushnell, Zijun Chen, Benjamin Chiaro, Roberto Collins, William Courtney, Sean Demura, Alan R Derk, Andrew Dunsworth, Daniel Eppens, Catherine Erickson, Edward Farhi, Austin G Fowler, Brooks Foxen, Craig Gidney, Marissa Giustina, Jonathan A Gross, Matthew P Harrigan, Sean D Harrington, Jeremy Hilton, Alan Ho, Sabrina Hong, Trent Huang, William J Huggins, LB Ioffe, Sergei V Isakov, Evan Jeffrey, Zhang Jiang, Cody Jones, Dvir Kafri, Julian Kelly, Seon Kim, Alexei Kitaev, Paul V Klimov, Alexander N Korotkov, Fedor Kostritsa, David Landhuis, Pavel Laptev, Erik Lucero, Orion Martin, Jarrod R McClean, Trevor McCourt, Matt McEwen, Anthony Megrant, Kevin C Miao, Masoud Mohseni, Shirin Montazeri, Wojciech Mruczkiewicz, Josh Mutus, Ofer Naaman, Matthew Neeley, Michael Newman, Murphy Yuezhen Niu, Thomas E O’Brien, Alex Opremcak, Eric Ostby, Balint Pato, Andre Petukhov, Nicholas Redd, Nicholas C Rubin, Daniel Sank, Kevin J Satzinger, Vladimir Shvarts, Doug Strain, Marco Szalay, Matthew D Trevithick, Benjamin Villalonga, Theodore White, Z Jamie Yao, Ping Yeh, Adam Zalcman, Hartmut Neven, Igor Aleiner, Kostyantyn Kechedzhi, Vadim Smelyanskiy, Yu Chen ·  Science 374 (6574), 1479-1483, 2021
Download PDF View
Interactions in quantum systems can spread initially localized quantum information into the exponentially many degrees of freedom of the entire system. Understanding this process, known as quantum scrambling, is key to resolving several open questions in physics. Here, by measuring the time-dependent evolution and fluctuation of out-of-time-order correlators, we experimentally investigate the dynamics of quantum scrambling on a 53-qubit quantum processor. We engineer quantum circuits that distinguish operator spreading and operator entanglement and experimentally observe their respective signatures. We show that whereas operator spreading is captured by an efficient classical model, operator entanglement in idealized circuits requires exponentially scaled computational resources to simulate. These results open the path to studying complex and practically relevant physical observables with near-term …
Realizing topologically ordered states on a quantum processor
KJ Satzinger, Y-J Liu, A Smith, C Knapp, M Newman, C Jones, Zhaoshi Chen, Céline Quintana, Xiaohua Mi, A Dunsworth, C Gidney, I Aleiner, F Arute, K Arya, J Atalaya, R Babbush, JC Bardin, R Barends, J Basso, A Bengtsson, A Bilmes, M Broughton, BB Buckley, DA Buell, B Burkett, N Bushnell, B Chiaro, R Collins, W Courtney, S Demura, AR Derk, D Eppens, C Erickson, L Faoro, E Farhi, AG Fowler, B Foxen, M Giustina, A Greene, JA Gross, MP Harrigan, SD Harrington, J Hilton, S Hong, T Huang, WJ Huggins, LB Ioffe, SV Isakov, E Jeffrey, Z Jiang, D Kafri, K Kechedzhi, T Khattar, S Kim, PV Klimov, AN Korotkov, F Kostritsa, D Landhuis, P Laptev, A Locharla, E Lucero, O Martin, JR McClean, M McEwen, KC Miao, M Mohseni, S Montazeri, W Mruczkiewicz, J Mutus, O Naaman, M Neeley, C Neill, MY Niu, TE O’Brien, A Opremcak, B Pató, A Petukhov, NC Rubin, D Sank, V Shvarts, D Strain, M Szalay, B Villalonga, TC White, Z Yao, P Yeh, J Yoo, A Zalcman, H Neven, S Boixo, A Megrant, Y Chen, J Kelly, V Smelyanskiy, A Kitaev, M Knap, F Pollmann, P Roushan ·  Science 374 (6572), 1237-1241, 2021
Download PDF View
The discovery of topological order has revised the understanding of quantum matter and provided the theoretical foundation for many quantum error–correcting codes. Realizing topologically ordered states has proven to be challenging in both condensed matter and synthetic quantum systems. We prepared the ground state of the toric code Hamiltonian using an efficient quantum circuit on a superconducting quantum processor. We measured a topological entanglement entropy near the expected value of –ln2 and simulated anyon interferometry to extract the braiding statistics of the emergent excitations. Furthermore, we investigated key aspects of the surface code, including logical state injection and the decay of the nonlocal order parameter. Our results demonstrate the potential for quantum processors to provide insights into topological quantum matter and quantum error correction.
Revisiting dequantization and quantum advantage in learning tasks
Jordan Cotler, Hsin-Yuan Huang, Jarrod R McClean ·  arXiv preprint arXiv:2112.00811, 2021
Download PDF View
It has been shown that the apparent advantage of some quantum machine learning algorithms may be efficiently replicated using classical algorithms with suitable data access -- a process known as dequantization. Existing works on dequantization compare quantum algorithms which take copies of an n-qubit quantum state as input to classical algorithms which have sample and query (SQ) access to the vector . In this note, we prove that classical algorithms with SQ access can accomplish some learning tasks exponentially faster than quantum algorithms with quantum state inputs. Because classical algorithms are a subset of quantum algorithms, this demonstrates that SQ access can sometimes be significantly more powerful than quantum state inputs. Our findings suggest that the absence of exponential quantum advantage in some learning tasks may be due to SQ access being too powerful relative to quantum state inputs. If we compare quantum algorithms with quantum state inputs to classical algorithms with access to measurement data on quantum states, the landscape of quantum advantage can be dramatically different. We remark that when the quantum states are constructed from exponential-size classical data, comparing SQ access and quantum state inputs is appropriate since both require exponential time to prepare.
Nonequilibrium Monte Carlo for unfreezing variables in hard combinatorial optimization
Masoud Mohseni, Daniel Eppens, Johan Strumpfer, Raffaele Marino, Vasil Denchev, Alan K Ho, Sergei V Isakov, Sergio Boixo, Federico Ricci-Tersenghi, Hartmut Neven ·  arXiv preprint arXiv:2111.13628, 2021
Download PDF View
Optimizing highly complex cost/energy functions over discrete variables is at the heart of many open problems across different scientific disciplines and industries. A major obstacle is the emergence of many-body effects among certain subsets of variables in hard instances leading to critical slowing down or collective freezing for known stochastic local search strategies. An exponential computational effort is generally required to unfreeze such variables and explore other unseen regions of the configuration space. Here, we introduce a quantum-inspired family of nonlocal Nonequilibrium Monte Carlo (NMC) algorithms by developing an adaptive gradient-free strategy that can efficiently learn key instance-wise geometrical features of the cost function. That information is employed on-the-fly to construct spatially inhomogeneous thermal fluctuations for collectively unfreezing variables at various length scales, circumventing costly exploration versus exploitation trade-offs. We apply our algorithm to two of the most challenging combinatorial optimization problems: random k-satisfiability (k-SAT) near the computational phase transitions and Quadratic Assignment Problems (QAP). We observe significant speedup and robustness over both specialized deterministic solvers and generic stochastic solvers. In particular, for 90% of random 4-SAT instances we find solutions that are inaccessible for the best specialized deterministic algorithm known as Survey Propagation (SP) with an order of magnitude improvement in the quality of solutions for the hardest 10% instances. We also demonstrate two orders of magnitude improvement in time-to-solution over the …
Machine learning of high dimensional data on a noisy quantum processor
Evan Peters, João Caldeira, Alan Ho, Stefan Leichenauer, Masoud Mohseni, Hartmut Neven, Panagiotis Spentzouris, Doug Strain, Gabriel N Perdue ·  npj Quantum Information 7 (1), 161, 2021
Download PDF View
Quantum kernel methods show promise for accelerating data analysis by efficiently learning relationships between input data points that have been encoded into an exponentially large Hilbert space. While this technique has been used successfully in small-scale experiments on synthetic datasets, the practical challenges of scaling to large circuits on noisy hardware have not been thoroughly addressed. Here, we present our findings from experimentally implementing a quantum kernel classifier on real high-dimensional data taken from the domain of cosmology using Google’s universal quantum processor, Sycamore. We construct a circuit ansatz that preserves kernel magnitudes that typically otherwise vanish due to an exponentially growing Hilbert space, and implement error mitigation specific to the task of computing quantum kernels on near-term hardware. Our experiment utilizes 17 qubits to classify …
Fault-tolerant quantum simulations of chemistry in first quantization
Yuan Su, Dominic W Berry, Nathan Wiebe, Nicholas Rubin, Ryan Babbush ·  PRX Quantum 2 (4), 040332, 2021
Download PDF View
Quantum simulations of chemistry in first quantization offer some important advantages over approaches in second quantization including faster convergence to the continuum limit and the opportunity for practical simulations outside of the Born-Oppenheimer approximation. However, since all prior work on quantum simulation of chemistry in first quantization has been limited to asymptotic analysis, it has been impossible to directly compare the resources required for these approaches to those required for the more commonly studied algorithms in second quantization. Here, we compile, optimize, and analyze the finite resources required to implement two first quantized quantum algorithms for chemistry from Babbush et al. [Npj Quantum Inf. 5, 92 (2019)] that realize block encodings for the qubitization and interaction-picture frameworks of Low et al. [Quantum 3, 163 (2019), arXiv:1805.00675 (2018)]. The two algorithms we study enable …
The fermionic quantum emulator
Nicholas C Rubin, Klaas Gunst, Alec White, Leon Freitag, Kyle Throssell, Garnet Kin-Lic Chan, Ryan Babbush, Toru Shiozaki ·  Quantum 5, 568, 2021
Download PDF View
The fermionic quantum emulator (FQE) is a collection of protocols for emulating quantum dynamics of fermions efficiently taking advantage of common symmetries present in chemical, materials, and condensed-matter systems. The library is fully integrated with the OpenFermion software package and serves as the simulation backend. The FQE reduces memory footprint by exploiting number and spin symmetry along with custom evolution routines for sparse and dense Hamiltonians, allowing us to study significantly larger quantum circuits at modest computational cost when compared against qubit state vector simulators. This release paper outlines the technical details of the simulation methods and key advantages.
The quantum approximate optimization algorithm at high depth for maxcut on large-girth regular graphs and the sherrington-kirkpatrick model
Joao Basso, Edward Farhi, Kunal Marwaha, Benjamin Villalonga, Leo Zhou ·  arXiv preprint arXiv:2110.14206, 2021
Download PDF View
The Quantum Approximate Optimization Algorithm (QAOA) finds approximate solutions to combinatorial optimization problems. Its performance monotonically improves with its depth . We apply the QAOA to MaxCut on large-girth -regular graphs. We give an iterative formula to evaluate performance for any at any depth . Looking at random -regular graphs, at optimal parameters and as goes to infinity, we find that the QAOA beats all classical algorithms (known to the authors) that are free of unproven conjectures. While the iterative formula for these -regular graphs is derived by looking at a single tree subgraph, we prove that it also gives the ensemble-averaged performance of the QAOA on the Sherrington-Kirkpatrick (SK) model defined on the complete graph. We also generalize our formula to Max--XORSAT on large-girth regular hypergraphs. Our iteration is a compact procedure, but its computational complexity grows as . This iteration is more efficient than the previous procedure for analyzing QAOA performance on the SK model, and we are able to numerically go to . Encouraged by our findings, we make the optimistic conjecture that the QAOA, as goes to infinity, will achieve the Parisi value. We analyze the performance of the quantum algorithm, but one needs to run it on a quantum computer to produce a string with the guaranteed performance.
What the foundations of quantum computer science teach us about chemistry
Jarrod R McClean, Nicholas C Rubin, Joonho Lee, Matthew P Harrigan, Thomas E O’Brien, Ryan Babbush, William J Huggins, Hsin-Yuan Huang ·  The Journal of Chemical Physics 155 (15), 2021
Download PDF View
With the rapid development of quantum technology, one of the leading applications that has been identified is the simulation of chemistry. Interestingly, even before full scale quantum computers are available, quantum computer science has exhibited a remarkable string of results that directly impact what is possible in a chemical simulation with any computer. Some of these results even impact our understanding of chemistry in the real world. In this Perspective, we take the position that direct chemical simulation is best understood as a digital experiment. While on the one hand, this clarifies the power of quantum computers to extend our reach, it also shows us the limitations of taking such an approach too directly. Leveraging results that quantum computers cannot outpace the physical world, we build to the controversial stance that some chemical problems are best viewed as problems for which no algorithm can …
Virtual distillation for quantum error mitigation
William J Huggins, Sam McArdle, Thomas E O’Brien, Joonho Lee, Nicholas C Rubin, Sergio Boixo, K Birgitta Whaley, Ryan Babbush, Jarrod R McClean ·  Physical Review X 11 (4), 041036, 2021
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 copies of a noisy state . This enables us to estimate expectation values with respect to a state with dramatically reduced error without explicitly preparing it, hence the name “virtual distillation.” As increases, this state approaches the closest pure state to exponentially quickly. We analyze the effectiveness of virtual distillation and find that it is governed in many regimes by the behavior of this pure state (corresponding to the dominant eigenvector of …
Efficient approximation of experimental Gaussian boson sampling
Benjamin Villalonga, Murphy Yuezhen Niu, Li Li, Hartmut Neven, John C Platt, Vadim N Smelyanskiy, Sergio Boixo ·  arXiv preprint arXiv:2109.11525, 2021
Download PDF View
Two recent landmark experiments have performed Gaussian boson sampling (GBS) with a non-programmable linear interferometer and threshold detectors on up to 144 output modes (see Refs.~\onlinecite{zhong_quantum_2020,zhong2021phase}). Here we give classical sampling algorithms with better total variation distance and Kullback-Leibler divergence than these experiments and a computational cost quadratic in the number of modes. Our method samples from a distribution that approximates the single-mode and two-mode ideal marginals of the given Gaussian boson sampler, which are calculated efficiently. One implementation sets the parameters of a Boltzmann machine from the calculated marginals using a mean field solution. This is a 2nd order approximation, with the uniform and thermal approximations corresponding to the 0th and 1st order, respectively. The th order approximation reproduces Ursell functions (also known as connected correlations) up to order with a cost exponential in and high precision, while the experiment exhibits higher order Ursell functions with lower precision. This methodology, like other polynomial approximations introduced previously, does not apply to random circuit sampling because the th order approximation would simply result in the uniform distribution, in contrast to GBS.
Fermionic partial tomography via classical shadows
Andrew Zhao, Nicholas C Rubin, Akimasa Miyake ·  Physical Review Letters 127 (11), 110504, 2021
Download PDF View
We propose a tomographic protocol for estimating any -body reduced density matrix (-RDM) of an -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 -RDM elements to additive precision requires on the order of (nk)k3/2log(n)/ϵ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 , as compared to prior deterministic strategies. We …
Variational quantum algorithms
Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, Patrick J Coles ·  Nature Reviews Physics 3 (9), 625-644, 2021
Download PDF View
Applications such as simulating complicated quantum systems or solving large-scale linear algebra problems are very challenging for classical computers, owing to the extremely high computational cost. Quantum computers promise a solution, although fault-tolerant quantum computers will probably not be available in the near future. Current quantum devices have serious constraints, including limited numbers of qubits and noise processes that limit circuit depth. Variational quantum algorithms (VQAs), which use a classical optimizer to train a parameterized quantum circuit, have emerged as a leading strategy to address these constraints. VQAs have now been proposed for essentially all applications that researchers have envisaged for quantum computers, and they appear to be the best hope for obtaining quantum advantage. Nevertheless, challenges remain, including the trainability, accuracy and efficiency of …
Lilliput: A lightweight low-latency lookup-table based decoder for near-term quantum error correction
Poulami Das, Aditya Locharla, Cody Jones ·  arXiv preprint arXiv:2108.06569, 2021
View
None
A quantum algorithm for training wide and deep classical neural networks
Alexander Zlokapa, Hartmut Neven, Seth Lloyd ·  arXiv preprint arXiv:2107.09200, 2021
Download PDF View
Given the success of deep learning in classical machine learning, quantum algorithms for traditional neural network architectures may provide one of the most promising settings for quantum machine learning. Considering a fully-connected feedforward neural network, we show that conditions amenable to classical trainability via gradient descent coincide with those necessary for efficiently solving quantum linear systems. We propose a quantum algorithm to approximately train a wide and deep neural network up to error for a training set of size by performing sparse matrix inversion in time. To achieve an end-to-end exponential speedup over gradient descent, the data distribution must permit efficient state preparation and readout. We numerically demonstrate that the MNIST image dataset satisfies such conditions; moreover, the quantum algorithm matches the accuracy of the fully-connected network. Beyond the proven architecture, we provide empirical evidence for training of a convolutional neural network with pooling.
Exponential suppression of bit or phase errors with cyclic error correction
Nature 595 (7867), 383-387, 2021
Download PDF View
Realizing the potential of quantum computing requires sufficiently low logical error rates. Many applications call for error rates as low as 10−15 (refs. , , , , , , –), but state-of-the-art quantum platforms typically have physical error rates near 10−3 (refs. , , , –). Quantum error correction, – promises to bridge this divide by distributing quantum logical information across many physical qubits in such a way that errors can be detected and corrected. Errors on the encoded logical qubit state can be exponentially suppressed as the number of physical qubits grows, provided that the physical error rates are below a certain threshold and stable over the course of a computation. Here we implement one-dimensional repetition codes embedded in a two-dimensional grid of superconducting qubits that demonstrate exponential suppression of bit-flip or phase-flip errors, reducing logical error per round more than 100-fold when …
Stim: a fast stabilizer circuit simulator
Craig Gidney ·  Quantum 5, 497, 2021
Download PDF View
This paper presents “Stim", a fast simulator for quantum stabilizer circuits. The paper explains how Stim works and compares it to existing tools. With no foreknowledge, Stim can analyze a distance 100 surface code circuit (20 thousand qubits, 8 million gates, 1 million measurements) in 15 seconds and then begin sampling full circuit shots at a rate of 1 kHz. Stim uses a stabilizer tableau representation, similar to Aaronson and Gottesman's CHP simulator, but with three main improvements. First, Stim improves the asymptotic complexity of deterministic measurement from quadratic to linear by tracking the $ inverse $ of the circuit's stabilizer tableau. Second, Stim improves the constant factors of the algorithm by using a cache-friendly data layout and 256 bit wide SIMD instructions. Third, Stim only uses expensive stabilizer tableau simulation to create an initial reference sample. Further samples are collected in bulk by using that sample as a reference for batches of Pauli frames propagating through the circuit.
Even more efficient quantum computations of chemistry through tensor hypercontraction
Joonho Lee, Dominic W Berry, Craig Gidney, William J Huggins, Jarrod R McClean, Nathan Wiebe, Ryan Babbush ·  PRX Quantum 2 (3), 030305, 2021
Download PDF View
We describe quantum circuits with only Toffoli complexity that block encode the spectra of quantum chemistry Hamiltonians in a basis of arbitrary (e.g., molecular) orbitals. With repetitions of these circuits one can use phase estimation to sample in the molecular eigenbasis, where is the 1-norm of Hamiltonian coefficients and is the target precision. This is the lowest complexity 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 work only 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 nonorthogonal basis defined by the THC factors …
Low-depth mechanisms for quantum optimization
Jarrod R McClean, Matthew P Harrigan, Masoud Mohseni, Nicholas C Rubin, Zhang Jiang, Sergio Boixo, Vadim N Smelyanskiy, Ryan Babbush, Hartmut Neven ·  PRX Quantum 2 (3), 030312, 2021
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 …
Cryogenic low-noise amplifiers: Noise performance and power dissipation
Joseph C Bardin ·  IEEE Solid-State Circuits Magazine 13 (2), 22-35, 2021
Download PDF View
Cryogenically cooled low-noise amplifiers (LNAs) have had a profound impact on experimental science. For instance, these amplifiers allow us to communicate with distant spacecraft, probe the history and composition of the universe through radio astronomy, study basic phenomena through low-temperature physics research, and read out the state of quantum systems as required for quantum computing. These devices-which can achieve noise performance within an order of magnitude of the fundamental limits imposed by quantum mechanics-find use from low frequencies through several hundreds of gigahertz. Without cryogenic LNAs, whole branches of experimental science simply could not exist.
Cryogenic single-port calibration for superconducting microwave resonator measurements
Haozhi Wang, Suren Singh, CRH McRae, Joseph C Bardin, SX Lin, N Messaoudi, AR Castelli, YJ Rosen, ET Holland, DP Pappas, JY Mutus ·  Quantum Science and Technology 6 (3), 035015, 2021
Download PDF View
Superconducting circuit testing and materials loss characterization requires robust and reliable methods for the extraction of internal and coupling quality factors of microwave resonators. A common method, imposed by limitations on the device design or experimental configuration, is the single-port reflection geometry, ie reflection-mode. However, impedance mismatches in cryogenic systems must be accounted for through calibration of the measurement chain while it is at low temperatures. In this paper, we demonstrate a data-based, single-port calibration using commercial microwave standards and a vector network analyzer with samples at millikelvin temperature in a dilution refrigerator, making this method useful for measurements of quantum phenomena. Finally, we cross reference our data-based, single-port calibration and reflection measurement with over-coupled 2D-and 3D-resonators against well …
Accurately computing the electronic properties of a quantum ring
C Neill, T McCourt, X Mi, Z Jiang, MY Niu, W Mruczkiewicz, I Aleiner, F Arute, K Arya, J Atalaya, R Babbush, JC Bardin, R Barends, A Bengtsson, A Bourassa, M Broughton, BB Buckley, DA Buell, B Burkett, N Bushnell, J Campero, Z Chen, B Chiaro, R Collins, W Courtney, S Demura, AR Derk, A Dunsworth, D Eppens, C Erickson, E Farhi, AG Fowler, B Foxen, C Gidney, M Giustina, JA Gross, MP Harrigan, SD Harrington, J Hilton, A Ho, S Hong, T Huang, WJ Huggins, SV Isakov, M Jacob-Mitos, E Jeffrey, C Jones, D Kafri, K Kechedzhi, J Kelly, S Kim, PV Klimov, AN Korotkov, F Kostritsa, D Landhuis, P Laptev, E Lucero, O Martin, JR McClean, M McEwen, A Megrant, KC Miao, M Mohseni, J Mutus, O Naaman, M Neeley, M Newman, TE O’Brien, A Opremcak, E Ostby, B Pató, A Petukhov, C Quintana, N Redd, NC Rubin, D Sank, KJ Satzinger, V Shvarts, D Strain, M Szalay, MD Trevithick, B Villalonga, TC White, Z Yao, P Yeh, A Zalcman, H Neven, S Boixo, LB Ioffe, P Roushan, Y Chen, V Smelyanskiy ·  Nature 594 (7864), 508-512, 2021
Download PDF View
A promising approach to study condensed-matter systems is to simulate them on an engineered quantum platform, , –. However, the accuracy needed to outperform classical methods has not been achieved so far. Here, using 18 superconducting qubits, we provide an experimental blueprint for an accurate condensed-matter simulator and demonstrate how to investigate fundamental electronic properties. We benchmark 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 measure the energy eigenvalues of this wire with an error of approximately 0.01 rad, whereas typical energy scales are of the order of 1 rad. Insight into the fidelity of this algorithm is gained by highlighting the robust properties of a Fourier transform, including the ability to resolve eigenenergies with a statistical …
A CCCZ gate performed with 6 T gates
Craig Gidney, N Cody Jones ·  arXiv preprint arXiv:2106.11513, 2021
Download PDF View
We construct a CCCZ gate using six T gates, assisted by stabilizer operations and classical feedback. More generally, we reduce the T cost of a gate from to , for .
Characterization of shot noise suppression in nanometer MOSFETs
Sayan Das, Joseph C Bardin ·  2021 IEEE MTT-S International Microwave Symposium (IMS), 892-895, 2021
Download PDF View
Shot noise contributes significantly to the drain current noise in short-channel MOSFETs. The transport of carriers at the source-side of the channel is dominated by diffusion, leading to shot noise. However, channel resistance introduces carrier scattering, which eventually causes suppression of shot noise. The degree of suppression is described by a scaling factor, known as the Fano factor. This paper presents a detailed experimental evaluation of the Fano factor for nanometer-scale MOSFETs across seven different technology nodes, ranging from 12 nm to 180 nm. The dependence of the Fano factor on device bias, gate length, and channel doping is studied. We find that it is a strong function of device bias when the MOSFET operates at or close to the minimum noise bias. We also find that it rises for shorter gate length devices and is dependent on channel doping. The dependence of the Fano factor on channel …
A frequency and bandwidth reconfigurable 3–6 GHz cryogenic SiGe BiCMOS LNA with a power consumption of≤ 2.9 mW
Zhenjie Zou, Mohsen Hosseini, Randy Kwende, Sanjay Raman, Joseph C Bardin ·  2021 IEEE MTT-S International Microwave Symposium (IMS), 653-656, 2021
Download PDF View
A 3–6 GHz reconfigurable SiGe cryogenic low-noise amplifier has been designed, fabricated, and tested. The integrated circuit features a broadband input-stage followed by a pair of buffered reconfigurable second-order systems. When characterized at a physical temperature of 15K and configured for a broadband response (3–6 GHz), we find that it provides in excess of 35 dB of gain while achieving an average noise temperature of 4.3K from 3–6 GHz and dissipating 1.8mW. By changing the states of the digitally controllable second-order systems and on-chip digital-to-analog-converter-based bias generators, we show that the amplifier can be tuned in both bandwidth and center frequency while maintaining similar performance specifications to those achieved in the broadband mode of operation. In all cases, the power consumption of the amplifier is lower than 2.9mW. To the best of the authors' knowledge, this …
Layerwise learning for quantum neural networks
Andrea Skolik, Jarrod R McClean, Masoud Mohseni, Patrick Van Der Smagt, Martin Leib ·  Quantum Machine Intelligence 3, 1-11, 2021
Download PDF View
With the increased focus on quantum circuit learning for near-term applications on quantum devices, in conjunction with unique challenges presented by cost function landscapes of parametrized quantum circuits, strategies for effective training are becoming increasingly important. In order to ameliorate some of these challenges, we investigate a layerwise learning strategy for parametrized quantum circuits. The circuit depth is incrementally grown during optimization, and only subsets of parameters are updated in each training step. We show that when considering sampling noise, this strategy can help avoid the problem of barren plateaus of the error surface due to the low depth of circuits, low number of parameters trained in one step, and larger magnitude of gradients compared to training the full circuit. These properties make our algorithm preferable for execution on noisy intermediate-scale quantum …
Universal discriminative quantum neural networks
Hongxiang Chen, Leonard Wossnig, Simone Severini, Hartmut Neven, Masoud Mohseni ·  Quantum Machine Intelligence 3, 1-11, 2021
Download PDF View
Recent results have demonstrated the successful applications of quantum-classical hybrid methods to train quantum circuits for a variety of machine learning tasks. A natural question to ask is consequentially whether we can also train such quantum circuits to discriminate quantum data, i.e., perform classification on data stored in form of quantum states. Although quantum mechanics fundamentally forbids deterministic discrimination of non-orthogonal states, we show in this work that it is possible to train a quantum circuit to discriminate such data with a trade-off between minimizing error rates and inconclusiveness rates of the classification tasks. Our approach achieves at the same time a performance which is close to the theoretically optimal values and a generalization ability to previously unseen quantum data. This generalization power hence distinguishes our work from previous circuit optimization …
Low rank representations for quantum simulation of electronic structure
Mario Motta, Erika Ye, Jarrod R McClean, Zhendong Li, Austin J Minnich, Ryan Babbush, Garnet Kin-Lic Chan ·  npj Quantum Information 7 (1), 83, 2021
Download PDF View
The quantum simulation of quantum chemistry is a promising application of quantum computers. However, for N molecular orbitals, the O (N 4) gate complexity of performing Hamiltonian and unitary Coupled Cluster Trotter steps makes simulation based on such primitives challenging. We substantially reduce the gate complexity of such primitives through a two-step low-rank factorization of the Hamiltonian and cluster operator, accompanied by truncation of small terms. Using truncations that incur errors below chemical accuracy allow one 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) gate complexity in the asymptotic regime; and unitary Coupled Cluster Trotter steps with 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 …
Error mitigation via verified phase estimation
Thomas E O’Brien, Stefano Polla, Nicholas C Rubin, William J Huggins, Sam McArdle, Sergio Boixo, Jarrod R McClean, Ryan Babbush ·  PRX quantum 2 (2), 020317, 2021
Download PDF View
The accumulation of noise in quantum computers is the dominant issue stymieing the push of quantum algorithms beyond their classical counterparts. We do not expect to be able to afford the overhead required for quantum error correction in the next decade, so in the meantime we must rely on low-cost, unscalable error mitigation techniques to bring quantum computing to its full potential. In this paper we present a new error mitigation technique based on quantum phase estimation that can also reduce errors in expectation value estimation (e.g., for variational algorithms). The general idea is to apply phase estimation while effectively postselecting for the system register to be in the starting state, which allows us to catch and discard errors that knock us away from there. We refer to this technique as “verified phase estimation” (VPE) and show that it can be adapted to function without the use of control qubits in order to …
How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
Craig Gidney, Martin Ekerå ·  Quantum 5, 433, 2021
Download PDF View
We significantly reduce the cost of factoring integers and computing discrete logarithms in finite fields on a quantum computer by combining techniques from Shor 1994, Griffiths-Niu 1996, Zalka 2006, Fowler 2012, Ekerå-Håstad 2017, Ekerå 2017, Ekerå 2018, Gidney-Fowler 2019, Gidney 2019. We estimate the approximate cost of our construction using plausible physical assumptions for large-scale superconducting qubit platforms: a planar grid of qubits with nearest-neighbor connectivity, a characteristic physical gate error rate of , a surface code cycle time of 1 microsecond, and a reaction time of 10 microseconds. We account for factors that are normally ignored such as noise, the need to make repeated attempts, and the spacetime layout of the computation. When factoring 2048 bit RSA integers, our construction's spacetime volume is a hundredfold less than comparable estimates from earlier works (Van Meter et al. 2009, Jones et al. 2010, Fowler et al. 2012, Gheorghiu et al. 2019). In the abstract circuit model (which ignores overheads from distillation, routing, and error correction) our construction uses logical qubits, Toffolis, and measurement depth to factor -bit RSA integers. We quantify the cryptographic implications of our work, both for RSA and for schemes based on the DLP in finite fields.
Removing leakage-induced correlated errors in superconducting quantum error correction
Matt McEwen, Dvir Kafri, Z Chen, Juan Atalaya, KJ Satzinger, Chris Quintana, Paul Victor Klimov, Daniel Sank, C Gidney, AG Fowler, F Arute, Kunal Arya, B Buckley, Brian Burkett, Nicholas Bushnell, Benjamin Chiaro, Roberto Collins, Sean Demura, Andrew Dunsworth, Catherine Erickson, B 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, M Niu, Alexandru Paler, Nick Redd, Pedram Roushan, TC White, Jamie Yao, Ping Yeh, A Zalcman, Yu Chen, VN Smelyanskiy, John M Martinis, Hartmut Neven, J Kelly, AN Korotkov, Andre Gregory Petukhov, Rami Barends ·  Nature communications 12 (1), 1761, 2021
Download PDF View
Quantum computing can become scalable through error correction, but logical error rates only decrease with system size when physical errors are sufficiently uncorrelated. During computation, unused high energy levels of the qubits can become excited, creating leakage states that are long-lived and mobile. Particularly for superconducting transmon qubits, this leakage opens a path to errors that are correlated in space and time. Here, we report a reset protocol that returns a qubit to the ground state from all relevant higher level states. We test its performance with the bit-flip stabilizer code, a simplified version of the surface code for quantum error correction. We investigate the accumulation and dynamics of leakage during error correction. Using this protocol, we find lower rates of logical errors and an improved scaling and stability of error suppression with increasing qubit number. This demonstration provides a key …
Focus beyond quadratic speedups for error-corrected quantum advantage
Ryan Babbush, Jarrod R McClean, Michael Newman, Craig Gidney, Sergio Boixo, Hartmut Neven ·  PRX quantum 2 (1), 010103, 2021
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 …
Quantum approximate optimization of non-planar graph problems on a planar superconducting processor
Matthew P Harrigan, Kevin J Sung, Matthew Neeley, Kevin J Satzinger, Frank Arute, Kunal Arya, Juan Atalaya, Joseph C Bardin, Rami Barends, Sergio Boixo, Michael Broughton, Bob B Buckley, David A Buell, Brian Burkett, Nicholas Bushnell, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Sean Demura, Andrew Dunsworth, Daniel Eppens, Austin Fowler, Brooks Foxen, Craig Gidney, Marissa Giustina, Rob Graff, Steve Habegger, Alan Ho, Sabrina Hong, Trent Huang, LB Ioffe, Sergei V Isakov, Evan Jeffrey, Zhang Jiang, Cody Jones, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Seon Kim, Paul V Klimov, Alexander N Korotkov, Fedor Kostritsa, David Landhuis, Pavel Laptev, Mike Lindmark, Martin Leib, Orion Martin, John M Martinis, Jarrod R McClean, Matt McEwen, Anthony Megrant, Xiao Mi, Masoud Mohseni, Wojciech Mruczkiewicz, Josh Mutus, Ofer Naaman, Charles Neill, Florian Neukart, Murphy Yuezhen Niu, Thomas E O’Brien, Bryan O’Gorman, Eric Ostby, Andre Petukhov, Harald Putterman, Chris Quintana, Pedram Roushan, Nicholas C Rubin, Daniel Sank, Andrea Skolik, Vadim Smelyanskiy, Doug Strain, Michael Streif, Marco Szalay, Amit Vainsencher, Theodore White, Z Jamie Yao, Ping Yeh, Adam Zalcman, Leo Zhou, Hartmut Neven, Dave Bacon, Erik Lucero, Edward Farhi, Ryan Babbush ·  Nature Physics 17 (3), 332-336, 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 …
Scaling advantage over path-integral Monte Carlo in quantum simulation of geometrically frustrated magnets
Andrew D King, Jack Raymond, Trevor Lanting, Sergei V Isakov, Masoud Mohseni, Gabriel Poulin-Lamarre, Sara Ejtemaee, William Bernoudy, Isil Ozfidan, Anatoly Yu Smirnov, Mauricio Reis, Fabio Altomare, Michael Babcock, Catia Baron, Andrew J Berkley, Kelly Boothby, Paul I Bunyk, Holly Christiani, Colin Enderud, Bram Evert, Richard Harris, Emile Hoskinson, Shuiyuan Huang, Kais Jooya, Ali Khodabandelou, Nicolas Ladizinsky, Ryan Li, P Aaron Lott, Allison JR MacDonald, Danica Marsden, Gaelen Marsden, Teresa Medina, Reza Molavi, Richard Neufeld, Mana Norouzpour, Travis Oh, Igor Pavlov, Ilya Perminov, Thomas Prescott, Chris Rich, Yuki Sato, Benjamin Sheldan, George Sterling, Loren J Swenson, Nicholas Tsai, Mark H Volkmann, Jed D Whittaker, Warren Wilkinson, Jason Yao, Hartmut Neven, Jeremy P Hilton, Eric Ladizinsky, Mark W Johnson, Mohammad H Amin ·  Nature communications 12 (1), 1113, 2021
Download PDF View
The promise of quantum computing lies in harnessing programmable quantum devices for practical applications such as efficient simulation of quantum materials and condensed matter systems. One important task is the simulation of geometrically frustrated magnets in which topological phenomena can emerge from competition between quantum and thermal fluctuations. Here we report on experimental observations of equilibration in such simulations, measured on up to 1440 qubits with microsecond resolution. By initializing the system in a state with topological obstruction, we observe quantum annealing (QA) equilibration timescales in excess of one microsecond. Measurements indicate a dynamical advantage in the quantum simulation compared with spatially local update dynamics of path-integral Monte Carlo (PIMC). The advantage increases with both system size and inverse temperature, exceeding a …
Efficient and noise resilient measurements for quantum chemistry on near-term quantum computers
William J Huggins, Jarrod R McClean, Nicholas C Rubin, Zhang Jiang, Nathan Wiebe, K Birgitta Whaley, Ryan Babbush ·  npj Quantum Information 7 (1), 23, 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 …
Quantum simulators: Architectures and opportunities
Ehud Altman, Kenneth R Brown, Giuseppe Carleo, Lincoln D Carr, Eugene Demler, Cheng Chin, Brian DeMarco, Sophia E Economou, Mark A Eriksson, Kai-Mei C Fu, Markus Greiner, Kaden RA Hazzard, Randall G Hulet, Alicia J Kollár, Benjamin L Lev, Mikhail D Lukin, Ruichao Ma, Xiao Mi, Shashank Misra, Christopher Monroe, Kater Murch, Zaira Nazario, Kang-Kuen Ni, Andrew C Potter, Pedram Roushan, Mark Saffman, Monika Schleier-Smith, Irfan Siddiqi, Raymond Simmonds, Meenakshi Singh, IB Spielman, Kristan Temme, David S Weiss, Jelena Vučković, Vladan Vuletić, Jun Ye, Martin Zwierlein ·  PRX quantum 2 (1), 017003, 2021
Download PDF View
Quantum simulators are a promising technology on the spectrum of quantum devices from specialized quantum experiments to universal quantum computers. These quantum devices utilize entanglement and many-particle behavior to explore and solve hard scientific, engineering, and computational problems. Rapid development over the last two decades has produced more than 300 quantum simulators in operation worldwide using a wide variety of experimental platforms. Recent advances in several physical architectures promise a golden age of quantum simulators ranging from highly optimized special purpose simulators to flexible programmable devices. These developments have enabled a convergence of ideas drawn from fundamental physics, computer science, and device engineering. They have strong potential to address problems of societal importance, ranging from understanding vital chemical …
From pulses to circuits and back again: A quantum optimal control perspective on variational quantum algorithms
Alicia B Magann, Christian Arenz, Matthew D Grace, Tak-San Ho, Robert L Kosut, Jarrod R McClean, Herschel A Rabitz, Mohan Sarovar ·  PRX Quantum 2 (1), 010101, 2021
Download PDF View
The last decade has witnessed remarkable progress in the development of quantum technologies. Although fault-tolerant devices likely remain years away, the noisy intermediate-scale quantum devices of today may be leveraged for other purposes. Leading candidates are variational quantum algorithms (VQAs), which have been developed for applications including chemistry, optimization, and machine learning, but whose implementations on quantum devices have yet to demonstrate improvements over classical capabilities. In this Perspective, we propose a variety of ways that the performance of VQAs could be informed by quantum optimal control theory. A major theme throughout is the need for sufficient control resources in VQA implementations; we discuss different ways this need can manifest, outline a variety of open questions, and look to the future.
Power of data in quantum machine learning
HY Huang, M Broughton, M Mohseni, R Babbush, S Boixo, H Neven, JR McClean ·  Nature Communications 12, 2631, 2021
Download PDF View
The use of quantum computing for machine learning is among the most exciting prospective applications of quantum technologies. However, machine learning tasks where data is provided can be considerably different than commonly studied computational tasks. In this work, we show that some problems that are classically hard to compute can be easily predicted by classical machines learning from data. Using rigorous prediction error bounds as a foundation, we develop a methodology for assessing potential quantum advantage in learning tasks. The bounds are tight asymptotically and empirically predictive for a wide range of learning models. These constructions explain numerical results showing that with the help of data, classical machine learning models can be competitive with quantum models even if they are tailored to quantum problems. We then propose a projected quantum model that provides a …
Compilation of fault-tolerant quantum heuristics for combinatorial optimization
Yuval R Sanders, Dominic W Berry, Pedro CS Costa, Louis W Tessler, Nathan Wiebe, Craig Gidney, Hartmut Neven, Ryan Babbush ·  PRX quantum 1 (2), 020312, 2020
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 …
Observation of separated dynamics of charge and spin in the Fermi-Hubbard model
Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Andreas Bengtsson, Sergio Boixo, Michael Broughton, Bob B Buckley, David A Buell, Brian Burkett, Nicholas Bushnell, Yu Chen, Zijun Chen, Yu-An Chen, Ben Chiaro, Roberto Collins, Stephen J Cotton, William Courtney, Sean Demura, Alan Derk, Andrew Dunsworth, Daniel Eppens, Thomas Eckl, Catherine Erickson, Edward Farhi, Austin Fowler, Brooks Foxen, Craig Gidney, Marissa Giustina, Rob Graff, Jonathan A Gross, Steve Habegger, Matthew P Harrigan, Alan Ho, Sabrina Hong, Trent Huang, William Huggins, Lev B Ioffe, Sergei V Isakov, Evan Jeffrey, Zhang Jiang, Cody Jones, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Seon Kim, Paul V Klimov, Alexander N Korotkov, Fedor Kostritsa, David Landhuis, Pavel Laptev, Mike Lindmark, Erik Lucero, Michael Marthaler, Orion Martin, John M Martinis, Anika Marusczyk, Sam McArdle, Jarrod R McClean, Trevor McCourt, Matt McEwen, Anthony Megrant, Carlos Mejuto-Zaera, Xiao Mi, Masoud Mohseni, Wojciech Mruczkiewicz, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Hartmut Neven, Michael Newman, Murphy Yuezhen Niu, Thomas E O'Brien, Eric Ostby, Bálint Pató, Andre Petukhov, Harald Putterman, Chris Quintana, Jan-Michael Reiner, Pedram Roushan, Nicholas C Rubin, Daniel Sank, Kevin J Satzinger, Vadim Smelyanskiy, Doug Strain, Kevin J Sung, Peter Schmitteckert, Marco Szalay, Norm M Tubman, Amit Vainsencher, Theodore White, Nicolas Vogt, Z Jamie Yao, Ping Yeh, Adam Zalcman, Sebastian Zanker ·  arXiv preprint arXiv:2010.07965, 2020
Download PDF View
Strongly correlated quantum systems give rise to many exotic physical phenomena, including high-temperature superconductivity. Simulating these systems on quantum computers may avoid the prohibitively high computational cost incurred in classical approaches. However, systematic errors and decoherence effects presented in current quantum devices make it difficult to achieve this. Here, we simulate the dynamics of the one-dimensional Fermi-Hubbard model using 16 qubits on a digital superconducting quantum processor. We observe separations in the spreading velocities of charge and spin densities in the highly excited regime, a regime that is beyond the conventional quasiparticle picture. To minimize systematic errors, we introduce an accurate gate calibration procedure that is fast enough to capture temporal drifts of the gate parameters. We also employ a sequence of error-mitigation techniques to reduce decoherence effects and residual systematic errors. These procedures allow us to simulate the time evolution of the model faithfully despite having over 600 two-qubit gates in our circuits. Our experiment charts a path to practical quantum simulation of strongly correlated phenomena using available quantum devices.
Using models to improve optimizers for variational quantum algorithms
Kevin J Sung, Jiahao Yao, Matthew P Harrigan, Nicholas C Rubin, Zhang Jiang, Lin Lin, Ryan Babbush, Jarrod R McClean ·  Quantum Science and Technology 5 (4), 044008, 2020
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. In this work, we introduce two optimization methods and numerically compare their performance with common methods in use today. The methods are surrogate model-based algorithms designed to improve reuse of collected data. They do so by utilizing a least-squares quadratic fit of sampled …
Demonstrating a continuous set of two-qubit gates for near-term quantum algorithms
Brooks Foxen, Charles Neill, Andrew Dunsworth, Pedram Roushan, Ben Chiaro, Anthony Megrant, Julian Kelly, Zijun Chen, Kevin Satzinger, Rami Barends, F Arute, Kunal Arya, Ryan Babbush, Dave Bacon, JC Bardin, Sergio Boixo, D Buell, Brian Burkett, Yu Chen, Roberto Collins, Edward Farhi, Austin Fowler, C Gidney, Marissa Giustina, Rob Graff, M Harrigan, Trent Huang, SV 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, JY Mutus, Ofer Naaman, Matthew Neeley, M Niu, A Petukhov, C Quintana, N Rubin, D Sank, V Smelyanskiy, A Vainsencher, TC White, Z Yao, P Yeh, A Zalcman, H Neven, John M Martinis, (Google AI Quantum) ·  Physical Review Letters 125 (12), 120504, 2020
Download PDF View
Quantum algorithms offer a dramatic speedup for computational problems in material science and chemistry. However, any near-term realizations of these algorithms will need to be optimized to fit within the finite resources offered by existing noisy hardware. Here, taking advantage of the adjustable coupling of gmon qubits, we demonstrate a continuous two-qubit gate set that can provide a threefold reduction in circuit depth as compared to a standard decomposition. We implement two gate families: an imaginary swap-like (iSWAP-like) gate to attain an arbitrary swap angle, , and a controlled-phase gate that generates an arbitrary conditional phase, . 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 (fSim) gate set. We benchmark the fidelity of the iSWAP-like and controlled …
Discontinuous Galerkin discretization for quantum simulation of chemistry
Jarrod R McClean, Fabian M Faulstich, Qinyi Zhu, Bryan O’Gorman, Yiheng Qiu, Steven R White, Ryan Babbush, Lin Lin ·  New Journal of Physics 22 (9), 093015, 2020
Download PDF View
All-electron electronic structure methods based on the linear combination of atomic orbitals method with Gaussian basis set discretization offer a well established, compact representation that forms much of the foundation of modern 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 …
Hartree-Fock on a superconducting qubit quantum computer
Google AI Quantum and Collaborators*†, Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Sergio Boixo, Michael Broughton, Bob B Buckley, David A Buell, Brian Burkett, Nicholas Bushnell, Yu Chen, Zijun Chen, Benjamin Chiaro, Roberto Collins, William Courtney, Sean Demura, Andrew Dunsworth, Edward Farhi, Austin Fowler, Brooks Foxen, Craig Gidney, Marissa Giustina, Rob Graff, Steve Habegger, Matthew P Harrigan, Alan Ho, Sabrina Hong, Trent Huang, William J Huggins, Lev Ioffe, Sergei V Isakov, Evan Jeffrey, Zhang Jiang, Cody Jones, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Seon Kim, Paul V Klimov, Alexander Korotkov, Fedor Kostritsa, David Landhuis, Pavel Laptev, Mike Lindmark, Erik Lucero, Orion Martin, John M Martinis, Jarrod R McClean, Matt McEwen, Anthony Megrant, Xiao Mi, Masoud Mohseni, Wojciech Mruczkiewicz, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Hartmut Neven, Murphy Yuezhen Niu, Thomas E O’Brien, Eric Ostby, Andre Petukhov, Harald Putterman, Chris Quintana, Pedram Roushan, Nicholas C Rubin, Daniel Sank, Kevin J Satzinger, Vadim Smelyanskiy, Doug Strain, Kevin J Sung, Marco Szalay, Tyler Y Takeshita, Amit Vainsencher, Theodore White, Nathan Wiebe, Z Jamie Yao, Ping Yeh, Adam Zalcman ·  Science 369 (6507), 1084-1089, 2020
Download PDF View
The simulation of fermionic systems is among the most anticipated applications of quantum computing. We performed several quantum simulations of chemistry with up to one dozen qubits, including modeling the isomerization mechanism of diazene. We also demonstrated error-mitigation strategies based on N-representability that dramatically improve the effective fidelity of our experiments. Our parameterized ansatz circuits realized the Givens rotation approach to noninteracting fermion evolution, which we variationally optimized to prepare the Hartree-Fock wave function. This ubiquitous algorithmic primitive is classically tractable to simulate yet still generates highly entangled states over the computational basis, which allowed us to assess the performance of our hardware and establish a foundation for scaling up correlated quantum chemistry simulations.
Improved fault-tolerant quantum simulation of condensed-phase correlated electrons via trotterization
Ian D Kivlichan, Craig Gidney, Dominic W Berry, Nathan Wiebe, Jarrod McClean, Wei Sun, Zhang Jiang, Nicholas Rubin, Austin Fowler, Alán Aspuru-Guzik, Hartmut Neven, Ryan Babbush ·  Quantum 4, 296, 2020
Download PDF View
Recent work has deployed linear combinations of unitaries techniques to reduce the cost of fault-tolerant quantum simulations of correlated electron models. Here, we show that one can sometimes improve upon 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 (eg energies per unit cell), as is often the goal for condensed-phase systems. In this context, simulations of the Hubbard and plane-wave electronic structure models with fermionic modes can be performed with roughly and T complexities. We perform numerics revealing tradeoffs between the error and gate complexity of a Trotter step; eg, we show that split-operator techniques have less Trotter error than popular alternatives. By compiling to surface code fault-tolerant gates and assuming error rates of one part per thousand, we show that one can error-correct quantum simulations of interesting, classically intractable instances with a few hundred thousand physical qubits.
Nearly optimal measurement scheduling for partial tomography of quantum states
Xavier Bonet-Monroig, Ryan Babbush, Thomas E O’Brien ·  Physical Review X 10 (3), 031064, 2020
Download PDF View
Many applications of quantum simulation require one to prepare and then characterize quantum states by efficiently estimating -body reduced density matrices (-RDMs), from which observables of interest may be obtained. For instance, the fermionic 2-RDM contains the energy, charge density, and energy gradients of an electronic system, while the qubit 2-RDM contains the spatial correlation functions of magnetic systems. Naive estimation of such RDMs requires repeated state preparations for each matrix element, which makes for prohibitively large computation times. However, commuting matrix elements may be measured simultaneously, allowing for a significant cost reduction. In this work, we design schemes for such a parallelization with near-optimal complexity in the system size . We first describe a scheme to sample all elements of a qubit -RDM using only unique measurement circuits, an exponential improvement …
OpenFermion: the electronic structure package for quantum computers
Jarrod R McClean, Nicholas C Rubin, Kevin J Sung, Ian D Kivlichan, Xavier Bonet-Monroig, Yudong Cao, Chengyu Dai, E Schuyler Fried, Craig Gidney, Brendan Gimby, Pranav Gokhale, Thomas Häner, Tarini Hardikar, Vojtěch Havlíček, Oscar Higgott, Cupjin Huang, Josh Izaac, Zhang Jiang, Xinle Liu, Sam McArdle, Matthew Neeley, Thomas O’brien, Bryan O’gorman, Isil Ozfidan, Maxwell D Radin, Jhonathan Romero, Nicolas PD Sawaya, Bruno Senjean, Kanav Setia, Sukin Sim, Damian S Steiger, Mark Steudtner, Qiming Sun, Wei Sun, Daochen Wang, Fang Zhang, Ryan Babbush ·  Quantum Science and Technology 5 (3), 034014, 2020
Download PDF View
Quantum simulation of chemistry and materials is predicted to be an important 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 (www. openfermion. org). OpenFermion is an open-source software library written largely in Python under an Apache 2.0 license, aimed at enabling the simulation of fermionic and bosonic 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 …
The snake optimizer for learning quantum processor control parameters
Paul V Klimov, Julian Kelly, John M Martinis, Hartmut Neven ·  arXiv preprint 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, the Snake Optimizer scales favorably with qubit number and is amenable to both local re-optimization and parallelization, showing promise for optimizing much larger quantum processors.
Optimal fermion-to-qubit mapping via ternary trees with applications to reduced quantum states learning
Zhang Jiang, Amir Kalev, Wojciech Mruczkiewicz, Hartmut Neven ·  Quantum 4, 276, 2020
Download PDF View
We introduce a fermion-to-qubit mapping defined on ternary trees, where any single Majorana operator on an -mode fermionic system is mapped to a multi-qubit Pauli operator acting nontrivially on qubits. The mapping has a simple structure and is optimal in the sense that it is impossible to construct Pauli operators in any fermion-to-qubit mapping acting nontrivially on less than qubits on average. We apply it to the problem of learning -fermion reduced density matrix (RDM), a problem relevant in various quantum simulation applications. We show that one can determine individual elements of all -fermion RDMs in parallel, to precision , by repeating a single quantum circuit for times. This result is based on a method we develop here that allows one to determine individual elements of all -qubit RDMs in parallel, to precision , by repeating a single quantum circuit for times, independent of the system size. This improves over existing schemes for determining qubit RDMs.
Establishing the quantum supremacy frontier with a 281 pflop/s simulation
Benjamin Villalonga, Dmitry Lyakh, Sergio Boixo, Hartmut Neven, Travis S Humble, Rupak Biswas, Eleanor G Rieffel, Alan Ho, Salvatore Mandrà ·  Quantum Science and Technology 5 (3), 034003, 2020
Download PDF View
Noisy intermediate-scale quantum (NISQ) computers are entering an era in which they can perform computational tasks beyond the capabilities of the most powerful classical computers, thereby achieving'quantum supremacy', a major milestone in quantum computing. NISQ supremacy requires comparison with a state-of-the-art classical simulator. We report HPC simulations of hard random quantum circuits (RQC), which have been recently used as a benchmark for the first experimental demonstration of quantum supremacy, sustaining an average performance of 281 Pflop/s (true single precision) on Summit, currently the fastest supercomputer in the world. These simulations were carried out using qFlex, a tensor-network-based classical high-performance simulator of RQCs. Our results show an advantage of many orders of magnitude in energy consumption of NISQ devices over classical supercomputers. In …
The quantum approximate optimization algorithm needs to see the whole graph: A typical case
Edward Farhi, David Gamarnik, Sam Gutmann ·  arXiv preprint arXiv:2004.09002, 2020
Download PDF View
The Quantum Approximate Optimization Algorithm can naturally be applied to combinatorial search problems on graphs. The quantum circuit has p applications of a unitary operator that respects the locality of the graph. On a graph with bounded degree, with p small enough, measurements of distant qubits in the state output by the QAOA give uncorrelated results. We focus on finding big independent sets in random graphs with dn/2 edges keeping d fixed and n large. Using the Overlap Gap Property of almost optimal independent sets in random graphs, and the locality of the QAOA, we are able to show that if p is less than a d-dependent constant times log n, the QAOA cannot do better than finding an independent set of size .854 times the optimal for d large. Because the logarithm is slowly growing, even at one million qubits we can only show that the algorithm is blocked if p is in single digits. At higher p the algorithm "sees" the whole graph and we have no indication that performance is limited.
Tensorflow quantum: A software framework for quantum machine learning
Michael Broughton, Guillaume Verdon, Trevor McCourt, Antonio J Martinez, Jae Hyeon Yoo, Sergei V Isakov, Philip Massey, Ramin Halavati, Murphy Yuezhen Niu, Alexander Zlokapa, Evan Peters, Owen Lockwood, Andrea Skolik, Sofiene Jerbi, Vedran Dunjko, Martin Leib, Michael Streif, David Von Dollen, Hongxiang Chen, Shuxiang Cao, Roeland Wiersema, Hsin-Yuan Huang, Jarrod R McClean, Ryan Babbush, Sergio Boixo, Dave Bacon, Alan K Ho, Hartmut Neven, Masoud Mohseni ·  arXiv preprint arXiv:2003.02989, 2020
Download PDF View
We introduce TensorFlow Quantum (TFQ), an open source library for the rapid prototyping of hybrid quantum-classical models for classical or quantum data. This framework offers high-level abstractions for the design and training of both discriminative and generative quantum models under TensorFlow and supports high-performance quantum circuit simulators. We provide an overview of the software architecture and building blocks through several examples and review the theory of hybrid quantum-classical neural networks. We illustrate TFQ functionalities via several basic applications including supervised learning for quantum classification, quantum control, simulating noisy quantum circuits, and quantum approximate optimization. Moreover, we demonstrate how one can apply TFQ to tackle advanced quantum learning tasks including meta-learning, layerwise learning, Hamiltonian learning, sampling thermal states, variational quantum eigensolvers, classification of quantum phase transitions, generative adversarial networks, and reinforcement learning. We hope this framework provides the necessary tools for the quantum computing and machine learning research communities to explore models of both natural and artificial quantum systems, and ultimately discover new quantum algorithms which could potentially yield a quantum advantage.
Variational quantum unsampling on a quantum photonic processor
Jacques Carolan, Masoud Mohseni, Jonathan P Olson, Mihika Prabhu, Changchen Chen, Darius Bunandar, Murphy Yuezhen Niu, Nicholas C Harris, Franco NC Wong, Michael Hochberg, Seth Lloyd, Dirk Englund ·  Nature Physics 16 (3), 322-327, 2020
Download PDF View
A promising route towards the demonstration of near-term quantum advantage (or supremacy) over classical systems relies on running tailored quantum algorithms on noisy intermediate-scale quantum machines. These algorithms typically involve sampling from probability distributions that—under plausible complexity-theoretic conjectures—cannot be efficiently generated classically. Rather than determining the computational features of output states produced by a given physical system, we investigate what features of the generating system can be efficiently learnt given direct access to an output state. To tackle this question, here we introduce the variational quantum unsampling protocol, a nonlinear quantum neural network approach for verification and inference of near-term quantum circuit outputs. In our approach, one can variationally train a quantum operation to unravel the action of an unknown unitary on a …
Decoding quantum errors with subspace expansions
Jarrod R McClean, Zhang Jiang, Nicholas C Rubin, Ryan Babbush, Hartmut Neven ·  Nature communications 11 (1), 636, 2020
Download PDF View
With rapid developments in quantum hardware comes a push towards the first practical applications. While fully fault-tolerant quantum computers are not yet realized, there may exist intermediate forms of error correction that enable practical applications. In this work, we consider the idea of post-processing error decoders using existing quantum codes, which mitigate errors on logical qubits using post-processing without explicit syndrome measurements or additional qubits beyond the encoding overhead. This greatly simplifies the experimental exploration of quantum codes on real, near-term devices, removing the need for locality of syndromes or fast feed-forward. We develop the theory of the method and demonstrate it on an 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 of …
Nonergodic delocalized states for efficient population transfer within a narrow band of the energy landscape
Vadim N Smelyanskiy, Kostyantyn Kechedzhi, Sergio Boixo, Sergei V Isakov, Hartmut Neven, Boris Altshuler ·  Physical Review X 10 (1), 011017, 2020
Download PDF View
We address the long-standing problem of the structure of the low-energy eigenstates and long-time coherent dynamics in quantum spin-glass models. Below the spin-glass freezing transition, the energy landscape of the spin system is characterized by a proliferation of local minima where classical dynamics gets trapped. A theoretical description of quantum dynamics in this regime is challenging due to the complex nature of the distribution of the tunneling matrix elements between the local minima of the energy landscape. We study the transverse-field-induced quantum dynamics of the following “impurity band” (IB) spin model: zero energy of all spin configurations except for a small fraction of spin configurations (“marked states”) that form a narrow band at a large negative energy. At a zero transverse field, the IB model demonstrates the freezing transition at inverse temperature characterized by a nonzero value of the Edwards-Anderson …
Increasing the representation accuracy of quantum simulations of chemistry without extra quantum resources
Tyler Takeshita, Nicholas C Rubin, Zhang Jiang, Eunseok Lee, Ryan Babbush, Jarrod R McClean ·  Physical Review X 10 (1), 011004, 2020
Download PDF View
Proposals for 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 explore two techniques requiring no additional qubits or circuit depth that are able to remove much of this approximation in favor of additional measurements. The techniques are constructed and analyzed theoretically, and some numerical …
Qubitization of arbitrary basis quantum chemistry leveraging sparsity and low rank factorization
Dominic W Berry, Craig Gidney, Mario Motta, Jarrod R McClean, Ryan Babbush ·  Quantum 3, 208, 2019
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 T complexity, where 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 about seven hundred times less surface code spacetime volume than prior quantum algorithms for this system, despite us using a larger and more accurate active space.
Majorana loop stabilizer codes for error mitigation in fermionic quantum simulations
Zhang Jiang, Jarrod McClean, Ryan Babbush, Hartmut Neven ·  Physical Review Applied 12 (6), 064041, 2019
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 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 …
Diabatic gates for frequency-tunable superconducting qubits
Rami Barends, CM Quintana, AG Petukhov, Yu Chen, Dvir Kafri, Kostyantyn Kechedzhi, Roberto Collins, Ofer Naaman, Sergio Boixo, F Arute, Kunal Arya, D Buell, Brian Burkett, Z Chen, Ben Chiaro, Andrew Dunsworth, Brooks Foxen, Austin Fowler, C 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, KJ Satzinger, A Vainsencher, T White, J Yao, P Yeh, A Zalcman, H Neven, VN Smelyanskiy, John M Martinis ·  Physical review letters 123 (21), 210501, 2019
Download PDF View
We demonstrate diabatic two-qubit gates with Pauli error rates down to 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.
Quantum simulation of chemistry with sublinear scaling in basis size
Ryan Babbush, Dominic W Berry, Jarrod R McClean, Hartmut Neven ·  npj Quantum Information 5 (1), 92, 2019
Download PDF View
We present a quantum algorithm for simulating quantum chemistry with gate complexity 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 . 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.
Quantum supremacy using a programmable superconducting processor
Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, Brian Burkett, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Andrew Dunsworth, Edward Farhi, Brooks Foxen, Austin Fowler, Craig Gidney, Marissa Giustina, Rob Graff, Keith Guerin, Steve Habegger, Matthew P Harrigan, Michael J Hartmann, Alan Ho, Markus Hoffmann, Trent Huang, Travis S Humble, Sergei V Isakov, Evan Jeffrey, Zhang Jiang, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Paul V Klimov, Sergey Knysh, Alexander Korotkov, Fedor Kostritsa, David Landhuis, Mike Lindmark, Erik Lucero, Dmitry Lyakh, Salvatore Mandrà, Jarrod R 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 C Platt, Chris Quintana, Eleanor G Rieffel, Pedram Roushan, Nicholas C Rubin, Daniel Sank, Kevin J Satzinger, Vadim Smelyanskiy, Kevin J Sung, Matthew D Trevithick, Amit Vainsencher, Benjamin Villalonga, Theodore White, Z Jamie Yao, Ping Yeh, Adam Zalcman, Hartmut Neven, John M Martinis ·  Nature 574 (7779), 505-510, 2019
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 253 (about 1016). 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 …
Design and characterization of a 28-nm bulk-CMOS cryogenic quantum controller dissipating less than 2 mW at 3 K
Joseph C Bardin, Evan Jeffrey, Erik Lucero, Trent Huang, Sayan Das, Daniel Thomas Sank, Ofer Naaman, Anthony Edward Megrant, Rami Barends, Ted White, Marissa Giustina, Kevin J Satzinger, Kunal Arya, Pedram Roushan, Benjamin Chiaro, Julian Kelly, Zijun Chen, Brian Burkett, Yu Chen, Andrew Dunsworth, Austin Fowler, Brooks Foxen, Craig Gidney, Rob Graff, Paul Klimov, Josh Mutus, Matthew J McEwen, Matthew Neeley, Charles J Neill, Chris Quintana, Amit Vainsencher, Hartmut Neven, John Martinis ·  IEEE Journal of Solid-State Circuits 54 (11), 3043-3060, 2019
Download PDF View
Implementation of an error-corrected quantum computer is believed to require a quantum processor with 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 16-word (4-bit) XY gate instruction set for controlling 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 …
A flexible high-performance simulator for verifying and benchmarking quantum circuits implemented on real hardware
Benjamin Villalonga, Sergio Boixo, Bron Nelson, Christopher Henze, Eleanor Rieffel, Rupak Biswas, Salvatore Mandrà ·  npj Quantum Information 5 (1), 86, 2019
Download PDF View
Here we present qFlex, a flexible tensor network-based quantum circuit simulator. qFlex can compute both the exact amplitudes, essential for the verification of the quantum hardware, as well as low-fidelity amplitudes, to mimic sampling from Noisy Intermediate-Scale Quantum (NISQ) devices. In this work, we focus on random quantum circuits (RQCs) in the range of sizes expected for supremacy experiments. Fidelity f simulations are performed at a cost that is 1/f lower than perfect fidelity ones. We also present a technique to eliminate the overhead introduced by rejection sampling in most tensor network approaches. We benchmark the simulation of square lattices and Google’s Bristlecone QPU. Our analysis is supported by extensive simulations on NASA HPC clusters Pleiades and Electra. For our most computationally demanding simulation, the two clusters combined reached a peak of 20 Peta Floating Point …
Learning to learn with quantum neural networks via classical neural networks
Guillaume Verdon, Michael Broughton, Jarrod R McClean, Kevin J Sung, Ryan Babbush, Zhang Jiang, Hartmut Neven, Masoud Mohseni ·  arXiv preprint 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.
Quantum-assisted genetic algorithm
James King, Masoud Mohseni, William Bernoudy, Alexandre Fréchette, Hossein Sadeghi, Sergei V Isakov, Hartmut Neven, Mohammad H Amin ·  arXiv preprint arXiv:1907.00707, 2019
Download PDF View
Genetic algorithms, which mimic evolutionary processes to solve optimization problems, can be enhanced by using powerful semi-local search algorithms as mutation operators. Here, we introduce reverse quantum annealing, a class of quantum evolutions that can be used for performing families of quasi-local or quasi-nonlocal search starting from a classical state, as novel sources of mutations. Reverse annealing enables the development of genetic algorithms that use quantum fluctuation for mutations and classical mechanisms for the crossovers -- we refer to these as Quantum-Assisted Genetic Algorithms (QAGAs). We describe a QAGA and present experimental results using a D-Wave 2000Q quantum annealing processor. On a set of spin-glass inputs, standard (forward) quantum annealing finds good solutions very quickly but struggles to find global optima. In contrast, our QAGA proves effective at finding global optima for these inputs. This successful interplay of non-local classical and quantum fluctuations could provide a promising step toward practical applications of Noisy Intermediate-Scale Quantum (NISQ) devices for heuristic discrete optimization.
Flexible layout of surface code computations using AutoCCZ states
Craig Gidney, Austin G Fowler ·  arXiv preprint arXiv:1905.08916, 2019
Download PDF View
We construct a self-correcting CCZ state (the "AutoCCZ") with embedded delayed choice CZs for completing gate teleportations. Using the AutoCCZ state we create efficient surface code spacetime layouts for both a depth-limited circuit (a ripply-carry addition) and a Clifford-limited circuit (a QROM read). Our layouts account for distillation and routing, are based on plausible physical assumptions for a large-scale superconducting qubit platform, and suggest that circuit-level Toffoli parallelism (e.g. using a carry-lookahead adder instead of a ripple-carry adder) will not reduce the execution time of computations involving fewer than five million physical qubits. We reduce the spacetime volume of delayed choice CZs by a factor of 4 compared to techniques from previous work (Fowler 2012), and make several improvements to the CCZ magic state factory from (Gidney 2019).
Windowed quantum arithmetic
Craig Gidney ·  arXiv preprint arXiv:1905.07682, 2019
Download PDF View
We demonstrate a technique for optimizing quantum circuits that is analogous to classical windowing. Specifically, we show that small table lookups can allow control qubits to be iterated in groups instead of individually. We present various windowed quantum arithmetic circuits, including a windowed modular exponentiation with nested windowed modular multiplications, which have lower Toffoli counts than previous work at register sizes ranging from tens of qubits to thousands of qubits.
Efficient magic state factories with a catalyzed to transformation
Craig Gidney, Austin G Fowler ·  Quantum 3, 135, 2019
Download PDF View
We present magic state factory constructions for producing states and states. For the factory we apply the surface code lattice surgery construction techniques described in [15] to the fault-tolerant Toffoli [21, 12]. The resulting factory has a footprint of (where is the code distance) and produces one every surface code cycles. Our state factory uses the factory's output and a catalyst state to exactly transform one state into two states. It has a footprint smaller than the factory in [15] but outputs states twice as quickly. We show how to generalize the catalyzed transformation to arbitrary phase angles, and note that the case produces a particularly efficient circuit for producing states. Compared to using the factory of [15], our factory can quintuple the speed of algorithms that are dominated by the cost of applying Toffoli gates, including Shor's algorithm [31] and the chemistry algorithm of Babbush et al.[1]. Assuming a physical gate error rate of , our CCZ factory can produce states on average before an error occurs. This is sufficient for classically intractable instantiations of the chemistry algorithm, but for more demanding algorithms such as Shor's algorithm the mean number of states until failure can be increased to by increasing the factory footprint .
Universal quantum control through deep reinforcement learning
Murphy Yuezhen Niu, Sergio Boixo, Vadim N Smelyanskiy, Hartmut Neven ·  npj Quantum Information 5 (1), 33, 2019
Download PDF View
Emerging reinforcement learning techniques using deep neural networks have shown great promise in control optimization. They harness non-local regularities of noisy control trajectories and facilitate transfer learning between tasks. To leverage these powerful capabilities for quantum control optimization, we propose a new control framework to simultaneously optimize the speed and fidelity of quantum computation against both leakage and stochastic control errors. For a broad family of two-qubit unitary gates that are important for quantum simulation of many-electron systems, we improve the control robustness by adding control noise into training environments for reinforcement learning agents trained with trusted-region-policy-optimization. The agent control solutions demonstrate a two-order-of-magnitude reduction in average-gate-error over baseline stochastic-gradient-descent solutions and up to a one-order …
Asymptotically efficient quantum Karatsuba multiplication
Craig Gidney ·  arXiv preprint arXiv:1904.07356, 2019
Download PDF View
We improve the space complexity of Karatsuba multiplication on a quantum computer from to while maintaining gate complexity. We achieve this by ensuring recursive calls can add their outputs directly into subsections of the output register. This avoids the need to store, and uncompute, intermediate results. This optimization, which is analogous to classical tail-call optimization, should be applicable to a wide range of recursive quantum algorithms.
Quantum simulation of the Sachdev-Ye-Kitaev model by asymmetric qubitization
Ryan Babbush, Dominic W Berry, Hartmut Neven ·  Physical Review A 99 (4), 040301, 2019
Download PDF View
We show that one can quantum simulate the dynamics of a Sachdev-Ye-Kitaev model with Majorana modes for time to precision with gate complexity . In addition to scaling sublinearly in the number of Hamiltonian terms, this gate complexity represents an exponential improvement in and large polynomial improvement in and over prior state-of-the-art algorithms which scale as . Our approach involves a variant of the qubitization technique in which we encode the Hamiltonian as an asymmetric projection of a signal oracle onto two different signal states prepared by state oracles, and , such that . Our strategy for applying this method to the Sachdev-Ye-Kitaev model involves realizing using only Hadamard gates and realizing as a random quantum circuit.
For fixed control parameters the quantum approximate optimization algorithm's objective function value concentrates for typical instances
Fernando GSL Brandao, Michael Broughton, Edward Farhi, Sam Gutmann, Hartmut Neven ·  arXiv preprint arXiv:1812.04170, 2018
Download PDF View
The Quantum Approximate Optimization Algorithm, QAOA, uses a shallow depth quantum circuit to produce a parameter dependent state. For a given combinatorial optimization problem instance, the quantum expectation of the associated cost function is the parameter dependent objective function of the QAOA. We demonstrate that if the parameters are fixed and the instance comes from a reasonable distribution then the objective function value is concentrated in the sense that typical instances have (nearly) the same value of the objective function. This applies not just for optimal parameters as the whole landscape is instance independent. We can prove this is true for low depth quantum circuits for instances of MaxCut on large 3-regular graphs. Our results generalize beyond this example. We support the arguments with numerical examples that show remarkable concentration. For higher depth circuits the numerics also show concentration and we argue for this using the Law of Large Numbers. We also observe by simulation that if we find parameters which result in good performance at say 10 bits these same parameters result in good performance at say 24 bits. These findings suggest ways to run the QAOA that reduce or eliminate the use of the outer loop optimization and may allow us to find good solutions with fewer calls to the quantum computer.
Barren plateaus in quantum neural network training landscapes
Jarrod R McClean, Sergio Boixo, Vadim N Smelyanskiy, Ryan Babbush, Hartmut Neven ·  Nature communications 9 (1), 4812, 2018
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 …
Strategies for quantum computing molecular energies using the unitary coupled cluster ansatz
Jonathan Romero, Ryan Babbush, Jarrod R McClean, Cornelius Hempel, Peter J Love, Alán Aspuru-Guzik ·  Quantum Science and Technology 4 (1), 014008, 2018
Download PDF View
The variational quantum eigensolver (VQE) algorithm combines the ability of quantum computers to efficiently compute expectation 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 an analytical method to compute the energy gradient that reduces the sampling cost for gradient estimation by several orders of magnitude compared to numerical gradients. We illustrate our methodology with numerical simulations for a system of four hydrogen atoms that exhibit strong correlation and show that the …
Engineering non-equilibrium quantum phase transitions via causally gapped Hamiltonians
Masoud Mohseni, Johan Strumpfer, Marek M Rams ·  New Journal of Physics 20 (10), 105002, 2018
Download PDF View
We introduce a phenomenological theory for many-body control of critical phenomena by engineering causally-induced gaps for quantum Hamiltonian systems. The core mechanisms are controlling information flow within and/or between clusters that are created near a quantum critical point. To this end, we construct inhomogeneous quantum phase transitions via designing spatiotemporal quantum fluctuations. We show how non-equilibrium evolution of disordered quantum systems can create new effective correlation length scales and effective dynamical critical exponents. In particular, we construct a class of causally-induced non-adiabatic quantum annealing transitions for strongly disordered quantum Ising chains leading to exponential suppression of topological defects beyond standard Kibble–Zurek predictions. Using exact numerical techniques for 1D quantum Hamiltonian systems, we demonstrate that our …
Encoding electronic spectra in quantum circuits with linear T complexity
Ryan Babbush, Craig Gidney, Dominic W Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler, Hartmut Neven ·  Physical Review X 8 (4), 041015, 2018
Download PDF View
We construct quantum circuits that 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 , where is an absolute sum of Hamiltonian coefficients and is the 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 , where is the number of orbitals in the basis. This scenario enables sampling in the eigenbasis of electronic structure Hamiltonians with T complexity . Compared to prior approaches, our algorithms are asymptotically more efficient in gate complexity and require fewer T gates near the …
Postponing the orthogonality catastrophe: efficient state preparation for electronic structure simulations on quantum devices
Norm M Tubman, Carlos Mejuto-Zaera, Jeffrey M Epstein, Diptarka Hait, Daniel S Levine, William Huggins, Zhang Jiang, Jarrod R McClean, Ryan Babbush, Martin Head-Gordon, K Birgitta Whaley ·  arXiv preprint 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.
Fluctuations of energy-relaxation times in superconducting qubits
Paul V Klimov, Julian Kelly, Zijun Chen, Matthew Neeley, Anthony Megrant, Brian Burkett, Rami Barends, Kunal Arya, Ben Chiaro, Yu Chen, Andrew Dunsworth, Austin Fowler, Brooks Foxen, Craig Gidney, Marissa Giustina, Rob Graff, Trent Huang, Evan Jeffrey, Erik Lucero, Josh Y Mutus, Ofer Naaman, Charles Neill, Chris Quintana, Pedram Roushan, Daniel Sank, Amit Vainsencher, Jim Wenner, Timothy C White, Sergio Boixo, Ryan Babbush, Vadim N Smelyanskiy, Hartmut Neven, John M Martinis ·  Physical review letters 121 (9), 090502, 2018
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.
Low overhead quantum computation using lattice surgery
Austin G Fowler, Craig Gidney ·  arXiv preprint arXiv:1808.06709, 2018
Download PDF View
When calculating the overhead of a quantum algorithm made fault-tolerant using the surface code, many previous works have used defects and braids for logical qubit storage and state distillation. In this work, we show that lattice surgery reduces the storage overhead by over a factor of 4, and the distillation overhead by nearly a factor of 5, making it possible to run algorithms with T gates using only physical qubits capable of executing gates with error . These numbers strongly suggest that defects and braids in the surface code should be deprecated in favor of lattice surgery.
Quantum supremacy is both closer and farther than it appears
Igor L Markov, Aneeqa Fatima, Sergei V Isakov, Sergio Boixo ·  arXiv preprint arXiv:1807.10749, 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 milestone entails sampling from the output distribution defined by a random quantum circuit. We develop a massively-parallel simulation tool Rollright that does not require inter-process communication (IPC) or proprietary hardware. We also develop two ways to trade circuit fidelity for computational speedups, so as to match the fidelity of a given quantum computer --- a task previously thought impossible. We report massive speedups for the sampling task over prior software from Microsoft, IBM, Alibaba and Google, as well as supercomputer and GPU-based simulations. By using publicly available Google Cloud Computing, we price such simulations and enable comparisons by total cost across hardware platforms. We simulate approximate sampling from the output of a circuit with 7x8 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. Scaling the simulation to 10M bitstring probabilities needed for sampling 1M bitstrings helps comparing simulation to quantum computers. We describe refinements in benchmarks that slow down leading simulators, halving the circuit depth that can be simulated within the same time.
Efficient population transfer via non-ergodic extended states in quantum spin glass
Kostyantyn Kechedzhi, Vadim Smelyanskiy, Jarrod R McClean, Vasil S Denchev, Masoud Mohseni, Sergei Isakov, Sergio Boixo, Boris Altshuler, Hartmut Neven ·  arXiv preprint arXiv:1807.04792, 2018
Download PDF View
We analyze a new computational role of coherent multi-qubit quantum tunneling that gives rise to bands of non-ergodic extended (NEE) quantum states each formed by a superposition of a large number of computational states (deep local minima of the energy landscape) with similar energies. NEE provide a mechanism for population transfer (PT) between computational states and therefore can serve as a new quantum subroutine for quantum search, quantum parallel tempering and reverse annealing optimization algorithms. We study PT in a quantum n-spin system subject to a transverse field where the energy function encodes a classical optimization problem over the set of spin configurations . Given an initial spin configuration with low energy, PT protocol searches for other bitstrings at energies within a narrow window around the initial one. We provide an analytical solution for PT in a simple yet nontrivial model: randomly chosen marked bit-strings are assigned energies within a narrow strip , while the rest of the states are assigned energy 0. We find that the scaling of a typical PT runtime with n and L is the same as that in the multi-target Grover's quantum search algorithm, except for a factor that is equal to for finite transverse field . Unlike the Hamiltonians used in analog quantum unstructured search algorithms known so far, the model we consider is non-integrable and population transfer is not exponentially sensitive in n to the weight of the driver Hamiltonian. We study numerically the PT subroutine as a part of quantum parallel tempering algorithm for a number of examples of binary …
Quantum chemistry calculations on a trapped-ion quantum simulator
Cornelius Hempel, Christine Maier, Jonathan Romero, Jarrod McClean, Thomas Monz, Heng Shen, Petar Jurcevic, Ben P Lanyon, Peter Love, Ryan Babbush, Alán Aspuru-Guzik, Rainer Blatt, Christian F Roos ·  Physical Review X 8 (3), 031022, 2018
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.
Halving the cost of quantum addition
Craig Gidney ·  Quantum 2, 74, 2018
Download PDF View
We improve the number of T gates needed to perform an n-bit adder from to . We do so via a" temporary logical-AND" construction which uses four T gates to store the logical-AND of two qubits into an ancilla and zero T gates to later erase the ancilla. This construction is equivalent to one by Jones, except that our framing makes it clear that the technique is far more widely applicable than previously realized. Temporary logical-ANDs can be applied to integer arithmetic, modular arithmetic, rotation synthesis, the quantum Fourier transform, Shor's algorithm, Grover oracles, and many other circuits. Because T gates dominate the cost of quantum computation based on the surface code, and temporary logical-ANDs are widely applicable, this represents a significant reduction in projected costs of quantum computation. In addition to our n-bit adder, we present an n-bit controlled adder circuit with T-count of , a temporary adder that can be computed for the same cost as the normal adder but whose result can be kept until it is later uncomputed without using T gates, and discuss some other constructions whose T-count is improved by the temporary logical-AND.
Characterizing quantum supremacy in near-term devices
Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J Bremner, John M Martinis, Hartmut Neven ·  Nature Physics 14 (6), 595-600, 2018
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 …
The promise and challenges of quantum computing for energy storage
Alan Ho, Jarrod McClean, Shyue Ping Ong ·  Joule 2 (5), 810-813, 2018
Download PDF View
Jarrod McClean is a research scientist in Google's Quantum Artificial Intelligence Lab working on the development of practical quantum algorithms for quantum simulation and other problems. He received his PhD in Chemical Physics from Harvard University specializing in quantum chemistry and quantum computation supported by the US Department of Energy as a Computational Science Graduate Fellow. His research interests broadly include quantum computation, quantum chemistry, numerical methods, and information sparsity.Alan Ho is a product manager in Google's Quantum Artificial Intelligence Lab working on identifying applications of quantum computing. He has spent his career in a number of engineering and entrepreneurial roles. His engineering interests broadly include quantum computation, quantum chemistry, and productization of new technologies.Shyue Ping Ong is an Associate Professor in …
Application of fermionic marginal constraints to hybrid quantum algorithms
Nicholas C Rubin, Ryan Babbush, Jarrod McClean ·  New Journal of Physics 20 (5), 053020, 2018
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 …
Improved techniques for preparing eigenstates of fermionic Hamiltonians
Dominic W Berry, Mária Kieferová, Artur Scherer, Yuval R Sanders, Guang Hao Low, Nathan Wiebe, Craig Gidney, Ryan Babbush ·  npj Quantum Information 4 (1), 22, 2018
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 …
A blueprint for demonstrating quantum supremacy with superconducting qubits
Charles Neill, Pedran Roushan, K Kechedzhi, Sergio Boixo, Sergei V Isakov, V Smelyanskiy, A Megrant, B Chiaro, A Dunsworth, K Arya, Rami Barends, B Burkett, Y Chen, Z Chen, A Fowler, B Foxen, M Giustina, R Graff, E Jeffrey, T Huang, J Kelly, P Klimov, E Lucero, J Mutus, M Neeley, C Quintana, D Sank, A Vainsencher, J Wenner, TC White, Hartmut Neven, John M Martinis ·  Science 360 (6385), 195-199, 2018
Download PDF View
A key step toward demonstrating a quantum system that can address difficult problems in physics and chemistry will be performing a computation beyond the capabilities of any classical computer, thus achieving so-called quantum supremacy. In this study, we used nine superconducting qubits to demonstrate a promising path toward quantum supremacy. By individually tuning the qubit parameters, we were able to generate thousands of distinct Hamiltonian evolutions and probe the output probabilities. The measured probabilities obey a universal distribution, consistent with uniformly sampling the full Hilbert space. As the number of qubits increases, the system continues to explore the exponentially growing number of states. Extending these results to a system of 50 qubits has the potential to address scientific questions that are beyond the capabilities of any classical computer.
Quantum algorithms to simulate many-body physics of correlated fermions
Zhang Jiang, Kevin J Sung, Kostyantyn Kechedzhi, Vadim N Smelyanskiy, Sergio Boixo ·  Physical Review Applied 9 (4), 044036, 2018
Download PDF View
Simulating strongly correlated fermionic systems is notoriously hard on classical computers. An alternative approach, as proposed by Feynman, is to use a quantum computer. We discuss simulating strongly correlated fermionic systems using near-term quantum devices. We focus specifically on two-dimensional (2D) or linear geometry with nearest-neighbor qubit-qubit couplings, typical for superconducting transmon qubit arrays. We improve an existing algorithm to prepare an arbitrary Slater determinant by exploiting a unitary symmetry. We also present a quantum algorithm to prepare an arbitrary fermionic Gaussian state with gates and circuit depth. Both algorithms are optimal in the sense that the numbers of parameters in the quantum circuits are equal to those describing the quantum states. Furthermore, we propose an algorithm to implement the 2D fermionic Fourier transformation on a 2D qubit array with only …
Quantum simulation of electronic structure with linear depth and connectivity
Ian D Kivlichan, Jarrod McClean, Nathan Wiebe, Craig Gidney, Alán Aspuru-Guzik, Garnet Kin-Lic Chan, Ryan Babbush ·  Physical review letters 120 (11), 110501, 2018
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 depth and with two-qubit entangling gates, and prepare arbitrary Slater determinants in at most 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 most Trotter-based algorithms for both variational and phase-estimation-based simulation of quantum chemistry.
Classification with quantum neural networks on near term processors
Edward Farhi, Hartmut Neven ·  arXiv preprint arXiv:1802.06002, 2018
Download PDF View
We introduce a quantum neural network, QNN, that can represent labeled data, classical or quantum, and be trained by supervised learning. The quantum circuit consists of a sequence of parameter dependent unitary transformations which acts on an input quantum state. For binary classification a single Pauli operator is measured on a designated readout qubit. The measured output is the quantum neural network's predictor of the binary label of the input state. First we look at classifying classical data sets which consist of n-bit strings with binary labels. The input quantum state is an n-bit computational basis state corresponding to a sample string. We show how to design a circuit made from two qubit unitaries that can correctly represent the label of any Boolean function of n bits. For certain label functions the circuit is exponentially long. We introduce parameter dependent unitaries that can be adapted by supervised learning of labeled data. We study an example of real world data consisting of downsampled images of handwritten digits each of which has been labeled as one of two distinct digits. We show through classical simulation that parameters can be found that allow the QNN to learn to correctly distinguish the two data sets. We then discuss presenting the data as quantum superpositions of computational basis states corresponding to different label values. Here we show through simulation that learning is possible. We consider using our QNN to learn the label of a general quantum state. By example we show that this can be done. Our work is exploratory and relies on the classical simulation of small quantum systems. The QNN proposed …
Witnessing eigenstates for quantum simulation of Hamiltonian spectra
Raffaele Santagati, Jianwei Wang, Antonio A Gentile, Stefano Paesani, Nathan Wiebe, Jarrod R McClean, Sam Morley-Short, Peter J Shadbolt, Damien Bonneau, Joshua W Silverstone, David P Tew, Xiaoqi Zhou, Jeremy L O’Brien, Mark G Thompson ·  Science advances 4 (1), eaap9646, 2018
Download PDF View
The efficient calculation of Hamiltonian spectra, a problem often intractable on classical machines, can find application in many fields, from physics to chemistry. We introduce the concept of an “eigenstate witness” and, through it, provide a new quantum approach that combines variational methods and phase estimation to approximate eigenvalues for both ground and excited states. This protocol is experimentally verified on a programmable silicon quantum photonic chip, a mass-manufacturable platform, which embeds entangled state generation, arbitrary controlled unitary operations, and projective measurements. Both ground and excited states are experimentally found with fidelities >99%, and their eigenvalues are estimated with 32 bits of precision. We also investigate and discuss the scalability of the approach and study its performance through numerical simulations of more complex Hamiltonians. This result …
Low-depth quantum simulation of materials
Ryan Babbush, Nathan Wiebe, Jarrod McClean, James McClain, Hartmut Neven, Garnet Kin-Lic Chan ·  Physical Review X 8 (1), 011044, 2018
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 Gaussian orbitals, leading to Hamiltonians with second-quantized terms. We avoid this overhead and extend methods to condensed phase materials by utilizing a dual form of the plane wave basis which diagonalizes the potential operator, leading to a Hamiltonian representation with second-quantized terms. Using this representation, we can implement single Trotter steps of the Hamiltonians with linear gate depth on a planar lattice. Properties of the basis allow us to deploy Trotter- and Taylor-series-based simulations with respective circuit depths of and O˜(N8/3) for fixed charge densities. Variational algorithms also require significantly fewer measurements in this basis, ameliorating a …
Simulation of low-depth quantum circuits as complex undirected graphical models
Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy, Hartmut Neven ·  arXiv preprint arXiv:1712.05384, 2017
Download PDF View
Near term quantum computers with a high quantity (around 50) and quality (around 0.995 fidelity for two-qubit gates) of qubits will approximately sample from certain probability distributions beyond the capabilities of known classical algorithms on state-of-the-art computers, achieving the first milestone of so-called quantum supremacy. This has stimulated recent progress in classical algorithms to simulate quantum circuits. Classical simulations are also necessary to approximate the fidelity of multiqubit quantum computers using cross entropy benchmarking. Here we present numerical results of a classical simulation algorithm to sample universal random circuits, on a single workstation, with more qubits and depth than previously reported. For example, circuits with qubits of depth 37, qubits of depth 27, and ) qubits of depth 19 are all easy to sample. We also show up to what depth the sampling, or estimation of observables, is trivially parallelizable. The algorithm is related to the "Feynmann path" method to simulate quantum circuits. For low-depth circuits, the algorithm scales exponentially in the depth times the smaller lateral dimension, or the treewidth, as explained in Boixo et. al., and therefore confirms the bounds in that paper. In particular, circuits with qubits and depth 40 remain currently out of reach. Follow up work on a supercomputer environment will tighten this bound.
Exponentially more precise quantum simulation of fermions in the configuration interaction representation
Ryan Babbush, Dominic W Berry, Yuval R Sanders, Ian D Kivlichan, Artur Scherer, Annie Y Wei, Peter J Love, Alán Aspuru-Guzik ·  Quantum Science and Technology 3 (1), 015006, 2017
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 Babbush et al (2016 New Journal of Physics 18, 033032), 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
Spectroscopic signatures of localization with interacting photons in superconducting qubits
Pedram Roushan, Charles Neill, J Tangpanitanon, Victor M Bastidas, A Megrant, Rami Barends, Yu Chen, Z Chen, B Chiaro, A Dunsworth, A Fowler, B Foxen, Marissa Giustina, E Jeffrey, J Kelly, Erik Lucero, J Mutus, Matthew Neeley, Chris Quintana, D Sank, Amit Vainsencher, James Wenner, T White, H Neven, DG Angelakis, J Martinis ·  Science 358 (6367), 1175-1179, 2017
Download PDF View
Quantized eigenenergies and their associated wave functions provide extensive information for predicting the physics of quantum many-body systems. Using a chain of nine superconducting qubits, we implement a technique for resolving the energy levels of interacting photons. We benchmark this method by capturing the main features of the intricate energy spectrum predicted for two-dimensional electrons in a magnetic field—the Hofstadter butterfly. We introduce disorder to study the statistics of the energy levels of the system as it undergoes the transition from a thermalized to a localized phase. Our work introduces a many-body spectroscopy technique to study quantum phases of matter.
Fourier analysis of sampling from noisy chaotic quantum circuits
Sergio Boixo, Vadim N Smelyanskiy, Hartmut Neven ·  arXiv preprint arXiv:1708.01875, 2017
Download PDF View
Sampling from the output distribution of chaotic quantum evolutions, and of pseudo-random universal quantum circuits in particular, has been proposed as a prominent milestone for near-term quantum supremacy. The same paper notes that chaotic distributions are very sensitive to noise, and under quite general noise models converge to the uniform distribution over bit-strings exponentially in the number of gates. On the one hand, for increasing number of gates, it suffices to choose bit-strings at random to approximate the noisy distribution with fixed statistical distance. On the other hand, cross-entropy benchmarking can be used to gauge the fidelity of an experiment, and the distance to the uniform distribution. We estimate that state-of-the-art classical supercomputers would fail to simulate high-fidelity chaotic quantum circuits with approximately fifty qubits and depth forty. A recent interesting paper proposed a different approximation algorithm to a noisy distribution, extending previous results on the Fourier analysis of commuting quantum circuits. Using the statistical properties of the Porter-Thomas distribution, we show that this new approximation algorithm does not improve random guessing, in polynomial time. Therefore, it confirms previous results and does not represent an additional challenge to the suggested failure stated above.
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 50 (30), 305301, 2017
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
Factoring with n+ 2 clean qubits and n-1 dirty qubits
Craig Gidney ·  arXiv preprint arXiv:1706.07884, 2017
Download PDF View
We present reversible classical circuits for performing various arithmetic operations aided by dirty ancillae (i.e. extra qubits in an unknown state that must be restored before the circuit ends). We improve the number of clean qubits needed to factor an n-bit number with Shor's algorithm from 1.5n+O(1) to n+2, assisted by n-1 dirty qubits, without increasing the asymptotic size or depth of the circuit.
Optimizing variational quantum algorithms using pontryagin’s minimum principle
Zhi-Cheng Yang, Armin Rahmani, Alireza Shabani, Hartmut Neven, Claudio Chamon ·  Physical Review X 7 (2), 021027, 2017
Download PDF View
We use Pontryagin’s minimum principle to optimize variational quantum algorithms. We show that for a fixed computation time, the optimal evolution has a bang-bang (square pulse) form, both for closed and open quantum systems with Markovian decoherence. Our findings support the choice of evolution ansatz in the recently proposed quantum approximate optimization algorithm. Focusing on the Sherrington-Kirkpatrick spin glass as an example, we find a system-size independent distribution of the duration of pulses, with characteristic time scale set by the inverse of the coupling constants in the Hamiltonian. The optimality of the bang-bang protocols and the characteristic time scale of the pulses provide an efficient parametrization of the protocol and inform the search for effective hybrid (classical and quantum) schemes for tackling combinatorial optimization problems. Furthermore, we find that the success rates …
Quantum algorithms for fixed qubit architectures
Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Hartmut Neven ·  arXiv preprint arXiv:1703.06199, 2017
Download PDF View
Gate model quantum computers with too many qubits to be simulated by available classical computers are about to arrive. We present a strategy for programming these devices without error correction or compilation. This means that the number of logical qubits is the same as the number of qubits on the device. The hardware determines which pairs of qubits can be addressed by unitary operators. The goal is to build quantum states that solve computational problems such as maximizing a combinatorial objective function or minimizing a Hamiltonian. These problems may not fit naturally on the physical layout of the qubits. Our algorithms use a sequence of parameterized unitaries that sit on the qubit layout to produce quantum states depending on those parameters. Measurements of the objective function (or Hamiltonian) guide the choice of new parameters with the goal of moving the objective function up (or lowering the energy). As an example we consider finding approximate solutions to MaxCut on 3-regular graphs whereas the hardware is physical qubits laid out on a rectangular grid. We prove that the lowest depth version of the Quantum Approximate Optimization Algorithm will achieve an approximation ratio of at least 0.5293 on all large enough instances which beats random guessing (0.5). We open up the algorithm to have different parameters for each single qubit rotation and for each interaction associated with the nearest neighbor interactions on the grid. Small numerical experiments indicate that an enveloping classical algorithm can be used to find the parameters which sit on the grid to optimize an objective function with a …
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 543 (7644), 171-174, 2017
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.
Observation of Classical-Quantum Crossover of Flux Noise and Its Paramagnetic Temperature Dependence
CM Quintana, Yu Chen, Daniel Sank, AG Petukhov, TC White, Dvir Kafri, Ben Chiaro, Anthony Megrant, Rami Barends, Brooks Campbell, Zijun Chen, Andrew Dunsworth, Austin G Fowler, Rob Graff, Evan Jeffrey, Julian Kelly, Erik Lucero, JY Mutus, Matthew Neeley, Charles Neill, PJJ O’Malley, Pedram Roushan, Alireza Shabani, VN Smelyanskiy, Amit Vainsencher, James Wenner, Hartmut Neven, John M Martinis ·  Physical review letters 118 (5), 057702, 2017
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 , allowing for the observation of a classical-quantum crossover. Below the crossover point, the symmetric noise component follows a power law that matches the magnitude of the noise near 1 Hz. The antisymmetric component displays a 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.
Blueprint for a microwave trapped ion quantum computer
Bjoern Lekitsch, Sebastian Weidt, Austin G Fowler, Klaus Mølmer, Simon J Devitt, Christof Wunderlich, Winfried K Hensinger ·  Science Advances 3 (2), e1601540, 2017
Download PDF View
The availability of a universal quantum computer may have a fundamental impact on a vast number of research fields and on society as a whole. An increasingly large scientific and industrial community is working toward the realization of such a device. An arbitrarily large quantum computer may best be constructed using a modular approach. We present a blueprint for a trapped ion–based scalable quantum computer module, making it possible to create a scalable quantum computer architecture based on long-wavelength radiation quantum gates. The modules control all operations as stand-alone units, are constructed using silicon microfabrication techniques, and are within reach of current technology. To perform the required quantum computations, the modules make use of long-wavelength radiation–based quantum gate technology. To scale this microwave quantum computer architecture to a large size, we …
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, PJJ O’Malley, Matthew Neeley, Chris Quintana, Daniel Sank, Amit Vainsencher, Jim Wenner, Ted White, Eliot Kapit, Hartmut Neven, John Martinis ·  Nature Physics 13 (2), 146-151, 2017
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 …
Scaling analysis and instantons for thermally assisted tunneling and quantum Monte Carlo simulations
Zhang Jiang, Vadim N Smelyanskiy, Sergei V Isakov, Sergio Boixo, Guglielmo Mazzola, Matthias Troyer, Hartmut Neven ·  Physical Review A 95 (1), 012322, 2017
Download PDF View
We develop an instantonic calculus to derive an analytical expression for the thermally assisted tunneling decay rate of a metastable state in a fully connected quantum spin model. The tunneling decay problem can be mapped onto the Kramers escape problem of a classical random dynamical field. This dynamical field is simulated efficiently by path-integral quantum Monte Carlo (QMC). We show analytically that the exponential scaling with the number of spins of the thermally assisted quantum tunneling rate and the escape rate of the QMC process are identical. We relate this effect to the existence of a dominant instantonic tunneling path. The instanton trajectory is described by nonlinear dynamical mean-field theory equations for a single-site magnetization vector, which we solve exactly. Finally, we derive scaling relations for the “spiky” barrier shape when the spin tunneling and QMC rates scale polynomially with the …
Inhomogeneous quasi-adiabatic driving of quantum critical dynamics in weakly disordered spin chains
Marek M Rams, Masoud Mohseni, Adolfo Del Campo ·  New Journal of Physics 18 (12), 123034, 2016
Download PDF View
We introduce an inhomogeneous protocol to drive a weakly disordered quantum spin chain quasi-adiabatically across a quantum phase transition and minimize the residual energy of the final state. The number of spins that simultaneously reach the critical point is controlled by the length scale in which the magnetic field is modulated, introducing an effective size that favors adiabatic dynamics. The dependence of the residual energy on this length scale and the velocity at which the magnetic field sweeps out the chain is shown to be nonmonotonic. We determine the conditions for an optimal suppression of the residual energy of the final state and show that inhomogeneous driving can outperform conventional adiabatic schemes based on homogeneous control fields by several orders of magnitude.
Topological pumping of photons in nonlinear resonator arrays
Jirawat Tangpanitanon, Victor M Bastidas, Sarah Al-Assam, Pedram Roushan, Dieter Jaksch, Dimitris G Angelakis ·  Physical Review Letters 117 (21), 213603, 2016
Download PDF View
We show how to implement topological or Thouless pumping of interacting photons in one-dimensional nonlinear resonator arrays by simply modulating the frequency of the resonators periodically in space and time. The interplay between the interactions and the adiabatic modulations enables robust transport of Fock states with few photons per site. We analyze the transport mechanism via an effective analytic model and study its topological properties and its protection to noise. We conclude by a detailed study of an implementation with existing circuit-QED architectures.
Ergodic dynamics and thermalization in an isolated quantum system
Charles Neill, P Roushan, M Fang, Y Chen, M Kolodrubetz, Z Chen, A Megrant, R Barends, B Campbell, B Chiaro, A Dunsworth, E Jeffrey, J Kelly, J Mutus, PJJ O’malley, C Quintana, D Sank, A Vainsencher, J Wenner, TC White, Anatoli Polkovnikov, JM Martinis ·  Nature Physics 12 (11), 1037-1041, 2016
Download PDF View
Statistical mechanics is founded on the assumption that all accessible configurations of a system are equally likely. This requires dynamics that explore all states over time, known as ergodic dynamics. In isolated quantum systems, however, the occurrence of ergodic behaviour has remained an outstanding question,,,. Here, we demonstrate ergodic dynamics in a small quantum system consisting of only three superconducting qubits. The qubits undergo a sequence of rotations and interactions and we measure the evolution of the density matrix. Maps of the entanglement entropy show that the full system can act like a reservoir for individual qubits, increasing their entropy through entanglement. Surprisingly, these maps bear a strong resemblance to the phase space dynamics in the classical limit; classically, chaotic motion coincides with higher entanglement entropy. We further show that in regions of high entropy …
Understanding quantum tunneling through quantum Monte Carlo simulations
Sergei V Isakov, Guglielmo Mazzola, Vadim N Smelyanskiy, Zhang Jiang, Sergio Boixo, Hartmut Neven, Matthias Troyer ·  Physical review letters 117 (18), 180402, 2016
Download PDF View
The tunneling between the two ground states of an Ising ferromagnet is a typical example of many-body tunneling processes between two local minima, as they occur during quantum annealing. Performing quantum Monte Carlo (QMC) simulations we find that the QMC tunneling rate displays the same scaling with system size, as the rate of incoherent tunneling. The scaling in both cases is , where is the tunneling splitting (or equivalently the minimum spectral gap). An important consequence is that QMC simulations can be used to predict the performance of a quantum annealer for tunneling through a barrier. Furthermore, by using open instead of periodic boundary conditions in imaginary time, equivalent to a projector QMC algorithm, we obtain a quadratic speedup for QMC simulations, and achieve linear scaling in . We provide a physical understanding of these results and their range of applicability …
What is the computational value of finite-range tunneling?
Vasil S Denchev, Sergio Boixo, Sergei V Isakov, Nan Ding, Ryan Babbush, Vadim Smelyanskiy, John Martinis, Hartmut Neven ·  Physical Review X 6 (3), 031015, 2016
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 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 times faster than an optimized implementation of the quantum Monte Carlo algorithm on a single …
Scalable quantum simulation of molecular energies
Peter JJ O’Malley, Ryan Babbush, Ian D Kivlichan, Jonathan Romero, Jarrod R McClean, Rami Barends, Julian Kelly, Pedram Roushan, Andrew Tranter, Nan Ding, Brooks Campbell, Yu Chen, Zijun Chen, Ben Chiaro, Andrew Dunsworth, Austin G Fowler, Evan Jeffrey, Erik Lucero, Anthony Megrant, Josh Y Mutus, Matthew Neeley, Charles Neill, Chris Quintana, Daniel Sank, Amit Vainsencher, Jim Wenner, Ted C White, Peter V Coveney, Peter J Love, Hartmut Neven, Alain Aspuru-Guzik, John M Martinis ·  Physical Review X 6 (3), 031007, 2016
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 …
Digitized adiabatic quantum computing with a superconducting circuit
Rami Barends, Alireza Shabani, Lucas Lamata, Julian Kelly, Antonio Mezzacapo, U Las Heras, Ryan Babbush, Austin G Fowler, Brooks Campbell, Yu Chen, Zijun Chen, Ben Chiaro, Andrew Dunsworth, Evan Jeffrey, Erik Lucero, Anthony Megrant, JY Mutus, Matthew Neeley, Charles Neill, PJJ O’Malley, Chris Quintana, Pedran Roushan, D Sank, Amit Vainsencher, James Wenner, TC White, Enrique Solano, Hartmut Neven, John M Martinis ·  Nature 534 (7606), 222-226, 2016
Download PDF View
Quantum mechanics can help to solve complex problems in physics and chemistry, provided they can be programmed in a physical device. In adiabatic quantum computing,,, a system is slowly evolved from the ground state of a simple initial Hamiltonian to a final Hamiltonian that encodes a computational problem. The appeal of this approach lies in the combination of simplicity and generality; in principle, any problem can be encoded. In practice, applications are restricted by limited connectivity, available interactions and noise. A complementary approach is digital quantum computing, which enables the construction of arbitrary interactions and is compatible with error correction,, but uses quantum circuit algorithms that are problem-specific. Here we combine the advantages of both approaches by implementing digitized adiabatic quantum computing in a superconducting system. We tomographically probe the …
Exponentially more precise quantum simulation of fermions in second quantization
Ryan Babbush, Dominic W Berry, Ian D Kivlichan, Annie Y Wei, Peter J Love, Alán Aspuru-Guzik ·  New Journal of Physics 18 (3), 033032, 2016
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 …
Preserving entanglement during weak measurement demonstrated with a violation of the Bell–Leggett–Garg inequality
Theodore C White, JY Mutus, Justin Dressel, J Kelly, R Barends, E Jeffrey, D Sank, A Megrant, B Campbell, Yu Chen, Z Chen, B Chiaro, A Dunsworth, IC Hoi, C Neill, PJJ O’malley, P Roushan, A Vainsencher, J Wenner, AN Korotkov, John M Martinis ·  npj Quantum Information 2 (1), 1-5, 2016
Download PDF View
Weak measurement has provided new insight into the nature of quantum measurement, by demonstrating the ability to extract average state information without fully projecting the system. For single-qubit measurements, this partial projection has been demonstrated with violations of the Leggett–Garg inequality. Here we investigate the effects of weak measurement on a maximally entangled Bell state through application of the Hybrid Bell–Leggett–Garg inequality (BLGI) on a linear chain of four transmon qubits. By correlating the results of weak ancilla measurements with subsequent projective readout, we achieve a violation of the BLGI with 27 sds of certainty.
The theory of variational hybrid quantum-classical algorithms
Jarrod R McClean, Jonathan Romero, Ryan Babbush, Alán Aspuru-Guzik ·  New Journal of Physics 18 (2), 023023, 2016
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 (Peruzzo et al 2014 Nat. Commun. 5 4213) 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 a relaxation of exponential operator splitting. We introduce the concept of quantum variational error suppression that allows some errors to be suppressed naturally in this …
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 7 (1), 10327, 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 …
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 D Whitfield, Jorg Wrachtrup ·  ACS nano 9 (8), 7769-7774, 2015
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 10–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 …
Digital quantum simulation of fermionic models with a superconducting circuit
Rami Barends, Lucas Lamata, Julian Kelly, L García-Álvarez, Austin G Fowler, Anthony Megrant, Evan Jeffrey, Ted C White, Daniel Sank, Josh Y Mutus, B Campbell, Yu Chen, Zhaoshi Chen, B Chiaro, A Dunsworth, I-C Hoi, C Neill, PJJ O’Malley, Céline Quintana, P Roushan, A Vainsencher, J Wenner, E Solano, John M Martinis ·  Nature communications 6 (1), 7654, 2015
Download PDF View
One of the key applications of quantum information is simulating nature. Fermions are ubiquitous in nature, appearing in condensed matter systems, chemistry and high energy physics. However, universally simulating their interactions is arguably one of the largest challenges, because of the difficulties arising from anticommutativity. Here we use digital methods to construct the required arbitrary interactions, and perform quantum simulation of up to four fermionic modes with a superconducting quantum circuit. We employ in excess of 300 quantum logic gates, and reach fidelities that are consistent with a simple model of uncorrelated errors. The presented approach is in principle scalable to a larger number of modes, and arbitrary spatial dimensions.
Tunable coupler for superconducting Xmon qubits: Perturbative nonlinear model
Michael R Geller, Emmanuel Donate, Yu Chen, Michael T Fang, Nelson Leung, Charles Neill, Pedram Roushan, John M Martinis ·  Physical Review A 92 (1), 012320, 2015
Download PDF View
We study a recently demonstrated design for a high-performance tunable coupler suitable for superconducting Xmon and planar transmon qubits [Y. Chen , Phys. Rev. Lett. 113, 220502 (2014)PRLTAO0031-900710.1103/PhysRevLett.113.220502]. The coupler circuit uses a single flux-biased Josephson junction and acts as a tunable current divider. We calculate the effective qubit-qubit interaction Hamiltonian by treating the nonlinearity of the qubit and coupler junctions perturbatively. We find that the qubit nonlinearity has two principal effects: The first is to suppress the magnitude of the transverse coupling from that obtained in the harmonic approximation by about 15%, assuming typical qubit parameters. The second is to induce a small diagonal coupling. The effects of the coupler junction nonlinearity are negligible in the parameter regime considered. The approach used here can be applied to …
Quantum brachistochrone curves as geodesics: Obtaining accurate minimum-time protocols for the control of quantum systems
Xiaoting Wang, Michele Allegra, Kurt Jacobs, Seth Lloyd, Cosmo Lupo, Masoud Mohseni ·  Physical review letters 114 (17), 170501, 2015
Download PDF View
Most methods of optimal control cannot obtain accurate time-optimal protocols. The quantum brachistochrone equation is an exception, and has the potential to provide accurate time-optimal protocols for a wide range of quantum control problems. So far, this potential has not been realized, however, due to the inadequacy of conventional numerical methods to solve it. Here we show that the quantum brachistochrone problem can be recast as that of finding geodesic paths in the space of unitary operators. We expect this brachistochrone-geodesic connection to have broad applications, as it opens up minimal-time control to the tools of geometry. As one such application, we use it to obtain a fast numerical method to solve the brachistochrone problem, and apply this method to two examples demonstrating its power.
State preservation by repetitive error detection in a superconducting quantum circuit
Julian Kelly, Rami Barends, Austin G Fowler, Anthony Megrant, Evan Jeffrey, Theodore C White, Daniel Sank, Josh Y Mutus, Brooks Campbell, Yu Chen, Zijun Chen, Ben Chiaro, Andrew Dunsworth, I-C Hoi, Charles Neill, Peter JJ O’Malley, Christopher Quintana, Pedran Roushan, Amit Vainsencher, James Wenner, Andrew N Cleland, John M Martinis ·  Nature 519 (7541), 66-69, 2015
Download PDF View
Quantum computing becomes viable when a quantum state can be protected from environment-induced error. If quantum bits (qubits) are sufficiently reliable, errors are sparse and quantum error correction (QEC),,,,, is capable of identifying and correcting them. Adding more qubits improves the preservation of states by guaranteeing that increasingly larger clusters of errors will not cause logical failure—a key requirement for large-scale systems. Using QEC to extend the qubit lifetime remains one of the outstanding experimental challenges in quantum computing. Here we report the protection of classical states from environmental bit-flip errors and demonstrate the suppression of these errors with increasing system size. We use a linear array of nine qubits, which is a natural step towards the two-dimensional surface code QEC scheme, and track errors as they occur by repeatedly performing projective quantum non …
Fast quantum methods for optimization
Sergio Boixo, Gerardo Ortiz, Rolando Somma ·  The European Physical Journal Special Topics 224 (1), 35-49, 2015
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 …
Qubit architecture with high coherence and fast tunable coupling
Yu Chen, C Neill, Pedram Roushan, Nelson Leung, Michael Fang, Rami Barends, Julian Kelly, Brooks Campbell, Z Chen, Benjamin Chiaro, Andrew Dunsworth, Evan Jeffrey, Anthony Megrant, JY Mutus, PJJ O’Malley, CM Quintana, D Sank, Amit Vainsencher, J Wenner, TC White, Michael R Geller, Andrew N Cleland, John M Martinis ·  Physical review letters 113 (22), 220502, 2014
Download PDF View
We introduce a superconducting qubit architecture that combines high-coherence qubits and tunable qubit-qubit coupling. With the ability to set the coupling to zero, we demonstrate that this architecture is protected from the frequency crowding problems that arise from fixed coupling. More importantly, the coupling can be tuned dynamically with nanosecond resolution, making this architecture a versatile platform with applications ranging from quantum logic gates to quantum simulation. We illustrate the advantages of dynamical coupling by implementing a novel adiabatic controlled-z gate, with a speed approaching that of single-qubit gates. Integrating coherence and scalable control, the introduced qubit architecture provides a promising path towards large-scale quantum computation and simulation.
Computational role of collective tunneling in a quantum annealer
Sergio Boixo, Vadim N Smelyanskiy, Alireza Shabani, Sergei V Isakov, Mark Dykman, Vasil S Denchev, Mohammad Amin, Anatoly Smirnov, Masoud Mohseni, Hartmut Neven ·  arXiv preprint arXiv:1411.4036, 2014
Download PDF View
Quantum tunneling is a phenomenon in which a quantum state traverses energy barriers above the energy of the state itself. Tunneling has been hypothesized as an advantageous physical resource for optimization. Here we present the first experimental evidence of a computational role of multiqubit quantum tunneling in the evolution of a programmable quantum annealer. We develop a theoretical model based on a NIBA Quantum Master Equation to describe the multiqubit dissipative tunneling effects under the complex noise characteristics of such quantum devices. We start by considering a computational primitive, an optimization problem consisting of just one global and one false minimum. The quantum evolutions enable tunneling to the global minimum while the corresponding classical paths are trapped in a false minimum. In our study the non-convex potentials are realized by frustrated networks of qubit clusters with strong intra-cluster coupling. We show that the collective effect of the quantum environment is suppressed in the "critical" phase during the evolution where quantum tunneling "decides" the right path to solution. In a later stage dissipation facilitates the multiqubit tunneling leading to the solution state. The predictions of the model accurately describe the experimental data from the D-Wave Two quantum annealer at NASA Ames. In our computational primitive the temperature dependence of the probability of success in the quantum model is opposite to that of the classical paths with thermal hopping. Specifically, we provide an analysis of an optimization problem with sixteen qubits, demonstrating eight qubit tunneling that …
Observation of topological transitions in interacting quantum circuits
Pedram Roushan, C Neill, Yu Chen, M Kolodrubetz, C Quintana, N Leung, M Fang, R Barends, B Campbell, Z Chen, B Chiaro, A Dunsworth, E Jeffrey, J Kelly, A Megrant, J Mutus, PJJ O’Malley, D Sank, A Vainsencher, J Wenner, T White, A Polkovnikov, AN Cleland, JM Martinis ·  Nature 515 (7526), 241-244, 2014
Download PDF View
Topology, with its abstract mathematical constructs, often manifests itself in physics and has a pivotal role in our understanding of natural phenomena. Notably, the discovery of topological phases in condensed-matter systems has changed the modern conception of phases of matter,,,,. The global nature of topological ordering, however, makes direct experimental probing an outstanding challenge. Present experimental tools are mainly indirect and, as a result, are inadequate for studying the topology of physical systems at a fundamental level. Here we employ the exquisite control afforded by state-of-the-art superconducting quantum circuits to investigate topological properties of various quantum systems. The essence of our approach is to infer geometric curvature by measuring the deflection of quantum trajectories in the curved space of the Hamiltonian. Topological properties are then revealed by integrating the …
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 345 (6195), 420-424, 2014
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.
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 preprint 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.
Entanglement in a quantum annealing processor
Trevor Lanting, Anthony J Przybysz, A Yu Smirnov, Federico M Spedalieri, Mohammad H Amin, Andrew J Berkley, Richard Harris, Fabio Altomare, Sergio Boixo, Paul Bunyk, Neil Dickson, C Enderud, Jeremy P Hilton, Emile Hoskinson, Mark W Johnson, Eric Ladizinsky, Nicholas Ladizinsky, Richard Neufeld, Travis Oh, Ilya Perminov, Chris Rich, Murray C Thom, E Tolkacheva, Sergey Uchaikin, AB Wilson, Geordie Rose ·  Physical Review X 4 (2), 021041, 2014
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.
Bayesian sampling using stochastic gradient thermostats
Nan Ding, Youhan Fang, Ryan Babbush, Changyou Chen, Robert D Skeel, Hartmut Neven ·  Advances in neural information processing systems 27, 2014
Download PDF View
Dynamics-based sampling methods, such as Hybrid Monte Carlo (HMC) and Langevin dynamics (LD), are commonly used to sample target distributions. Recently, such approaches have been combined with stochastic gradient techniques to increase sampling efficiency when dealing with large datasets. An outstanding problem with this approach is that the stochastic gradient introduces an unknown amount of noise which can prevent proper sampling after discretization. To remedy this problem, we show that one can leverage a small number of additional variables in order to stabilize momentum fluctuations induced by the unknown noise. Our method is inspired by the idea of a thermostat in statistical physics and is justified by a general theory.
Quantum algorithms for supervised and unsupervised machine learning
Seth Lloyd, Masoud Mohseni, Patrick Rebentrost ·  arXiv preprint arXiv:1307.0411, 2013
Download PDF View
Machine-learning tasks frequently involve problems of manipulating and classifying large numbers of vectors in high-dimensional spaces. Classical algorithms for solving such problems typically take time polynomial in the number of vectors and the dimension of the space. Quantum computers are good at manipulating high-dimensional vectors in large tensor product spaces. This paper provides supervised and unsupervised quantum machine learning algorithms for cluster assignment and cluster finding. Quantum machine learning can take time logarithmic in both the number of vectors and their dimension, an exponential speed-up over classical algorithms.
View more