🔬 physics

Quantum simulation with sum-of-squares spectral amplification

This paper introduces sum-of-squares spectral amplification (SOSSA), a framework that significantly improves quantum simulation for low-energy problems by providing fast algorithms for energy and phase estimation that achieve asymptotic speedups over generic methods, as demonstrated on the Sachdev-Ye-Kitaev model and real-world quantum chemistry systems.

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

Published 2026-10-01

📖 5 min read🧠 Deep dive

CC BY 4.0

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

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Quantum computers promise to solve problems that are impossible for today's machines, particularly in the realm of simulating the behavior of matter. At the heart of this challenge is the need to model quantum systems, such as molecules or exotic materials, where particles interact in complex, entangled ways. To do this, scientists use algorithms that translate the physical laws governing these systems into a sequence of operations a computer can execute. However, these operations are incredibly expensive in terms of time and resources, especially when the computer must account for every possible energy state a system could occupy, including those that are highly unlikely to occur in nature. A major bottleneck has been that standard methods treat all energy levels with equal weight, forcing the computer to work through a vast, unnecessary landscape of high-energy possibilities just to find the specific, low-energy state that actually exists in the real world.

A team of researchers at Google Quantum AI and the California Institute of Technology has developed a new framework called sum-of-squares spectral amplification to bypass this inefficiency. Their approach is designed specifically for "low-energy" problems, which are the most relevant for understanding matter at low temperatures, such as the ground state of a molecule or the behavior of materials near a phase transition. Instead of simulating the entire energy spectrum, their method focuses the computational power on the specific, narrow range of energies where the system actually lives. By mathematically reshaping the problem before the quantum computer even begins its work, they can amplify the signal of the low-energy states, making them much easier to detect and measure. This allows the computer to reach the same level of accuracy with significantly fewer steps, effectively speeding up the simulation by a factor related to the square root of the system's size.

The core of this new strategy involves two distinct steps that work together to simplify the task. First, the researchers take the mathematical description of the system, known as a Hamiltonian, and shift it so that its lowest energy state is close to zero. They then rewrite this shifted description as a sum of positive terms, a process known as a sum-of-squares representation. This step is performed using classical computers and optimization techniques to find the best possible way to break down the system's energy into manageable pieces. The goal is to create a version of the problem where the energy gap between the ground state and the next available state is as small as possible, which is a crucial condition for the next step to work efficiently.

Once this optimized representation is ready, the second step applies a technique called spectral amplification. This technique effectively takes the square root of the system's energy values. Because the square root function grows very steeply for numbers close to zero, it acts as a magnifying glass for the low-energy states that the researchers care about. A small change in the original energy becomes a much larger, easier-to-measure change in the new, amplified version. This means that when the quantum computer performs measurements to determine the energy, it does not need to be as precise or perform as many operations to distinguish the correct state from the noise. The result is a dramatic reduction in the number of times the computer needs to query the system to get a reliable answer.

To prove that this method works in practice, the team applied it to the Sachdev-Ye-Kitaev model, a complex theoretical system used to study strongly correlated matter. In this specific case, the new method demonstrated a clear advantage over existing generic simulation techniques. While traditional approaches would require a number of operations that scales with the square of the system size, the new method reduced this requirement to a scaling factor of the system size to the power of one and a half. This translates to a speedup proportional to the square root of the system size, a significant improvement for large-scale simulations. The researchers also showed that this framework could be applied to other important tasks, such as estimating the energy of a quantum state or simulating how a system evolves over time, providing faster algorithms for all of these scenarios.

The work builds on previous findings where similar techniques were used to improve the efficiency of simulating chemical systems, but this paper extends the concept to a broader class of problems and provides a rigorous proof of its advantages. The researchers emphasize that while the initial step of finding the best mathematical representation requires significant classical computing power, the savings gained during the quantum simulation phase are substantial enough to make the overall process more efficient. They also note that the method is not a universal fix for every type of problem; its success depends on the specific structure of the system being simulated and the ability to find a suitable mathematical representation. However, for the low-energy problems that are central to understanding quantum matter, this approach offers a powerful new tool that moves the field closer to realizing the full potential of quantum simulation.

Technical Summary: Quantum Simulation with Sum-of-Squares Spectral Amplification

Problem Statement
Simulating quantum many-body systems is a primary application of quantum computing. While efficient algorithms exist for various simulation tasks, realizing robust large-scale quantum simulation requires mitigating the significant constant-factor overheads associated with fault-tolerant quantum computation. Current methods often rely on worst-case complexity bounds, which can be suboptimal for specific instances, particularly those involving low-energy states (e.g., ground states or low-temperature dynamics). The challenge is to exploit the specific structure of low-energy problems to improve gate and query complexities beyond generic worst-case limits.

