Pith. sign in

REVIEW 3 major objections 5 minor 6 cited by

Quantum simulation with sum-of-squares spectral amplification

T0 review · 3 major / 5 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Rewriting a Hamiltonian as a sum of squares and simulating its square root turns $O(\lambda/\epsilon)$ energy estimation into $O(\sqrt{\Delta\lambda}/\epsilon)$ with a matching lower bound.

desk verdict Real framework, one real proof bug: Theorem 5's sign-discrimination step violates the phase-estimation lemma it invokes; the rest is coherent and worth serious refereeing. read the letter →

arxiv 2505.01528 v1 pith:TZGHNBU7 submitted 2025-05-02 quant-ph

Robbie King , Guang Hao Low , Ryan Babbush , Rolando D. Somma , Nicholas C. Rubin This is my paper · ORCID
classification quant-ph MSC 81P6868Q12
keywords quantumsimulationsum-of-squaresspectralamplificationenergyestimationground-statephaseSYKmodelblock-encodingquerycomplexity
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper argues that low-energy quantum simulation can be accelerated by rewriting the shifted Hamiltonian $H+\beta\mathbb{1}$ as an explicit sum of squares $\sum_j B_j^\dagger B_j$, then block-encoding the square root $H_{\mathrm{SOSSA}}=\sum_j |j\rangle\otimes B_j$ instead of $H$ itself. Because the square root is steep near zero, a coarse phase estimate of a small eigenvalue of the square root yields a fine estimate of the corresponding eigenvalue of $H$, reducing the query complexity of energy estimation and ground-state phase estimation from $O(\lambda/\epsilon)$ to $O(\sqrt{\Delta\lambda}/\epsilon)$. The paper provides adaptive algorithms that achieve this scaling without prior knowledge of the low-energy scale $\Delta$, and a matching $\Omega(\sqrt{\Delta\lambda}/\epsilon)$ lower bound showing the scaling is optimal in the square-root access model. For the SYK model, a degree-2 Majorana sum of squares gives $\beta=O(N)$ and a double-factorized block-encoding with $\lambda_{SOS}=O(N^2)$, making the total query cost $O(N^{3/2})$ instead of $O(N^2)$ with comparable gate costs per query. If the key random-matrix bound for the SOS relaxation holds, low-energy simulation of SYK and similar strongly correlated systems is polynomially faster and query-optimal.

What carries the argument

The load-bearing object is the SOSSA square-root operator $H_{\mathrm{SOSSA}}=\sum_j |j\rangle\otimes B_j$ built from the sum-of-squares identity $H+\beta\mathbb{1}=\sum_j B_j^\dagger B_j$; it satisfies $H_{\mathrm{SOSSA}}^\dagger H_{\mathrm{SOSSA}}=H+\beta\mathbb{1}$ and is block-encoded with normalization $\lambda_{SOS}$. Two supporting mechanisms carry the argument: the qubitization quantum walk, whose eigenphases are $\arccos((E+\beta)/\lambda_{SOS})$ and whose derivative near the low-energy edge produces the $\sqrt{\Delta\lambda}$ amplification, and adaptive gapped phase estimation, which locates the low-energy edge without an a priori bound on $\Delta$ and removes the logarithmic overhead a naive binary search would pay. For the SYK application, the generators $B_j$ are degree-2 Majorana polynomials, and double factorization compiles their block-encoding with $O(N^4)$ gates while keeping $\lambda_{SOS}=O(N^2)$, the same asymptotic gate cost as the LCU encodings it replaces.

What would settle it

Solve the degree-2 Majorana SOS relaxation for random SYK instances at increasing $N$ (for example $N=16,32,48,64$) by evaluating the dual pseudoexpectation or the primal SDP, and check whether $\beta/N$ stays bounded by a constant independent of $N$; if $\beta$ grows faster than linearly, or if the empirical low-energy gap $\Delta_{SOS}$ exceeds $O(N)$, the claimed $O(N^{3/2})$ scaling for SYK fails.

Watch

Extended reading notes

Core claim

