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:2608.12297

Eigenstate Preparation Through Near-Optimal Eigenprobability Filtering

Po-Wei Huang, Bence Bakó, Bálint Koczor

quant-phSubmitted Aug 12, 2026• Announced Aug 13, 2026• 0 citations
arXivHTMLPDF

Abstract

Quantum simulation is expected to be a main application of quantum computers with realistic utility in quantum chemistry, materials science and beyond. However, preparing excited or general eigenstates is a central challenge, particularly when the desired eigenvalue is not known in advance, or when the overlap with the initial state is insufficient. We introduce the Dominant Eigenstate Filtering via Eigenprobability Amplification and Thresholding (DEFEAT) algorithm that identifies and filters the eigenstate with the largest overlap with the supplied initial state. Our key observation is that we do not need prior knowledge of the target eigenvalue, as we construct efficient twirling superoperators that map initial states to eigenprobability density operators $ρ$, diagonal in the Hamiltonian eigenbasis and encoding its spectral weights, alongside its block-encoding implementation. Our crucial innovation is the quadratic amplification of probabilities via the factorisation $ρ=ρ_{\rm sqrt}^\daggerρ_{\rm sqrt}$, analogous to the recently introduced sum-of-squares spectral amplification (SOSSA), which we use here to amplify the separation between dominant and subdominant components. Thresholding then yields the dominant-eigenstate projector. Compared with conventional phase estimation, DEFEAT improves the dependence on the overlap with the initial state while requiring substantially fewer ancillary qubits. We prove that the query complexity of the filtering step is optimal up to logarithmic factors and establish a complementary lower bound for eigenstate preparation under purified query access to $ρ$. We validate in numerical simulations that the convergence rate of DEFEAT matches our theoretical results. Our results provide a general eigenvalue-agnostic primitive for dominant eigenstate filtering and preparation, and for estimating properties of dominant eigenstates.

Comments
18+29 pages, 11 figures

Related papers

Filtered Spectral Projection for Quantum Principal Component Analysis

Sk Mujaffar Hossain, Satadeep Bhattacharjee

Quantum principal component analysis (qPCA) is commonly formulated as the extraction of eigenvalues and eigenvectors of a covariance-encoded density operator. Yet in many qPCA settings the practical goal is simpler: projection onto the dominant spectral subspace. Here we introduce a projection-first framework, the Filtered Spectral Projection Algorithm (FSPA), which bypasses explicit eigenvalue estimation while preserving the relevant spectral structure. FSPA amplifies any nonzero warm-start overlap with the leading subspace and remains robust in small-gap and near-degenerate regimes, without artificial symmetry breaking in the absence of bias. We show that FSPA achieves an oracle complexity $\mathcal{O}((\log(1/ε)+\log(1/|a_1|^2))/\log(λ_1/λ_2))$,which is tight by a matching lower bound, establishing it as an\emph{optimal} projection primitive. We derive a convergence rate for degenerate spectra, give a circuit resource analysis with $n+\mathcal{O}(1)$ qubit overhead independent of system dimension, and extend the method to threshold spectral projection, Threshold-FSPA, which converges in $\mathcal{O}(\log(1/ε))$ calls when the threshold lies between eigenvalues. In the density matrix exponentiation access model, FSPA gives an exponential copy-complexity advantage over classical methods. For classical datasets, we show that for amplitude-encoded centered data the ensemble density matrix $ρ=\sum_i p_i|ψ_i\rangle\langleψ_i|$ equals the covariance matrix. Numerical tests on chemistry density matrices, noisy circuit outputs, Breast Cancer Wisconsin, handwritten Digits, and 1--4-qubit scalability confirm the theory. A minimal Qiskit implementation validates magnitude invariance, signal amplification, and no spurious symmetry breaking. These results establish FSPA as an optimal and deployable quantum spectral projection primitive.

arXiv:2603.13441•Mar 13, 2026•0 citations

Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems

Lin, L, Tong, Y

