pith. sign in

arxiv: 2508.21002 · v3 · submitted 2025-08-28 · 🪐 quant-ph · cs.DS· cs.NA· math.NA

Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation

Almudena Carrera Vazquez , Aleksandros Sobczyk This is my paper

Pith reviewed 2026-05-18 20:32 UTC · model grok-4.3

classification 🪐 quant-ph cs.DScs.NAmath.NA
keywords quantum algorithmspectral gapHermitian matrixquantum countingstate preparationquery complexityQRAM modeleigenvalue approximation
0
0 comments X

The pith

A quantum algorithm approximates the k-th spectral gap and midpoint of an N by N Hermitian matrix to additive error epsilon times the gap using logarithmic qubits and quadratic complexity.

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

The paper develops a quantum method to approximate the width and location of the k-th gap between eigenvalues of a large Hermitian matrix. It prepares a random initial state that supports quantum counting queries to tally how many eigenvalues lie below chosen thresholds. This produces approximations accurate to a fraction epsilon of the gap size, at total cost scaling as N squared over epsilon squared times gap squared, up to logarithmic factors. For matrices whose gaps are large relative to 1 over N, the cost improves on classical algorithms that scale with the matrix-multiplication exponent. The work also establishes an Omega of N squared query lower bound for deciding gap existence even in a non-symmetric black-box model.

Core claim

We present a quantum algorithm which approximates the k-th spectral gap Δ_k and corresponding midpoint μ_k of an N×N Hermitian matrix up to additive error εΔ_k using a logarithmic number of qubits. In the QRAM model its total complexity is bounded by O(N²/(ε² Δ_k²) polylog(N,1/Δ_k,1/ε,1/δ)). For large gaps this improves on the classical O(N^ω polylog) bound with ω≈2.37. The key technical step is preparation of a suitable random initial state that allows efficient counting of eigenvalues smaller than a threshold while maintaining quadratic complexity in N.

What carries the argument

Preparation of a suitable random initial state that enables quantum counting queries to determine the number of eigenvalues below a chosen threshold.

If this is right

  • For sufficiently large gaps the quantum method outperforms classical algorithms whose cost depends on fast matrix multiplication.
  • Only a logarithmic number of qubits is required, independent of matrix size.
  • An Omega(N²) query lower bound applies even to the simpler task of deciding whether a gap exists in certain binary matrices.
  • Spectral-gap estimation in science and engineering applications can use this approach when gaps are not too small.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same random-state counting primitive could be reused to approximate other spectral functions such as numerical rank or smoothed eigenvalue sums.
  • Hybridizing the method with quantum phase estimation might improve precision when gaps are small.
  • The quadratic lower bound suggests that further speed-ups would require additional structure or different input models beyond black-box or QRAM access.
  • Numerical tests on modest-sized random Hermitian matrices could check whether the hidden polylog factors remain modest in practice.

Load-bearing premise

A random initial state can be prepared efficiently enough to support accurate counting of eigenvalues below any threshold while the overall procedure stays quadratic in the matrix dimension N.

What would settle it

A concrete Hermitian matrix or family of matrices on which the random state preparation or the subsequent counting step requires super-quadratic resources or fails to reach the stated epsilon accuracy.

read the original abstract