The paper's central claim is that any Hamiltonian admitting an SOS identity $H+\beta\mathbb{1}=\sum_j B_j^\dagger B_j$ with efficiently block-encodable generators $B_j$ can be simulated in the low-energy sector through the spectral-amplified operator $H_{\mathrm{SOSSA}}=\sum_j |j\rangle\otimes B_j$, whose composition with itself is $H+\beta\mathbb{1}$. Qubitization of the block-encoding $H_{\mathrm{SOSSA}}/\sqrt{\lambda_{SOS}}$ gives a quantum walk whose eigenphases are $\arccos((E+\beta)/\lambda_{SOS})$, and the nonlinearity of arccos at the low-energy edge lets a phase measurement of accuracy $\epsilon/\sqrt{\Delta\lambda}$ supply an energy estimate of accuracy $\epsilon$ when the state lies at most $\Delta$ above the lower bound $-\beta$. The resulting expectation estimator has query complexity $O(\sqrt{\max\{\epsilon,\lambda-|E|\}}\,\lambda/\epsilon)$, and the ground-state phase estimator with overlap $p$ has query complexity $O(\sqrt{\max\{\epsilon,\lambda+E\}}\,\lambda/(\sqrt{p}\,\epsilon)\log(1/p)\log(1/q))$, both with adaptive versions that need no prior bound on $\Delta$. For the SYK model the paper proves, using the dual pseudoexpectation formulation plus the random-matrix bound $\|J\|=O(N^{-1})$, that the degree-2 Majorana SOS achieves $\beta=O(N)$ with high probability, and with double factorization gives $\lambda_{SOS}=O(N^2)$ and $\Delta_{SOS}=O(N)$, hence $\sqrt{\Delta_{SOS}\lambda_{SOS}}=O(N^{3/2})$ versus $\lambda_{LCU}\sim N^2$. Theorem 8 establishes an $\Omega(\sqrt{\Delta\lambda}/\epsilon)$ lower bound for phase estimation in this access model, so the quadratic reduction is not an artifact of a weak upper bound.

Load-bearing premise

The load-bearing premise is Lemma 8's high-probability bound $\beta=O(N)$ for the degree-2 Majorana SOS on the SYK model; if the constants in the spectral-norm estimate $\|J\|=O(N^{-1})$ or in the known spectrum support $[-c\sqrt{N},c\sqrt{N}]$ grow with $N$ or are unusually large, then $\Delta_{SOS}$ could exceed $O(N)$ and the claimed $\sqrt{N}$ speedup would degrade.

Editorial extensions

If this is right

  • Energy expectation values in the low-energy sector can be estimated with $O(\sqrt{\max\{\epsilon,\lambda-|E|\}}\,\lambda/\epsilon)$ queries, improving the generic $O(\lambda/\epsilon)$ cost; the dependence on $\lambda-|E|$ rather than a known bound $\Delta$ means no prior knowledge of the low-energy scale is needed.
  • Ground-state phase estimation inherits the same quadratic reduction, costing $O(\sqrt{\max\{\epsilon,\lambda+E\}}\,\lambda/(\sqrt{p}\,\epsilon)\log(1/p)\log(1/q))$ queries with only two ancillary qubits.
  • For the SYK model, the total query complexity drops from $O(N^2)$ for LCU and termwise spectral amplification to $O(N^{3/2})$, a factor $\sqrt{N}$ speedup at equal $O(N^4)$ block-encoding gate costs.
  • The matching lower bound $\Omega(\sqrt{\Delta\lambda}/\epsilon)$ for phase estimation in the square-root access model shows these algorithms saturate the information-theoretic limit, not just beat the previous best known upper bound.
  • A low-depth variant estimates expectations of sum-of-squares observables at the standard quantum limit, with sample complexity $O\big((\sum_j \sqrt{\Delta_j a_j}/\sigma)^2\big)$ and only single-query Hadamard tests per term.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same $\sqrt{\Delta\lambda}$ reduction should transfer to any strongly correlated model that admits a low-degree SOS with a tight lower bound and a cheaply block-encoded normalization; the paper demonstrates this only for SYK, so extending it to lattice fermion or spin models with local generators is an untested extrapolation.
  • The degree-3 SOS example from the paper's reference [31] gives a tighter $\beta=O(\sqrt{N})$ but a larger $\lambda_{SOS}=O(N^{7/2})$, washing out the gain; this tradeoff suggests future SOS design should co-optimize the spectral gap with the encoding normalization rather than minimize $\beta$ alone, a program the paper notes but does not pursue.
  • The lower bound is proven when the algorithm receives the square-root block-encoding $H_{SOSSA}/\sqrt{\lambda_{SOS}}$; whether the same $\Omega(\sqrt{\Delta\lambda}/\epsilon)$ holds for algorithms given only the standard LCU block-encoding of $H$ directly is left open, since the advantage may partly be a re-encoding choice.
  • A practical test of the adaptive estimators would be to run the coarse first pass on small SYK instances to see how often the state is correctly classified as low-energy before committing to the full $\sqrt{\Delta\lambda}$ precision; the paper's complexity bounds assume this classification succeeds, and its empirical probability on finite systems is unmeasured.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The manuscript introduces SOSSA, a framework that combines sum-of-squares (SOS) decompositions of shifted Hamiltonians with spectral amplification (SA) to improve quantum algorithms for low-energy simulation problems. It claims gate- and query-complexity improvements for expectation estimation and ground-state phase estimation, replacing the standard O(lambda/epsilon) scaling by O(sqrt(Delta lambda)/epsilon) when a low-energy bound Delta is known, and by an adaptive no-prior bound of the form stated in Theorem 5 and Table II. The framework is applied to the Sachdev-Ye-Kitaev model, where a degree-2 Majorana SOS is shown via a random-matrix dual argument (Lemma 8) to give beta = O(N), implying Delta_SOS = O(N) and lambda_SOS = O(N^2), and hence a query complexity O(N^{3/2}) compared with O(N^2) for LCU. The paper also proves a matching lower bound Omega(sqrt(lambda Delta)/epsilon) for phase estimation in the block-encoding access model and gives a low-depth, standard-quantum-limit expectation estimator using Hadamard tests.