We present a quantum eigenstate filtering algorithm based on quantum signal processing (QSP) and minimax polynomials. The algorithm allows us to efficiently prepare a target eigenstate of a given Hamiltonian, if we have access to an initial state with non-trivial overlap with the target eigenstate and have a reasonable lower bound for the spectral gap. We apply this algorithm to the quantum linear system problem (QLSP), and present two algorithms based on quantum adiabatic computing (AQC) and quantum Zeno effect respectively. Both algorithms prepare the final solution as a pure state, and achieves the near optimal Oe(dκlog(1/∊)) query complexity for a d-sparse matrix, where κ is the condition number, and ∊ is the desired precision. Neither algorithm uses phase estimation or amplitude amplification.

•Nov 11, 2020•75 citations

Near-Optimal Ground-State Preparation without Controlled Hamiltonian Evolutions

Dhrumil Patel, Steven T. Flammia, Raul Garcia-Patron

Ground-state preparation, energy estimation, and property estimation are fundamental tasks in quantum simulation. Existing ground-state preparation algorithms achieve near-optimal complexity using block encodings or controlled Hamiltonian evolution, raising a natural question: is controlled Hamiltonian evolution necessary, or can the same scaling be attained in the weaker access model that provides access to only uncontrolled Hamiltonian evolution? We resolve this question by giving two algorithms that access the input Hamiltonian $H$ only through queries to $U_H$ and its inverse $U_H^\dagger$, where $\|H\|\leα_H$ and $τ=Θ(1/α_H)$. Given an input state with ground-state weight at least $η$ and a spectral gap of $H$ of at least $γ$, our first algorithm uses fresh copies of the input state and requires $\widetilde O(α_H/(γη))$ queries to $U_H$ and $U_H^\dagger$, while our second algorithm uses coherent access to the input-state preparation unitary and its inverse to improve this complexity to $\widetilde O(α_H/(γ\sqrtη))$. The latter bound matches the known lower bound up to logarithmic factors, showing that algorithms with additional access to controlled Hamiltonian evolution cannot improve the query complexity for ground-state preparation beyond logarithmic factors. Both algorithms are based on a simple mechanism that we call the spectral descent principle, in which the algorithm starts from the input state $|ψ\rangle$ and progressively descends through the energy spectrum, moving closer to the ground state until the desired fidelity is reached. We also extend this framework to ground-state property and energy estimation and give explicit complexity guarantees for both tasks.

quant-pharXiv:2610.00520•Oct 2, 2026•0 citations

Solving quantum linear system problem with near-optimal complexity.

Lin Lin, Yu Tong

We present a quantum eigenstate filtering algorithm based on quantum signal processing (QSP) and minimax polynomials. The algorithm allows us to efficiently prepare a target eigenstate of a given Hamiltonian, if we have access to an initial state with non-trivial overlap with the target eigenstate and have a reasonable lower bound for the spectral gap. We apply this algorithm to the quantum linear system problem (QLSP), and present two algorithms based on quantum adiabatic computing (AQC) and quantum Zeno effect respectively. Both algorithms prepare the final solution as a pure state, and achieves the near optimal $\mathcal{\widetilde{O}}(d\kappa\log(1/\epsilon))$ query complexity for a $d$-sparse matrix, where $\kappa$ is the condition number, and $\epsilon$ is the desired precision. Neither algorithm uses phase estimation or amplitude amplification.

•Oct 31, 2019•4 citations

Optimal Query Complexity for Ground-State Preparation

Boyang Chen, Minbo Gao, Xinzhao Wang +1 more

