Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2505.01528 · Physical Review Letters

Quantum Simulation with Sum-of-Squares Spectral Amplification

Robbie King, Guang Hao Low, Ryan Babbush, Rolando D. Somma, Nicholas C. Rubin

Published Dec 12, 2025• 19 citations
arXivHTMLPDF

Abstract

We present sum-of-squares spectral amplification (SOSSA), a framework for improving quantum simulation relevant to low-energy problems. We show how SOSSA can be applied to problems like energy and phase estimation and provide fast quantum algorithms for these problems that significantly improve over prior art. To illustrate the power of SOSSA in applications, we consider the Sachdev-Ye-Kitaev model, a representative strongly correlated system, and demonstrate asymptotic speedups over generic simulation methods by a factor of the square root of the system size. Our results reinforce those observed in [G. H. Low et al., arXiv:2502.15882], where SOSSA was used to achieve state-of-the-art gate costs for phase estimation of real-world quantum chemistry systems.

DOI
10.1103/m3fj-m4rm

Related papers

Fast Quantum Simulation of Electronic Structure by Spectral Amplification

Guang Hao Low, Robbie King, Dominic William Berry +6 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 spectral amplification, which magnifies the spectrum of the low-energy states of Hamiltonians that can be expressed as sums of squares. Spectral amplification enables estimating ground-state energies with significantly improved cost scaling in the block encoding normalization factor Λ to just 2 Λ E gap , where E gap ≪ Λ 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 spectral 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.

arXiv:2502.15882•Physical Review X•Sep 9, 2025•64 citations

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

Alicja Dutkiewicz, Alec F. White, Guang Hao Low +6 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.

quant-pharXiv:2607.15358•Jul 20, 2026•7 citations

Eigenstate Preparation Through Near-Optimal Eigenprobability Filtering

Po-Wei Huang, Bence Bakó, Bálint Koczor

Quantum simulation is expected to be a main application of quantum computers with realistic utility in quantum chemistry, materials science and beyond. However, preparing excited or general eigenstates is a central challenge, particularly when the desired eigenvalue is not known in advance, or when the overlap with the initial state is insufficient. We introduce the Dominant Eigenstate Filtering via Eigenprobability Amplification and Thresholding (DEFEAT) algorithm that identifies and filters the eigenstate with the largest overlap with the supplied initial state. Our key observation is that we do not need prior knowledge of the target eigenvalue, as we construct efficient twirling superoperators that map initial states to eigenprobability density operators $ρ$, diagonal in the Hamiltonian eigenbasis and encoding its spectral weights, alongside its block-encoding implementation. Our crucial innovation is the quadratic amplification of probabilities via the factorisation $ρ=ρ_{\rm sqrt}^\daggerρ_{\rm sqrt}$, analogous to the recently introduced sum-of-squares spectral amplification (SOSSA), which we use here to amplify the separation between dominant and subdominant components. Thresholding then yields the dominant-eigenstate projector. Compared with conventional phase estimation, DEFEAT improves the dependence on the overlap with the initial state while requiring substantially fewer ancillary qubits. We prove that the query complexity of the filtering step is optimal up to logarithmic factors and establish a complementary lower bound for eigenstate preparation under purified query access to $ρ$. We validate in numerical simulations that the convergence rate of DEFEAT matches our theoretical results. Our results provide a general eigenvalue-agnostic primitive for dominant eigenstate filtering and preparation, and for estimating properties of dominant eigenstates.

quant-pharXiv:2608.12297•Aug 13, 2026•2 citations

Hamiltonian Simulation by Uniform Spectral Amplification

Guang Hao Low, Isaac L. Chuang

