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

2019/10/31 by Lin Lin, Yu Tong · 2 citations
Computer Science · Mathematics · Physics and Astronomy · #Eigenvalues and eigenvectors #Polynomial #Quantum #Quantum Computing Algorithms and Architecture #Quantum Fourier transform #Quantum Information and Cryptography #Quantum algorithm #Quantum algorithm for linear systems of equations #Quantum computer #Quantum error correction #Quantum phase estimation algorithm #Spectroscopy and Quantum Chemical Studies #cs.NA #math.NA #quant-ph

paper · pdf · doi:10.22331/q-2020-11-11-361

published as Quantum 4, 361 (2020)

arxiv created 2020/11/08 · openalex publication_date 2020/11/11 · arxiv updated 2020/11/12 · openalex created_date 2020/11/23 · openalex updated_date 2026/08/05

Abstract

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<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mover><mml:mi class="MJX-tex-caligraphic" mathvariant="script">O</mml:mi><mml:mo class="MJX-tex-caligraphic" mathvariant="script">~</mml:mo></mml:mover></mml:mrow></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mi>d</mml:mi><mml:mi>κ</mml:mi><mml:mi>log</mml:mi><mml:mo>⁡</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mn>1</mml:mn><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mi>ϵ</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo stretchy="false">)</mml:mo></mml:math>query complexity for a<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>d</mml:mi></mml:math>-sparse matrix, where<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>κ</mml:mi></mml:math>is the condition number, and<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>ϵ</mml:mi></mml:math>is the desired precision. Neither algorithm uses phase estimation or amplitude amplification.

Citations

• Speedup via quantum sampling
• Quantum Simulations of Classical Annealing Processes
• A fast quantum mechanical algorithm for database search
• Bounds for the adiabatic approximation with applications to quantum computation
• Quantum search by measurement
• Quantum Algorithm for Systems of Linear Equations with Exponentially Improved Dependence on Precision
• A quantum-inspired classical algorithm for recommendation systems

Cited by

• Quantum phase discrimination with applications to quantum search on graphs
• Robust Iterative Method for Symmetric Quantum Signal Processing in All Parameter Regimes