Showing 1–50 of 123 results for author: Berry, D

Cascading amplifiers can create exponentially large coherence

Authors: Lucas A. Ostrowski, Giacomo Pantaleoni, Howard M. Wiseman, Dominic W. Berry

Abstract: A standard laser beam has photon degeneracy, or coherence, $\mathfrak{C}$, of at most $8μ^2$, where $μ$ is the number of photons in the laser itself. Even quantum-engineered lasers, if required to produce a beam with the standard statistical properties, have limited coherence, scaling as $μ^4$. Moreover, such lasers (still unrealised) require very unconventional gain and output-coupling mechanisms… ▽ More A standard laser beam has photon degeneracy, or coherence, $\mathfrak{C}$, of at most $8μ^2$, where $μ$ is the number of photons in the laser itself. Even quantum-engineered lasers, if required to produce a beam with the standard statistical properties, have limited coherence, scaling as $μ^4$. Moreover, such lasers (still unrealised) require very unconventional gain and output-coupling mechanisms. Here, we propose a different path to increasing $\mathfrak{C}$: cascaded linear amplifiers, with conventional couplings. By dropping the requirement on the beam's properties, this approach can, in theory, achieve $\mathfrak{C}$ scaling exponentially in $μ$. Here $μ$ is the total source excitation number, across all the amplifiers. Two amplifiers suffice to surpass the standard $μ^2$ scaling. △ Less

Submitted 30 July, 2026; originally announced July 2026.

Comments: 29 pages, 5 figures

Spectral amplification for ground-state energy estimation of electronic structure in first quantization

Authors: Alicja Dutkiewicz, Alec F. White, Guang Hao Low, A. Eugene DePrince III, Matthew P. Harrigan, Marika Kieferova, Ryan Babbush, Dominic W. Berry, Nicholas C. Rubin

Abstract: We demonstrate an asymptotic gate complexity improvement in first-quantized ground-state energy estimation of electronic structure Hamiltonians in a plane wave basis by employing the sum-of-squares spectral gap amplification protocol. The improvement relies on identifying a sum-of-squares representation of the Hamiltonian which provides a lower bound certificate and low cost block encoding that le… ▽ More We demonstrate an asymptotic gate complexity improvement in first-quantized ground-state energy estimation of electronic structure Hamiltonians in a plane wave basis by employing the sum-of-squares spectral gap amplification protocol. The improvement relies on identifying a sum-of-squares representation of the Hamiltonian which provides a lower bound certificate and low cost block encoding that leads to a provably lower quantum phase estimation gate cost. This is achieved by using a sum-of-squares operator generated by the total charge density operator resulting in a block encoding normalization improvement of $λ= \mathcal{O}\left(ηΔ^{-1.5}+η^{1.5}Δ^{-1} \right)$ compared to prior work $λ= \mathcal{O}(ηΔ^{-2}+η^2Δ^{-1})$ where $η$ is the number of electrons and $Δ$ is the simulation grid spacing. The asymptotic reduction in block encoding normalization and similar block encoding costs to prior work is demonstrated to reduce resource estimates for materials and chemical systems by a factor of $2 - 44\times$ corresponding to the lowest cost estimates for ab initio materials simulation. △ Less

Submitted 16 July, 2026; originally announced July 2026.

A Denser Planar Surface Code

Authors: Guang Hao Low, William J. Huggins, Dominic W. Berry, Tanuj Khattar, Alec F. White, Nicholas C. Rubin, Ryan Babbush

