Jump to Content

Quantum Computing

Quantum Computing merges two great scientific revolutions of the 20th century: computer science and quantum physics. Quantum physics is the theoretical basis of the transistor, the laser, and other technologies which enabled the computing revolution. But on the algorithmic level, today's computing machinery still operates on ""classical"" Boolean logic. Quantum Computing is the design of hardware and software that replaces Boolean logic by quantum law at the algorithmic level. For certain computations such as optimization, sampling, search or quantum simulation this promises dramatic speedups. We are particularly interested in applying quantum computing to artificial intelligence and machine learning. This is because many tasks in these areas rely on solving hard optimization problems or performing efficient sampling.

Recent Publications

Analyzing Prospects for Quantum Advantage in Topological Data Analysis
Dominic W. Berry
Yuan Su
Casper Gyurik
Robbie King
Joao Basso
Abhishek Rajput
Nathan Wiebe
Vedran Djunko
PRX Quantum, vol. 5 (2024), pp. 010319
Preview abstract Lloyd et al. were first to demonstrate the promise of quantum algorithms for computing Betti numbers in persistent homology (a way of characterizing topological features of data sets). Here, we propose, analyze, and optimize an improved quantum algorithm for topological data analysis (TDA) with reduced scaling, including a method for preparing Dicke states based on inequality testing, a more efficient amplitude estimation algorithm using Kaiser windows, and an optimal implementation of eigenvalue projectors based on Chebyshev polynomials. We compile our approach to a fault-tolerant gate set and estimate constant factors in the Toffoli complexity. Our analysis reveals that super-quadratic quantum speedups are only possible for this problem when targeting a multiplicative error approximation and the Betti number grows asymptotically. Further, we propose a dequantization of the quantum TDA algorithm that shows that having exponentially large dimension and Betti number are necessary, but insufficient conditions, for super-polynomial advantage. We then introduce and analyze specific problem examples for which super-polynomial advantages may be achieved, and argue that quantum circuits with tens of billions of Toffoli gates can solve some seemingly classically intractable instances. View details
Quantum Error Mitigation
Zhenyu Cai
Simon Benjamin
Suguru Endo
William J. Huggins
Ying Li
Thomas E O'Brien
Reviews of Modern Physics, vol. 95 (2023), pp. 045005
Preview abstract 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 devices that can deliver a quantum advantage with an impact on science and business are discussed. View details
Exponential Quantum Speedup in Simulating Coupled Classical Oscillators
Dominic Berry
Rolando Somma
Nathan Wiebe
Physical Review X, vol. 13 (2023), pp. 041041
Preview abstract We present a quantum algorithm for simulating the classical dynamics of 2^n coupled oscillators (e.g., 2^n masses coupled by springs). Our approach leverages a mapping between the Schrodinger equation and Newton's equations 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 n, 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, for a specification of the problem that we prove is \BQP-complete. Thus, our approach solves a potentially practical application with an exponential speedup over classical computers. Finally, we show that under similar conditions our approach can efficiently simulate more general classical harmonic systems with 2^n modes. View details
Preview abstract We demonstrate a 3-port Josephson parametric circulator, matched to 50 Ohm 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, simplifying the requirements for its integration into standard dispersive qubit readout setups. The device utilizes parametric couplers based on a balanced bridge of rf-SQUID arrays, which offer purely parametric coupling and high dynamic range. We characterize the device by measuring its full 3x3 S-matrix as a function of frequency 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 dB, and saturation power exceeding -80 dBm. View details
Preview abstract Quadratic programming over the (special) orthogonal group encompasses a broad class of optimization problems such as group synchronization, point-set registration, and simultaneous localization and mapping. Such problems are instances of the little noncommutative Grothendieck problem (LNCG), a natural generalization of quadratic combinatorial optimization where, instead of binary decision variables, one optimizes over orthogonal matrices. In this work, we establish an embedding of this class of LNCG problems over the orthogonal group onto a quantum Hamiltonian. This embedding is accomplished by identifying orthogonal matrices with their double cover (Pin and Spin group) elements, which we represent as quantum states. We connect this construction to the theory of free fermions, which provides a physical interpretation of the derived LNCG Hamiltonian as a two-body interacting-fermion model due to the quadratic nature of the problem. Determining extremal states of this Hamiltonian provides an outer approximation to the original problem, analogous to classical relaxations of the problem via semidefinite programming. Furthermore, we show that when considering optimization over the special orthogonal group, our quantum relaxation naturally obeys additional, powerful constraints based on the convex hull of rotation matrices. The classical size of this convex-hull representation is exponential in matrix dimension, whereas the quantum representation requires only a linear number of qubits. Finally, to project the relaxed solution into the feasible space, we employ rounding procedures which return orthogonal matrices from appropriate measurements of the quantum state. Through numerical experiments we provide evidence that this quantum relaxation can produce high-quality approximations. View details
Purification-Based Quantum Error Mitigation of Pair-Correlated Electron Simulations
Thomas E O'Brien
Gian-Luca R. Anselmetti
Fotios Gkritsis
Vincent Elfving
Stefano Polla
William J. Huggins
Oumarou Oumarou
Kostyantyn Kechedzhi
Dmitry Abanin
Rajeev Acharya
Igor Aleiner
Richard Ross Allen
Trond Ikdahl Andersen
Kyle Anderson
Markus Ansmann
Frank Carlton Arute
Kunal Arya
Juan Atalaya
Michael Blythe Broughton
Bob Benjamin Buckley
Alexandre Bourassa
Leon Brill
Tim Burger
Nicholas Bushnell
Jimmy Chen
Yu Chen
Benjamin Chiaro
Desmond Chun Fung Chik
Josh Godfrey Cogan
Roberto Collins
Paul Conner
William Courtney
Alex Crook
Ben Curtin
Ilya Drozdov
Andrew Dunsworth
Daniel Eppens
Lara Faoro
Edward Farhi
Reza Fatemi
Ebrahim Forati
Brooks Riley Foxen
William Giang
Dar Gilboa
Alejandro Grajales Dau
Steve Habegger
Michael C. Hamilton
Sean Harrington
Jeremy Patterson Hilton
Trent Huang
Ashley Anne Huff
Sergei Isakov
Justin Thomas Iveland
Cody Jones
Pavol Juhas
Marika Kieferova
Andrey Klots
Alexander Korotkov
Fedor Kostritsa
John Mark Kreikebaum
Dave Landhuis
Pavel Laptev
Kim Ming Lau
Lily MeeKit Laws
Joonho Lee
Kenny Lee
Alexander T. Lill
Wayne Liu
Orion Martin
Trevor Johnathan Mccourt
Anthony Megrant
Xiao Mi
Masoud Mohseni
Shirin Montazeri
Alexis Morvan
Ramis Movassagh
Wojtek Mruczkiewicz
Charles Neill
Ani Nersisyan
Michael Newman
Jiun How Ng
Murray Nguyen
Alex Opremcak
Andre Gregory Petukhov
Rebecca Potter
Kannan Aryaperumal Sankaragomathi
Christopher Schuster
Mike Shearn
Aaron Shorter
Vladimir Shvarts
Jindra Skruzny
Vadim Smelyanskiy
Clarke Smith
Rolando Diego Somma
Doug Strain
Marco Szalay
Alfredo Torres
Guifre Vidal
Jamie Yao
Ping Yeh
Juhwan Yoo
Grayson Robert Young
Yaxing Zhang
Ningfeng Zhu
Christian Gogolin
Nature Physics (2023)
Preview abstract An important measure of the development of quantum computing platforms has been the simulation of increasingly complex physical systems. Prior to fault-tolerant quantum computing, robust error mitigation strategies are necessary to continue this growth. Here, we study physical simulation within the seniority-zero electron pairing subspace, which affords both a computational stepping stone to a fully correlated model, and an opportunity to validate recently introduced ``purification-based'' error-mitigation strategies. We compare the performance of error mitigation based on doubling quantum resources in time (echo verification) or in space (virtual distillation), on up to 20 qubits of a superconducting qubit quantum processor. We observe a reduction of error by one to two orders of magnitude below less sophisticated techniques (e.g. post-selection); the gain from error mitigation is seen to increase with the system size. Employing these error mitigation strategies enables the implementation of the largest variational algorithm for a correlated chemistry system to-date. Extrapolating performance from these results allows us to estimate minimum requirements for a beyond-classical simulation of electronic structure. We find that, despite the impressive gains from purification-based error mitigation, significant hardware improvements will be required for classically intractable variational chemistry simulations. View details

Some of our teams