Significance. If the main theorems are correct, SOSSA is a significant contribution to quantum simulation: it generalizes prior spectral-amplification results [5, 16], removes the need for a priori energy upper bounds in expectation estimation, and exhibits a polynomial speedup for a strongly correlated model. The SYK analysis is a genuine strength: Lemma 8 is internally consistent, the random-matrix bound ||J|| = O(N^{-1}) and the trace inequality give beta = O(N), and the double-factorization bound lambda_SOS = O(N^2) is derived explicitly. The lower-bound reduction from PARITY of OR (Theorem 8) is an interesting and appropriate optimality result. The paper is carefully written and the appendices contain detailed proofs. However, the proof of the no-prior expectation-estimation theorem has a gap in its final sign-discrimination step, and the theorem statements of Theorems 5 and 7 contain a dimensional inconsistency with the bounds derived in their own proofs. These issues are local and repairable, but they are load-bearing for the advertised complexity claims, so the paper needs a major revision.

major comments (3)
  1. [Appendix B 1, proof of Theorem 5, final sign-discrimination step (after Eq. (B45))] The proof invokes Corollary 1 with parameters (epsilon, theta0) = (pi/2 - I_{imax,r}, pi/2). Corollary 1 and Lemma 6 require 0 < epsilon <= theta0 <= epsilon + theta0 <= pi/2. With theta0 = pi/2, the condition forces epsilon <= 0, while the actual value epsilon = pi/2 - I_{imax,r} is positive whenever I_{imax,r} < pi/2. The invoked subroutine is therefore outside the stated hypotheses, and the proof does not provide a valid way to distinguish the cases E < 0 and E > 0. Since Theorem 5 claims to estimate E for arbitrary sign and this final step is the only mechanism for that distinction, the no-prior expectation-estimation result is unproven as written. The text after Lemma 6 already notes the correct remedy (another round of phase estimation on, say, e^{i pi/2} U), so the gap is likely repairable, but it must be fixed explicitly.
  2. [Theorems 5 and 7 statements and Table II] The stated query complexity in Theorem 5 is O(sqrt(max{epsilon, lambda-|E|}) * lambda / epsilon * log(1/q)), and Theorem 7 has an analogous expression with lambda/(sqrt(p) epsilon). However, the proof's final bound in Eq. (B48) is Q = O(sqrt(lambda) * (sqrt(epsilon) + sqrt(lambda-|E|)) / epsilon * log(1/q)) = O(sqrt(lambda * max{epsilon, lambda-|E|}) / epsilon * log(1/q)), and the corresponding bound in Eq. (B69) is sqrt(lambda * max{epsilon, lambda+E}) / (sqrt(p) epsilon). The printed theorem statements and Table II carry an extra factor sqrt(lambda) and are not invariant under the physical rescaling (lambda, epsilon) -> (s lambda, s epsilon). The proof's version is dimensionally consistent and is the bound needed for the advertised speedup over lambda/epsilon. The theorem statements and Table II should be corrected to match the proof, and the comparison with prior work should be restated accordingly.
  3. [Appendix B 2, proof of Theorem 7, decision step around Eqs. (B60)-(B61)] The proof defines the non-Hermitian operator O = (|0><0| ⊗ I) Gpe and claims that, because Be[O/1] can be constructed with one query to Gpe, one may apply Theorem 4 or Theorem 5 to estimate kappa = <psi|O†O|psi> to additive error p/2. Theorem 4 and Theorem 5 estimate expectations of Hermitian operators from their block-encodings; the operator whose expectation equals kappa is O†O = Gpe† (|0><0| ⊗ I) Gpe, not O, and the text does not show how Be[O†O] is obtained. The quoted costs Q_{P,i} = O((1/sqrt(p)) log(1/q_i)) and Q_{H,i} = O(1/(sqrt(p) r^i) log(1/p) log(1/q_i)) are those of amplitude estimation, suggesting that the intended subroutine is standard amplitude estimation on Gpe followed by the projector. The proof needs a precise reduction to such a subroutine; as written, the justification for this step is incomplete.