Abstract: We present a quantum code implementable on a regular $2$D hex grid with an estimated encoding rate up to $4.5\times$ of that of a rotated surface code patch using circuit-level noise in a one- and two-qubit $10^{-3}$ error uniform depolarizing model. Our approach is based on yoking a dense packing of surface code twist defects, enabled by new stabilizer measurement cycles with an optimal four laye… ▽ More We present a quantum code implementable on a regular $2$D hex grid with an estimated encoding rate up to $4.5\times$ of that of a rotated surface code patch using circuit-level noise in a one- and two-qubit $10^{-3}$ error uniform depolarizing model. Our approach is based on yoking a dense packing of surface code twist defects, enabled by new stabilizer measurement cycles with an optimal four layers of nearest-neighbor two-qubit gates, almost no distance-reducing hook errors, and efficient decoding. We demonstrate a space-efficient architecture for computing on densely packed logical qubits, including new padding-free lattice surgery protocols in an optimal bounding box of $2d^2$ data and measurement qubits per patch. Assuming a $1μ$s surface code cycle time and a $10μ$s reaction time, these developments enable chemically accurate ground state phase estimation of a broad class of `utility-scale' electronic structure simulation problems such as the $108$ spin-orbital FeMoco-based nitrogen fixation catalyst in under a month with $89$k noisy superconducting qubits. We elucidate a Pareto frontier of space-time trade-offs and find a minimum physical quantum volume of $1.3$ mega-qubit-hours. These correspond to a $36\times$ space and $6.6\times$ spacetime improvement, respectively, over our previous state-of-the-art minimum-Toffoli resource estimates (Phys. Rev. X 15, 041016). △ Less

Submitted 28 May, 2026; originally announced May 2026.

Comments: 105 pages, 70 figures, 27 tables

Efficient quantum algorithm for linear matrix differential equations and applications to open quantum systems

Authors: Sophia Simon, Dominic W. Berry, Rolando D. Somma

Abstract: We present an efficient, nearly optimal quantum algorithm for solving linear matrix differential equations, with applications to the simulation of open quantum systems and beyond. For unitary or dissipative dynamics, the algorithm computes an entry of the solution matrix with query complexity $\widetilde{\mathcal{O}}(ν\mathcal{L} t/ε)$, where the constant $ν$ depends on the problem parameters,… ▽ More We present an efficient, nearly optimal quantum algorithm for solving linear matrix differential equations, with applications to the simulation of open quantum systems and beyond. For unitary or dissipative dynamics, the algorithm computes an entry of the solution matrix with query complexity $\widetilde{\mathcal{O}}(ν\mathcal{L} t/ε)$, where the constant $ν$ depends on the problem parameters, $\mathcal{L}$ involves a time integral of upper bounds on the norms of evolution operators, and $ε$ is the error. In particular, $ν\mathcal{L}$ is linear in $t$ for unitary dynamics and can be a constant for dissipative dynamics. Our result contrasts prior quantum approaches for differential equations that typically require exponential time for this problem due to the encoding in a quantum state, which can lead to exponentially small amplitudes. We demonstrate the utility of the algorithm through an end-to-end application, namely the simulation of dissipative dynamics for non-interacting fermions, which can be extended to other quantum and classical systems. We compare with classical algorithms and give evidence of polynomial quantum speedups for systems in a lattice, which become more pronounced for systems with long-range interactions and can be shown to be exponential in general. We also provide a lower bound of $Ω(ν\mathcal{L} t/ε)$ for unitary or dissipative dynamics that proves our algorithm is optimal up to logarithmic factors. △ Less

Submitted 15 May, 2026; originally announced May 2026.

Comments: 56 pages

Quantum algorithm for solving differential equations using SLAC derivatives

Authors: Rakshit M. Gharat, Gopikrishnan Muraleedharan, Dominic W. Berry, Gavin K. Brennen

Abstract: In numerical approaches to solving differential equations on a lattice, a representation of the derivative operator that correctly matches the continuum behaviour of functions of momentum up to the band limit must be non-local. We present the construction of efficient linear-combination-of-unitaries ($\mathrm{LCU}$)-based block-encodings for the first-order derivative and Laplacian operators in th… ▽ More In numerical approaches to solving differential equations on a lattice, a representation of the derivative operator that correctly matches the continuum behaviour of functions of momentum up to the band limit must be non-local. We present the construction of efficient linear-combination-of-unitaries ($\mathrm{LCU}$)-based block-encodings for the first-order derivative and Laplacian operators in the non-local \(N=2^n\)-dimensional SLAC representation. We use state-preparation techniques designed for smoothly decaying functions to prepare the dense $\mathrm{LCU}$ amplitudes with high success probability and low gate cost. Furthermore, we demonstrate how Shannon wavelet transforms can be applied to these block-encodings to obtain multiscale representations of the SLAC derivative operators. We then show how to apply a diagonal preconditioner that reduces the condition number of these matrices in the multiscale wavelet basis to a small constant. This enables the solution of partial differential equations (PDEs) with SLAC-discretised derivative operators on a finite lattice using the quantum linear solving algorithm ($\mathrm{QLSA}$). For a $d$-dimensional PDE, after projection away from the nullspace, the resulting quantum linear-system algorithm has overall gate complexity ${O}(dn^3α^{(k)}\log(1/\varepsilon))$, where $α^{(k)}$ is the subnormalisation factor of the order-$k$ SLAC block-encoding and $\varepsilon$ denotes the algorithmic approximation error. △ Less

Submitted 25 May, 2026; v1 submitted 6 May, 2026; originally announced May 2026.

Comments: 37 Pages 9 Figures (Version 2: added new figures and expanded discussion)

Constant Factor Analysis of Optimal Quantum Linear Solvers in Practice

Authors: Pedro C. S. Costa, Alexander M. Dalzell, Dong An, Dominic W. Berry

Abstract: Optimal quantum linear equation solvers provide complexity $O(κ\log(1/ε))$, where $κ$ is the condition number and $ε$ is the allowable error. The optimal solver using a discrete adiabatic approach [PRX Quantum 3, 040303 (2022)] has large analytically proven constant factors for the upper bound on the complexity. The constant factors were later found to be about 1,200 times smaller in numerical tes… ▽ More Optimal quantum linear equation solvers provide complexity $O(κ\log(1/ε))$, where $κ$ is the condition number and $ε$ is the allowable error. The optimal solver using a discrete adiabatic approach [PRX Quantum 3, 040303 (2022)] has large analytically proven constant factors for the upper bound on the complexity. The constant factors were later found to be about 1,200 times smaller in numerical testing [Quantum 9, 1887 (2025)]. This meant it is about an order of magnitude more efficient than using a randomised approach from [PRX Quantum 6, 040373 (2025)], which has far smaller analytically proven constant factors. Recently, a ``Shortcut'' method has been found to provide an optimal solver which also has small proven constant factors. In the present work, we conduct a comprehensive numerical analysis comparing this method with the adiabatic solver for two families of random linear systems. We find that, in the case where the solution norm is unknown, the adiabatic solver provides slightly better performance. If the solution norm is known, then the shortcut method provides significantly better performance for non-Hermitian matrices. △ Less

Submitted 27 April, 2026; v1 submitted 23 April, 2026; originally announced April 2026.

Comments: 20 pages, 24 figures

End-to-End Simulation of Chemical Dynamics on a Quantum Computer

Authors: Elliot C. Eklund, Arkin Tikku, Patrick Sinnott, William J. Huggins, Guang Hao Low, Dominic W. Berry, Ivan Kassal

Abstract: Simulations of chemical dynamics are a powerful means for understanding chemistry. However, classical computers struggle to simulate many chemical processes, especially non-adiabatic ones, where the Born-Oppenheimer approximation breaks down. Quantum computers could simulate quantum-chemical dynamics more efficiently than classical computers, but there is currently no complete quantum algorithm fo… ▽ More Simulations of chemical dynamics are a powerful means for understanding chemistry. However, classical computers struggle to simulate many chemical processes, especially non-adiabatic ones, where the Born-Oppenheimer approximation breaks down. Quantum computers could simulate quantum-chemical dynamics more efficiently than classical computers, but there is currently no complete quantum algorithm for calculating dynamical observables to within a known error. Here, we develop an efficient, end-to-end quantum algorithm for simulating chemical dynamics that avoids all uncontrolled approximations (including the Born-Oppenheimer approximation) and whose error is bounded subject to mild assumptions. To do so, we treat the nuclei and the electrons on an equal footing and simulate the full molecular wavefunction on a momentum-space grid in first quantization, including all algorithmic steps: initial-state preparation, time evolution using qubitization, and measurement of chemical observables such as reaction yields and rates. Our work gives the first algorithm for quantum simulation of chemistry whose end-to-end complexity achieves sublinear scaling in the size of the grid. We achieve this by developing an exponentially faster method for initial-state-preparation. Photochemistry is a likely early application of our algorithm and we estimate resources required for end-to-end simulations of non-adiabatic dynamics of atmospherically important molecules. Classically intractable photochemical computations could be performed using resources comparable to those required for other chemical applications of quantum computing. △ Less

Submitted 19 March, 2026; originally announced March 2026.

Quantum phase estimation with optimal confidence interval using three control qubits

Authors: Kaur Kristjuhan, Dominic W. Berry

Abstract: Quantum phase estimation is an important routine in many quantum algorithms, particularly for estimating the ground state energy in quantum chemistry simulations. This estimation involves applying powers of a unitary to the ground state, controlled by an auxiliary state prepared on a control register. In many applications the goal is to provide a confidence interval for the phase estimate, and opt… ▽ More Quantum phase estimation is an important routine in many quantum algorithms, particularly for estimating the ground state energy in quantum chemistry simulations. This estimation involves applying powers of a unitary to the ground state, controlled by an auxiliary state prepared on a control register. In many applications the goal is to provide a confidence interval for the phase estimate, and optimal performance is provided by a discrete prolate spheroidal sequence. We show how to prepare the corresponding state in a far more efficient way than prior work. We find that a matrix product state representation with a bond dimension of 4 is sufficient to give a highly accurate approximation for all dimensions tested, up to $2^{24}$. This matrix product state can be efficiently prepared using a sequence of simple three-qubit operations. When the dimension is a power of 2, the phase estimation can be performed with only three qubits for the control register, making it suitable for early-generation fault-tolerant quantum computers with a limited number of logical qubits. △ Less

Submitted 7 August, 2026; v1 submitted 23 January, 2026; originally announced January 2026.

Journal ref: Quantum 10, 2193 (2026)

Quantum computation of molecular geometry via many-body nuclear spin echoes

Authors: C. Zhang, R. G. Cortiñas, A. H. Karamlou, N. Noll, J. Provazza, J. Bausch, S. Shirobokov, A. White, M. Claassen, S. H. Kang, A. W. Senior, N. Tomašev, J. Gross, K. Lee, T. Schuster, W. J. Huggins, H. Celik, A. Greene, B. Kozlovskii, F. J. H. Heras, A. Bengtsson, A. Grajales Dau, I. Drozdov, B. Ying, W. Livingstone , et al. (298 additional authors not shown)

Abstract: Quantum-information-inspired experiments in nuclear magnetic resonance spectroscopy may yield a pathway towards determining molecular structure and properties that are otherwise challenging to learn. We measure out-of-time-ordered correlators (OTOCs) [1-4] on two organic molecules suspended in a nematic liquid crystal, and investigate the utility of this data in performing structural learning task… ▽ More Quantum-information-inspired experiments in nuclear magnetic resonance spectroscopy may yield a pathway towards determining molecular structure and properties that are otherwise challenging to learn. We measure out-of-time-ordered correlators (OTOCs) [1-4] on two organic molecules suspended in a nematic liquid crystal, and investigate the utility of this data in performing structural learning tasks. We use OTOC measurements to augment molecular dynamics models, and to correct for known approximations in the underlying force fields. We demonstrate the utility of OTOCs in these models by estimating the mean ortho-meta H-H distance of toluene and the mean dihedral angle of 3',5'-dimethylbiphenyl, achieving similar accuracy and precision to independent spectroscopic measurements of both quantities. To ameliorate the apparent exponential classical cost of interpreting the above OTOC data, we simulate the molecular OTOCs on a Willow superconducting quantum processor, using AlphaEvolve-optimized [5] quantum circuits and arbitrary-angle fermionic simulation gates. We implement novel zero-noise extrapolation techniques based on the Pauli pathing model of operator dynamics [6], to repeat the learning experiments with root-mean-square error $0.05$ over all circuits used. Our work highlights a computational protocol to interpret many-body echoes from nuclear magnetic systems using low resource quantum computation. △ Less

Submitted 22 October, 2025; originally announced October 2025.

Quantum simulation of electronic structure via quantum fast multipole method

Authors: Dominic W. Berry, Kianna Wan, Andrew D. Baczewski, Elliot C. Eklund, Arkin Tikku, Ryan Babbush

Abstract: Here we describe an approach for simulating electronic structure 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 comp… ▽ More Here we describe an approach for simulating electronic structure 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 $\widetilde{\cal O}(η)$ complexity for a simulation with $η$ 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(η^{4/3}N^{1/3} + η^{1/3} N^{2/3} ) (ηNt/ε)^{o(1)}$ gate complexity, where $N$ is the number of grid points, $ε$ is target precision, and $t$ is the duration of time evolution. This is roughly a speedup by ${\cal O}(η)$ over most prior algorithms. We provide lower complexity than all prior work for $N<η^7$ (the regime of practical interest), with only first-quantised interaction-picture simulations providing better performance for $N>η^7$. As with the classical fast multipole method, large particle numbers $η\gtrsim 10^3$ would be needed to realise this advantage. △ Less

Submitted 3 May, 2026; v1 submitted 8 October, 2025; originally announced October 2025.

Comments: 34 pages, 3 figures

Large time-step discretisation of adiabatic quantum dynamics

Authors: Dong An, Pedro C. S. Costa, Dominic W. Berry

Abstract: Adiabatic quantum computing is a general framework for preparing eigenstates of Hamiltonians on quantum devices. However, its digital implementation requires an efficient Hamiltonian simulation subroutine, which may introduce extra computational overhead or complicated quantum control logic. In this work, we show that the time step sizes in time discretization can be much larger than expected, and… ▽ More Adiabatic quantum computing is a general framework for preparing eigenstates of Hamiltonians on quantum devices. However, its digital implementation requires an efficient Hamiltonian simulation subroutine, which may introduce extra computational overhead or complicated quantum control logic. In this work, we show that the time step sizes in time discretization can be much larger than expected, and the overall complexity is greatly reduced. Remarkably, regardless of the general convergence order of the numerical method, we can choose a uniform time step size independent of tolerated error and evolution time for sufficiently accurate simulation. Furthermore, with the boundary cancellation condition where the continuous diabatic errors are exponentially suppressed, we provide strong evidence on an exponential convergence of even first-order Trotter with uniform time step size. We apply our analysis to the example of adiabatic unstructured search and show several preferable features of the Trotterized adiabatic approach: it can match the Grover lower bound, it does not require a priori knowledge on the number of marked states, and its performance can be asymptotically comparable with that of the quantum approximate optimization algorithm. △ Less

Submitted 29 August, 2025; originally announced September 2025.

Comments: 48 pages, 5 figures

Quantum algorithm for linear matrix equations

Authors: Rolando D. Somma, Guang Hao Low, Dominic W. Berry, Ryan Babbush

Abstract: We describe an efficient quantum algorithm for solving the linear matrix equation AX+XB=C, where A, B, and C are given complex matrices and X is unknown. This is known as the Sylvester equation, a fundamental equation with applications in control theory and physics. Our approach constructs the solution matrix X/x in a block-encoding, where x is a rescaling factor needed for normalization. This all… ▽ More We describe an efficient quantum algorithm for solving the linear matrix equation AX+XB=C, where A, B, and C are given complex matrices and X is unknown. This is known as the Sylvester equation, a fundamental equation with applications in control theory and physics. Our approach constructs the solution matrix X/x in a block-encoding, where x is a rescaling factor needed for normalization. This allows us to obtain certain properties of the entries of X exponentially faster than would be possible from preparing X as a quantum state. The query and gate complexities of the quantum circuit that implements this block-encoding are almost linear in a condition number that depends on A and B, and depend logarithmically in the dimension and inverse error. We show how our quantum circuits can solve BQP-complete problems efficiently, discuss potential applications and extensions of our approach, its connection to Riccati equation, and comment on open problems. △ Less

Submitted 21 August, 2025; v1 submitted 4 August, 2025; originally announced August 2025.

Comments: 24 pages, 1 figure

Analytical results for laser models producing a beam with sub-Poissonian photon statistics and coherence scaling as the Heisenberg limit

Authors: Lucas A. Ostrowski, Travis J. Baker, Dominic W. Berry, Howard M. Wiseman

Abstract: Recent advances in laser theory have demonstrated that a quantum enhancement is possible for the production of coherence $\mathfrak{C}$ by a continuous-wave laser device. Curiously, natural families of laser models that achieve Heisenberg-limited scaling for coherence produce the most coherence when the beam exhibits sub-Poissonian photon statistics. In this work, we provide an analytical treatmen… ▽ More Recent advances in laser theory have demonstrated that a quantum enhancement is possible for the production of coherence $\mathfrak{C}$ by a continuous-wave laser device. Curiously, natural families of laser models that achieve Heisenberg-limited scaling for coherence produce the most coherence when the beam exhibits sub-Poissonian photon statistics. In this work, we provide an analytical treatment of those novel families of laser models by specializing to a parameter regime that permits a linearization. We characterize the dynamics of each laser system, and find that some of the intuitions from standard laser theory may be applied here. Specifically, the intracavity number dynamics are well-described as an Ornstein-Uhlenbeck process, while the intracavity phase dynamics are well-described in terms of a physically realizable ensemble of pure states, which evolve according to pure phase diffusion. Unlike a standard laser, however, we find that the pure states comprising the ensemble in the Heisenberg-limited lasers are substantially phase squeezed. From our dynamical analysis, we deduce various quantities of the beam for each laser family, including the first- and second-order Glauber coherence functions, intensity noise spectrum, Mandel-Q parameter and coherence $\mathfrak{C}$. In addition, inspired from these phase diffusion dynamics, we derive an upper bound on laser coherence $\mathfrak{C} \lesssim 1.1156 μ^4$ -- which is tighter by a factor of $3/8$ when compared to that derived in [Baker et al., Nat. Phys. 17 179 (2021)] -- by making one of the assumptions of that paper slightly stronger. △ Less

Submitted 27 November, 2025; v1 submitted 24 February, 2025; originally announced February 2025.

Fast quantum simulation of electronic structure by spectrum amplification

Authors: Guang Hao Low, Robbie King, Dominic W. Berry, Qiushi Han, A. Eugene DePrince III, Alec White, Ryan Babbush, Rolando D. Somma, Nicholas C. Rubin

Abstract: The most advanced techniques using fault-tolerant quantum computers to estimate the ground-state energy of a chemical Hamiltonian involve compression of the Coulomb operator through tensor factorizations, enabling efficient block-encodings of the Hamiltonian. A natural challenge of these methods is the degree to which block-encoding costs can be reduced. We address this challenge through the techn… ▽ More The most advanced techniques using fault-tolerant quantum computers to estimate the ground-state energy of a chemical Hamiltonian involve compression of the Coulomb operator through tensor factorizations, enabling efficient block-encodings of the Hamiltonian. A natural challenge of these methods is the degree to which block-encoding costs can be reduced. We address this challenge through the technique of spectrum amplification, which magnifies the spectrum of the low-energy states of Hamiltonians that can be expressed as sums of squares. Spectrum amplification enables estimating ground-state energies with significantly improved cost scaling in the block encoding normalization factor $Λ$ to just $\sqrt{2ΛE_{\text{gap}}}$, where $E_{\text{gap}} \ll Λ$ is the lowest energy of the sum-of-squares Hamiltonian. To achieve this, we show that sum-of-squares representations of the electronic structure Hamiltonian are efficiently computable by a family of classical simulation techniques that approximate the ground-state energy from below. In order to further optimize, we also develop a novel factorization that provides a trade-off between the two leading Coulomb integral factorization schemes -- namely, double factorization and tensor hypercontraction -- that when combined with spectrum amplification yields 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 CO$_{2}$-fixation catalyst. △ Less

Submitted 21 February, 2025; originally announced February 2025.

Journal ref: Physical Review X 15, 041016 (2025)

Quantum Linear System Solvers: A Survey of Algorithms and Applications

Authors: Mauro E. S. Morales, Lirandë Pira, Philipp Schleich, Kelvin Koor, Pedro C. S. Costa, Dong An, Alán Aspuru-Guzik, Lin Lin, Patrick Rebentrost, Dominic W. Berry

Abstract: Solving linear systems of equations plays a fundamental role in numerous computational problems from different fields of science. The widespread use of numerical methods to solve these systems motivates investigating the feasibility of solving linear systems problems using quantum computers. In this work, we provide a survey of the main advances in quantum linear systems algorithms, together with… ▽ More Solving linear systems of equations plays a fundamental role in numerous computational problems from different fields of science. The widespread use of numerical methods to solve these systems motivates investigating the feasibility of solving linear systems problems using quantum computers. In this work, we provide a survey of the main advances in quantum linear systems algorithms, together with some applications. We summarize and analyze the main ideas behind some of the algorithms for the quantum linear systems problem in the literature. The analysis begins by examining the Harrow-Hassidim-Lloyd (HHL) solver. We note its limitations and reliance on computationally expensive quantum methods, then highlight subsequent research efforts which aimed to address these limitations and optimize runtime efficiency and precision via various paradigms. We focus in particular on the post-HHL enhancements which have paved the way towards optimal lower bounds with respect to error tolerance and condition number. By doing so, we propose a taxonomy that categorizes these studies. Furthermore, by contextualizing these developments within the broader landscape of quantum computing, we explore the foundational work that have inspired and informed their development, as well as subsequent refinements. Finally, we discuss the potential applications of these algorithms in differential equations, quantum machine learning, and many-body physics. △ Less

Submitted 9 January, 2025; v1 submitted 4 November, 2024; originally announced November 2024.

Comments: 42 pages, 7 figures

Rapid initial state preparation for the quantum simulation of strongly correlated molecules

Authors: Dominic W. Berry, Yu Tong, Tanuj Khattar, Alec White, Tae In Kim, Sergio Boixo, Lin Lin, Seunghoon Lee, Garnet Kin-Lic Chan, Ryan Babbush, Nicholas C. Rubin

Abstract: 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.… ▽ More 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 $7 \times$ 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 $0.003$. 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 $\sim 0.9$ overlap squared with a candidate ground-state of the FeMo cofactor, producing a total resource estimate of $7.3 \times 10^{10}$ 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 challenging-to-compute chemical system. △ Less

Submitted 18 September, 2024; originally announced September 2024.

Comments: 47 pages, 20 figures

Journal ref: PRX Quantum 6, 020327 (2025)

Faster Algorithmic Quantum and Classical Simulations by Corrected Product Formulas

Authors: Mohsen Bagherimehrab, Luis Mantilla Calderon, Dominic W. Berry, Philipp Schleich, Mohammad Ghazi Vakili, Abdulrahman Aldossary, Jorge A. Campos Gonzalez Angulo, Christoph Gorgulla, Alan Aspuru-Guzik

Abstract: Hamiltonian simulation using product formulas is arguably the most straightforward and practical approach for algorithmic simulation of a quantum system's dynamics on a quantum computer. Here we present corrected product formulas (CPFs), a variation of product formulas achieved by injecting auxiliary terms called correctors into standard product formulas. We establish several correctors that impro… ▽ More Hamiltonian simulation using product formulas is arguably the most straightforward and practical approach for algorithmic simulation of a quantum system's dynamics on a quantum computer. Here we present corrected product formulas (CPFs), a variation of product formulas achieved by injecting auxiliary terms called correctors into standard product formulas. We establish several correctors that improve the accuracy of standard product formulas by orders of magnitude when simulating Hamiltonians comprised of two exactly simulatable partitions, a common structure of lattice Hamiltonians. Importantly, injecting these correctors increases the overall simulation cost by only a small additive or multiplicative factor. We show that correctors are particularly advantageous for perturbed systems, where one partition has a relatively small norm compared to the other, as they allow the small norm to be utilized as an additional parameter for controlling the simulation error. We demonstrate the performance of CPFs by numerical simulations for several lattice Hamiltonians. Numerical results show that our theoretical error bounds for CPFs match or outperform the empirical error scaling of standard product formulas for these systems. We also demonstrate improvements offered by CPFs by implementing small-size systems on actual quantum hardware, as well as on noisy and noiseless quantum simulators. CPFs could be a valuable algorithmic tool for early fault-tolerant quantum computers with limited computing resources. As for standard product formulas, CPFs could also be used for simulations on a classical computer. △ Less

Submitted 28 July, 2026; v1 submitted 12 September, 2024; originally announced September 2024.

Comments: 37 pages; 9 figures (extended the numerical simulations; provided better compilations for correctors; and improved presentation)

Journal ref: PRX Quantum 7, 033018 (2026)

Doubling Efficiency of Hamiltonian Simulation via Generalized Quantum Signal Processing

Authors: Dominic W. Berry, Danial Motlagh, Giacomo Pantaleoni, Nathan Wiebe

Abstract: Quantum signal processing provides an optimal procedure for simulating Hamiltonian evolution on a quantum computer using calls to a block encoding of the Hamiltonian. In many situations it is possible to control between forward and reverse steps with almost identical cost to a simple controlled operation. We show that it is then possible to reduce the cost of Hamiltonian simulation by a factor of… ▽ More Quantum signal processing provides an optimal procedure for simulating Hamiltonian evolution on a quantum computer using calls to a block encoding of the Hamiltonian. In many situations it is possible to control between forward and reverse steps with almost identical cost to a simple controlled operation. We show that it is then possible to reduce the cost of Hamiltonian simulation by a factor of 2 using the recent results of generalised quantum signal processing. △ Less

Submitted 18 January, 2024; originally announced January 2024.

Comments: 9 pages, no figures

Journal ref: Physical Review A 110, 012612 (2024)

Further improving quantum algorithms for nonlinear differential equations via higher-order methods and rescaling

Authors: Pedro C. S. Costa, Philipp Schleich, Mauro E. S. Morales, Dominic W. Berry

Abstract: The solution of large systems of nonlinear differential equations is needed for many applications in science and engineering. In this study, we present three main improvements to existing quantum algorithms based on the Carleman linearisation technique. First, by using a high-precision technique for the solution of the linearised differential equations, we achieve logarithmic dependence of the com… ▽ More The solution of large systems of nonlinear differential equations is needed for many applications in science and engineering. In this study, we present three main improvements to existing quantum algorithms based on the Carleman linearisation technique. First, by using a high-precision technique for the solution of the linearised differential equations, we achieve logarithmic dependence of the complexity on the error and near-linear dependence on time. Second, we demonstrate that a rescaling technique can considerably reduce the cost, which would otherwise be exponential in the Carleman order for a system of ODEs, preventing a quantum speedup for PDEs. Third, we provide improved, tighter bounds on the error of Carleman linearisation. We apply our results to a class of discretised reaction-diffusion equations using higher-order finite differences for spatial resolution. We show that providing a stability criterion independent of the discretisation can conflict with the use of the rescaling due to the difference between the max-norm and 2-norm. An efficient solution may still be provided if the number of discretisation points is limited, as is possible when using higher-order discretisations. △ Less

Submitted 14 December, 2023; originally announced December 2023.

Comments: 37 pages, 2 figures

Journal ref: npj Quantum Information 11, 141 (2025)

The discrete adiabatic quantum linear system solver has lower constant factors than the randomized adiabatic solver

Authors: Pedro C. S. Costa, Dong An, Ryan Babbush, Dominic Berry

Abstract: 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}, 040303 (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 s… ▽ More 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}, 040303 (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,200 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 about an order of magnitude more efficient than using a randomised approach from [arXiv:2305.11352] that claimed to be more efficient. △ Less

Submitted 11 October, 2025; v1 submitted 12 December, 2023; originally announced December 2023.

Comments: 16 pages, 35 figures

Journal ref: Quantum 9, 1887 (2025)

Quantum Simulation of Realistic Materials in First Quantization Using Non-local Pseudopotentials

Authors: Dominic W. Berry, Nicholas C. Rubin, Ahmed O. Elnabawy, Gabriele Ahlers, A. Eugene DePrince III, Joonho Lee, Christian Gogolin, Ryan Babbush

Abstract: This paper improves and demonstrates the usefulness of the first quantized plane-wave algorithms for the quantum simulation of electronic structure, developed by Babbush et al. and Su et al. We describe the first quantum algorithm for first quantized simulation that accurately includes pseudopotentials. We focus on the Goedecker-Tetter-Hutter (GTH) pseudopotential, which is among the most accurate… ▽ More This paper improves and demonstrates the usefulness of the first quantized plane-wave algorithms for the quantum simulation of electronic structure, developed by Babbush et al. and Su et al. We describe the first quantum algorithm for first quantized simulation that accurately includes pseudopotentials. We focus on the Goedecker-Tetter-Hutter (GTH) pseudopotential, which is among the most accurate and widely used norm-conserving pseudopotentials enabling the removal of core electrons from the simulation. The resultant screened nuclear potential regularizes cusps in the electronic wavefunction so that orders of magnitude fewer plane waves are required for a chemically accurate basis. Despite the complicated form of the GTH pseudopotential, we are able to 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 the block-encoding costs for commercially relevant instances of heterogeneous catalysis (e.g. carbon monoxide adsorption on transition metals) and compare to the quantum resources needed to simulate materials in second quantization. We conclude that for computational cells with many particles, first quantization often requires meaningfully less spacetime volume. △ Less

Submitted 24 July, 2024; v1 submitted 12 December, 2023; originally announced December 2023.

Comments: 46 pages, 6 figures, 16 tables

Journal ref: npj Quantum Information 10, 130 (2024)

Quantum computation of stopping power for inertial fusion target design

Authors: Nicholas C. Rubin, Dominic W. Berry, Alina Kononov, Fionn D. Malone, Tanuj Khattar, Alec White, Joonho Lee, Hartmut Neven, Ryan Babbush, Andrew D. Baczewski

Abstract: 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… ▽ More 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. 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. △ Less

Submitted 23 August, 2023; originally announced August 2023.

Journal ref: Proceedings of the National Academy of Sciences Volume 121, Issue 23, 2024

Exponential quantum speedup in simulating coupled classical oscillators

Authors: Ryan Babbush, Dominic W. Berry, Robin Kothari, Rolando D. Somma, Nathan Wiebe

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 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 s… ▽ More 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 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 $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. We show that any classical algorithm solving this same problem is inefficient and must make $2^{Ω(n)}$ queries to the oracle and, when the oracles are instantiated by efficient quantum circuits, the problem 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. △ Less

Submitted 19 September, 2023; v1 submitted 22 March, 2023; originally announced March 2023.

Comments: 43 pages, 4 figures. v3 changes include improved presentation, discussion of applications related to potential energies, and new appendix discussing relation to prior work

Journal ref: Phys. Rev. X 13, 041041 (2023)

Optimum phase estimation with two control qubits

Authors: Peyman Najafi, Pedro C. S. Costa, Dominic W. Berry

Abstract: Phase estimation is used in many quantum algorithms, particularly in order to estimate energy eigenvalues for quantum systems. When using a single qubit as the probe (used to control the unitary we wish to estimate the eigenvalue of), it is not possible to measure the phase with a minimum mean-square error. In standard methods, there would be a logarithmic (in error) number of control qubits neede… ▽ More Phase estimation is used in many quantum algorithms, particularly in order to estimate energy eigenvalues for quantum systems. When using a single qubit as the probe (used to control the unitary we wish to estimate the eigenvalue of), it is not possible to measure the phase with a minimum mean-square error. In standard methods, there would be a logarithmic (in error) number of control qubits needed in order to achieve this minimum error. Here show how to perform this measurement using only two control qubits, thereby reducing the qubit requirements of the quantum algorithm. Our method corresponds to preparing the optimal control state one qubit at a time, while it is simultaneously consumed by the measurement procedure. △ Less

Submitted 22 March, 2023; originally announced March 2023.

Comments: 11 pages, 7 figures. Paper sent for Jonathan P. Dowling Memorial Special Issue

Fault-tolerant quantum simulation of materials using Bloch orbitals

Authors: Nicholas C. Rubin, Dominic W. Berry, Fionn D. Malone, Alec F. White, Tanuj Khattar, A. Eugene DePrince III, Sabrina Sicolo, Michael Kühn, Michael Kaicher, Joonho Lee, Ryan Babbush

Abstract: 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 s… ▽ More 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 \textit{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 tensor factorizations and a new Bloch orbital form of tensor hypercontraction. Finally, we estimate the resources required to deploy our algorithms to classically challenging model materials relevant to the chemistry of Lithium Nickel Oxide battery cathodes within the surface code. △ Less

Submitted 10 February, 2023; originally announced February 2023.

Journal ref: PRX Quantum 4, 040303 (2023)

Quantum simulation of exact electron dynamics can be more efficient than classical mean-field methods

Authors: Ryan Babbush, William J. Huggins, Dominic W. Berry, Shu Fay Ung, Andrew Zhao, David R. Reichman, Hartmut Neven, Andrew D. Baczewski, Joonho Lee

Abstract: 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 showi… ▽ More 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 size. We also introduce a more efficient quantum algorithm for first quantized mean-field state preparation that is likely cheaper than the cost of time evolution. We conclude that quantum speedup is most pronounced for finite temperature simulations and suggest several practically important electron dynamics problems with potential quantum advantage. △ Less

Submitted 3 January, 2023; originally announced January 2023.

Comments: 31 pages, 2 tables, 1 figure

Journal ref: Nat. Comms 14: 4058 (2023)

Quantum algorithm for time-dependent differential equations using Dyson series

Authors: Dominic W. Berry, Pedro C. S. Costa

Abstract: Time-dependent linear differential equations are a common type of problem that needs to be solved in classical physics. Here we provide a quantum algorithm for solving time-dependent linear differential equations with logarithmic dependence of the complexity on the error and derivative. As usual, there is an exponential improvement over classical approaches in the scaling of the complexity with th… ▽ More Time-dependent linear differential equations are a common type of problem that needs to be solved in classical physics. Here we provide a quantum algorithm for solving time-dependent linear differential equations with logarithmic dependence of the complexity on the error and derivative. As usual, there is an exponential improvement over classical approaches in the scaling of the complexity with the dimension, with the caveat that the solution is encoded in the amplitudes of a quantum state. Our method is to encode the Dyson series in a system of linear equations, then solve via the optimal quantum linear equation solver. Our method also provides a simplified approach in the case of time-independent differential equations. △ Less

Submitted 4 June, 2024; v1 submitted 7 December, 2022; originally announced December 2022.

Comments: 19 pages

Journal ref: Quantum 8, 1369 (2024)

Selection and improvement of product formulae for best performance of quantum simulation

Authors: Mauro E. S. Morales, Pedro C. S. Costa, Giacomo Pantaleoni, Daniel K. Burgarth, Yuval R. Sanders, Dominic W. Berry

Abstract: Quantum algorithms for simulation of Hamiltonian evolution are often based on product formulae. The fractal methods give a systematic way to find arbitrarily high-order product formulae, but result in a large number of exponentials. On the other hand, product formulae with fewer exponentials can be found by numerical solution of simultaneous nonlinear equations. It is also possible to reduce the c… ▽ More Quantum algorithms for simulation of Hamiltonian evolution are often based on product formulae. The fractal methods give a systematic way to find arbitrarily high-order product formulae, but result in a large number of exponentials. On the other hand, product formulae with fewer exponentials can be found by numerical solution of simultaneous nonlinear equations. It is also possible to reduce the cost of long-time simulations by processing, where a kernel is repeated and a processor need only be applied at the beginning and end of the simulation. In this work, we found thousands of new product formulae, and numerically tested these formulae, together with many formulae from prior literature. We provide methods to fairly compare product formulae of different lengths and different orders. For the case of 8th order, we have found new product formulae with exceptional performance, about two orders of magnitude better accuracy than prior work, both in the processed and non-processed cases. The processed product formula provides the best performance due to being shorter than the non-processed product formula. It outperforms all other tested product formulae over a range of many orders of magnitude in system parameters $T$ (time) and $ε$ (allowable error). That includes reasonable combinations of parameters to be used in quantum algorithms, where the size of the simulation is large enough to be classically intractable, but not so large it takes an impractically long time on a quantum computer. △ Less

Submitted 9 January, 2025; v1 submitted 27 October, 2022; originally announced October 2022.

Comments: Greatly expanded with new solutions and new comparisons to prior work. 31 pages, 2 figures

Journal ref: Quantum Information & Computation Volume 25. 1 (2025)

Doubling the order of approximation via the randomized product formula

Authors: Chien Hung Cho, Dominic W. Berry, Min-Hsiu Hsieh

Abstract: Randomization has been applied to Hamiltonian simulation in a number of ways to improve the accuracy or efficiency of product formulas. Deterministic product formulas are often constructed in a symmetric way to provide accuracy of even order 2k. We show that by applying randomized corrections, it is possible to more than double the order to 4k + 1 (corresponding to a doubling of the order of the e… ▽ More Randomization has been applied to Hamiltonian simulation in a number of ways to improve the accuracy or efficiency of product formulas. Deterministic product formulas are often constructed in a symmetric way to provide accuracy of even order 2k. We show that by applying randomized corrections, it is possible to more than double the order to 4k + 1 (corresponding to a doubling of the order of the error). In practice, applying the corrections in a quantum algorithm requires some structure to the Hamiltonian, for example the Pauli strings as are used in the simulation of quantum chemistry. △ Less

Submitted 20 October, 2022; originally announced October 2022.

Comments: 12 pages, no figure. Comments are welcome

Journal ref: Phys. Rev. A 109, 062431, 2024

Analyzing Prospects for Quantum Advantage in Topological Data Analysis

Authors: Dominic W. Berry, Yuan Su, Casper Gyurik, Robbie King, Joao Basso, Alexander Del Toro Barba, Abhishek Rajput, Nathan Wiebe, Vedran Dunjko, Ryan Babbush

Abstract: Lloyd et al. 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… ▽ More Lloyd et al. 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 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 which have parameters in the regime where super-polynomial advantages may be achieved, and argue that quantum circuits with tens of billions of Toffoli gates can solve seemingly classically intractable instances. △ Less

Submitted 27 September, 2023; v1 submitted 27 September, 2022; originally announced September 2022.

Comments: 54 pages, 7 figures. Added a number of theorems and lemmas to clarify findings and also a discussion in the main text and new appendix about variants of our problems with high Betti numbers that are challenging for recent classical algorithms

Journal ref: PRX Quantum 5, 010319 (2024)

Approaching optimal entangling collective measurements on quantum computing platforms

Authors: Lorcan O. Conlon, Tobias Vogl, Christian D. Marciniak, Ivan Pogorelov, Simon K. Yung, Falk Eilenberger, Dominic W. Berry, Fabiana S. Santana, Rainer Blatt, Thomas Monz, Ping Koy Lam, Syed M. Assad

Abstract: Entanglement is a fundamental feature of quantum mechanics and holds great promise for enhancing metrology and communications. Much of the focus of quantum metrology so far has been on generating highly entangled quantum states that offer better sensitivity, per resource, than what can be achieved classically. However, to reach the ultimate limits in multi-parameter quantum metrology and quantum i… ▽ More Entanglement is a fundamental feature of quantum mechanics and holds great promise for enhancing metrology and communications. Much of the focus of quantum metrology so far has been on generating highly entangled quantum states that offer better sensitivity, per resource, than what can be achieved classically. However, to reach the ultimate limits in multi-parameter quantum metrology and quantum information processing tasks, collective measurements, which generate entanglement between multiple copies of the quantum state, are necessary. Here, we experimentally demonstrate theoretically optimal single- and two-copy collective measurements for simultaneously estimating two non-commuting qubit rotations. This allows us to implement quantum-enhanced sensing, for which the metrological gain persists for high levels of decoherence, and to draw fundamental insights about the interpretation of the uncertainty principle. We implement our optimal measurements on superconducting, trapped-ion and photonic systems, providing an indication of how future quantum-enhanced sensing networks may look. △ Less

Submitted 12 July, 2023; v1 submitted 30 May, 2022; originally announced May 2022.

Comments: 6.5 pages, published version

Journal ref: Nature. Physics. 19, 351 to 357 (2023)

Efficient quantum computation of molecular forces and other energy gradients

Authors: 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

Abstract: 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 intr… ▽ More While most work on the quantum simulation of chemistry has focused on computing energy surfaces, a similarly important application requiring subtly different algorithms is the computation of energy derivatives. Almost all molecular properties can be expressed an energy derivative, including molecular forces, which are essential for applications such as molecular dynamics simulations. Here, we introduce new quantum algorithms for computing molecular energy derivatives with significantly lower complexity than prior methods. Under cost models appropriate for noisy-intermediate scale quantum devices we demonstrate how low rank factorizations and other tomography schemes can be optimized for energy derivative calculations. We perform numerics revealing that our techniques reduce the number of circuit repetitions required by many orders of magnitude for even modest systems. In the context of fault-tolerant algorithms, we develop new methods of estimating energy derivatives with Heisenberg limited scaling incorporating state-of-the-art techniques for block encoding fermionic operators. Our results suggest that the calculation of forces on a single nucleus may be of similar cost to estimating energies of chemical systems, but that further developments are needed for quantum computers to meaningfully assist with molecular dynamics simulations. △ Less

Submitted 16 December, 2021; v1 submitted 24 November, 2021; originally announced November 2021.

Comments: 48 pages, 14 page appendix, 10 figures. v2 contains updated lambdas (rescaling factors) for sparse FT encodings and some NISQ methods, obtained by localizing orbitals

Journal ref: Phys. Rev. Research 4, 043210 (2022)

Optimal scaling quantum linear systems solver via discrete adiabatic theorem

Authors: Pedro C. S. Costa, Dong An, Yuval R. Sanders, Yuan Su, Ryan Babbush, Dominic W. Berry

Abstract: Recently, several approaches to solving linear systems on a quantum computer have been formulated in terms of the quantum adiabatic theorem for a continuously varying Hamiltonian. Such approaches enabled near-linear scaling in the condition number $κ$ of the linear system, without requiring a complicated variable-time amplitude amplification procedure. However, the most efficient of those procedur… ▽ More Recently, several approaches to solving linear systems on a quantum computer have been formulated in terms of the quantum adiabatic theorem for a continuously varying Hamiltonian. Such approaches enabled near-linear scaling in the condition number $κ$ of the linear system, without requiring a complicated variable-time amplitude amplification procedure. However, the most efficient of those procedures is still asymptotically sub-optimal by a factor of $\log(κ)$. Here, we prove a rigorous form of the adiabatic theorem that bounds the error in terms of the spectral gap for intrinsically discrete time evolutions. We use this discrete adiabatic theorem to develop a quantum algorithm for solving linear systems that is asymptotically optimal, in the sense that the complexity is strictly linear in $κ$, matching a known lower bound on the complexity. Our $\mathcal{O}(κ\log(1/ε))$ complexity is also optimal in terms of the combined scaling in $κ$ and the precision $ε$. Compared to existing suboptimal methods, our algorithm is simpler and easier to implement. Moreover, we determine the constant factors in the algorithm, which would be suitable for determining the complexity in terms of gate counts for specific applications. △ Less

Submitted 15 November, 2021; originally announced November 2021.

Comments: 56 pages, 8 figures

Nearly optimal quantum algorithm for generating the ground state of a free quantum field theory

Authors: Mohsen Bagherimehrab, Yuval R. Sanders, Dominic W. Berry, Gavin K. Brennen, Barry C. Sanders

Abstract: We devise a quasilinear quantum algorithm for generating an approximation for the ground state of a quantum field theory (QFT). Our quantum algorithm delivers a super-quadratic speedup over the state-of-the-art quantum algorithm for ground-state generation, overcomes the ground-state-generation bottleneck of the prior approach and is optimal up to a polylogarithmic factor. Specifically, we establi… ▽ More We devise a quasilinear quantum algorithm for generating an approximation for the ground state of a quantum field theory (QFT). Our quantum algorithm delivers a super-quadratic speedup over the state-of-the-art quantum algorithm for ground-state generation, overcomes the ground-state-generation bottleneck of the prior approach and is optimal up to a polylogarithmic factor. Specifically, we establish two quantum algorithms -- Fourier-based and wavelet-based -- to generate the ground state of a free massive scalar bosonic QFT with gate complexity quasilinear in the number of discretized-QFT modes. The Fourier-based algorithm is limited to translationally invariant QFTs. Numerical simulations show that the wavelet-based algorithm successfully yields the ground state for a QFT with broken translational invariance. Furthermore, the cost of preparing particle excitations in the wavelet approach is independent of the energy scale. Our algorithms require a routine for generating one-dimensional Gaussian (1DG) states. We replace the standard method for 1DG-state generation, which requires the quantum computer to perform lots of costly arithmetic, with a novel method based on inequality testing that significantly reduces the need for arithmetic. Our method for 1DG-state generation is generic and could be extended to preparing states whose amplitudes can be computed on the fly by a quantum computer. △ Less

Submitted 29 June, 2022; v1 submitted 11 October, 2021; originally announced October 2021.

Comments: This version is identical in content to the published version. Presentation improved and figure 11 added. ( 73 pages, 15 figures, 2 tables)

Journal ref: PRX QUANTUM 3, 020364 (2022)

Fault-Tolerant Quantum Simulations of Chemistry in First Quantization

Authors: Yuan Su, Dominic W. Berry, Nathan Wiebe, Nicholas Rubin, Ryan Babbush

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

Submitted 11 October, 2021; v1 submitted 26 May, 2021; originally announced May 2021.

Comments: 96 pages, 9 figures, 8 tables

Journal ref: PRX Quantum 2, 040332 (2021)

Even more efficient quantum computations of chemistry through tensor hypercontraction

Authors: Joonho Lee, Dominic W. Berry, Craig Gidney, William J. Huggins, Jarrod R. McClean, Nathan Wiebe, Ryan Babbush

Abstract: We describe quantum circuits with only $\widetilde{\cal O}(N)$ Toffoli complexity that block encode the spectra of quantum chemistry Hamiltonians in a basis of $N$ arbitrary (e.g., molecular) orbitals. With ${\cal O}(λ/ ε)$ 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 prec… ▽ More We describe quantum circuits with only $\widetilde{\cal O}(N)$ Toffoli complexity that block encode the spectra of quantum chemistry Hamiltonians in a basis of $N$ arbitrary (e.g., molecular) orbitals. With ${\cal O}(λ/ ε)$ 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 that has been shown for quantum computations of chemistry within an arbitrary basis. Furthermore, up to logarithmic factors, this matches the scaling of the most efficient prior block encodings that can only work with orthogonal basis functions diagonalizing the Coloumb operator (e.g., the plane wave dual basis). Our key insight is to factorize the Hamiltonian using a method known as tensor hypercontraction (THC) and then to transform the Coulomb operator into an isospectral diagonal form with a non-orthogonal basis defined by the THC factors. We then use qubitization to simulate the non-orthogonal THC Hamiltonian, in a fashion that avoids most complications of the non-orthogonal basis. We also reanalyze and reduce the cost of several of the best prior algorithms for these simulations in order to facilitate a clear comparison to the present work. In addition to having lower asymptotic scaling spacetime volume, compilation of our algorithm for challenging finite-sized molecules such as FeMoCo reveals that our method requires the least fault-tolerant resources of any known approach. By laying out and optimizing the surface code resources required of our approach we show that FeMoCo can be simulated using about four million physical qubits and under four days of runtime, assuming $1\,μ$s cycle times and physical gate error rates no worse than $0.1\%$. △ Less

Submitted 15 December, 2021; v1 submitted 6 November, 2020; originally announced November 2020.

Comments: 73 pages, fixed typos

Journal ref: PRX Quantum 2, 030305 (2021)

The Heisenberg limit for laser coherence

Authors: Travis J. Baker, S. N. Saadatmand, Dominic W. Berry, Howard M. Wiseman

Abstract: To quantify quantum optical coherence requires both the particle- and wave-natures of light. For an ideal laser beam [1,2,3], it can be thought of roughly as the number of photons emitted consecutively into the beam with the same phase. This number, $\mathfrak{C}$, can be much larger than $μ$, the number of photons in the laser itself. The limit on $\mathfrak{C}$ for an ideal laser was thought to… ▽ More To quantify quantum optical coherence requires both the particle- and wave-natures of light. For an ideal laser beam [1,2,3], it can be thought of roughly as the number of photons emitted consecutively into the beam with the same phase. This number, $\mathfrak{C}$, can be much larger than $μ$, the number of photons in the laser itself. The limit on $\mathfrak{C}$ for an ideal laser was thought to be of order $μ^2$ [4,5]. Here, assuming nothing about the laser operation, only that it produces a beam with certain properties close to those of an ideal laser beam, and that it does not have external sources of coherence, we derive an upper bound: $\mathfrak{C} = O(μ^4)$. Moreover, using the matrix product states (MPSs) method [6,7,8,9], we find a model that achieves this scaling, and show that it could in principle be realised using circuit quantum electrodynamics (QED) [10]. Thus $\mathfrak{C} = O(μ^2)$ is only a standard quantum limit (SQL); the ultimate quantum limit, or Heisenberg limit, is quadratically better. △ Less

Submitted 5 November, 2020; v1 submitted 11 September, 2020; originally announced September 2020.

Comments: 6 pages, 4 figures, and 31 pages of supplemental information. v2: This paper is now published [Nature Physics DOI:10.1038/s41567-020-01049-3 (26 October 2020)]. For copyright reasons, this arxiv paper is based on a version of the paper prior to the accepted (21 August 2020) version

Journal ref: Nat. Phys. (2020)

Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization

Authors: Yuval R. Sanders, Dominic W. Berry, Pedro C. S. Costa, Louis W. Tessler, Nathan Wiebe, Craig Gidney, Hartmut Neven, Ryan Babbush

Abstract: 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… ▽ More Here we explore which heuristic quantum algorithms for combinatorial optimization might be most practical to try out on a small fault-tolerant quantum computer. We compile circuits for several variants of quantum accelerated simulated annealing including those using qubitization or Szegedy walks to quantize classical Markov chains and those simulating spectral gap amplified Hamiltonians encoding a Gibbs state. We also optimize fault-tolerant realizations of the adiabatic algorithm, quantum enhanced population transfer, the quantum approximate optimization algorithm, and other approaches. Many of these methods are bottlenecked by calls to the same subroutines; thus, optimized circuits for those primitives should be of interest regardless of which heuristic is most effective in practice. We compile these bottlenecks for several families of optimization problems and report for how long and for what size systems one can perform these heuristics in the surface code given a range of resource budgets. Our results discourage the notion that any quantum optimization heuristic realizing only a quadratic speedup will achieve an advantage over classical algorithms on modest superconducting qubit surface code processors without significant improvements in the implementation of the surface code. For instance, under quantum-favorable assumptions (e.g., that the quantum algorithm requires exactly quadratically fewer steps), our analysis suggests that quantum accelerated simulated annealing would require roughly a day and a million physical qubits to optimize spin glasses that could be solved by classical simulated annealing in about four CPU-minutes. △ Less

Submitted 5 August, 2020; v1 submitted 14 July, 2020; originally announced July 2020.

Comments: 77 pages, 19 figures, 9 tables. v2 contains new appendix on in-place binary to unary conversion

Journal ref: PRX Quantum 1, 020312 (2020)

$π$-Corrected Heisenberg Limit

Authors: Wojciech Gorecki, Rafal Demkowicz-Dobrzanski, Howard M. Wiseman, Dominic W. Berry

Abstract: We consider the precision $Δ\varphi$ with which the parameter $\varphi$, appearing in the unitary map $U_\varphi = e^{ i \varphi Λ}$ acting on some type of probe system, can be estimated when there is a finite amount of prior information about $\varphi$. We show that, if $U_\varphi$ acts $n$ times in total, then, asymptotically in $n$, there is a tight lower bound… ▽ More We consider the precision $Δ\varphi$ with which the parameter $\varphi$, appearing in the unitary map $U_\varphi = e^{ i \varphi Λ}$ acting on some type of probe system, can be estimated when there is a finite amount of prior information about $\varphi$. We show that, if $U_\varphi$ acts $n$ times in total, then, asymptotically in $n$, there is a tight lower bound $Δ\varphi \geq \fracπ{n (λ_+ - λ_-)}$, where $λ_+$, $λ_-$ are the extreme eigenvalues of the generator $Λ$. This is greater by a factor of $π$ than the conventional Heisenberg limit, derived from the properties of the quantum Fisher information. That is, the conventional bound is never saturable. Our result makes no assumptions on the measurement protocol, and is relevant not only in the noiseless case but also if noise can be eliminated using quantum error correction techniques. △ Less

Submitted 23 January, 2020; v1 submitted 11 July, 2019; originally announced July 2019.

Comments: 5 + 6 pages

Journal ref: Phys. Rev. Lett. 124, 030501 (2020)

Time-dependent Hamiltonian simulation with $L^1$-norm scaling

Authors: Dominic W. Berry, Andrew M. Childs, Yuan Su, Xin Wang, Nathan Wiebe

Abstract: The difficulty of simulating quantum dynamics depends on the norm of the Hamiltonian. When the Hamiltonian varies with time, the simulation complexity should only depend on this quantity instantaneously. We develop quantum simulation algorithms that exploit this intuition. For sparse Hamiltonian simulation, the gate complexity scales with the $L^1$ norm… ▽ More The difficulty of simulating quantum dynamics depends on the norm of the Hamiltonian. When the Hamiltonian varies with time, the simulation complexity should only depend on this quantity instantaneously. We develop quantum simulation algorithms that exploit this intuition. For sparse Hamiltonian simulation, the gate complexity scales with the $L^1$ norm $\int_{0}^{t}\mathrm{d}τ\left\lVert H(τ)\right\lVert_{\max}$, whereas the best previous results scale with $t\max_{τ\in[0,t]}\left\lVert H(τ)\right\lVert_{\max}$. We also show analogous results for Hamiltonians that are linear combinations of unitaries. Our approaches thus provide an improvement over previous simulation algorithms that can be substantial when the Hamiltonian varies significantly. We introduce two new techniques: a classical sampler of time-dependent Hamiltonians and a rescaling principle for the Schrödinger equation. The rescaled Dyson-series algorithm is nearly optimal with respect to all parameters of interest, whereas the sampling-based approach is easier to realize for near-term simulation. These algorithms could potentially be applied to semi-classical simulations of scattering processes in quantum chemistry. △ Less

Submitted 15 April, 2020; v1 submitted 17 June, 2019; originally announced June 2019.

Comments: 40 pages, 1 figure

Journal ref: Quantum 4, 254 (2020)

Photonic quantum data locking

Authors: Zixin Huang, Peter P. Rohde, Dominic W. Berry, Pieter Kok, Jonathan P. Dowling, Cosmo Lupo

Abstract: Quantum data locking is a quantum phenomenon that allows us to encrypt a long message with a small secret key with information-theoretic security. This is in sharp contrast with classical information theory where, according to Shannon, the secret key needs to be at least as long as the message. Here we explore photonic architectures for quantum data locking, where information is encoded in multi-p… ▽ More Quantum data locking is a quantum phenomenon that allows us to encrypt a long message with a small secret key with information-theoretic security. This is in sharp contrast with classical information theory where, according to Shannon, the secret key needs to be at least as long as the message. Here we explore photonic architectures for quantum data locking, where information is encoded in multi-photon states and processed using multi-mode linear optics and photo-detection, with the goal of extending an initial secret key into a longer one. % The secret key consumption depends on the number of modes and photons employed. In the no-collision limit, where the likelihood of photon bunching is suppressed, the key consumption is shown to be logarithmic in the dimensions of the system. Our protocol can be viewed as an application of the physics of Boson Sampling to quantum cryptography. Experimental realisations are challenging but feasible with state-of-the-art technology, as techniques recently used to demonstrate Boson Sampling can be adapted to our scheme (e.g., Phys. Rev. Lett. 123, 250503, 2019). △ Less

Submitted 24 April, 2021; v1 submitted 8 May, 2019; originally announced May 2019.

Journal ref: Quantum 5, 447 (2021)

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

Authors: 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

Abstract: 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 comput… ▽ More 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 (e.g. 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 $N < 10^5$ fermionic modes can be performed with roughly $O(1)$ and $O(N^2)$ T complexities. We perform numerics revealing tradeoffs between the error and gate complexity of a Trotter step; e.g., 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. △ Less

Submitted 13 July, 2020; v1 submitted 27 February, 2019; originally announced February 2019.

Comments: 45 pages, 15 figures. Only difference from v3 is change to CC BY 4.0 license

Journal ref: Quantum 4, 296 (2020)

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

Authors: Dominic W. Berry, Craig Gidney, Mario Motta, Jarrod R. McClean, Ryan Babbush

Abstract: 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 fas… ▽ More 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 $\widetilde{\cal O}(N^{3/2} λ)$ T complexity, where $N$ is number of orbitals and $λ$ is the 1-norm of the chemistry Hamiltonian. We deploy our algorithms to simulate the FeMoco molecule (relevant to Nitrogen fixation) and obtain circuits requiring 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. △ Less

Submitted 27 November, 2019; v1 submitted 6 February, 2019; originally announced February 2019.

Comments: 44 pages, 17 figures, formatted for Quantum

Journal ref: Quantum 3, 208 (2019)

Quantum Simulation of Chemistry with Sublinear Scaling in Basis Size

Authors: Ryan Babbush, Dominic W. Berry, Jarrod R. McClean, Hartmut Neven

Abstract: We present a quantum algorithm for simulating quantum chemistry with gate complexity $\tilde{O}(N^{1/3} η^{8/3})$ where $η$ is the number of electrons and $N$ is the number of plane wave orbitals. In comparison, the most efficient prior algorithms for simulating electronic structure using plane waves (which are at least as efficient as algorithms using any other basis) have complexity… ▽ More We present a quantum algorithm for simulating quantum chemistry with gate complexity $\tilde{O}(N^{1/3} η^{8/3})$ where $η$ is the number of electrons and $N$ is the number of plane wave orbitals. In comparison, the most efficient prior algorithms for simulating electronic structure using plane waves (which are at least as efficient as algorithms using any other basis) have complexity $\tilde{O}(N^{8/3} /η^{2/3})$. We achieve our scaling in first quantization by performing simulation in the rotating frame of the kinetic operator using interaction picture techniques. Our algorithm is far more efficient than all prior approaches when $N \gg η$, as is needed to suppress discretization error when representing molecules in the plane wave basis, or when simulating without the Born-Oppenheimer approximation. △ Less

Submitted 19 August, 2019; v1 submitted 25 July, 2018; originally announced July 2018.

Comments: 8 pages, 1 figure

Journal ref: npj Quantum Information 5, 92 (2019)

Black-box quantum state preparation without arithmetic

Authors: Yuval R. Sanders, Guang Hao Low, Artur Scherer, Dominic W. Berry

Abstract: Black-box quantum state preparation is an important subroutine in many quantum algorithms. The standard approach requires the quantum computer to do arithmetic, which is a key contributor to the complexity. Here we present a new algorithm that avoids arithmetic. We thereby reduce the number of gates by a factor of 286-374 over the best prior work for realistic precision; the improvement factor inc… ▽ More Black-box quantum state preparation is an important subroutine in many quantum algorithms. The standard approach requires the quantum computer to do arithmetic, which is a key contributor to the complexity. Here we present a new algorithm that avoids arithmetic. We thereby reduce the number of gates by a factor of 286-374 over the best prior work for realistic precision; the improvement factor increases with the precision. As quantum state preparation is a crucial subroutine in many approaches to simulating physics on a quantum computer, our new method brings useful quantum simulation closer to reality. △ Less

Submitted 30 January, 2019; v1 submitted 9 July, 2018; originally announced July 2018.

Comments: This version is identical in content to the published version. Presentation much improved and Table I added

Journal ref: Phys. Rev. Lett. 122, 020502 (2019)

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

Authors: Ryan Babbush, Dominic Berry, Hartmut Neven

Abstract: We show that one can quantum simulate the dynamics of a Sachdev-Ye-Kitaev model with $N$ Majorana modes for time $t$ to precision $ε$ with gate complexity $O(N^{7/2} t + N^{5/2} t \,{\rm polylog}(N/ ε))$. In addition to scaling sublinearly in the number of Hamiltonian terms, this gate complexity represents an exponential improvement in $1/ε$ and large polynomial improvement in $N$ and $t$ over pri… ▽ More We show that one can quantum simulate the dynamics of a Sachdev-Ye-Kitaev model with $N$ Majorana modes for time $t$ to precision $ε$ with gate complexity $O(N^{7/2} t + N^{5/2} t \,{\rm polylog}(N/ ε))$. In addition to scaling sublinearly in the number of Hamiltonian terms, this gate complexity represents an exponential improvement in $1/ε$ and large polynomial improvement in $N$ and $t$ over prior state-of-the-art algorithms which scale as $O(N^{10} t^2 / ε)$. Our approach involves a variant of the qubitization technique in which we encode the Hamiltonian $H$ as an asymmetric projection of a signal oracle $U$ onto two different signal states prepared by state oracles, $A\left\vert{0}\right\rangle \mapsto \left\vert{A}\right\rangle$ and $B \left\vert{0}\right\rangle \mapsto \left\vert{B}\right\rangle$, such that $H = \left\langle{B}\right\vert U\left\vert{A}\right\rangle$. Our strategy for applying this method to the Sachdev-Ye-Kitaev model involves realizing $B$ using only Hadamard gates and realizing $A$ as a random quantum circuit. △ Less

Submitted 13 March, 2019; v1 submitted 7 June, 2018; originally announced June 2018.

Comments: 8 pages, 1 figure. This version adds a more complete analysis in appendix

Journal ref: Phys. Rev. A 99, 040301 (2019)

Bayesian estimation for quantum sensing in the absence of single-shot detection

Authors: Hossein T. Dinani, Dominic W. Berry, Raul Gonzalez, Jeronimo R. Maze, Cristian Bonato

Abstract: Quantum information protocols, such as quantum error correction and quantum phase estimation, have been widely used to enhance the performance of quantum sensors. While these protocols have relied on single-shot detection, in most practical applications only an averaged readout is available, as in the case of room-temperature sensing with the electron spin associated with a nitrogen-vacancy center… ▽ More Quantum information protocols, such as quantum error correction and quantum phase estimation, have been widely used to enhance the performance of quantum sensors. While these protocols have relied on single-shot detection, in most practical applications only an averaged readout is available, as in the case of room-temperature sensing with the electron spin associated with a nitrogen-vacancy center in diamond. Here, we theoretically investigate the application of the quantum phase estimation algorithm for high dynamic-range magnetometry, in the case where single-shot readout is not available. We show that, even in this case, Bayesian estimation provides a natural way to use the available information in an efficient way. We apply Bayesian analysis to achieve an optimized sensing protocol for estimating a time-independent magnetic field with a single electron spin associated to a nitrogen-vacancy center at room temperature and show that this protocol improves the sensitivity over previous protocols by more than a factor of 3. Moreover, we show that an extra enhancement can be achieved by considering the timing information in the detector clicks. △ Less

Submitted 11 March, 2019; v1 submitted 4 June, 2018; originally announced June 2018.

Comments: 7 pages + 2 pages supplementary, 5 figures, In the updated version we have added updating the probability after every single measurement. Comments are welcome

Journal ref: Phys. Rev. B 99, 125413 (2019)

Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity

Authors: Ryan Babbush, Craig Gidney, Dominic W. Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler, Hartmut Neven

Abstract: We construct quantum circuits which exactly encode the spectra of correlated electron models up to errors from rotation synthesis. By invoking these circuits as oracles within the recently introduced "qubitization" framework, one can use quantum phase estimation to sample states in the Hamiltonian eigenbasis with optimal query complexity $O(λ/ ε)$ where $λ$ is an absolute sum of Hamiltonian coeffi… ▽ More We construct quantum circuits which exactly encode the spectra of correlated electron models up to errors from rotation synthesis. By invoking these circuits as oracles within the recently introduced "qubitization" framework, one can use quantum phase estimation to sample states in the Hamiltonian eigenbasis with optimal query complexity $O(λ/ ε)$ where $λ$ is an absolute sum of Hamiltonian coefficients and $ε$ is target precision. For both the Hubbard model and electronic structure Hamiltonian in a second quantized basis diagonalizing the Coulomb operator, our circuits have T gate complexity $O({N + \log (1/ε}))$ where $N$ is number of orbitals in the basis. This enables sampling in the eigenbasis of electronic structure Hamiltonians with T complexity $O(N^3 /ε+ N^2 \log(1/ε)/ε)$. Compared to prior approaches, our algorithms are asymptotically more efficient in gate complexity and require fewer T gates near the classically intractable regime. Compiling to surface code fault-tolerant gates and assuming per gate error rates of one part in a thousand reveals that one can error correct phase estimation on interesting instances of these problems beyond the current capabilities of classical methods using only about a million superconducting qubits in a matter of hours. △ Less

Submitted 18 September, 2018; v1 submitted 9 May, 2018; originally announced May 2018.

Comments: 39 pages, 25 figures, 9 tables; fixed minor errors from v1

Journal ref: Phys. Rev. X 8, 041015 (2018)

Simulating the dynamics of time-dependent Hamiltonians with a truncated Dyson series

Authors: Maria Kieferova, Artur Scherer, Dominic Berry

Abstract: We provide a general method for efficiently simulating time-dependent Hamiltonian dynamics on a circuit-model based quantum computer. Our approach is based on approximating the truncated Dyson series of the evolution operator, extending the earlier proposal by Berry to evolution generated by explicitly time-dependent Hamiltonians. Two alternative strategies are proposed to implement time ordering… ▽ More We provide a general method for efficiently simulating time-dependent Hamiltonian dynamics on a circuit-model based quantum computer. Our approach is based on approximating the truncated Dyson series of the evolution operator, extending the earlier proposal by Berry to evolution generated by explicitly time-dependent Hamiltonians. Two alternative strategies are proposed to implement time ordering while exploiting the superposition principle for sampling the Hamiltonian at different times. The resource cost of our simulation algorithm retains the optimal logarithmic dependence on the inverse of the desired precision. △ Less

Submitted 1 May, 2018; originally announced May 2018.

Journal ref: Phys. Rev. A 99, 042314 (2019)

Experimental optical phase measurement approaching the exact Heisenberg limit

Authors: Shakib Daryanoosh, Sergei Slussarenko, Dominic W. Berry, Howard M. Wiseman, Geoff J. Pryde

Abstract: The use of quantum resources can provide measurement precision beyond the shot-noise limit (SNL). The task of ab initio optical phase measurement---the estimation of a completely unknown phase---has been experimentally demonstrated with precision beyond the SNL, and even scaling like the ultimate bound, the Heisenberg limit (HL), but with an overhead factor. However, existing approaches have not b… ▽ More The use of quantum resources can provide measurement precision beyond the shot-noise limit (SNL). The task of ab initio optical phase measurement---the estimation of a completely unknown phase---has been experimentally demonstrated with precision beyond the SNL, and even scaling like the ultimate bound, the Heisenberg limit (HL), but with an overhead factor. However, existing approaches have not been able---even in principle---to achieve the best possible precision, saturating the HL exactly. Here we demonstrate a scheme to achieve true HL phase measurement, using a combination of three techniques: entanglement, multiple samplings of the phase shift, and adaptive measurement. Our experimental demonstration of the scheme uses two photonic qubits, one double passed, so that, for a successful coincidence detection, the number of photon-passes is $N=3$. We achieve a precision that is within $4\%$ of the HL, surpassing the best precision theoretically achievable with simpler techniques with $N=3$. This work represents a fundamental achievement of the ultimate limits of metrology, and the scheme can be extended to higher $N$ and other physical systems. △ Less

Submitted 1 May, 2019; v1 submitted 18 December, 2017; originally announced December 2017.

Comments: (12 pages, 6 figures), typos corrected

Journal ref: Nature Communications 9, 4606 (2018)