Quantum linear system algorithm with optimal queries to initial state preparation

Quantum Linear System Algorithm with Optimal Queries to Initial State Preparation

Overview

This paper presents a new quantum linear system algorithm with improved query complexity, particularly for the initial state preparation. The key contributions are:

• A quantum linear system algorithm that makes $\Theta(1/\sqrt{p})$ queries to the initial state oracle and $O(\kappa \log(1/\sqrt{p})(\log \log(1/\sqrt{p})+\log(1/\epsilon)))$ queries to the coefficient matrix oracle. This is optimal for the initial state preparation and nearly optimal for the coefficient matrix.
• Applications of this algorithm to improve the initial state preparation cost in solving differential equations, estimating eigenvalues of non-normal matrices, and preparing ground states of non-Hermitian operators.
• A new "Tunable Variable Time Amplitude Amplification" (Tunable VTAA) algorithm that fully characterizes generic nested amplitude amplifications and achieves an improved $\ell_2/3$-quasinorm scaling.
• A block preconditioning technique that can artificially boost the success probability, leading to further reductions in initial state preparation cost.

Problem & Context

The quantum linear system problem is one of the most promising sources of exponential quantum speedups. It underlies many other quantum algorithms for differential equations, eigenvalue processing, and more. The goal is to produce a state proportional to the solution $A^{-1}|b\rangle$ of a linear system, given oracular access to the coefficient matrix $A$ and the initial state $|b\rangle$.

Previous quantum linear system algorithms have focused on improving the overall query complexity, measured by the combined cost of querying both the $OA$ and $Ob$ oracles. However, the cost of initial state preparation can be significantly higher than that of the coefficient matrix in many applications, motivating the need for a more refined analysis.

Methodology

The key technical contributions are:

1. Tunable Variable Time Amplitude Amplification (Tunable VTAA): A generalized VTAA framework that fully characterizes generic nested amplitude amplifications. It eliminates redundant nestings and achieves an improved $\ell_2/3$-quasinorm scaling in the cost of input algorithms.
2. Discretized Inverse State: A new state representation for the quantum linear system problem, where the reciprocal of eigenvalues are replaced by discrete values. This allows a substantially simplified VTAA with an optimal initial state preparation cost.
3. Block Preconditioning: A technique that can artificially boost the success probability of the quantum linear system solver, further reducing the cost of initial state preparation in various applications.

Results

1. Optimal Quantum Linear System Solver: The authors develop a quantum linear system algorithm with:
   • $\Theta(1/\sqrt{p})$ queries to the initial state oracle, which is proven to be optimal.
   • $O(\kappa \log(1/\sqrt{p})(\log \log(1/\sqrt{p})+\log(1/\epsilon)))$ queries to the coefficient matrix oracle, which is nearly optimal.
2. Applications:
   • Solving differential equations: The initial state preparation cost is reduced to $O(\max_{0 \leq \tau \leq t} e^{\tau A}/e^{tA}|b\rangle)$, nearly matching the lower bound.
   • Estimating eigenvalues of non-normal matrices: The initial state preparation cost is reduced to $O(\kappaS \log(n)/p(A/\alphaA)|ψ\rangle)$, outperforming previous results.
   • Preparing ground states of non-Hermitian operators: The initial state preparation cost is reduced to $O(\kappaS/|\gamma0|\log(\alphaA/\deltaA\log(\kappaS/|\gamma0|\epsilon)))$.
3. Block-Encoded Eigenvalue Transformer: The authors also apply block preconditioning to improve the cost of block-encoding the transformed matrix, reducing it from $O(n^{1.5})$ to $O(n)$ in the degree of the target polynomial.

Interpretation

• The new quantum linear system algorithm achieves the optimal scaling for initial state preparation, contrasting with previous results that were suboptimal in this regard.
• The applications demonstrate that the improved initial state preparation can lead to significant performance gains in a variety of problems beyond just linear system solving.
• The Tunable VTAA framework and block preconditioning technique are general tools that may find further applications in the design of quantum algorithms.

Limitations & Uncertainties

• The algorithm assumes the availability of a constant multiplicative approximation of the solution norm. Relaxing this assumption may introduce additional overhead.
• The applications rely on specific properties of the problem instances (e.g., sparsity, spectral gaps) that may not hold in general.
• The block preconditioning technique may not be applicable in all scenarios, as it requires identifying a suitable preconditioner.

What Comes Next

• Exploring applications of the Tunable VTAA and block preconditioning techniques to other quantum algorithms beyond linear systems.
• Investigating the practicality and implementation challenges of the proposed algorithms, especially in the context of near-term quantum hardware.
• Developing techniques to relax the assumptions on known solution norms and spectral properties, towards more generally applicable quantum algorithms.