quantum-computing

Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation

Quantum Journal

23 min read

0 likes

⚡ Quantum Brief

Researchers Carrera Vazquez and Sobczyk introduced a quantum algorithm that approximates the k-th spectral gap and midpoint of Hermitian matrices with logarithmic qubits, achieving quadratic speedup over classical methods for large gaps. The algorithm’s QRAM complexity is O(N²/ε²Δₖ² polylog(N,1/Δₖ,1/ε,1/δ)), outperforming classical O(N^ω) approaches (ω≈2.371) when gaps are significant, offering efficiency gains for eigenproblems in physics and engineering. A key innovation is oblivious state preparation, enabling efficient eigenvalue counting below a threshold while maintaining O(N²) query complexity, crucial for spectral analysis in quantum simulations. In black-box models, the team proved an Ω(N²) query lower bound for detecting spectral gaps in binary matrices, establishing fundamental limits for quantum advantage in such tasks. Applications span quantum chemistry, machine learning, and materials science, where spectral gaps underpin stability analysis, phase transitions, and optimization algorithms.

Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation

Summarize this article with:

AbstractApproximating 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.► BibTeX data@article{CarreraVazquez2026spectralgapsquantum, doi = {10.22331/q-2026-04-15-2067}, url = {https://doi.org/10.22331/q-2026-04-15-2067}, title = {Spectral {G}aps with {Q}uantum {C}ounting {Q}ueries and {O}blivious {S}tate {P}reparation}, author = {Carrera Vazquez, Almudena and Sobczyk, Aleksandros}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2067}, month = apr, year = {2026} }► References [1] Alex N. Beavers and Eugene D. Denman. ``A new similarity transformation method for eigenvalues and eigenvectors''. Mathematical Biosciences 21, 143–169 (1974). https://doi.org/10.1016/0025-5564(74)90111-4 [2] 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, A1325–A1349 (2013). https://doi.org/10.1137/120876605 [3] Jess Banks, Jorge Garza-Vargas, Archit Kulkarni, and Nikhil Srivastava. ``Pseudospectral shattering, the sign function, and diagonalization in nearly matrix multiplication time''. Foundations of Computational Mathematics 23, 1959–2047 (2023). https://doi.org/10.1007/s10208-022-09577-5 [4] Rikhav Shah. ``Hermitian diagonalization in linear precision''. In Proc. ACM-SIAM Symposium on Discrete Algorithms. Pages 5599–5615. SIAM (2025). https://doi.org/10.1137/1.9781611978322.192 [5] Ian Jolliffe. ``Principal Component Analysis''. Springer-Verlag. (2002). https://doi.org/10.1007/b98835 [6] 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 Berlin Heidelberg (1997). https://doi.org/10.1007/bfb0020217 [7] Ulrike von Luxburg. ``A tutorial on spectral clustering''. Statistics and Computing 17, 395–416 (2007). https://doi.org/10.1007/s11222-007-9033-z [8] Jeff Cheeger. ``A lower bound for the smallest eigenvalue of the Laplacian''. In Problems in analysis: A symposium in honor of Salomon Bochner. Pages 195–199.

Princeton University Press, Princeton, NJ (1970). https://doi.org/10.1515/9781400869312-013 [9] Noga Alon and Vitali D. Milman. ``$\lambda$1, Isoperimetric inequalities for graphs, and superconcentrators''. Journal of Combinatorial Theory, Series B 38, 73–88 (1985). https://doi.org/10.1016/0095-8956(85)90092-9 [10] Anand Louis, Prasad Raghavendra, Prasad Tetali, and Santosh Vempala. ``Many sparse cuts via higher eigenvalues''. In Proc. ACM Symposium on Theory of Computing. Pages 1131–1140. (2012). https://doi.org/10.1145/2213977.2214079 [11] Subir Sachdev. ``Quantum phase transitions''.

Cambridge University Press. (2011). 2nd edition. https://doi.org/10.1017/cbo9780511973765 [12] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Joshua Lapan, Andrew Lundgren, and Daniel Preda. ``A quantum adiabatic evolution algorithm applied to random instances of an np-complete problem''. Science 292, 472–475 (2001). https://doi.org/10.1126/science.1057726 [13] Yunkai Zhou, Yousef Saad, Murilo L. Tiago, and James R. Chelikowsky. ``Self-consistent-field calculations using Chebyshev-filtered subspace iteration''. Journal of Computational Physics 219, 172–184 (2006). https://doi.org/10.1016/j.jcp.2006.03.017 [14] Georg Kresse and Jürgen Furthmüller. ``Efficient iterative schemes for ab initio total-energy calculations using a plane-wave basis set''. Physical Review B 54, 11169 (1996). https://doi.org/10.1103/PhysRevB.54.11169 [15] Joost VandeVondele, Urban Borstnik, and Jurg Hutter. ``Linear scaling self-consistent field calculations with millions of atoms in the condensed phase''. Journal of Chemical Theory and Computation 8, 3565–3573 (2012). https://doi.org/10.1021/ct200897x [16] Lin Lin, Jianfeng Lu, and Lexing Ying. ``Numerical methods for Kohn–Sham density functional theory''. Acta Numerica 28, 405–539 (2019). https://doi.org/10.1017/S0962492919000047 [17] Taehee Ko, Xiantao Li, and Chunhao Wang. ``Implementation of the density-functional theory on quantum computers with linear scaling with respect to the number of atoms'' (2023). [18] Martin Ziegler and Vasco Brattka. ``Computability in linear algebra''.

Theoretical Computer Science 326, 187–211 (2004). https://doi.org/10.1016/j.tcs.2004.06.022 [19] Aleksandros Sobczyk, Marko Mladenović, and Mathieu Luisier. ``Invariant subspaces and PCA in nearly matrix multiplication time''. Advances in Neural Information Processing Systems 37, 19013–19086 (2024). https://doi.org/10.52202/079017-0602 [20] Aleksandros Sobczyk. ``Deterministic complexity analysis of hermitian eigenproblems''. In 52nd International Colloquium on Automata, Languages, and Programming. Volume 334, pages 131:1–131:21. Schloss Dagstuhl–Leibniz-Zentrum für Informatik (2025). https://doi.org/10.4230/LIPIcs.ICALP.2025.131 [21] James Demmel, Ioana Dumitriu, and Ryan Schneider. ``Generalized pseudospectral shattering and inverse-free matrix pencil diagonalization''. Foundations of Computational Mathematics 24, 1–77 (2024). https://doi.org/10.1007/s10208-024-09682-7 [22] James Demmel, Ioana Dumitriu, and Ryan Schneider. ``Fast and inverse-free algorithms for deflating subspaces''. Linear Algebra and its Applications 735, 222–258 (2026). https://doi.org/10.1016/j.laa.2026.01.01 [23] 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). https://doi.org/10.1137/1.9781611978322.63 [24] Ming Gu and Stanley C. Eisenstat. ``A divide-and-conquer algorithm for the symmetric tridiagonal eigenproblem''. SIAM Journal on Matrix Analysis and Applications 16, 172–191 (1995). https://doi.org/10.1137/S0895479892241287 [25] Daniel A. Spielman and Shang-Hua Teng. ``Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems''. SIAM Journal on Matrix Analysis and Applications 35, 835–885 (2014). https://doi.org/10.1137/090771430 [26] Ioannis Koutis, Alex Levin, and Richard Peng. ``Faster spectral sparsification and numerical algorithms for SDD matrices''. ACM Transactions on Algorithms 12, 1–16 (2015). https://doi.org/10.1145/2743021 [27] Michele Benzi, Michele Rinelli, and Igor Simunec. ``Estimation of spectral gaps for sparse symmetric matrices'' (2024). https://doi.org/10.1007/s00211-026-01532-8 [28] Michael F. Hutchinson. ``A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines''. Communications in Statistics - Simulation and Computation 19, 433–450 (1990). https://doi.org/10.1080/03610919008812866 [29] Haim Avron and Sivan Toledo. ``Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix''. Journal of the ACM 58, 1–34 (2011). https://doi.org/10.1145/1944345.1944349 [30] Farbod Roosta-Khorasani and Uri Ascher. ``Improved bounds on sample size for implicit matrix trace estimators''. Foundations of Computational Mathematics 15, 1187–1212 (2015). https://doi.org/10.1007/s10208-014-9220-1 [31] Alice Cortinovis and Daniel Kressner. ``On randomized trace estimates for indefinite matrices with an application to determinants''. Foundations of Computational Mathematics 22, 875–903 (2022). https://doi.org/10.1007/s10208-021-09525-9 [32] Jules Tilly, Hongxiang Chen, Shuxiang Cao, Dario Picozzi, Kanav Setia, Ying Li, Edward Grant, Leonard Wossnig, Ivan Rungger, George H Booth, et al. ``The Variational Quantum Eigensolver: A review of methods and best practices''. Physics Reports 986, 1–128 (2022). https://doi.org/10.1016/j.physrep.2022.08.003 [33] 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, 4213 (2014). https://doi.org/10.1038/ncomms5213 [34] 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, 023023 (2016). https://doi.org/10.1088/1367-2630/18/2/023023 [35] A. Yu. Kitaev. ``Quantum measurements and the Abelian Stabilizer Problem'' (1995). [36] Daniel S. Abrams and Seth Lloyd. ``Quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors''.

Physical Review Letters 83, 5162 (1999). https://doi.org/10.1103/PhysRevLett.83.5162 [37] Uwe Dorner, Rafal Demkowicz-Dobrzanski, Brian J. Smith, Jeff S. Lundeen, Wojciech Wasilewski, Konrad Banaszek, and Ian A. Walmsley. ``Optimal quantum phase estimation''.

Physical Review Letters 102, 040403 (2009). https://doi.org/10.1103/PhysRevLett.102.040403 [38] Lin Lin and Yu Tong. ``Near-optimal ground state preparation''. Quantum 4, 372 (2020). https://doi.org/10.22331/q-2020-12-14-372 [39] Guang Hao Low and Yuan Su. ``Quantum Eigenvalue Processing''. SIAM Journal on Computing 55, 135–215 (2026). https://doi.org/10.1137/24m1689363 [40] Alex Kerzner, Vlad Gheorghiu, Michele Mosca, Thomas Guilbaud, Federico Carminati, Fabio Fracas, and Luca Dellantonio. ``A square-root speedup for finding the smallest eigenvalue''. Quantum Science and Technology 9, 045025 (2024). https://doi.org/10.1088/2058-9565/ad6a36 [41] Iordanis Kerenidis and Anupam Prakash. ``Quantum recommendation systems''. In Proc. Innovations in Theoretical Computer Science. Volume 67, pages 49:1–49:21. Schloss Dagstuhl–Leibniz-Zentrum für Informatik (2017). https://doi.org/10.4230/LIPIcs.ITCS.2017.49 [42] Changpeng Shao. ``Computing eigenvalues of diagonalizable matrices on a quantum computer''. ACM Transactions on Quantum Computing 3, 1–20 (2022). https://doi.org/10.1145/3527845 [43] Jeffrey B. Parker and Ilon Joseph. ``Quantum phase estimation for a class of generalized eigenvalue problems''. Physical Review A 102, 022422 (2020). https://doi.org/10.1103/PhysRevA.102.022422 [44] Zhiyan Ding, Haoya Li, Lin Lin, HongKang Ni, Lexing Ying, and Ruizhe Zhang. ``Quantum multiple eigenvalue gaussian filtered search: an efficient and versatile quantum phase estimation method''. Quantum 8, 1487 (2024). https://doi.org/10.22331/q-2024-10-02-1487 [45] Zhiyan Ding and Lin Lin. ``Simultaneous estimation of multiple eigenvalues with short-depth quantum circuit on early fault-tolerant quantum computers''. Quantum 7, 1136 (2023). https://doi.org/10.22331/q-2023-10-11-1136 [46] Simon Apers and Ronald de Wolf. ``Quantum speedup for graph sparsification, cut approximation, and Laplacian solving''. SIAM Journal on Computing 51, 1703–1742 (2022). https://doi.org/10.1137/21M1391018 [47] Yanlin Chen, András Gilyén, and Ronald de Wolf. ``A quantum speed-up for approximating the top eigenvectors of a matrix''. In Proc. ACM-SIAM Symposium on Discrete Algorithms. Pages 994–1036. SIAM (2025). https://doi.org/10.1137/1.9781611978322.29 [48] Ian D. Kivlichan, Jarrod McClean, Nathan Wiebe, Craig Gidney, Alán Aspuru-Guzik, Garnet Kin-Lic Chan, and Ryan Babbush. ``Quantum simulation of electronic structure with linear depth and connectivity''.

Physical Review Letters 120, 110501 (2018). https://doi.org/10.1103/PhysRevLett.120.110501 [49] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. ``Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics''. In Proc. ACM Symposium on Theory of Computing. Pages 193–204. (2019). https://doi.org/10.1145/3313276.3316366 [50] Shantanav Chakraborty, András Gilyén, and Stacey Jeffery. ``The Power of Block-Encoded Matrix Powers: Improved Regression Techniques via Faster Hamiltonian Simulation''. In Proc. International Colloquium on Automata, Languages, and Programming. Volume 132, pages 33:1–33:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2019). https://doi.org/10.4230/LIPIcs.ICALP.2019.33 [51] Charles Kenney and Alan J Laub. ``Rational iterative methods for the matrix sign function''. SIAM Journal on Matrix Analysis and Applications 12, 273–291 (1991). https://doi.org/10.1137/0612020 [52] Nir Ailon and Bernard Chazelle. ``The fast Johnson–Lindenstrauss transform and approximate nearest neighbors''. SIAM Journal on Computing 39, 302–322 (2009). https://doi.org/10.1137/060673096 [53] Nam H. Nguyen, Thong T. Do, and Trac D. Tran. ``A fast and efficient algorithm for low-rank approximation of a matrix''. In Proc. ACM Symposium on Theory of Computing. Pages 215–224. (2009). https://doi.org/10.1145/1536414.1536446 [54] Joel A Tropp. ``Improved analysis of the subsampled randomized Hadamard transform''. Advances in Adaptive Data Analysis 3, 115–126 (2011). https://doi.org/10.1142/S1793536911000787 [55] Andris Ambainis. ``Quantum lower bounds by quantum arguments''. In Proc. ACM Symposium on Theory of Computing. Pages 636–643. (2000). https://doi.org/10.1145/335305.335394 [56] Sebastian Dörn and Thomas Thierauf. ``The quantum query complexity of the determinant''.

Information Processing Letters 109, 325–328 (2009). https://doi.org/10.1016/j.ipl.2008.11.006 [57] 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, 1–23 (2024). https://doi.org/10.1145/3649320 [58] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. ``Quantum Random Access Memory''.

Physical Review Letters 100, 160501 (2008). https://doi.org/10.1103/PhysRevLett.100.160501 [59] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. ``Architectures for a quantum random access memory''. Physical Review A 78, 052310 (2008). https://doi.org/10.1103/PhysRevA.78.052310 [60] Samuel Jaques and Arthur G Rattew. ``QRAM: A Survey and Critique''. Quantum 9, 1922 (2025). https://doi.org/10.22331/q-2025-12-02-1922 [61] Patrick Rall. ``Quantum algorithms for estimating physical quantities using block encodings''. Physical Review A 102, 022408 (2020). https://doi.org/10.1103/PhysRevA.102.022408 [62] Afonso Bandeira, Amit Singer, and Thomas Strohmer. ``Mathematics of data science''. Draft available online. (2020). url: https://people.math.ethz.ch/abandeira/BandeiraSingerStrohmer-MDS-draft.pdf. https://people.math.ethz.ch/abandeira/BandeiraSingerStrohmer-MDS-draft.pdf [63] James W. Demmel. ``Applied numerical linear algebra''. SIAM. (1997). https://doi.org/10.1137/1.9781611971446 [64] Zhaojun Bai, James Demmel, and Ming Gu. ``An inverse free parallel spectral divide and conquer algorithm for nonsymmetric eigenproblems''. Numerische Mathematik 76, 279–308 (1997). https://doi.org/10.1007/s002110050264 [65] Iordanis Kerenidis and Anupam Prakash. ``Quantum gradient descent for linear systems and least squares''. Physical Review A 101, 022316 (2020). https://doi.org/10.1103/PhysRevA.101.022316 [66] Lov Grover and Terry Rudolph. ``Creating superpositions that correspond to efficiently integrable probability distributions'' (2002). [67] Mikko Möttönen, Juha J. Vartiainen, Ville Bergholm, and Martti M. Salomaa. ``Transformation of quantum states using uniformly controlled rotations''. Quantum Information & Computation 5, 467–473 (2005). url: https://dl.acm.org/doi/10.5555/2011670.2011675. https://dl.acm.org/doi/10.5555/2011670.2011675 [68] 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). https://doi.org/10.1145/301250.301349 [69] Scott Aaronson and Patrick Rall. ``Quantum Approximate Counting, Simplified''. In Proc. SIAM Symposium on Simplicity in Algorithms. Pages 24–32. SIAM (2020). https://doi.org/10.1137/1.9781611976014.5 [70] Scott Aaronson, Robin Kothari, William Kretschmer, and Justin Thaler. ``Quantum Lower Bounds for Approximate Counting via Laurent Polynomials''. In 35th Computational Complexity Conference. (2020). https://doi.org/10.4230/LIPIcs.CCC.2020.7 [71] John M. Martyn, Zane M. Rossi, Andrew K. Tan, and Isaac L. Chuang. ``Grand unification of quantum algorithms''. PRX Quantum 2, 040203 (2021). https://doi.org/10.1103/PRXQuantum.2.040203 [72] Daan Camps, Lin Lin, Roel Van Beeumen, and Chao Yang. ``Explicit quantum circuits for block encodings of certain sparse matrices''. SIAM Journal on Matrix Analysis and Applications 45, 801–827 (2024). https://doi.org/10.1137/22M1484298 [73] Christoph Sünderhauf, Earl Campbell, and Joan Camps. ``Block-encoding structured matrices for data input in quantum computing''. Quantum 8, 1226 (2024). https://doi.org/10.22331/q-2024-01-11-1226 [74] Daan Camps and Roel Van Beeumen. ``FABLE: Fast approximate quantum circuits for block-encodings''. In 2022 IEEE International Conference on Quantum Computing and Engineering. Pages 104–113. IEEE (2022). https://doi.org/10.1109/QCE53715.2022.00029 [75] Kaoru Mizuta and Keisuke Fujii. ``Recursive quantum eigenvalue and singular-value transformation: Analytic construction of matrix sign function by newton iteration''.

Physical Review Research 6, L012007 (2024). https://doi.org/10.1103/PhysRevResearch.6.L012007 [76] Guang Hao Low. ``Quantum signal processing by single-qubit dynamics''. PhD thesis. Massachusetts Institute of Technology. (2017).Cited byCould not fetch Crossref cited-by data during last attempt 2026-04-15 07:24:53: Could not fetch cited-by data for 10.22331/q-2026-04-15-2067 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-04-15 07:24:54: No response from ADS or unable to decode the received json data when getting the list of citing works.This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions. AbstractApproximating 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.► BibTeX data@article{CarreraVazquez2026spectralgapsquantum, doi = {10.22331/q-2026-04-15-2067}, url = {https://doi.org/10.22331/q-2026-04-15-2067}, title = {Spectral {G}aps with {Q}uantum {C}ounting {Q}ueries and {O}blivious {S}tate {P}reparation}, author = {Carrera Vazquez, Almudena and Sobczyk, Aleksandros}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2067}, month = apr, year = {2026} }► References [1] Alex N. Beavers and Eugene D. Denman. ``A new similarity transformation method for eigenvalues and eigenvectors''. Mathematical Biosciences 21, 143–169 (1974). https://doi.org/10.1016/0025-5564(74)90111-4 [2] 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, A1325–A1349 (2013). https://doi.org/10.1137/120876605 [3] Jess Banks, Jorge Garza-Vargas, Archit Kulkarni, and Nikhil Srivastava. ``Pseudospectral shattering, the sign function, and diagonalization in nearly matrix multiplication time''. Foundations of Computational Mathematics 23, 1959–2047 (2023). https://doi.org/10.1007/s10208-022-09577-5 [4] Rikhav Shah. ``Hermitian diagonalization in linear precision''. In Proc. ACM-SIAM Symposium on Discrete Algorithms. Pages 5599–5615. SIAM (2025). https://doi.org/10.1137/1.9781611978322.192 [5] Ian Jolliffe. ``Principal Component Analysis''. Springer-Verlag. (2002). https://doi.org/10.1007/b98835 [6] Bernhard Schölkopf, Alexander Smola, and Klaus-Robert Müller. ``Kernel Principal Component Analysis''.

In International Conference on Artificial Neural Networks. Pages 583–588.

Read Original

Source Information

Source: Quantum Journal

Website: https://quantum-journal.org/feed/

Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation

Tags

Source Information