Approximating the $k$-th spectral gap $\Delta_k=|\lambda_k-\lambda_{k+1}|$ and the corresponding midpoint $\mu_k=\frac{\lambda_k+\lambda_{k+1}}{2}$ of an $N\times N$ Hermitian matrix with eigenvalues $\lambda_1\geq\lambda_2\geq\ldots\geq\lambda_N$, is an important special case of the eigenproblem with numerous applications in science and engineering. In this work, we present a quantum algorithm which approximates these values up to additive error $\epsilon\Delta_k$ using a logarithmic number of qubits. Notably, in the QRAM model, its total complexity (queries and gates) is bounded by $O\left( \frac{N^2}{\epsilon^{2}\Delta_k^2}\mathrm{polylog}\left( N,\frac{1}{\Delta_k},\frac{1}{\epsilon},\frac{1}{\delta}\right)\right)$, where $\epsilon,\delta\in(0,1)$ are the accuracy and the failure probability, respectively. For large gaps $\Delta_k$, this provides a speed-up against the best-known complexities of classical algorithms, namely, $O \left( N^{\omega}\mathrm{polylog} \left( N,\frac{1}{\Delta_k},\frac{1}{\epsilon}\right)\right)$, where $\omega\lesssim 2.371$ is the matrix multiplication exponent. A key technical step in the analysis is the preparation of a suitable random initial state, which ultimately allows us to efficiently count the number of eigenvalues that are smaller than a threshold, while maintaining a quadratic complexity in $N$. In the black-box access model, we also report an $\Omega(N^2)$ query lower bound for deciding the existence of a spectral gap in a binary (albeit non-symmetric) matrix.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The manuscript proposes a quantum algorithm for approximating the k-th spectral gap Δ_k = |λ_k - λ_{k+1}| and midpoint μ_k = (λ_k + λ_{k+1})/2 of an N×N Hermitian matrix to additive error εΔ_k. The algorithm uses a logarithmic number of qubits and, in the QRAM model, achieves total query and gate complexity O(N²/(ε² Δ_k²) polylog(N, 1/Δ_k, 1/ε, 1/δ)). This is claimed to yield a speedup over classical algorithms with complexity O(N^ω polylog(N, 1/Δ_k, 1/ε)) for sufficiently large gaps, where ω ≲ 2.371. The central technical step is the oblivious preparation of a suitable random initial state that enables efficient quantum counting of eigenvalues below a given threshold while preserving quadratic scaling in N. The paper also proves an Ω(N²) query lower bound in the black-box model for deciding the existence of a spectral gap in a binary non-symmetric matrix.

Significance. If substantiated, the result offers a concrete quantum speedup for a practically relevant special case of the eigenproblem, with potential applications in scientific computing and engineering. The combination of quantum counting queries with oblivious state preparation to achieve quadratic-N scaling is a technically interesting contribution that may extend to other linear-algebra tasks. The matching-style lower bound in the black-box setting strengthens the overall narrative by establishing near-optimality in a related model.

major comments (1)
  1. The claimed O(N²/(ε² Δ_k²) polylog) bound is load-bearing on the oblivious random-state preparation subroutine. The manuscript must supply an explicit complexity analysis (query count, gate count, and dependence on Δ_k) of this preparation step and its composition with the subsequent counting procedure (phase estimation or amplitude amplification) to confirm that no additional N-factor is introduced when the gap is only Δ_k. Without this breakdown, the asserted quadratic scaling and the speedup relative to classical O(N^ω …) methods cannot be verified.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading, positive evaluation of the significance of our results, and constructive feedback. We address the single major comment below and will revise the manuscript to incorporate the requested clarifications.

read point-by-point responses

  1. Referee: The claimed O(N²/(ε² Δ_k²) polylog) bound is load-bearing on the oblivious random-state preparation subroutine. The manuscript must supply an explicit complexity analysis (query count, gate count, and dependence on Δ_k) of this preparation step and its composition with the subsequent counting procedure (phase estimation or amplitude amplification) to confirm that no additional N-factor is introduced when the gap is only Δ_k. Without this breakdown, the asserted quadratic scaling and the speedup relative to classical O(N^ω …) methods cannot be verified.

    Authors: We appreciate the referee drawing attention to the need for greater transparency in the complexity accounting. In the revised version we will add a new subsection (approximately 3.2) that provides a complete, self-contained breakdown. We will first analyze the oblivious random-state preparation subroutine in isolation, establishing that it uses O(N² polylog(N,1/Δ_k)) QRAM queries and gates with no hidden linear dependence on 1/Δ_k beyond the already-stated polylog factors. We will then show the composition with the subsequent quantum counting (via phase estimation and amplitude amplification) step-by-step: each invocation of counting contributes a factor of O(1/(ε Δ_k)) to the query count, while the state-preparation cost is incurred only a constant number of times per binary-search iteration and does not scale with N when Δ_k shrinks. The resulting total remains strictly O(N²/(ε² Δ_k²) polylog(N,1/Δ_k,1/ε,1/δ)) with no additional N-factor. This explicit accounting will confirm both the quadratic-N scaling and the claimed speedup over classical matrix-multiplication-based methods for sufficiently large gaps. revision: yes