minor comments (5)
  1. [Lemma 8, proof] The trace step Tr(J rho) >= -||J|| Tr(rho) uses the identity Tr(rho) = C(N,2); this depends on the normalization E[1] = 1 and on the choice of basis elements i gamma_a gamma_b (whose squares are +1). Please state these conventions explicitly, since the same calculation with gamma_a gamma_b would give diagonal entries -1 and change the sign of the bound.
  2. [Theorem 4, inequality (B14)] The error-propagation inequality epsilon <= sqrt(2 Delta lambda) * epsilon_PEA is stated without derivation; a one-line argument using the derivative of arccos at E/lambda would make the constant transparent to the reader.
  3. [Throughout, and Theorem 5 proof] The symbols Delta (energy gap) and Delta_1, Delta_2, Delta_3 (failure probabilities in Theorem 5) are overloaded; please rename the failure probabilities, e.g. q_1, q_2, q_3, to avoid confusion.
  4. [Introduction and Lemma 5] There are small textual issues: "of ofH" appears in the Introduction, and Lemma 5's phrasing "with probability p_j we estimate" should be rephrased to indicate that each eigencomponent with weight p_j is estimated with confidence 1-q.
  5. [Section IV] The statement that the number of terms in HSYK scales like ~N^4 could be made precise (e.g., Theta(N^4) with the combinatorial constant absorbed), since it is used to argue the optimality of the O(N^4) gate count for the LCU block-encoding.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: SOSSA theorems are proved from stated assumptions; the SYK speedup rests on independent random-matrix and spectrum bounds; self-citations are not load-bearing.

full rationale

The derivation chain is not circular. The framework is defined by an SOS decomposition H + beta I = sum_j B_j^dag B_j (Eq. 6) and the spectral-amplified operator H_SOSSA (Eq. 7), whose block-encoding normalization lambda_SOS is set by the chosen SOS representation. The query-complexity theorems (Thms 4-7) are proved from qubitization (Lemma 1), phase estimation (Lemma 5), gapped phase estimation (Lemma 6 from [40]), and error propagation through arccos; the final bounds O(sqrt(max{epsilon, lambda - |E|}) lambda/epsilon) are instance-dependent but are not obtained by renaming a fitted parameter. For SYK, Lemma 8 proves beta = O(N) using the dual SOS problem, matrix Holder, and the random-matrix bound ||J|| = O(N^{-1}) (Vershynin [47]), with spectral support [-c sqrt(N), c sqrt(N)] taken from Hastings-O'Donnell [31]; these are external, parameter-free inputs. lambda_SOS = O(N^2) follows from double factorization and the trace bound lambda_SOS <= 4N Tr(H + beta I) = 4N beta, so sqrt(Delta_SOS lambda_SOS) = O(N^{3/2}) is derived rather than assumed. The self-citations ([16] for chemistry, [5] for the PARITY-OR lower bound, [40] for Lemma 6) are building blocks or contextual reinforcement; none assumes the conclusion of this paper. The Theorem 5 sign-discrimination step flagged by the skeptical review (CGpe with theta0 = pi/2 and positive epsilon may violate Lemma 6's epsilon + theta0 <= pi/2 condition) is a proof gap in a subroutine rather than a circular dependence; it does not make an output equal to an input. Overall, the central claims have independent content, so the circularity score is low.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

The framework's speedup depends on three derived scalings for SYK: beta=O(N), lambda_SOS=O(N^2), and Delta_SOS=O(N), all stated without numerical constants. No parameters are fitted to data; the beta and lambda_SOS scalings are outputs of convex optimization and norm bounds. The listed axioms capture the external results the analysis pulls in (RMT spectral bound, known SYK spectrum, SDP strong duality, double-factorization block-encoding cost) and the algorithmic low-energy input condition.

free parameters (3)
  • SOS shift beta (SYK) = O(N) asymptotic, constant unspecified
    Output of the degree-2 Majorana SOS SDP; Lemma 8 proves beta=O(N) with high probability via the dual. Not fitted to data, but its scaling sets Delta_SOS.
  • Low-energy window Delta_SOS = O(N) asymptotic
    Follows from the SYK spectrum support [-c*sqrt(N), c*sqrt(N)] and beta=O(N). Controls the query complexity through sqrt(Delta_SOS).
  • SOS normalization lambda_SOS = O(N^2) asymptotic
    Bounded via lambda_SOS <= 4N Tr(H_SYK+beta I) = 4N*beta = O(N^2); depends on the double-factorization ansatz for the B_j block-encodings.
