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.
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) compared to prior work
λ=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× 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, 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 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.
The exponential speedups promised by Hamiltonian simulation on a quantum computer depends crucially on structure in both the Hamiltonian
H^, and the quantum circuit
U^ that encodes its description. In the quest to better approximate time-evolution
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^ 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^ 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
O(t(d∥H^∥max∥H^∥1)1/2log(t∥H^∥/ε)) queries, where
∥H^∥≤∥H^∥1≤d∥H^∥max. Up to logarithmic factors, this is a polynomial improvement upon prior art using
O(td∥H^∥max+loglog(1/ε)log(1/ε)) or
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) 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-
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.
In Ref. 1, a method was given for self-consistently generating sum-of-squares decompositions of quartic fermionic Hamiltonians. Perturbation theory was used to generate a useful choice of cubic operators in this sum-of-squares. On a range of model problems, this method, which is only a fragment of degree-six sum-of-squares, was able to outperform the full degree-four sum-of-squares in both speed and accuracy. Unfortunately for applications, many problems in chemistry have strong density-density interaction terms, as well as moderately strong density-dependent hopping and spin-spin interaction terms, limiting the power of the perturbative choice of the cubic operators. Here we propose a method for generating these decompositions in the presence of these strong interaction terms, hopefully extending the range of applicability of this method.