Circularity Check

0 steps flagged

No significant circularity; complexity bound follows from standard quantum primitives with independent state-preparation subroutine

full rationale

The paper derives its O(N²/(ε² Δ_k²) polylog) query/gate bound for spectral-gap approximation by combining oblivious random-state preparation with quantum counting (phase estimation plus amplitude amplification) to count eigenvalues below a threshold. This construction is self-contained: the state-preparation routine is presented as a technical contribution whose cost is absorbed into the stated polylog factors, and the subsequent counting step uses standard quantum-query techniques whose overhead is independent of the target gap Δ_k once the initial state is fixed. No equation reduces to a fitted parameter renamed as a prediction, no uniqueness theorem is imported from the authors' prior work, and no ansatz is smuggled via self-citation. The Ω(N²) black-box lower bound is stated separately and does not rely on the upper-bound derivation. The overall argument therefore remains non-circular and externally falsifiable against classical matrix-multiplication exponents.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard quantum query and QRAM access assumptions plus the feasibility of preparing a suitable random initial state for eigenvalue counting; no free parameters or new physical entities are introduced in the abstract.

axioms (2)
  • domain assumption QRAM model provides efficient access to matrix elements
    Complexity bound is stated explicitly in the QRAM model.
  • ad hoc to paper A suitable random initial state can be prepared that enables efficient counting of eigenvalues below a threshold while keeping quadratic N cost
    Abstract identifies this preparation as the key technical step.

pith-pipeline@v0.9.0 · 5881 in / 1372 out tokens · 43530 ms · 2026-05-18T20:32:55.201011+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