assumptions (5)
  • standard math Random matrix spectral norm bound: ||J|| = O(N^{-1}) with high probability for the SYK coupling matrix (Theorem 4.4.5 of [47]).
    Used in Lemma 8 (Appendix D.3) to lower bound the SOS dual objective by -cN; if the constant or growth differs, beta=O(N) fails.
  • domain assumption SYK spectrum support: eigenvalues of H_SYK lie in [-c*sqrt(N), c*sqrt(N)] for a constant c>0 with high probability.
    Invoked in Section IV to conclude Delta_SOS = O(N); cited to Ref. [31].
  • standard math Strong duality and Slater's condition for the SOS SDP, so the primal and dual optima coincide.
    Invoked in the Lemma 8 proof to transfer the dual lower bound to the primal; references [26, Section 5.2.3].
  • domain assumption Efficient block-encoding of B_j via double factorization, with O(N^2) gates per B_j and R = O(N^2) terms.
    Assumed in Section IV and Appendix D.2 to obtain total O(N^4) gate cost for the SOSSA block-encoding; based on quantum chemistry techniques [30,45].
  • domain assumption Low-energy input condition: for energy estimation, <psi|H|psi> <= -beta + Delta_SOS; for phase estimation, the trial state is supported on energies in [-beta, -beta+Delta_SOS].
    This is the defining setting of the algorithms (Section II); if the state is not low-energy, the sqrt(Delta*lambda) improvement does not apply.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quantum simulation with sum-of-squares spectral amplification." pith.science (2026). https://pith.science/paper/TZGHNBU7

@misc{pith2026250501528,
  author       = {Pith},
  title        = {Pith review of: Quantum simulation with sum-of-squares spectral amplification},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TZGHNBU7}},
  note         = {Machine review of arXiv:2505.01528}
}
read the original 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 \textit{et al.}, arXiv:2502.15882 (2025)], where SOSSA was used to achieve state-of-the-art gate costs for phase estimation of real-world quantum chemistry systems.

Figures

Figures reproduced from arXiv: 2505.01528 by the authors.

