Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2606.23967

Polynomial-time exact diagonalization via sparse guided eigenwalks

Zachary E. Chin, Mario Motta, Javier Robledo Moreno, Antonio Mezzacapo, Isaac L. Chuang, William Kirby

quant-phSubmitted Jun 22, 2026• Announced Jun 24, 2026• 1 citation
arXivHTMLPDF

Abstract

Computing quantum ground states is generically difficult, but additional structure can sometimes allow diagonalization to be recast as a more feasible problem. For example, when the desired ground state is sparse in a given basis, diagonalization can be facilitated via graph search. We make this reformulation precise by introducing the eigenwalk problem, which seeks the support of a sparse eigenvector of a Hermitian matrix by exploring the graph induced by its nonzero entries. However, it is not obvious whether the relevant support vertices must always be efficiently reachable by a search on the graph. To resolve this question, we prove that for every sparse eigenvector, there exists a (possibly different) sparse eigenvector with the same eigenvalue whose support is tightly localized in the graph, with diameter scaling only linearly in the sparsity and independently of the total number of vertices. As a consequence, if a $2^n$-dimensional, ${\rm poly}(n)$-sparse Hamiltonian has an $\mathcal{O}(1)$-sparse extremal eigenvector and one support element is known, then an exact eigenvector with the same eigenvalue can be computed classically in ${\rm poly}(n)$ time. The same conclusion follows when the $\mathcal{O}(1)$-sparse eigenvector is non-extremal, provided that it is sparser than every eigenvector with a different eigenvalue. These results hold with no assumptions on the degeneracy, locality, spectral width, or spectral gap of the Hamiltonian, and the underlying support-localization principle also extends to problems beyond exact diagonalization, such as sparse principal component analysis.

Comments
11 pages (5 figures) + 14 page appendix (2 figures)

Related papers

A Quantum Algorithm for Computing All Eigenvalues and Eigenstates of Sparse Hermitian Matrices

Krishnakanta Barik, Goutam Paul

Computation of eigenvalues and eigenvectors of a sparse Hermitian matrix is a fundamental problem in algebra, arising both as a problem of independent interest and as a key subroutine in a wide range of computational and scientific applications. In this work, we develop a quantum algorithm that determines the spectrum of a sparse Hermitian matrix, defined as the set of its distinct eigenvalues, and for each eigenvalue, prepares a corresponding eigenvector as a quantum state in its eigenspace. The eigenvalues are represented as binary strings with a prescribed precision, while the corresponding eigenvectors are kept as quantum states, eliminating the need to reconstruct their classical counterparts. The algorithm instead enables estimation of expectation values $\braket{x|M|x}$, where $\ket{x}$ is a prepared eigenstate and $M$ is an observable. For an $n \times n$ $s$-sparse Hermitian matrix $H$, dense methods based on Householder tridiagonalization and QR iteration compute all eigenvalues and eigenvectors in $\mathcal{O}(n^3)$ time. Exploiting sparsity, the Lanczos method computes all eigenvalues in $\mathcal{O}(n^2 s)$ time in exact arithmetic, but recovering all eigenvectors still requires $\mathcal{O}(n^3)$ time. In contrast, our algorithm runs in time $\tilde{\mathcal{O}}(n s^2 \log^2 n / Δ_{\min})$, where $Δ_{\min}$ denotes the minimum spectral gap of the normalized matrix. For inverse gaps up to $Δ_{\min}^{-1} = \mathcal{O}(n)$, the most favorable scaling for $n$ distinct eigenvalues, attained by nearly uniformly spaced spectra such as those of perfect-state-transfer spin chains and the Sylvester-Kac matrix, and for sparsity up to $s = o(\sqrt{n}/\log n)$, the proposed algorithm achieves an improved asymptotic runtime over the classical $\mathcal{O}(n^3)$ approach for computing all eigenvalues and eigenvectors, under standard sparse-access assumptions.

arXiv:2611.16610•Nov 12, 2026•0 citations

An efficient Pauli decomposition algorithm for structured matrices

Daniel J. Spencer, Kishor Bharti, Alexey V. Gorshkov

