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

Optimal quantum eigenstate filtering with application to solving quantum linear systems

Lin Lin, Yu Tong

Published Oct 31, 2019• 5 citations
OpenAlex

Related papers

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•159 citations

Quantum Filtering for Linear Dynamical Quantum Systems

Hendra I. Nurdin, Naoki Yamamoto

Communications and control engineering/Communications and control engineering series•Jan 1, 2017•1 citation

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

Robust and optimal quantum control for some classes of linear quantum systems

pAline I Maaloufp

Journal of Astrophysics & Aerospace Technology•May 21, 2018•0 citations

A shortcut to an optimal quantum linear system solver

Alexander M. Dalzell

Given a linear system of equations $A\boldsymbol{x}=\boldsymbol{b}$, quantum linear system solvers (QLSSs) approximately prepare a quantum state $|\boldsymbol{x}\rangle$ for which the amplitudes are proportional to the solution vector $\boldsymbol{x}$. Asymptotically optimal QLSSs have query complexity $O(κ\log(1/\varepsilon))$, where $κ$ is the condition number of $A$, and $\varepsilon$ is the approximation error. However, runtime guarantees for existing optimal and near-optimal QLSSs do not have favorable constant prefactors, in part because they rely on complex or difficult-to-analyze techniques like variable-time amplitude amplification and adiabatic path-following. Here, we give a conceptually simple QLSS that does not use these techniques. If the solution norm $\lVert\boldsymbol{x}\rVert$ is known exactly, our QLSS requires only a single application of kernel reflection (a straightforward extension of the eigenstate filtering (EF) technique of previous work) and the query complexity of the QLSS is $(1+O(\varepsilon))κ\ln(2\sqrt{2}/\varepsilon)$. If the norm is unknown, our method allows it to be estimated up to a constant factor using $O(\log\log(κ))$ applications of kernel projection (a direct generalization of EF) yielding a straightforward QLSS with near-optimal $O(κ\log\log(κ)\log\log\log(κ)+κ\log(1/\varepsilon))$ total complexity. Alternatively, by reintroducing a concept from the adiabatic path-following technique, we show that $O(κ)$ complexity can be achieved for norm estimation, yielding an optimal QLSS with $O(κ\log(1/\varepsilon))$ complexity while still avoiding the need to invoke the adiabatic theorem. Finally, we compute an explicit upper bound of $56κ+1.05κ\ln(1/\varepsilon)+o(κ)$ for the complexity of our optimal QLSS.

arXiv:2406.12086•Jun 17, 2024•69 citations

Quantum algorithm for linear systems

Yunah Choi, Jeihee Cho, Shiho Kim

Advances in computers•Nov 29, 2025•0 citations
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.
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.
Given a linear system of equations Ax=bA\boldsymbol{x}=\boldsymbol{b}Ax=b, quantum linear system solvers (QLSSs) approximately prepare a quantum state ∣x⟩|\boldsymbol{x}\rangle∣x⟩ for which the amplitudes are proportional to the solution vector x\boldsymbol{x}x. Asymptotically optimal QLSSs have query complexity O(κlog⁡(1/ε))O(κ\log(1/\varepsilon))O(κlog(1/ε)), where κκκ is the condition number of AAA, and ε\varepsilonε is the approximation error. However, runtime guarantees for existing optimal and near-optimal QLSSs do not have favorable constant prefactors, in part because they rely on complex or difficult-to-analyze techniques like variable-time amplitude amplification and adiabatic path-following. Here, we give a conceptually simple QLSS that does not use these techniques. If the solution norm ∥x∥\lVert\boldsymbol{x}\rVert∥x∥ is known exactly, our QLSS requires only a single application of kernel reflection (a straightforward extension of the eigenstate filtering (EF) technique of previous work) and the query complexity of the QLSS is (1+O(ε))κln⁡(22/ε)(1+O(\varepsilon))κ\ln(2\sqrt{2}/\varepsilon)(1+O(ε))κln(22​/ε). If the norm is unknown, our method allows it to be estimated up to a constant factor using O(log⁡log⁡(κ))O(\log\log(κ))O(loglog(κ)) applications of kernel projection (a direct generalization of EF) yielding a straightforward QLSS with near-optimal O(κlog⁡log⁡(κ)log⁡log⁡log⁡(κ)+κlog⁡(1/ε))O(κ\log\log(κ)\log\log\log(κ)+κ\log(1/\varepsilon))O(κloglog(κ)logloglog(κ)+κlog(1/ε)) total complexity. Alternatively, by reintroducing a concept from the adiabatic path-following technique, we show that O(κ)O(κ)O(κ) complexity can be achieved for norm estimation, yielding an optimal QLSS with O(κlog⁡(1/ε))O(κ\log(1/\varepsilon))O(κlog(1/ε)) complexity while still avoiding the need to invoke the adiabatic theorem. Finally, we compute an explicit upper bound of 56κ+1.05κln⁡(1/ε)+o(κ)56κ+1.05κ\ln(1/\varepsilon)+o(κ)56κ+1.05κln(1/ε)+o(κ) for the complexity of our optimal QLSS.