Ryan Babbush

We present sum-of-squares spectral amplification (SOSSA), a framework for improving quantum simulation relevant to low-energy problems. We show how SOSSA can be applied to problems like energy and phase estimation and provide fast quantum algorithms for these problems that significantly improve over prior art. We analyze the performance of SOSSA on the Sachdev-Ye-Kitaev model, a representative strongly correlated system, and demonstrate asymptotic speedups over generic simulation methods by a factor of the square root of the system size. We then apply SOSSA to electronic structure problems in quantum chemistry, yielding a factor of 4 to 195 speedup over the state of the art in ground-state energy estimation for models of Iron-Sulfur complexes and a CO2-fixation catalyst.

Here we describe an approach for simulating quantum chemistry on quantum computers with significantly lower asymptotic complexity than prior work. The approach uses a real-space first-quantised representation of the molecular Hamiltonian which we propagate using high-order product formulae. Essential for this low complexity is the use of a technique similar to the fast multipole method for computing the Coulomb operator with O(eta) complexity for a simulation with eta particles. We show how to modify this algorithm so that it can be implemented on a quantum computer. We ultimately demonstrate an approach with t(eta^{4/3} N^{1/3} + eta^{1/3} N^{2/3})(eta Nt/epsilon)^o(1) gate complexity, where N is the number of grid points, epsilon is target precision, and t is the duration of time evolution. This is roughly a speedup by O(eta) over most prior algorithms. We provide lower complexity than all prior work for N<eta^7 (the regime of practical interest), with only first-quantised interaction-picture simulations providing better performance for N>eta^7. As with the classical fast multipole method, large numbers eta>10^3 would be needed to realise this advantage.

Recently, a quantum algorithm called Decoded Quantum Interferometry (DQI) was introduced that achieves an apparent exponential speedup for Optimal Polynomial Intersection (OPI) problem, which has previously been studied in the contexts of cryptography and error correcting codes. However, this left open the question of how many logical gates and logical qubits would be needed to solve a classically intractable instance of OPI. Here, we develop optimized implementations of DQI which greatly reduce its resource requirements. We establish that DQI for OPI is the first known candidate for verifiable quantum advantage with optimal asymptotic speedup: solving instances with classical hardness $O(2^N)$ requires only $\widetilde{O}(N)$ quantum gates, matching the theoretical lower bound. To realize this, we overcome the primary bottleneck of reversible Reed-Solomon decoding by introducing novel quantum circuits for the Extended Euclidean Algorithm (EEA) that reduce the leading-order space complexity to the theoretical minimum of $2nb$ qubits. These improvements are broadly applicable, including to Shor's algorithm for the discrete logarithm. We analyze OPI over binary extension fields $\GF(2^b)$, assess hardness against new classical attacks, and identify resilient instances. Our resource estimates show that classically intractable OPI instances (requiring $>10^{23}$ classical trials) can be solved with approximately 5.72 million Toffoli gates. This is roughly $1000$ times fewer gates than required for factoring RSA-2048 and, remarkably, is also less than the leading interactive protocol for computational proof of quantumness, positioning DQI as a compelling candidate for practical, verifiable quantum advantage.

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 Quantum 2, 040332 2021], adapting and optimizing those algorithms to estimate observables of interest from the non-Born-Oppenheimer dynamics of multiple particle species at finite temperature. We also work out the constant factors associated with a novel implementation of a high-order Trotter approach to simulating a grid representation of these systems. Ultimately, we report logical qubit requirements and leading-order Toffoli costs for computing the stopping power of various projectile/target combinations relevant to interpreting and designing inertial fusion experiments. We estimate that scientifically interesting and classically intractable stopping power calculations can be quantum simulated with roughly the same number of logical qubits and about one hundred times more Toffoli gates than is required for state-of-the-art quantum simulations of industrially relevant molecules such as FeMoco or P450.

First-quantized plane-wave representations provide a very promising approach for quantum algorithms for solid state materials. Pseudopotentials provide a method of further reducing the complexity by avoiding the need to simulate highly localized core orbitals. The complicated functional form of pseudopotentials constitutes a major challenge for the design of quantum algorithms. In this work we provide new techniques to efficiently implement pseudopotentials in quantum algorithms, with orders of magnitude improvement in complexity. Our methods include a high-accuracy QROM interpolation of the exponential function, combined with QROM for the pseudopotential parameters and coherent arithmetic. Moreover, we generalize prior methods to enable the simulation of materials defined by non-cubic unit cells. Finally, we combine these techniques to estimate the resources for block encoding required for simulating commercially relevant instances of heterogeneous catalysis.

Abstract This talk will give an update regarding Google’s plans in quantum computing. We will highlight some recent results from our team and discuss some example problems where engagement with the quantum computer science community endemic to QIP will be important as the field advances. The first part of our talk will focus on quantum error-correction and the second part of our talk will focus on quantum algorithms.

Abstract Machine learning (ML) provides the potential to solve challenging quantum many-body problems in physics and chemistry. Yet, this prospect has not been fully justified. In this work, we establish rigorous results to understand the power of classical ML and the potential for quantum advantage in an important example application: predicting outcomes of quantum mechanical processes. We prove that for achieving a small average prediction error, one can always design a classical ML model whose sample complexity is comparable to the best quantum ML model (up to a small polynomial factor). Regarding computational complexity, we show that the class of problems that can be solved by efficient classical ML models with access to sampled data is strictly larger than BPP. Hence, classical ML models may be able to solve some challenging quantum problems after training from data obtained in physical experiments. As a concrete example, we prove that a simple, classical ML model can efficiently learn to predict ground state representations that approximate expectation values of local observables up to a small, constant error. This holds for any smooth family of gapped local Hamiltonians in a finite spatial dimension.

Abstract We show how to achieve the highest efficiency yet for simulations with arbitrary basis sets by using a representation of the Coulomb operator known as tensor hypercontraction (THC). We use THC to express the Coulomb operator in a non-orthogonal basis, which we are able to block encode by separately rotating each term with angles that are obtained via QROM. Our algorithm has the best complexity scaling for an arbitrary basis, as well as the best complexity for the specific case of FeMoCo. By optimising the surface code resources, we show that FeMoCo can be simulated using about 4 million physical qubits and 3.5 days of runtime, assuming 1 s cycle times and physical gate error rates no worse than 0.1%.

Abstract We compile explicit circuits and evaluate the computational cost for heuristic-based quantum algorithms for combinatorial optimization. We consider several variants of quantum-accelerated simulated annealing as well as adiabatic algorithms, quantum-enhanced population transfer, the quantum approximate optimization algorithm, and other approaches. We provide novel methods for executing the bottleneck subroutines for these heuristics, and our methods can easily be applied to other algorithms where numerical performance matters. We estimate how quickly the subroutines could be executed on a modestly sized superconducting-qubit-based quantum computer with surface code error correction. We conclude that quadratic speedups for heuristic-based quantum optimization algorithms are insufficient for early quantum computers to beat present day classical computers.