Methodology: Sum-of-Squares Spectral Amplification (SOSSA)
The paper introduces Sum-of-Squares Spectral Amplification (SOSSA), a framework that combines two algorithmic concepts to improve simulation efficiency in the low-energy regime:

Sum-of-Squares (SOS) Representations: The Hamiltonian $H$ is shifted by a constant $\beta$ and represented as a sum of positive terms: $H + \beta \mathbb{1} = \sum_j B_j^\dagger B_j$ . This step is performed via classical preprocessing using semidefinite programming (SDP) to find a tight lower bound $-\beta$ on the ground-state energy. The operators $B_j$ are chosen to be efficiently block-encodable.
Spectral Amplification (SA): The framework constructs a "square root" Hamiltonian $H_{SOSSA}$ such that $H_{SOSSA}^\dagger H_{SOSSA} = H + \beta \mathbb{1}$ . The eigenvalues of $H_{SOSSA}$ are the square roots of the eigenvalues of the shifted Hamiltonian. Because the square root function is steep near zero ( $\sqrt{x} \gg x$ for small $x$ ), this transformation "amplifies" the low-energy spectrum.

The core insight is that by simulating the square root of the shifted Hamiltonian, the precision requirements for tasks like phase estimation are relaxed. An estimate of the square root eigenvalue with precision $\epsilon/\sqrt{E}$ translates to an estimate of the original energy $E$ with precision $\epsilon$ . This allows for a reduction in query complexity from linear in the Hamiltonian norm $\lambda$ to linear in $\sqrt{\Delta \lambda}$ , where $\Delta$ represents the energy gap above the ground state (or the relevant low-energy scale).

Key Contributions

General Framework: The paper provides a self-contained description of SOSSA, generalizing previous results (specifically Ref. [16]) beyond quantum chemistry to any finite-dimensional Hamiltonian. It details how to construct suitable SOS representations for arbitrary Hamiltonians to enable SA.
Improved Quantum Algorithms: The authors derive fast quantum algorithms for:
- Energy Estimation: Algorithms that estimate expectation values $\langle \psi | H | \psi \rangle$ without requiring an a priori upper bound on the expectation, applicable to arbitrary block-encoded operators.
- Ground-State Phase Estimation: Algorithms that estimate ground-state energies even when the overlap $p$ between the trial state and the ground state is small ( $p < 1$ ) and without requiring an upper bound on the energy.
Complexity Improvements: The proposed methods improve the linear dependence on the Hamiltonian norm $\lambda$ found in generic methods to a dependence on $\sqrt{\Delta \lambda}$ . This offers significant advantages when $\Delta \ll \lambda$ , a condition typical of low-energy instances.
Optimality Proofs: The paper establishes tight lower bounds for energy and phase estimation in the low-energy setting, demonstrating that the proposed SOSSA algorithms are query-optimal.
SYK Model Application: The framework is applied to the Sachdev-Ye-Kitaev (SYK) model, a representative strongly correlated system. By using a degree-2 SOS representation, the authors demonstrate an asymptotic speedup in gate complexity by a factor of $\sqrt{N}$ (where $N$ is the system size) compared to standard Linear Combination of Unitaries (LCU) and termwise SA methods.

Results

Query Complexity: For energy estimation and phase estimation, the query complexity improves from $\Theta(\lambda/\epsilon)$ to $\Theta(\sqrt{\Delta \lambda}/\epsilon)$ (or adaptive variants thereof).
SYK Model: For the SYK model, the standard LCU approach yields a normalization factor $\lambda_{LCU} \sim N^2$ . The termwise SA approach does not improve the scaling asymptotically. However, the SOSSA approach, utilizing a degree-2 SOS representation, achieves a normalization factor $\lambda_{SOS} \sim N^2$ but with a reduced energy gap $\Delta_{SOS} \sim N$ . This results in a query complexity scaling of $\sqrt{\Delta_{SOS}\lambda_{SOS}} \sim N^{3/2}$ , providing an asymptotic speedup of $\sqrt{N}$ over generic methods.
Gate Complexity: While the SOS step may introduce overheads in the complexity of the terms $B_j$ , the reduction in query complexity via SA leads to an overall improvement in gate complexity for the studied instances. The paper notes that optimizing the lower bound $-\beta$ alone does not guarantee improved gate complexity; the balance between the SOS representation complexity and the SA gain is critical.

Significance
The paper claims that SOSSA provides a useful and general framework for improving quantum simulation tasks, particularly for low-energy problems. The results reinforce findings from related work (Ref. [16]) where SOSSA achieved state-of-the-art gate costs for phase estimation in quantum chemistry. The authors posit that this framework is broadly applicable to other quantum systems, especially those where the low-energy properties can be exploited to reduce the effective norm of the Hamiltonian during simulation. The work also provides a low-depth version for expectation estimation that scales with the standard quantum limit, which may be of interest for near-term applications.

More like this