Figure 1
Figure 1. FIG. 1. Uncertainty propagation through the square root [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 6 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Optimal quantum simulation of linear non-unitary dynamics

    quant-ph 2025-08 conditional novelty 8.0 of 10

    A query-optimal quantum algorithm for non-unitary linear dynamics using generalized LCHS with approximate exponential-decay kernels and exponentially convergent uniform quadrature.

  2. Optimal Lower Bounds for Hamiltonian Simulation

    quant-ph 2026-07 conditional novelty 7.0 of 10

    There exist simple weighted-local Hamiltonians for which quantum simulation requires Ω(min over K of (Kt + t²λ_K²/ε)) gates — exactly matching the composite qDRIFT algorithm's cost.

  3. Trace-Based Reconstruction of Quantum Circuit Dataflow in Surface Codes

    quant-ph 2025-08 conditional novelty 7.0 of 10

    From per-patch binary activity traces of surface-code lattice surgery, TraceQ reconstructs the two-qubit gate dependency DAG and detects embedded subroutines with 74-95% success and no false positives, but only on syn...

  4. Heisenberg limited quantum algorithm for estimating the fidelity susceptibility

    quant-ph 2025-09 conditional novelty 6.0 of 10

    A quantum algorithm estimates fidelity susceptibility in O~(1/epsilon) queries using a resolvent reformulation, achieving Heisenberg-limited precision.

  5. Qubit-Efficient Quantum Algorithm for Linear Differential Equations

    quant-ph 2025-07 conditional novelty 5.0 of 10

    A single-ancilla postselection algorithm solves dissipative linear ODEs with first-order error bounds and locality-preserving circuit structure.

  6. Quantum Computing Technology Roadmaps and Capability Assessment for Scientific Computing -- An analysis of use cases from the NERSC workload

    quant-ph 2025-09 conditional novelty 2.0 of 10

    A NERSC analysis finds that more than 50% of its workload could ultimately benefit from quantum computing and that vendor roadmaps and quantum application requirements are projected to overlap in the next 5 to 10 years.

Reference graph

Works this paper leans on

65 extracted references · 38 canonical work pages · cited by 6 Pith papers

  1. [16]

    G. H. Low, R. King, D. W. Berry, Q. Han, A. E. De- Prince III, A. White, R. Babbush, R. D. Somma, and N. C. Rubin, arXiv preprint arXiv:2502.15882 (2025)

    arXiv 2025

  2. [1]

    Knill, G

    E. Knill, G. Ortiz, and R. D. Somma, Physical Review A—Atomic, Molecular, and Optical Physics 75, 012328 (2007)

    2007

  3. [2]

    D. W. Berry, Y. Tong, T. Khattar, A. White, T. I. Kim, S. Boixo, L. Lin, S. Lee, G. K.-L. Chan, R. Babbush, and N. C. Rubin, Rapid initial state preparation for the quan- tum simulation of strongly correlated molecules (2024), arXiv:2409.11748 [quant-ph]

    arXiv 2024

  4. [3]

    G. H. Low and I. L. Chuang, Physical review letters 118, 010501 (2017)

    2017

  5. [4]

    G. H. Low and I. L. Chuang, Quantum 3, 163 (2019)

    2019

  6. [5]

    Zlokapa and R

    A. Zlokapa and R. D. Somma, Quantum 8, 1449 (2024)

    work page 2024

  7. [6]

    A. Y. Kitaev, arXiv preprint quant-ph/9511026 (1995)

    arXiv 1995

  8. [7]

    Lloyd, Science 273, 1073 (1996)

    S. Lloyd, Science 273, 1073 (1996)

    1996

Show all 65 references
  1. [8]

    Wiebe, D

    N. Wiebe, D. Berry, P. Høyer, and B. C. Sanders, Journal of Physics A: Mathematical and Theoretical 43, 065203 (2010)

    2010

  2. [9]

    D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma, Physical review letters114, 090502 (2015)

    2015

  3. [10]

    N. C. Rubin, D. W. Berry, F. D. Malone, A. F. White, T. Khattar, A. E. DePrince III, S. Sicolo, M. K¨ uehn, M. Kaicher, J. Lee, et al. , PRX Quantum 4, 040303 (2023)

    2023

  4. [11]

    Babbush, J

    R. Babbush, J. R. McClean, M. Newman, C. Gidney, S. Boixo, and H. Neven, PRX quantum 2, 010103 (2021)

    2021

  5. [12]

    Loaiza and A

    I. Loaiza and A. F. Izmaylov, Journal of Chemical Theory and Computation 19, 8201 (2023)

    2023

  6. [13]

    J. Haah, M. B. Hastings, R. Kothari, and G. H. Low, SIAM Journal on Computing 52, FOCS18 (2023)

    2023

  7. [14]

    R. D. Somma and S. Boixo, SIAM Journal on Computing 42, 593 (2013)

    2013

  8. [15]

    G. H. Low and I. L. Chuang, arXiv preprint arXiv:1707.05391 (2017)

    2017 arXiv

  9. [17]

    Simon, M

    S. Simon, M. Degroote, N. Moll, R. Santagati, M. Streif, and N. Wiebe, Amplified amplitude estimation: Exploit- ing prior knowledge to improve estimates of expectation values (2024), arXiv:2402.14791 [quant-ph]

    2024 arXiv

  10. [18]

    M. X. Goemans and D. P. Williamson, Journal of the ACM (JACM) 42, 1115 (1995)

    1995

  11. [19]

    Pironio, M

    S. Pironio, M. Navascu´ es, and A. Acin, SIAM Journal on Optimization 20, 2157 (2010)

    2010

  12. [20]

    D. A. Mazziotti, Accounts of chemical research 39, 207 (2006)

    2006

  13. [21]

    Nakata, H

    M. Nakata, H. Nakatsuji, M. Ehara, M. Fukuda, K. Nakata, and K. Fujisawa, The Journal of Chemical Physics 114, 8282 (2001)

    2001

  14. [22]

    Navascu´ es, S

    M. Navascu´ es, S. Pironio, and A. Ac´ ın, New Journal of Physics 10, 073013 (2008)

    2008

  15. [23]

    Gily´ en, Y

    A. Gily´ en, Y. Su, G. H. Low, and N. Wiebe, in Proceed- ings of the 51st annual ACM SIGACT symposium on theory of computing (2019) pp. 193–204

    2019

  16. [24]

    J. M. Martyn, Z. M. Rossi, A. K. Tan, and I. L. Chuang, PRX quantum 2, 040203 (2021)

    2021

  17. [25]

    A. M. Childs and N. Wiebe, arXiv preprint arXiv:1202.5822 (2012)

    2012 arXiv

  18. [26]

    S. P. Boyd and L. Vandenberghe, Convex optimization (Cambridge university press, 2004)

    2004

  19. [27]

    Burer and R

    S. Burer and R. D. Monteiro, Mathematical program- ming 95, 329 (2003)

    2003

  20. [28]

    J. Povh, F. Rendl, and A. Wiegele, Computing 78, 277 (2006)

    2006

  21. [29]

    R. M. Erdahl, International Journal of Quantum Chem- istry 13, 697 (1978)

    1978

  22. [30]

    von Burg, G

    V. von Burg, G. H. Low, T. H¨ aner, D. S. Steiger, M. Rei- her, M. Roetteler, and M. Troyer, Physical Review Re- search 3, 033055 (2021)

    2021

  23. [31]

    M. B. Hastings and R. O’Donnell, in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (2022) pp. 776–789

    2022

  24. [32]

    D. W. Berry, M. Kieferov´ a, A. Scherer, Y. R. Sanders, G. H. Low, N. Wiebe, C. Gidney, and R. Babbush, npj Quantum Information 4, 22 (2018)

    2018

  25. [33]

    N. S. Mande and R. de Wolf, arXiv preprint arXiv:2305.04908 (2023)

    2023 arXiv

  26. [34]

    D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma, in Proceedings of the forty-sixth annual ACM symposium on Theory of computing (2014) pp. 283–292

    2014

  27. [35]

    A. M. Childs, D. Maslov, Y. Nam, N. J. Ross, and Y. Su, Proceedings of the National Academy of Sciences 115, 9456 (2018)

    2018

  28. [36]

    Jiang, A

    Z. Jiang, A. Kalev, W. Mruczkiewicz, and H. Neven, Quantum 4, 276 (2020)

    2020

  29. [37]

    Babbush, C

    R. Babbush, C. Gidney, D. W. Berry, N. Wiebe, J. Mc- Clean, A. Paler, A. Fowler, and H. Neven, Phys. Rev. X 8, 041015 (2018)

    2018

  30. [38]

    He, M.-X

    Y. He, M.-X. Luo, E. Zhang, H.-K. Wang, and X.-F. Wang, International Journal of Theoretical Physics 56, 2350 (2017)

    2017

  31. [39]

    Brassard, P

    G. Brassard, P. Hoyer, M. Mosca, and A. Tapp, Contem- porary Mathematics 305, 53 (2002)

    2002

  32. [40]

    G. H. Low and Y. Su, Quantum linear system algorithm with optimal queries to initial state preparation (2024), arXiv:2410.18178 [quant-ph]

    2024

  33. [41]

    Y. Ge, J. Tura, and J. I. Cirac, Faster ground state prepa- ration and high-precision ground energy estimation with fewer qubits (2018), arXiv:1712.03193 [quant-ph]

    2018 arXiv

  34. [42]

    Lin and Y

    L. Lin and Y. Tong, Quantum 4, 372 (2020)

    2020

  35. [43]

    Hall, Phys

    W. Hall, Phys. Rev. A 75, 032102 (2007)

    2007

  36. [44]

    Wittek, ACM Transactions on Mathematical Software (TOMS) 41, 1 (2015)

    P. Wittek, ACM Transactions on Mathematical Software (TOMS) 41, 1 (2015)

    2015

  37. [45]

    J. Lee, D. W. Berry, C. Gidney, W. J. Huggins, J. R. McClean, N. Wiebe, and R. Babbush, PRX Quantum 2, 030305 (2021)

    2021

  38. [46]

    Baumgartner, arXiv preprint arXiv:1106.6189 (2011)

    B. Baumgartner, arXiv preprint arXiv:1106.6189 (2011)

    2011 arXiv

  39. [47]

    Vershynin, High-dimensional probability: An introduc- tion with applications in data science , Vol

    R. Vershynin, High-dimensional probability: An introduc- tion with applications in data science , Vol. 47 (Cambridge university press, 2018)

    2018

  40. [48]

    N. C. Rubin, R. Babbush, and J. McClean, New Journal of Physics 20, 053020 (2018). 7 Appendix A: Quantum simulation using block-encodings and linear combination of unitaries In this section we discuss the LCU results in Table I for energy estimation, phase estimation, and time...

    2018

  41. [49]

    A standard approach is based on the linear combination of unitaries (LCU) method [9, 25]

    Block-encodings from linear combination of unitaries We discussed quantum simulation when having access to Be[H/λ] but in applications the block-encoding must be constructed from some representation of the Hamiltonian. A standard approach is based on the linear combination of ...

  42. [50]

    Expectation estimation by spectral amplification In this section, we present new quantum algorithms summarized in Table II that exploit SA to improve expectation estimation. Given a block-encoding Be[H/λ] of an arbitrary Hamiltonian H and a unitary preparing the state |ψ⟩, 11 ...

    2002

  43. [51]

    (B38) 15 We now evaluate the final error ϵ′ imax of the estimate of E for some choice of imax

    Hence sin |Iif|ri−if 2 ≤ π 3ri−if sin |Iif| 2 , sin 3|Iif| 2 ≤ 3 2 sin|Iif|, and ϵi = 2 sin (θi) sin|Ii| 2 = 2 sin (θi) sin|Iif|ri−if 2 ≤ 2 sin 3|Iif| 2 sin|Iif|ri−if 2 ≤πri−if sin|Iif| sin|Iif| 2 =πri−ifϵif≤ 8πri−ifo. (B38) 15 We now evaluate the final error ϵ′ imax of the es...

  44. [52]

    Choose imax = imax,1 +d, where d =⌈log1/r(16π)⌉, and q = ∆ 1

    Let imax,1 :=⌈ 1 2 log1/r(π2λ 8ϵ′ )⌉. Choose imax = imax,1 +d, where d =⌈log1/r(16π)⌉, and q = ∆ 1. The query complexity is Q1 =O √ λ√ ϵ′ log 1 ∆1 ! , (B39) and we show that we either obtain an estimate ofE to error at mostϵ′, or obtain an estimate of (λ−|E|)∈ [0,λ ] to at mos...

  45. [53]

    Choose imax = imax,2, and q = ∆ 2

    Let imax,2 := ⌈log1/r( √ (λ−|Himax ,r|)λ cϵ′ )⌉, where c = 2√ 3π . Choose imax = imax,2, and q = ∆ 2. The query complexity is Q2 =O p (λ−|Himax,r|)λ ϵ′ log 1 ∆2 ! , (B43) and we obtain an estimate of E to error at most ϵ′ as follows. ϵimax = 2 sin(θi) sin(|Ii|/2)≤ sin(θi)π 2ri...

  46. [54]

    Phase estimation by spectral amplification In this section, we present new quantum algorithms summarized in Table III that exploit SA to improve phase estimation of the energy of quantum ground states. Given a block-encoding Be[H/λ] and a unitary P preparing the state|ψ⟩, such...

    2017

  47. [55]

    θ>θ i +φi: The probability that we obtain outcome m = 1 is κ = X j |⟨ψj|ψt⟩|2 1 2 X ± |β(Θj,±)|2≤ X j |⟨ψj|ψt⟩|2 max j,± |β(Θj,±)|2 = max j,± |β(Θj,±)|2≤δi. (B59)

  48. [56]

    (B60) 19 Let us choose δi = p/4

    θ≤θi−φi: The probability that we obtain outcome m = 1 is κ = X j |⟨ψj|ψt⟩|2 1 2 X ± |α(Θj,±)|2 = p 2 X ± (1−|α(±θ)|2) + X j>0 |⟨ψj|ψt⟩|2 1 2 X ± |α(Θj,±)|2 ≥p(1−δi). (B60) 19 Let us choose δi = p/4. Hence, we can determine which of the two cases hold by deciding whether κ≤ δi ...

  49. [57]

    Then we either determine that E +λ≤ϵ′ and terminate the algorithm, or obtain an estimate ˆE = Θ(E) to constant multiplicative error

    Let imax =imax,1 + Θ(1), where imax,1 = 1 2 log1/r λ ϵ′ . Then we either determine that E +λ≤ϵ′ and terminate the algorithm, or obtain an estimate ˆE = Θ(E) to constant multiplicative error

  50. [58]

    Then we estimate E to additive error at most ϵ′

    Let imax =imax,2 + Θ(1), where imax,2 = log1/r √ ˆEλ ϵ′ . Then we estimate E to additive error at most ϵ′. The overall query complexity for these two loops over different imax is QH =O √ λ√pϵ′ ( √ ϵ′ + √ E +λ) log 1 p log 1 q ! , (B69) QP =O log(λ/ϵ′)√p log log(λ/ϵ′) q . (B70)

  51. [59]

    Indeed, these results can be shown to be optimal and tight lower bounds can be found

    Optimality of spectral amplification Some results in Table I are presented using Θ( .) notation and thus far we only commented on the upper bounds on the query complexity for quantum phase estimation and energy estimation. Indeed, these results can be shown to be optimal and t...

  52. [60]

    Aj PL−1 l=0 ajl # = Be

    Spectral amplification and linear combination of unitaries Thus far we provided the query complexities for various simulation tasks using spectral amplification. These results required access to Be[HSA/ √ λ], which can be constructed from the Be[Aj/aj] as explained in Lemma 3....

  53. [61]

    In the following, we will restrict our exposition to Hamiltonians composed of Pauli strings but the construction can be applied more generally

    SOS optimization Section III advocates for an SOS representation with increased complexity beyond termwise SA, which resulted in a loose lower bound that potentially negates an advantage through SA. In the following, we will restrict our exposition to Hamiltonians composed of ...

  54. [62]

    (B2), (B4)

    SOSSA block-encoding for Pauli operators Utilizing the solution of the SDP to construct the SOS generators Bj, we can now replace these in the spectral amplified Hamiltonian; that is, we can replace Aj→Bj in Eqs. (B2), (B4). Expanding Eq. (C6), each SOS generator is a linear c...

  55. [63]

    Degree-2 Majorana SOS For fermionic systems, a natural SOS ansatz is the degree-2 Majorana SOS, which we will use for the SYK model. In this section we describe how to implement degree-2 Majorana SOS for a general fermionic Hamiltonians of the form: H =i NX a,b=1 Kabγaγb− NX a...

  56. [64]

    Double factorization The degree-2 Majorana SOS leads to a representation of the Hamiltonian that takes the form H +β1 l = X j B† jBj , (D8) Bj =ej1 l + X a fj,aγa + X ab gj,abγaγb (D9) A similar factorization occurs in the 2-body term of quantum chemistry Hamiltonians. Using t...

  57. [65]

    Be " A† jAj Λj − 1 l ## |0⟩|ψ⟩ ! = 1 2 1 +⟨0|⟨ψ|

    Application to SYK model We can now bring all of these ingredients together to analyze the performance of degree-2 Majorana SOSSA with double factorization on the SYK model, when compared to the standard LCU approach. The asymptotic gate complexities to construct the necessary...

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.