59 extracted references · 59 canonical work pages · 2 internal anchors

  1. [1]

    Quantum lower bounds for approximate counting via laurent polynomials

    Scott Aaronson, Robin Kothari, William Kretschmer, and Justin Thaler. Quantum lower bounds for approximate counting via laurent polynomials. In35th Computa- tional Complexity Conference, 2020

    work page 2020

  2. [2]

    Quantum approximate counting, simplified

    Scott Aaronson and Patrick Rall. Quantum approximate counting, simplified. InProc. SIAM Symposium on Simplicity in Algorithms, pages 24–32. SIAM, 2020

    work page 2020

  3. [3]

    Quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors.Physical Review Letters, 83(24):5162, 1999

    Daniel S Abrams and Seth Lloyd. Quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors.Physical Review Letters, 83(24):5162, 1999

    work page 1999

  4. [4]

    The fast johnson–lindenstrauss transform and ap- proximate nearest neighbors.SIAM Journal on computing, 39(1):302–322, 2009

    Nir Ailon and Bernard Chazelle. The fast johnson–lindenstrauss transform and ap- proximate nearest neighbors.SIAM Journal on computing, 39(1):302–322, 2009

    work page 2009

  5. [5]

    More asymmetry yields faster matrix multiplication

    Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. More asymmetry yields faster matrix multiplication. In Proc. ACM- SIAM Symposium on Discrete Algorithms, pages 2005–2039. SIAM, 2025

    work page 2005

  6. [6]

    Journal of Combinatorial Theory, Series B, 38(1):73–88, 1985

    Noga Alon and Vitali D Milman.λ1, isoperimetric inequalities for graphs, and super- concentrators. Journal of Combinatorial Theory, Series B, 38(1):73–88, 1985

    work page 1985

  7. [7]

    Quantum speedup for graph sparsification, cut approximation, and laplacian solving.SIAM Journal on Computing, 51(6):1703–1742, 2022

    Simon Apers and Ronald De Wolf. Quantum speedup for graph sparsification, cut approximation, and laplacian solving.SIAM Journal on Computing, 51(6):1703–1742, 2022

    work page 2022

  8. [8]

    An inverse free parallel spectral divide and conquer algorithm for nonsymmetric eigenproblems

    Zhaojun Bai, James Demmel, and Ming Gu. An inverse free parallel spectral divide and conquer algorithm for nonsymmetric eigenproblems. Numerische Mathematik, 76(3):279–308, 1997

    work page 1997

  9. [9]

    Draft available at: https://people.math.ethz.ch/abandeira/BandeiraSingerStrohmer- MDS-draft.pdf, 2020

    Afonso Bandeira, Amit Singer, and Thomas Strohmer.Mathematics of data science. Draft available at: https://people.math.ethz.ch/abandeira/BandeiraSingerStrohmer- MDS-draft.pdf, 2020

    work page 2020

  10. [10]

    Pseudospec- tral shattering, the sign function, and diagonalization in nearly matrix multiplication time

    Jess Banks, Jorge Garza-Vargas, Archit Kulkarni, and Nikhil Srivastava. Pseudospec- tral shattering, the sign function, and diagonalization in nearly matrix multiplication time. Foundations of computational mathematics, 23(6):1959–2047, 2023

    work page 1959

  11. [11]

    A new similarity transformation method for eigen- values and eigenvectors.Mathematical Biosciences, 21(1-2):143–169, 1974

    AN Beavers Jr and ED Denman. A new similarity transformation method for eigen- values and eigenvectors.Mathematical Biosciences, 21(1-2):143–169, 1974. 20

    work page 1974

  12. [12]

    Estimation of spectral gaps for sparse symmetric matrices.arXiv preprint arXiv:2410.15349, 2024

    Michele Benzi, Michele Rinelli, and Igor Simunec. Estimation of spectral gaps for sparse symmetric matrices.arXiv preprint arXiv:2410.15349, 2024

    work page arXiv 2024

  13. [13]

    Explicit quantum circuits for block encodings of certain sparse matrices.arXiv preprint arXiv:2203.10236, 2022

    Daan Camps, Lin Lin, Roel Van Beeumen, and Chao Yang. Explicit quantum circuits for block encodings of certain sparse matrices.arXiv preprint arXiv:2203.10236, 2022

    work page arXiv 2022

  14. [14]

    Fable: Fast approximate quantum circuits for block-encodings

    Daan Camps and Roel Van Beeumen. Fable: Fast approximate quantum circuits for block-encodings. In2022 IEEE International Conference on Quantum Computing and Engineering (QCE), pages 104–113. IEEE, 2022

    work page 2022

  15. [15]

    The power of block- encoded matrix powers: Improved regression techniques via faster hamiltonian simu- lation

    Shantanav Chakraborty, András Gilyén, and Stacey Jeffery. The power of block- encoded matrix powers: Improved regression techniques via faster hamiltonian simu- lation. InProc. International Colloquium on Automata, Languages, and Programming. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019

    work page 2019

  16. [16]

    A lower bound for the smallest eigenvalue of the laplacian.Problems in analysis, 625(195-199):110, 1970

    Jeff Cheeger. A lower bound for the smallest eigenvalue of the laplacian.Problems in analysis, 625(195-199):110, 1970

    work page 1970

  17. [17]

    Fast and inverse-free algorithms for deflating subspaces.arXiv preprint arXiv:2310.00193, 2023

    James Demmel, Ioana Dumitriu, and Ryan Schneider. Fast and inverse-free algorithms for deflating subspaces.arXiv preprint arXiv:2310.00193, 2023

    work page arXiv 2023

  18. [18]

    Generalized pseudospectral shattering and inverse-free matrix pencil diagonalization.Foundations of Computa- tional Mathematics, pages 1–77, 2024

    James Demmel, Ioana Dumitriu, and Ryan Schneider. Generalized pseudospectral shattering and inverse-free matrix pencil diagonalization.Foundations of Computa- tional Mathematics, pages 1–77, 2024

    work page 2024

  19. [19]

    SIAM, 1997

    James W Demmel.Applied numerical linear algebra. SIAM, 1997

    work page 1997

  20. [20]

    The quantum query complexity of the deter- minant

    Sebastian Dörn and Thomas Thierauf. The quantum query complexity of the deter- minant. Information Processing Letters, 109(6):325–328, 2009

    work page 2009

  21. [21]

    Optimal quantum phase estima- tion

    Uwe Dorner, Rafal Demkowicz-Dobrzanski, Brian J Smith, Jeff S Lundeen, Wojciech Wasilewski, Konrad Banaszek, and Ian A Walmsley. Optimal quantum phase estima- tion. Physical review letters, 102(4):040403, 2009

    work page 2009

  22. [22]

    Quantum espresso: a modular and open-source software project for quantum- simulations of materials.Journal of physics: Condensed matter, 21(39):395502, 2009

    Paolo Giannozzi, Stefano Baroni, Nicola Bonini, Matteo Calandra, Roberto Car, Carlo Cavazzoni, Davide Ceresoli, Guido L Chiarotti, Matteo Cococcioni, Ismaila Dabo, et al. Quantum espresso: a modular and open-source software project for quantum- simulations of materials.Journal of physics: Condensed matter, 21(39):395502, 2009

    work page 2009

  23. [23]

    Quantum singu- lar value transformation and beyond: exponential improvements for quantum matrix arithmetics

    András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singu- lar value transformation and beyond: exponential improvements for quantum matrix arithmetics. InProc. ACM Symposium on Theory of Computing, pages 193–204, 2019

    work page 2019

  24. [24]

    Architectures for a quantum random access memory.Physical Review A, 78(5):052310, 2008

    Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Architectures for a quantum random access memory.Physical Review A, 78(5):052310, 2008

    work page 2008

  25. [25]

    An optimal linear- combination-of-unitaries-based quantum linear system solver.ACM Transactions on Quantum Computing, 5(2):1–23, 2024

    Sander Gribling, Iordanis Kerenidis, and Dániel Szilágyi. An optimal linear- combination-of-unitaries-based quantum linear system solver.ACM Transactions on Quantum Computing, 5(2):1–23, 2024

    work page 2024

  26. [26]

    Creating superpositions that correspond to efficiently integrable probability distributions

    Lov Grover and Terry Rudolph. Creating superpositions that correspond to efficiently integrable probability distributions.arXiv preprint quant-ph/0208112, 2002

    work page internal anchor Pith review Pith/arXiv arXiv 2002

  27. [27]

    Quantum algorithm for linear systems of equations.Physical review letters, 103(15):150502, 2009

    Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations.Physical review letters, 103(15):150502, 2009

    work page 2009

  28. [28]

    cp2k: atomistic simulations of condensed matter systems.Wiley Interdisciplinary Reviews: Computational Molecular Science, 4(1):15–25, 2014

    Jürg Hutter, Marcella Iannuzzi, Florian Schiffmann, and Joost VandeVondele. cp2k: atomistic simulations of condensed matter systems.Wiley Interdisciplinary Reviews: Computational Molecular Science, 4(1):15–25, 2014. 21

    work page 2014

  29. [29]

    Jaques and A

    Samuel Jaques and Arthur G Rattew. Qram: A survey and critique.arXiv preprint arXiv:2305.10310, 2023

    work page arXiv 2023

  30. [30]

    Springer, 2002

    Ian Jolliffe.Principal component analysis for special types of data. Springer, 2002

    work page 2002

  31. [31]

    Rational iterative methods for the matrix sign function

    Charles Kenney and Alan J Laub. Rational iterative methods for the matrix sign function. SIAM Journal on Matrix Analysis and Applications, 12(2):273–291, 1991

    work page 1991

  32. [32]

    Quantum recommendation systems

    Iordanis Kerenidis and Anupam Prakash. Quantum recommendation systems. In Proc. Innovations in Theoretical Computer Science, pages 49–1. Schloss Dagstuhl– Leibniz-Zentrum für Informatik, 2017

    work page 2017

  33. [33]

    A square-root speedup for finding the smallest eigenvalue.Quantum Science and Technology, 9(4):045025, aug 2024

    Alex Kerzner, Vlad Gheorghiu, Michele Mosca, Thomas Guilbaud, Federico Carmi- nati, Fabio Fracas, and Luca Dellantonio. A square-root speedup for finding the smallest eigenvalue.Quantum Science and Technology, 9(4):045025, aug 2024

    work page 2024

  34. [34]

    A. Yu. Kitaev. Quantum measurements and the abelian stabilizer problem.arXiv preprint arXiv:9511026, 1995

    work page 1995

  35. [35]

    Self-consistent equations including exchange and correlation effects.Physical review, 140(4A):A1133, 1965

    Walter Kohn and Lu Jeu Sham. Self-consistent equations including exchange and correlation effects.Physical review, 140(4A):A1133, 1965

    work page 1965

  36. [36]

    Efficient iterative schemes for ab initio total-energy calculations using a plane-wave basis set.Physical review B, 54(16):11169, 1996

    G Kresse and J Furthmüller. Efficient iterative schemes for ab initio total-energy calculations using a plane-wave basis set.Physical review B, 54(16):11169, 1996

    work page 1996

  37. [37]

    Near-optimal ground state preparation

    Lin Lin and Yu Tong. Near-optimal ground state preparation. Quantum, 4:372, December 2020

    work page 2020

  38. [38]

    Many sparse cuts via higher eigenvalues

    Anand Louis, Prasad Raghavendra, Prasad Tetali, and Santosh Vempala. Many sparse cuts via higher eigenvalues. InProc. ACM Symposium on Theory of Computing, pages 1131–1140, 2012

    work page 2012

  39. [39]

    Quantum signal processing by single-qubit dynamics

    Guang Hao Low. Quantum signal processing by single-qubit dynamics. PhD thesis, Massachusetts Institute of Technology, 2017

    work page 2017

  40. [40]

    Quantum eigenvalue processing

    Guang Hao Low and Yuan Su. Quantum eigenvalue processing. InProc. IEEE Sym- posium on Foundations of Computer Science, pages 1051–1062. IEEE, 2024

    work page 2024

  41. [41]

    Grandunification of quantum algorithms.PRX Quantum, 2(4):040203, 2021

    JohnMMartyn, ZaneMRossi, AndrewKTan, andIsaacLChuang. Grandunification of quantum algorithms.PRX Quantum, 2(4):040203, 2021

    work page 2021

  42. [42]

    The theory of variational hybrid quantum-classical algorithms.New Journal of Physics, 18(2):023023, 2016

    Jarrod R McClean, Jonathan Romero, Ryan Babbush, and Alán Aspuru-Guzik. The theory of variational hybrid quantum-classical algorithms.New Journal of Physics, 18(2):023023, 2016

    work page 2016

  43. [43]

    Recursive quantum eigenvalue/singular-value trans- formation

    Kaoru Mizuta and Keisuke Fujii. Recursive quantum eigenvalue/singular-value trans- formation. Bulletin of the American Physical Society, 2024

    work page 2024

  44. [44]

    Transformation of quantum states using uniformly controlled rotations

    Mikko Mottonen, Juha J Vartiainen, Ville Bergholm, and Martti M Salomaa. Trans- formation of quantum states using uniformly controlled rotations. arXiv preprint quant-ph/0407010, 2004

    work page internal anchor Pith review Pith/arXiv arXiv 2004

  45. [45]

    Stability of the lanczos method for matrix function approximation

    Cameron Musco, Christopher Musco, and Aaron Sidford. Stability of the lanczos method for matrix function approximation. InProc. ACM-SIAM Symposium on Dis- crete Algorithms, pages 1605–1624. SIAM, 2018

    work page 2018

  46. [46]

    Stable and efficient spectral divide and conquer algorithms for the symmetric eigenvalue decomposition and the svd.SIAM Journal on Scientific Computing, 35(3):A1325–A1349, 2013

    Yuji Nakatsukasa and Nicholas J Higham. Stable and efficient spectral divide and conquer algorithms for the symmetric eigenvalue decomposition and the svd.SIAM Journal on Scientific Computing, 35(3):A1325–A1349, 2013. 22

    work page 2013

  47. [47]

    The quantum query complexity of approximating the median and related statistics

    Ashwin Nayak and Felix Wu. The quantum query complexity of approximating the median and related statistics. In Proc. ACM Symposium on Theory of Computing, pages 384–393, 1999

    work page 1999

  48. [48]

    A fast and efficient algorithm for low- rank approximation of a matrix

    Nam H Nguyen, Thong T Do, and Trac D Tran. A fast and efficient algorithm for low- rank approximation of a matrix. InProc. ACM Symposium on Theory of Computing, pages 215–224, 2009

    work page 2009

  49. [49]

    Quantum phase estimation for a class of generalized eigenvalue problems.Physical Review A, 102(2):022422, 2020

    Jeffrey B Parker and Ilon Joseph. Quantum phase estimation for a class of generalized eigenvalue problems.Physical Review A, 102(2):022422, 2020

    work page 2020

  50. [50]

    A variational eigenvalue solver on a photonic quantum processor.Nature communications, 5(1):4213, 2014

    Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J Love, Alán Aspuru-Guzik, and Jeremy L O’brien. A variational eigenvalue solver on a photonic quantum processor.Nature communications, 5(1):4213, 2014

    work page 2014

  51. [51]

    Quantum algorithms for estimating physical quantities using block en- codings

    Patrick Rall. Quantum algorithms for estimating physical quantities using block en- codings. Phys. Rev. A, 102:022408, Aug 2020

    work page 2020

  52. [52]

    Kernel principal component analysis

    Bernhard Schölkopf, Alexander Smola, and Klaus-Robert Müller. Kernel principal component analysis. In International conference on artificial neural networks, pages 583–588. Springer, 1997

    work page 1997

  53. [53]

    Computing eigenvalues of diagonalizable matrices on a quantum computer

    Changpeng Shao. Computing eigenvalues of diagonalizable matrices on a quantum computer. ACM Transactions on Quantum Computing, 3(4):1–20, 2022

    work page 2022

  54. [54]

    Deterministic complexity analysis of hermitian eigenprob- lems

    Aleksandros Sobczyk. Deterministic complexity analysis of hermitian eigenprob- lems. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), pages 131–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2025

    work page 2025

  55. [55]

    Invariant subspaces and PCA in nearly matrix multiplication time.Advances in Neural Information Pro- cessing Systems, 2024

    Aleksandros Sobczyk, Marko Mladenović, and Mathieu Luisier. Invariant subspaces and PCA in nearly matrix multiplication time.Advances in Neural Information Pro- cessing Systems, 2024

    work page 2024

  56. [56]

    Block-encoding structured matrices for data input in quantum computing.Quantum, 8:1226, 2024

    Christoph Sünderhauf, Earl Campbell, and Joan Camps. Block-encoding structured matrices for data input in quantum computing.Quantum, 8:1226, 2024

    work page 2024

  57. [57]

    The varia- tional quantum eigensolver: a review of methods and best practices.Physics Reports, 986:1–128, 2022

    Jules Tilly, Hongxiang Chen, Shuxiang Cao, Dario Picozzi, Kanav Setia, Ying Li, Edward Grant, Leonard Wossnig, Ivan Rungger, George H Booth, et al. The varia- tional quantum eigensolver: a review of methods and best practices.Physics Reports, 986:1–128, 2022

    work page 2022

  58. [58]

    Improved analysis of the subsampled randomized hadamard transform

    Joel A Tropp. Improved analysis of the subsampled randomized hadamard transform. Advances in Adaptive Data Analysis, 3(01n02):115–126, 2011

    work page 2011

  59. [59]

    black-box

    Ulrike Von Luxburg. A tutorial on spectral clustering. Statistics and computing, 17:395–416, 2007. A Preliminaries on block-encodings and eigenvalue transformation In this section we recall some basic definitions and known results for block-encodings. Block-encoding refers to the derivation of a unitary operatorUA which can be described by a quantum circu...

    work page 2007