Decomposing classical matrices into linear combinations of Pauli strings is a major bottleneck for end-to-end implementations of near-term quantum algorithms. In this work, we consider a promise version of this Pauli decomposition problem in which the matrix is guaranteed to have support on only $k = \mathsf{poly}(n)$ Pauli strings and is given through classical sparse query access. Existing Pauli decomposition algorithms are designed for the generic, dense problem and do not inherently take advantage of this promised sparsity, so these approaches take time that is exponential in $n$. We present a randomized classical algorithm that does take advantage of this sparsity and recovers the exact Pauli decomposition with success probability at least $1 - δ$, for any $δ$. Under the stated access model, the algorithm executes with query and runtime complexity that is polynomial in $n$, $k$, and $\log(1/δ)$. These results show that, even though finding the Pauli decomposition is exponentially hard for general matrices, it becomes efficiently solvable for matrices that are known to be sparse in the Pauli basis, a regime that is relevant to near-term quantum algorithms operating on structured classical input.

quant-pharXiv:2606.31952•Jul 1, 2026•0 citations

A Quantum Speed-Up for Approximating the Top Eigenvectors of a Matrix

Yanlin Chen, András Gilyén, Ronald de Wolf

Finding a good approximation of the top eigenvector of a given d x d matrix A is a basic and important computational problem, with many applications. We give two different quantum algorithms that, given query access to the entries of a Hermitian matrix A and assuming a constant eigenvalue gap, output a classical description of a good approximation of the top eigenvector: one algorithm with time complexity Õ (d 1.75 ) and one with time complexity d 1.5+0(1) (the first algorithm has a slightly better dependence on the ℓ2-error of the approximating vector than the second, and uses different techniques of independent interest). Both of our quantum algorithms provide a polynomial speed-up over the best-possible classical algorithm, which needs Ω (d 2) queries to entries of A, and hence Ω(d 2) time. We extend this to a quantum algorithm that outputs a classical description of the subspace spanned by the top-q eigenvectors in time qd 1.5+o (1). We also prove a nearly-optimal lower bound of on the quantum query complexity of approximating the top eigenvector.

arXiv:2405.14765•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2025•15 citations

Spectral sparsification of matrix inputs as a preprocessing step for quantum algorithms

Steven Herbert, Sathyawageeswar Subramanian

We study the potential utility of classical techniques of spectral sparsification of graphs as a preprocessing step for digital quantum algorithms, in particular, for Hamiltonian simulation. Our results indicate that spectral sparsification of a graph with $n$ nodes through a sampling method, e.g.\ as in \cite{Spielman2011resistances} using effective resistances, gives, with high probability, a locally computable matrix $\tilde H$ with row sparsity at most $\mathcal{O}(\text{poly}\log n)$. For a symmetric matrix $H$ of size $n$ with $m$ non-zero entries, a one-time classical runtime overhead of $\mathcal{O}(m||H||t\log n/ε)$ expended in spectral sparsification is then found to be useful as a way to obtain a sparse matrix $\tilde H$ that can be used to approximate time evolution $e^{itH}$ under the Hamiltonian $H$ to precision $ε$. Once such a sparsifier is obtained, it could be used with a variety of quantum algorithms in the query model that make crucial use of row sparsity. We focus on the case of efficient quantum algorithms for sparse Hamiltonian simulation, since Hamiltonian simulation underlies, as a key subroutine, several quantum algorithms, including quantum phase estimation and recent ones for linear algebra. Finally, we also give two simple quantum algorithms to estimate the row sparsity of an input matrix, which achieve a query complexity of $\mathcal{O}(n^{3/2})$ as opposed to $\mathcal{O}(n^2)$ that would be required by any classical algorithm for the task.

arXiv:1910.02861•Oct 7, 2019•3 citations

Quantum 1-PCA with Pauli Measurements in Nearly Linear Time

Dutch Hansen, Jerry Li

We consider the problem of quantum 1-PCA: given copies of an unknown $n$-qubit mixed state, recover a classical description of its leading eigenvector. Our goal is to do so using non-adaptive and single-qubit measurements. For an $n$-qubit state with top eigenvalue $λ$ and spectral gap at least $Δ> 0$, we give an algorithm that recovers the leading eigenvector to fidelity at least $1 - \varepsilon$ with high probability using $\tilde{O}\left( {2^n \cdot η^2} / {Δ^3 \varepsilon^3}\right)$ copies and $\tilde{O}((2^n/Δ\varepsilon) \cdot \operatorname{poly}(η/Δ\varepsilon))$ time, where $η= \max (1 - λ, \varepsilon)$. All of our measurements are non-adaptively chosen, and performed in single-qubit Pauli bases. When the spectral gap is constant and the desired accuracy is comparable to the noise level, i.e. $\varepsilon = Ω(η)$, our runtime and copy complexity become $\tilde{O} (2^n / \varepsilon)$. This generalizes the guarantees of Grewal et al. [arXiv:2601.04444], who achieved similar rates, but under the assumption $η= 0$, i.e., that the state was pure. Our results show that the same rates hold in the presence of state misspecification, up to polylogarithmic factors. From a technical perspective, our algorithm works by recursively constructing low-dimensional subspaces that approximately preserve the target eigenvector. To achieve nearly linear runtime dependence on the dimension of the Hilbert space, we develop a novel structured Pauli sampling scheme that enables fast batched computation of exponentially many projected Pauli matrices.