The exponential speedups promised by Hamiltonian simulation on a quantum computer depends crucially on structure in both the Hamiltonian $\hat{H}$, and the quantum circuit $\hat{U}$ that encodes its description. In the quest to better approximate time-evolution $e^{-i\hat{H}t}$ with error $ε$, we motivate a systematic approach to understanding and exploiting structure, in a setting where Hamiltonians are encoded as measurement operators of unitary circuits $\hat{U}$ for generalized measurement. This allows us to define a \emph{uniform spectral amplification} problem on this framework for expanding the spectrum of encoded Hamiltonian with exponentially small distortion. We present general solutions to uniform spectral amplification in a hierarchy where factoring $\hat{U}$ into $n=1,2,3$ unitary oracles represents increasing structural knowledge of the encoding. Combined with structural knowledge of the Hamiltonian, specializing these results allow us simulate time-evolution by $d$-sparse Hamiltonians using $\mathcal{O}\left(t(d \|\hat H\|_{\text{max}}\|\hat H\|_{1})^{1/2}\log{(t\|\hat{H}\|/ε)}\right)$ queries, where $\|\hat H\|\le \|\hat H\|_1\le d\|\hat H\|_{\text{max}}$. Up to logarithmic factors, this is a polynomial improvement upon prior art using $\mathcal{O}\left(td\|\hat H\|_{\text{max}}+\frac{\log{(1/ε)}}{\log\log{(1/ε)}}\right)$ or $\mathcal{O}(t^{3/2}(d \|\hat H\|_{\text{max}}\|\hat H\|_{1}\|\hat H\|/ε)^{1/2})$ queries. In the process, we also prove a matching lower bound of $Ω(t(d\|\hat H\|_{\text{max}}\|\hat H\|_{1})^{1/2})$ queries, present a distortion-free generalization of spectral gap amplification, and an amplitude amplification algorithm that performs multiplication on unknown state amplitudes.

arXiv:1707.05391•Jul 17, 2017•179 citations

Perturbation Theory and the Sum of Squares

Matthew B. Hastings

The sum-of-squares (SoS) hierarchy is a powerful technique based on semi-definite programming that can be used for both classical and quantum optimization problems. This hierarchy goes under several names; in particular, in quantum chemistry it is called the reduced density matrix (RDM) method. We consider the ability of this hierarchy to reproduce weak coupling perturbation theory for three different kinds of systems: spin (or qubit) systems, bosonic systems (the anharmonic oscillator), and fermionic systems with quartic interactions. For such fermionic systems, we show that degree-$4$ SoS (called $2$-RDM in quantum chemsitry) does not reproduce second order perturbation theory but degree-$6$ SoS ($3$-RDM) does (and we conjecture that it reproduces third order perturbation theory). Indeed, we identify a fragment of degree-$6$ SoS which can do this, which may be useful for practical quantum chemical calculations as it may be possible to implement this fragment with less cost than the full degree-$6$ SoS. Remarkably, this fragment is very similar to one studied by Hastings and O'Donnell for the Sachdev-Ye-Kitaev (SYK) model.

arXiv:2205.12325•May 24, 2022•23 citations

Faster quantum simulation of quantum chemistry with tailored algorithms and Hamiltonians

Ian Kivlichan

With quantum computers on the horizon, it is essential to understand what problems they can be used to solve. One potential application is simulating quantum systems, in particular, systems with many interacting electrons. However, there is a disparity between the computational resources required to study these problems and the capabilities of modern experimental quantum devices. In this thesis, we make progress toward closing this gap by reducing the cost of quantum simulation of quantum chemistry on a number of fronts. In the first half, we develop three improved quantum simulation algorithms by approximating time evolution under the Hamiltonian using a truncated Taylor series rather than the Trotter-Suzuki decomposition. We do this first for the molecular electronic structure Hamiltonian in two representations, obtaining asymptotic improvements in terms of both the number of orbitals and the required precision. We also apply the truncated Taylor series paradigm to quantum simulation in real space, where we consider simulation of general wave functions discretized on a uniform grid. In the second half, by working with Hamiltonians tailored specifically to quantum algorithms, we demonstrate that Trotter steps of the electronic structure Hamiltonian can be simulated in exactly N depth and with only linear connectivity, where N is the number of spin-orbitals. This resolves the problem of non-locality in fermion-to-qubit mappings, and has wide-ranging applications for variational and phase estimation-based quantum simulation of quantum chemistry. We further study this algorithm on an error-corrected quantum computer using the surface code. Benchmarking it alongside other product formula approaches, we show that quantum simulation of scientifically important instances of the electronic structure problem that are classically intractable can be performed with only a few hundred thousand physical qubits and fewer than one billion costly fault-tolerant gates. Finally, we study the effect of using randomized Hamiltonians in iterative phase estimation, and how this allows us to reduce the costs of simulation as well as to exploit knowledge of the ground state in how we design our simulation algorithm.