We determine the optimal query complexity of ground-state preparation to trace-distance error $\varepsilon$ when an energy threshold in the spectral gap is known. Let $U_H$ be an $α$-block-encoding of a Hamiltonian with unique ground state $|ψ_0\rangle$, and suppose $|\langleψ_0|U_I|0\rangle|\geγ$ for a state-preparation oracle $U_I$. The threshold lies at least $Δ/2$ above the ground-state energy and at least $Δ/2$ below every excited-state energy. We give two algorithms that prepare a state within trace distance $\varepsilon$ of the ground state. One uses $O((α/Δ)(γ^{-1}+\log(1/\varepsilon)))$ calls to $U_H$ in expectation; the other uses $O((α/(γΔ))\log(1/\varepsilon))$ calls to $U_H$ in the worst case. We prove a lower bound matching the expected query count; the corresponding worst-case lower bound follows from Somma and de Wolf [SdW26]. The respective bounds on calls to $U_I$ are $O(1/γ)$ in expectation and $O(γ^{-1}\log(1/\varepsilon))$ in the worst case. On $(N+1)$-dimensional systems, these $U_I$ bounds are also optimal when the expected or worst-case count of $U_H$ calls, respectively, is $o((α/Δ)\sqrt N)$. Both algorithms use a constant-accuracy spectral filter to construct a purifier, which we then sequentially compose during amplitude amplification to prepare a state with constant overlap with the ground state. The expected-query algorithm repeats the preparation followed by one high-accuracy spectral filter until success. The worst-case algorithm uses filters of increasing accuracy and limits the total number of queries.

quant-pharXiv:2609.35668•Sep 29, 2026•0 citations

Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems

Lin Lin, Yu Tong

We present a quantum eigenstate filtering algorithm based on quantum signal processing (QSP) and minimax polynomials. The algorithm allows us to efficiently prepare a target eigenstate of a given Hamiltonian, if we have access to an initial state with non-trivial overlap with the target eigenstate and have a reasonable lower bound for the spectral gap. We apply this algorithm to the quantum linear system problem (QLSP), and present two algorithms based on quantum adiabatic computing (AQC) and quantum Zeno effect respectively. Both algorithms prepare the final solution as a pure state, and achieves the near optimal O ~ ( d κ log ⁡ ( 1 / ϵ ) ) query complexity for a d -sparse matrix, where κ is the condition number, and ϵ is the desired precision. Neither algorithm uses phase estimation or amplitude amplification.