quant-pharXiv:2610.06808•Oct 6, 2026•1 citation

Prelocality No-Go Theorems and Exactly Solvable Relational History Hamiltonians

Maxim V. Churilov

Exact permutation covariance does not itself supply a sparse metric geometry. For permutation-covariant, full-support $k$-body interaction orbits, the incident interaction norm scales as $\binom{N-1}{k-1}|J_N|\|h\|$; such orbits cannot have uniformly finite range in metrics of diverging diameter. A permutation-invariant Hamiltonian diagonal in the graph basis has ground-state multiplicity at least $N!/|\mathrm{Aut}(G)|$ whenever $G$ is a ground graph. We give a quantitative version for approximately symmetric energies, together with fixed-radius connectivity and unitary-isometry obstructions. The trace-distance asymmetry of an arbitrary state also bounds its probability of selecting one labeled graph. We then construct two exactly solvable finite relational history Hamiltonians. A cyclic clock with a reversible incidence update has a unique ground state; gauge reduction yields a cycle Laplacian with a rank-one pin and the exact gap $Δ_{N,L}=E_* (1-\cosθ_L)$, where $\tan(Lθ_L/2)=1/\sinθ_L$ and $0<θ_L<π/L$. In particular, $Δ_{N,L}/E_*=π^2/(2L^2)-2π^2/L^3+O(L^{-4})$, independently of the number of vertices. In an alternative order-free architecture, one clock qubit per unordered pair gives commuting four-local terms, $2^N$ ground states and a size-independent gap $E_*(1-1/\sqrt2)$. A fixed-weight control penalty selects $\binom Nq$ ground states without reducing the gap. These exact finite results expose clock and locality resource tradeoffs; they do not establish an emergent geometric phase.