•Jan 8, 2020•0 citations
We present sum-of-squares spectral amplification (SOSSA), a framework for improving quantum simulation relevant to low-energy problems. We show how SOSSA can be applied to problems like energy and phase estimation and provide fast quantum algorithms for these problems that significantly improve over prior art. To illustrate the power of SOSSA in applications, we consider the Sachdev-Ye-Kitaev model, a representative strongly correlated system, and demonstrate asymptotic speedups over generic simulation methods by a factor of the square root of the system size. Our results reinforce those observed in [G. H. Low et al., arXiv:2502.15882], where SOSSA was used to achieve state-of-the-art gate costs for phase estimation of real-world quantum chemistry systems.
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 spectral amplification, which magnifies the spectrum of the low-energy states of Hamiltonians that can be expressed as sums of squares. Spectral amplification enables estimating ground-state energies with significantly improved cost scaling in the block encoding normalization factor Λ to just 2 Λ E gap , where E gap ≪ Λ 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 spectral 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.
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 λ=O(ηΔ−1.5+η1.5Δ−1)λ= \mathcal{O}\left(ηΔ^{-1.5}+η^{1.5}Δ^{-1} \right)λ=O(ηΔ−1.5+η1.5Δ−1) compared to prior work λ=O(ηΔ−2+η2Δ−1)λ= \mathcal{O}(ηΔ^{-2}+η^2Δ^{-1})λ=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×2 - 44\times2−44× corresponding to the lowest cost estimates for ab initio materials simulation.
Quantum simulation is expected to be a main application of quantum computers with realistic utility in quantum chemistry, materials science and beyond. However, preparing excited or general eigenstates is a central challenge, particularly when the desired eigenvalue is not known in advance, or when the overlap with the initial state is insufficient. We introduce the Dominant Eigenstate Filtering via Eigenprobability Amplification and Thresholding (DEFEAT) algorithm that identifies and filters the eigenstate with the largest overlap with the supplied initial state. Our key observation is that we do not need prior knowledge of the target eigenvalue, as we construct efficient twirling superoperators that map initial states to eigenprobability density operators ρρρ, diagonal in the Hamiltonian eigenbasis and encoding its spectral weights, alongside its block-encoding implementation. Our crucial innovation is the quadratic amplification of probabilities via the factorisation ρ=ρsqrt†ρsqrtρ=ρ_{\rm sqrt}^\daggerρ_{\rm sqrt}ρ=ρsqrt†​ρsqrt​, analogous to the recently introduced sum-of-squares spectral amplification (SOSSA), which we use here to amplify the separation between dominant and subdominant components. Thresholding then yields the dominant-eigenstate projector. Compared with conventional phase estimation, DEFEAT improves the dependence on the overlap with the initial state while requiring substantially fewer ancillary qubits. We prove that the query complexity of the filtering step is optimal up to logarithmic factors and establish a complementary lower bound for eigenstate preparation under purified query access to ρρρ. We validate in numerical simulations that the convergence rate of DEFEAT matches our theoretical results. Our results provide a general eigenvalue-agnostic primitive for dominant eigenstate filtering and preparation, and for estimating properties of dominant eigenstates.
The exponential speedups promised by Hamiltonian simulation on a quantum computer depends crucially on structure in both the Hamiltonian H^\hat{H}H^, and the quantum circuit U^\hat{U}U^ that encodes its description. In the quest to better approximate time-evolution e−iH^te^{-i\hat{H}t}e−iH^t with error εεε, we motivate a systematic approach to understanding and exploiting structure, in a setting where Hamiltonians are encoded as measurement operators of unitary circuits U^\hat{U}U^ for generalized measurement. This allows us to define a \emph{uniform spectral amplification} problem on this framework for expanding the spectrum of encoded Hamiltonian with exponentially small distortion. We present general solutions to uniform spectral amplification in a hierarchy where factoring U^\hat{U}U^ into n=1,2,3n=1,2,3n=1,2,3 unitary oracles represents increasing structural knowledge of the encoding. Combined with structural knowledge of the Hamiltonian, specializing these results allow us simulate time-evolution by ddd-sparse Hamiltonians using O(t(d∥H^∥max∥H^∥1)1/2log⁡(t∥H^∥/ε))\mathcal{O}\left(t(d \|\hat H\|_{\text{max}}\|\hat H\|_{1})^{1/2}\log{(t\|\hat{H}\|/ε)}\right)O(t(d∥H^∥max​∥H^∥1​)1/2log(t∥H^∥/ε)) queries, where ∥H^∥≤∥H^∥1≤d∥H^∥max\|\hat H\|\le \|\hat H\|_1\le d\|\hat H\|_{\text{max}}∥H^∥≤∥H^∥1​≤d∥H^∥max​. Up to logarithmic factors, this is a polynomial improvement upon prior art using O(td∥H^∥max+log⁡(1/ε)log⁡log⁡(1/ε))\mathcal{O}\left(td\|\hat H\|_{\text{max}}+\frac{\log{(1/ε)}}{\log\log{(1/ε)}}\right)O(td∥H^∥max​+loglog(1/ε)log(1/ε)​) or O(t3/2(d∥H^∥max∥H^∥1∥H^∥/ε)1/2)\mathcal{O}(t^{3/2}(d \|\hat H\|_{\text{max}}\|\hat H\|_{1}\|\hat H\|/ε)^{1/2})O(t3/2(d∥H^∥max​∥H^∥1​∥H^∥/ε)1/2) queries. In the process, we also prove a matching lower bound of Ω(t(d∥H^∥max∥H^∥1)1/2)Ω(t(d\|\hat H\|_{\text{max}}\|\hat H\|_{1})^{1/2})Ω(t(d∥H^∥max​∥H^∥1​)1/2) queries, present a distortion-free generalization of spectral gap amplification, and an amplitude amplification algorithm that performs multiplication on unknown state amplitudes.
The sum-of-squares (SoS) hierarchy is a powerful technique based on semi-definite programming that can be used for both classical and quantum optimization problems. This hierarchy goes under several names; in particular, in quantum chemistry it is called the reduced density matrix (RDM) method. We consider the ability of this hierarchy to reproduce weak coupling perturbation theory for three different kinds of systems: spin (or qubit) systems, bosonic systems (the anharmonic oscillator), and fermionic systems with quartic interactions. For such fermionic systems, we show that degree-444 SoS (called 222-RDM in quantum chemsitry) does not reproduce second order perturbation theory but degree-666 SoS (333-RDM) does (and we conjecture that it reproduces third order perturbation theory). Indeed, we identify a fragment of degree-666 SoS which can do this, which may be useful for practical quantum chemical calculations as it may be possible to implement this fragment with less cost than the full degree-666 SoS. Remarkably, this fragment is very similar to one studied by Hastings and O'Donnell for the Sachdev-Ye-Kitaev (SYK) model.
With quantum computers on the horizon, it is essential to understand what problems they can be used to solve. One potential application is simulating quantum systems, in particular, systems with many interacting electrons. However, there is a disparity between the computational resources required to study these problems and the capabilities of modern experimental quantum devices. In this thesis, we make progress toward closing this gap by reducing the cost of quantum simulation of quantum chemistry on a number of fronts. In the first half, we develop three improved quantum simulation algorithms by approximating time evolution under the Hamiltonian using a truncated Taylor series rather than the Trotter-Suzuki decomposition. We do this first for the molecular electronic structure Hamiltonian in two representations, obtaining asymptotic improvements in terms of both the number of orbitals and the required precision. We also apply the truncated Taylor series paradigm to quantum simulation in real space, where we consider simulation of general wave functions discretized on a uniform grid. In the second half, by working with Hamiltonians tailored specifically to quantum algorithms, we demonstrate that Trotter steps of the electronic structure Hamiltonian can be simulated in exactly N depth and with only linear connectivity, where N is the number of spin-orbitals. This resolves the problem of non-locality in fermion-to-qubit mappings, and has wide-ranging applications for variational and phase estimation-based quantum simulation of quantum chemistry. We further study this algorithm on an error-corrected quantum computer using the surface code. Benchmarking it alongside other product formula approaches, we show that quantum simulation of scientifically important instances of the electronic structure problem that are classically intractable can be performed with only a few hundred thousand physical qubits and fewer than one billion costly fault-tolerant gates. Finally, we study the effect of using randomized Hamiltonians in iterative phase estimation, and how this allows us to reduce the costs of simulation as well as to exploit knowledge of the ground state in how we design our simulation algorithm.