arXiv:1910.14596•Quantum•Nov 11, 2020•106 citations
Quantum simulation is expected to be a main application of quantum computers with realistic utility in quantum chemistry, materials science and beyond. However, preparing excited or general eigenstates is a central challenge, particularly when the desired eigenvalue is not known in advance, or when the overlap with the initial state is insufficient. We introduce the Dominant Eigenstate Filtering via Eigenprobability Amplification and Thresholding (DEFEAT) algorithm that identifies and filters the eigenstate with the largest overlap with the supplied initial state. Our key observation is that we do not need prior knowledge of the target eigenvalue, as we construct efficient twirling superoperators that map initial states to eigenprobability density operators ρρρ, diagonal in the Hamiltonian eigenbasis and encoding its spectral weights, alongside its block-encoding implementation. Our crucial innovation is the quadratic amplification of probabilities via the factorisation ρ=ρsqrt†ρsqrtρ=ρ_{\rm sqrt}^\daggerρ_{\rm sqrt}ρ=ρsqrt†​ρsqrt​, analogous to the recently introduced sum-of-squares spectral amplification (SOSSA), which we use here to amplify the separation between dominant and subdominant components. Thresholding then yields the dominant-eigenstate projector. Compared with conventional phase estimation, DEFEAT improves the dependence on the overlap with the initial state while requiring substantially fewer ancillary qubits. We prove that the query complexity of the filtering step is optimal up to logarithmic factors and establish a complementary lower bound for eigenstate preparation under purified query access to ρρρ. We validate in numerical simulations that the convergence rate of DEFEAT matches our theoretical results. Our results provide a general eigenvalue-agnostic primitive for dominant eigenstate filtering and preparation, and for estimating properties of dominant eigenstates.
Quantum principal component analysis (qPCA) is commonly formulated as the extraction of eigenvalues and eigenvectors of a covariance-encoded density operator. Yet in many qPCA settings the practical goal is simpler: projection onto the dominant spectral subspace. Here we introduce a projection-first framework, the Filtered Spectral Projection Algorithm (FSPA), which bypasses explicit eigenvalue estimation while preserving the relevant spectral structure. FSPA amplifies any nonzero warm-start overlap with the leading subspace and remains robust in small-gap and near-degenerate regimes, without artificial symmetry breaking in the absence of bias. We show that FSPA achieves an oracle complexity O((log⁡(1/ε)+log⁡(1/∣a1∣2))/log⁡(λ1/λ2))\mathcal{O}((\log(1/ε)+\log(1/|a_1|^2))/\log(λ_1/λ_2))O((log(1/ε)+log(1/∣a1​∣2))/log(λ1​/λ2​)),which is tight by a matching lower bound, establishing it as an\emph{optimal} projection primitive. We derive a convergence rate for degenerate spectra, give a circuit resource analysis with n+O(1)n+\mathcal{O}(1)n+O(1) qubit overhead independent of system dimension, and extend the method to threshold spectral projection, Threshold-FSPA, which converges in O(log⁡(1/ε))\mathcal{O}(\log(1/ε))O(log(1/ε)) calls when the threshold lies between eigenvalues. In the density matrix exponentiation access model, FSPA gives an exponential copy-complexity advantage over classical methods. For classical datasets, we show that for amplitude-encoded centered data the ensemble density matrix ρ=∑ipi∣ψi⟩⟨ψi∣ρ=\sum_i p_i|ψ_i\rangle\langleψ_i|ρ=∑i​pi​∣ψi​⟩⟨ψi​∣ equals the covariance matrix. Numerical tests on chemistry density matrices, noisy circuit outputs, Breast Cancer Wisconsin, handwritten Digits, and 1--4-qubit scalability confirm the theory. A minimal Qiskit implementation validates magnitude invariance, signal amplification, and no spurious symmetry breaking. These results establish FSPA as an optimal and deployable quantum spectral projection primitive.
We present a quantum eigenstate filtering algorithm based on quantum signal processing (QSP) and minimax polynomials. The algorithm allows us to efficiently prepare a target eigenstate of a given Hamiltonian, if we have access to an initial state with non-trivial overlap with the target eigenstate and have a reasonable lower bound for the spectral gap. We apply this algorithm to the quantum linear system problem (QLSP), and present two algorithms based on quantum adiabatic computing (AQC) and quantum Zeno effect respectively. Both algorithms prepare the final solution as a pure state, and achieves the near optimal Oe(dκlog(1/∊)) query complexity for a d-sparse matrix, where κ is the condition number, and ∊ is the desired precision. Neither algorithm uses phase estimation or amplitude amplification.
Ground-state preparation, energy estimation, and property estimation are fundamental tasks in quantum simulation. Existing ground-state preparation algorithms achieve near-optimal complexity using block encodings or controlled Hamiltonian evolution, raising a natural question: is controlled Hamiltonian evolution necessary, or can the same scaling be attained in the weaker access model that provides access to only uncontrolled Hamiltonian evolution? We resolve this question by giving two algorithms that access the input Hamiltonian HHH only through queries to UHU_HUH​ and its inverse UH†U_H^\daggerUH†​, where ∥H∥≤αH\|H\|\leα_H∥H∥≤αH​ and τ=Θ(1/αH)τ=Θ(1/α_H)τ=Θ(1/αH​). Given an input state with ground-state weight at least ηηη and a spectral gap of HHH of at least γγγ, our first algorithm uses fresh copies of the input state and requires O~(αH/(γη))\widetilde O(α_H/(γη))O(αH​/(γη)) queries to UHU_HUH​ and UH†U_H^\daggerUH†​, while our second algorithm uses coherent access to the input-state preparation unitary and its inverse to improve this complexity to O~(αH/(γη))\widetilde O(α_H/(γ\sqrtη))O(αH​/(γη​)). The latter bound matches the known lower bound up to logarithmic factors, showing that algorithms with additional access to controlled Hamiltonian evolution cannot improve the query complexity for ground-state preparation beyond logarithmic factors. Both algorithms are based on a simple mechanism that we call the spectral descent principle, in which the algorithm starts from the input state ∣ψ⟩|ψ\rangle∣ψ⟩ and progressively descends through the energy spectrum, moving closer to the ground state until the desired fidelity is reached. We also extend this framework to ground-state property and energy estimation and give explicit complexity guarantees for both tasks.
We present a quantum eigenstate filtering algorithm based on quantum signal processing (QSP) and minimax polynomials. The algorithm allows us to efficiently prepare a target eigenstate of a given Hamiltonian, if we have access to an initial state with non-trivial overlap with the target eigenstate and have a reasonable lower bound for the spectral gap. We apply this algorithm to the quantum linear system problem (QLSP), and present two algorithms based on quantum adiabatic computing (AQC) and quantum Zeno effect respectively. Both algorithms prepare the final solution as a pure state, and achieves the near optimal O~(dκlog⁡(1/ϵ))\mathcal{\widetilde{O}}(d\kappa\log(1/\epsilon))O(dκlog(1/ϵ)) query complexity for a ddd-sparse matrix, where κ\kappaκ is the condition number, and ϵ\epsilonϵ is the desired precision. Neither algorithm uses phase estimation or amplitude amplification.
We determine the optimal query complexity of ground-state preparation to trace-distance error ε\varepsilonε when an energy threshold in the spectral gap is known. Let UHU_HUH​ be an ααα-block-encoding of a Hamiltonian with unique ground state ∣ψ0⟩|ψ_0\rangle∣ψ0​⟩, and suppose ∣⟨ψ0∣UI∣0⟩∣≥γ|\langleψ_0|U_I|0\rangle|\geγ∣⟨ψ0​∣UI​∣0⟩∣≥γ for a state-preparation oracle UIU_IUI​. The threshold lies at least Δ/2Δ/2Δ/2 above the ground-state energy and at least Δ/2Δ/2Δ/2 below every excited-state energy. We give two algorithms that prepare a state within trace distance ε\varepsilonε of the ground state. One uses O((α/Δ)(γ−1+log⁡(1/ε)))O((α/Δ)(γ^{-1}+\log(1/\varepsilon)))O((α/Δ)(γ−1+log(1/ε))) calls to UHU_HUH​ in expectation; the other uses O((α/(γΔ))log⁡(1/ε))O((α/(γΔ))\log(1/\varepsilon))O((α/(γΔ))log(1/ε)) calls to UHU_HUH​ in the worst case. We prove a lower bound matching the expected query count; the corresponding worst-case lower bound follows from Somma and de Wolf [SdW26]. The respective bounds on calls to UIU_IUI​ are O(1/γ)O(1/γ)O(1/γ) in expectation and O(γ−1log⁡(1/ε))O(γ^{-1}\log(1/\varepsilon))O(γ−1log(1/ε)) in the worst case. On (N+1)(N+1)(N+1)-dimensional systems, these UIU_IUI​ bounds are also optimal when the expected or worst-case count of UHU_HUH​ calls, respectively, is o((α/Δ)N)o((α/Δ)\sqrt N)o((α/Δ)N​). Both algorithms use a constant-accuracy spectral filter to construct a purifier, which we then sequentially compose during amplitude amplification to prepare a state with constant overlap with the ground state. The expected-query algorithm repeats the preparation followed by one high-accuracy spectral filter until success. The worst-case algorithm uses filters of increasing accuracy and limits the total number of queries.
We present a quantum eigenstate filtering algorithm based on quantum signal processing (QSP) and minimax polynomials. The algorithm allows us to efficiently prepare a target eigenstate of a given Hamiltonian, if we have access to an initial state with non-trivial overlap with the target eigenstate and have a reasonable lower bound for the spectral gap. We apply this algorithm to the quantum linear system problem (QLSP), and present two algorithms based on quantum adiabatic computing (AQC) and quantum Zeno effect respectively. Both algorithms prepare the final solution as a pure state, and achieves the near optimal O ~ ( d κ log ⁡ ( 1 / ϵ ) ) query complexity for a d -sparse matrix, where κ is the condition number, and ϵ is the desired precision. Neither algorithm uses phase estimation or amplitude amplification.