quant-pharXiv:2610.14081•Oct 9, 2026•0 citations
Computing quantum ground states is generically difficult, but additional structure can sometimes allow diagonalization to be recast as a more feasible problem. For example, when the desired ground state is sparse in a given basis, diagonalization can be facilitated via graph search. We make this reformulation precise by introducing the eigenwalk problem, which seeks the support of a sparse eigenvector of a Hermitian matrix by exploring the graph induced by its nonzero entries. However, it is not obvious whether the relevant support vertices must always be efficiently reachable by a search on the graph. To resolve this question, we prove that for every sparse eigenvector, there exists a (possibly different) sparse eigenvector with the same eigenvalue whose support is tightly localized in the graph, with diameter scaling only linearly in the sparsity and independently of the total number of vertices. As a consequence, if a 2n2^n2n-dimensional, poly(n){\rm poly}(n)poly(n)-sparse Hamiltonian has an O(1)\mathcal{O}(1)O(1)-sparse extremal eigenvector and one support element is known, then an exact eigenvector with the same eigenvalue can be computed classically in poly(n){\rm poly}(n)poly(n) time. The same conclusion follows when the O(1)\mathcal{O}(1)O(1)-sparse eigenvector is non-extremal, provided that it is sparser than every eigenvector with a different eigenvalue. These results hold with no assumptions on the degeneracy, locality, spectral width, or spectral gap of the Hamiltonian, and the underlying support-localization principle also extends to problems beyond exact diagonalization, such as sparse principal component analysis.
Computation of eigenvalues and eigenvectors of a sparse Hermitian matrix is a fundamental problem in algebra, arising both as a problem of independent interest and as a key subroutine in a wide range of computational and scientific applications. In this work, we develop a quantum algorithm that determines the spectrum of a sparse Hermitian matrix, defined as the set of its distinct eigenvalues, and for each eigenvalue, prepares a corresponding eigenvector as a quantum state in its eigenspace. The eigenvalues are represented as binary strings with a prescribed precision, while the corresponding eigenvectors are kept as quantum states, eliminating the need to reconstruct their classical counterparts. The algorithm instead enables estimation of expectation values ⟨x∣M∣x⟩\braket{x|M|x}⟨x∣M∣x⟩, where ∣x⟩\ket{x}∣x⟩ is a prepared eigenstate and MMM is an observable. For an n×nn \times nn×n sss-sparse Hermitian matrix HHH, dense methods based on Householder tridiagonalization and QR iteration compute all eigenvalues and eigenvectors in O(n3)\mathcal{O}(n^3)O(n3) time. Exploiting sparsity, the Lanczos method computes all eigenvalues in O(n2s)\mathcal{O}(n^2 s)O(n2s) time in exact arithmetic, but recovering all eigenvectors still requires O(n3)\mathcal{O}(n^3)O(n3) time. In contrast, our algorithm runs in time O~(ns2log⁡2n/Δmin⁡)\tilde{\mathcal{O}}(n s^2 \log^2 n / Δ_{\min})O~(ns2log2n/Δmin​), where Δmin⁡Δ_{\min}Δmin​ denotes the minimum spectral gap of the normalized matrix. For inverse gaps up to Δmin⁡−1=O(n)Δ_{\min}^{-1} = \mathcal{O}(n)Δmin−1​=O(n), the most favorable scaling for nnn distinct eigenvalues, attained by nearly uniformly spaced spectra such as those of perfect-state-transfer spin chains and the Sylvester-Kac matrix, and for sparsity up to s=o(n/log⁡n)s = o(\sqrt{n}/\log n)s=o(n​/logn), the proposed algorithm achieves an improved asymptotic runtime over the classical O(n3)\mathcal{O}(n^3)O(n3) approach for computing all eigenvalues and eigenvectors, under standard sparse-access assumptions.
Decomposing classical matrices into linear combinations of Pauli strings is a major bottleneck for end-to-end implementations of near-term quantum algorithms. In this work, we consider a promise version of this Pauli decomposition problem in which the matrix is guaranteed to have support on only k=poly(n)k = \mathsf{poly}(n)k=poly(n) Pauli strings and is given through classical sparse query access. Existing Pauli decomposition algorithms are designed for the generic, dense problem and do not inherently take advantage of this promised sparsity, so these approaches take time that is exponential in nnn. We present a randomized classical algorithm that does take advantage of this sparsity and recovers the exact Pauli decomposition with success probability at least 1−δ1 - δ1−δ, for any δδδ. Under the stated access model, the algorithm executes with query and runtime complexity that is polynomial in nnn, kkk, and log⁡(1/δ)\log(1/δ)log(1/δ). These results show that, even though finding the Pauli decomposition is exponentially hard for general matrices, it becomes efficiently solvable for matrices that are known to be sparse in the Pauli basis, a regime that is relevant to near-term quantum algorithms operating on structured classical input.
Finding a good approximation of the top eigenvector of a given d x d matrix A is a basic and important computational problem, with many applications. We give two different quantum algorithms that, given query access to the entries of a Hermitian matrix A and assuming a constant eigenvalue gap, output a classical description of a good approximation of the top eigenvector: one algorithm with time complexity Õ (d 1.75 ) and one with time complexity d 1.5+0(1) (the first algorithm has a slightly better dependence on the ℓ2-error of the approximating vector than the second, and uses different techniques of independent interest). Both of our quantum algorithms provide a polynomial speed-up over the best-possible classical algorithm, which needs Ω (d 2) queries to entries of A, and hence Ω(d 2) time. We extend this to a quantum algorithm that outputs a classical description of the subspace spanned by the top-q eigenvectors in time qd 1.5+o (1). We also prove a nearly-optimal lower bound of on the quantum query complexity of approximating the top eigenvector.
We study the potential utility of classical techniques of spectral sparsification of graphs as a preprocessing step for digital quantum algorithms, in particular, for Hamiltonian simulation. Our results indicate that spectral sparsification of a graph with nnn nodes through a sampling method, e.g.\ as in \cite{Spielman2011resistances} using effective resistances, gives, with high probability, a locally computable matrix H~\tilde HH~ with row sparsity at most O(polylog⁡n)\mathcal{O}(\text{poly}\log n)O(polylogn). For a symmetric matrix HHH of size nnn with mmm non-zero entries, a one-time classical runtime overhead of O(m∣∣H∣∣tlog⁡n/ε)\mathcal{O}(m||H||t\log n/ε)O(m∣∣H∣∣tlogn/ε) expended in spectral sparsification is then found to be useful as a way to obtain a sparse matrix H~\tilde HH~ that can be used to approximate time evolution eitHe^{itH}eitH under the Hamiltonian HHH to precision εεε. Once such a sparsifier is obtained, it could be used with a variety of quantum algorithms in the query model that make crucial use of row sparsity. We focus on the case of efficient quantum algorithms for sparse Hamiltonian simulation, since Hamiltonian simulation underlies, as a key subroutine, several quantum algorithms, including quantum phase estimation and recent ones for linear algebra. Finally, we also give two simple quantum algorithms to estimate the row sparsity of an input matrix, which achieve a query complexity of O(n3/2)\mathcal{O}(n^{3/2})O(n3/2) as opposed to O(n2)\mathcal{O}(n^2)O(n2) that would be required by any classical algorithm for the task.
We consider the problem of quantum 1-PCA: given copies of an unknown nnn-qubit mixed state, recover a classical description of its leading eigenvector. Our goal is to do so using non-adaptive and single-qubit measurements. For an nnn-qubit state with top eigenvalue λλλ and spectral gap at least Δ>0Δ> 0Δ>0, we give an algorithm that recovers the leading eigenvector to fidelity at least 1−ε1 - \varepsilon1−ε with high probability using O~(2n⋅η2/Δ3ε3)\tilde{O}\left( {2^n \cdot η^2} / {Δ^3 \varepsilon^3}\right)O~(2n⋅η2/Δ3ε3) copies and O~((2n/Δε)⋅poly⁡(η/Δε))\tilde{O}((2^n/Δ\varepsilon) \cdot \operatorname{poly}(η/Δ\varepsilon))O~((2n/Δε)⋅poly(η/Δε)) time, where η=max⁡(1−λ,ε)η= \max (1 - λ, \varepsilon)η=max(1−λ,ε). All of our measurements are non-adaptively chosen, and performed in single-qubit Pauli bases. When the spectral gap is constant and the desired accuracy is comparable to the noise level, i.e. ε=Ω(η)\varepsilon = Ω(η)ε=Ω(η), our runtime and copy complexity become O~(2n/ε)\tilde{O} (2^n / \varepsilon)O~(2n/ε). This generalizes the guarantees of Grewal et al. [arXiv:2601.04444], who achieved similar rates, but under the assumption η=0η= 0η=0, i.e., that the state was pure. Our results show that the same rates hold in the presence of state misspecification, up to polylogarithmic factors. From a technical perspective, our algorithm works by recursively constructing low-dimensional subspaces that approximately preserve the target eigenvector. To achieve nearly linear runtime dependence on the dimension of the Hilbert space, we develop a novel structured Pauli sampling scheme that enables fast batched computation of exponentially many projected Pauli matrices.
Exact permutation covariance does not itself supply a sparse metric geometry. For permutation-covariant, full-support kkk-body interaction orbits, the incident interaction norm scales as (N−1k−1)∣JN∣∥h∥\binom{N-1}{k-1}|J_N|\|h\|(k−1N−1​)∣JN​∣∥h∥; such orbits cannot have uniformly finite range in metrics of diverging diameter. A permutation-invariant Hamiltonian diagonal in the graph basis has ground-state multiplicity at least N!/∣Aut(G)∣N!/|\mathrm{Aut}(G)|N!/∣Aut(G)∣ whenever GGG is a ground graph. We give a quantitative version for approximately symmetric energies, together with fixed-radius connectivity and unitary-isometry obstructions. The trace-distance asymmetry of an arbitrary state also bounds its probability of selecting one labeled graph. We then construct two exactly solvable finite relational history Hamiltonians. A cyclic clock with a reversible incidence update has a unique ground state; gauge reduction yields a cycle Laplacian with a rank-one pin and the exact gap ΔN,L=E∗(1−cos⁡θL)Δ_{N,L}=E_* (1-\cosθ_L)ΔN,L​=E∗​(1−cosθL​), where tan⁡(LθL/2)=1/sin⁡θL\tan(Lθ_L/2)=1/\sinθ_Ltan(LθL​/2)=1/sinθL​ and 0<θL<π/L0<θ_L<π/L0<θL​<π/L. In particular, ΔN,L/E∗=π2/(2L2)−2π2/L3+O(L−4)Δ_{N,L}/E_*=π^2/(2L^2)-2π^2/L^3+O(L^{-4})ΔN,L​/E∗​=π2/(2L2)−2π2/L3+O(L−4), independently of the number of vertices. In an alternative order-free architecture, one clock qubit per unordered pair gives commuting four-local terms, 2N2^N2N ground states and a size-independent gap E∗(1−1/2)E_*(1-1/\sqrt2)E∗​(1−1/2​). A fixed-weight control penalty selects (Nq)\binom Nq(qN​) ground states without reducing the gap. These exact finite results expose clock and locality resource tradeoffs; they do not establish an emergent geometric phase.