Quantum linear system algorithm with optimal queries to initial state preparation

1. Problem Statement

The Quantum Linear System Problem (QLSP) aims to prepare a quantum state proportional to the solution $A^{-1}|b\rangle$ of a linear system $Ax=b$, given:

• An oracle $O_A$ that block-encodes the coefficient matrix $A$.
• An oracle $O_b$ that prepares the initial state $|b\rangle$.

The performance of QLSP algorithms is measured by their query complexity to these oracles, typically expressed in terms of:

• $\kappa$: The condition number of the system ($\kappa = \|A\|\|A^{-1}\|$).
• $\epsilon$: The desired accuracy.
• $p$: The success probability (or $1/\sqrt{p} = \|A^{-1}\|/\|A^{-1}|b\rangle\|$), representing the inverse of the solution amplitude.

The Gap: While recent algorithms have achieved optimal or near-optimal scaling with respect to $\kappa$ and $\epsilon$ (e.g., $O(\kappa \log(1/\epsilon))$), they often suffer from suboptimal scaling regarding the initial state preparation oracle $O_b$. Many state-of-the-art methods treat $O_A$ and $O_b$ symmetrically, resulting in a query complexity to $O_b$ that scales with $\kappa$ (or $\kappa \log \kappa$). However, in many practical applications (differential equations, ground state preparation), the solution norm $\|A^{-1}|b\rangle\|$ is much larger than the worst-case bound $\|A^{-1}\|$, meaning $1/\sqrt{p} \ll \kappa$. Existing algorithms fail to exploit this, leading to unnecessary overhead in preparing the initial state.

2. Methodology and Key Contributions

The authors propose a new framework to achieve optimal query complexity for $O_b$ (scaling strictly as $\Theta(1/\sqrt{p})$) while maintaining near-optimal complexity for $O_A$. This is achieved through three main technical innovations:

A. Tunable Variable Time Amplitude Amplification (Tunable VTAA)

The paper introduces a generalized version of Ambainis' Variable Time Amplitude Amplification (VTAA).

• Mechanism: Instead of fixed thresholds, Tunable VTAA uses tunable amplification thresholds ($\alpha_j$) at each stage of a nested amplification process.
• Optimization: By optimizing these thresholds, the algorithm minimizes the total query cost. The authors prove that the complexity scales with the $\ell_{2/3}$-quasinorm of the input costs, which is strictly better than the $\ell_1$ or $\ell_2$ norms used in previous VTAA analyses.
• Deterministic Schedule: Crucially, for the specific structure of the QLSP, the authors derive a deterministic amplification schedule (a fixed sequence of amplification steps, e.g., repeating 3 steps) that does not require prior knowledge of the success probability or expensive amplitude estimation during compilation. This eliminates the polylogarithmic overhead associated with estimating thresholds.

B. Discretized Inverse State

To leverage Tunable VTAA effectively, the authors construct a specific intermediate state called the discretized inverse state.

• Construction: Instead of directly inverting eigenvalues, the algorithm uses Gapped Phase Estimation (GPE) combined with Branch Marking.
  • Branch Marking: A technique to handle the two branches of eigenphases ($\pm \theta$) in the quantum walk operator, ensuring they undergo identical processing so they can be coherently merged later.
  • Discretization: Eigenvalues are partitioned into intervals based on powers of 3 (base-3 partitioning). The inverse is approximated by discrete values within these intervals.
• Benefit: This structure allows the "clock" register to track the amplification stages. Because the cost of GPE grows exponentially with the stage number, the algorithm pre-merges early, low-cost stages. The deterministic schedule ensures that the number of non-trivial amplification stages is logarithmic in $1/\sqrt{p}$, leading to the optimal $O(1/\sqrt{p})$ scaling for $O_b$.

C. Block Preconditioning

The authors introduce a technique to artificially boost the success probability $p$ (i.e., increase $\|A^{-1}|b\rangle\|$) without changing the solution state.

• Technique: They define a scaling operator $S$ that acts on a subspace containing the initial state (e.g., the ancilla space or the state $|b\rangle$ itself). By solving the preconditioned system $(SA)x = Sb$, the solution norm is boosted by a factor $1/s$.
• Impact: This reduces the effective $1/\sqrt{p}$ to a constant or a much smaller value in specific applications.
• Simplification: By choosing $|b\rangle$ itself as the preconditioner, they derive an extremely simple QLSP algorithm with optimal $O(\kappa \log(1/\epsilon))$ queries to both $O_A$ and $O_b$. This is conceptually simpler than previous optimal methods based on kernel reflection or discrete adiabatic evolution.

3. Main Results

The paper presents several theorems with improved complexity bounds:

1. Optimal Initial State Preparation (Theorem 2):

   • Queries to $O_b$: $\Theta(1/\sqrt{p})$. This is proven to be optimal via a reduction to Grover search.
   • Queries to $O_A$: $O(\kappa \log(1/\sqrt{p}) \log(\log(1/\sqrt{p})/\epsilon))$.
   • Significance: This is the first algorithm to achieve optimal scaling for $O_b$ without polylogarithmic overhead, even when $p$ is unknown (using a solution norm estimation subroutine).

2. Block Preconditioning for Optimal Coefficient Encoding (Theorem 4):

   • By preconditioning with $|b\rangle$, the algorithm achieves $O(\kappa \log(1/\epsilon))$ queries to both $O_A$ and $O_b$.
   • This matches the theoretical lower bound for $O_A$ and improves the $O_b$ scaling from $O(\kappa \dots)$ to $O(\kappa \dots)$ but with a much smaller constant factor and simpler structure.

3. Applications with Improved Scaling:

   • Differential Equations (Theorem 5): Reduces initial state preparation cost from $O(\kappa \dots)$ to $O(\text{evolution time} \dots)$, nearly matching the lower bound.
   • Eigenvalue Estimation (Theorem 6): Improves initial state cost for non-normal matrices, outperforming previous linear-system-based estimators.
   • Eigenvalue Transformation (Theorem 9): Achieves $O(n)$ scaling in the degree of the target polynomial for block-encoded eigenvalue transformers, improving upon the previous best $O(n^{1.5})$.
   • Ground State Preparation (Theorem 8): Reduces the cost of preparing ground states for non-Hermitian operators.

4. Significance and Impact

• Breaking the Symmetry: The work fundamentally decouples the cost of preparing the initial state from the condition number $\kappa$. It proves that one does not need to pay a $\kappa$ penalty for state preparation if the solution norm is large.
• Universality of Tunable VTAA: The introduction of Tunable VTAA provides a general framework for optimizing nested amplitude amplification, showing that $\ell_{2/3}$-quasinorm scaling is achievable, which is a theoretical improvement over standard $\ell_1$ or $\ell_2$ bounds.
• Practicality: The deterministic schedule removes the need for complex, overhead-heavy amplitude estimation during the compilation of the algorithm, making the approach more feasible for near-term and fault-tolerant implementations.
• Simplification: The block preconditioning technique offers a conceptually simpler alternative to kernel reflection and adiabatic methods for achieving optimal query complexity, potentially lowering the barrier to implementing these algorithms in real-world quantum chemistry and physics simulations.

In summary, this paper resolves a long-standing inefficiency in quantum linear system solvers by optimizing the interaction between the initial state oracle and the matrix oracle, providing both theoretical optimality and practical simplifications for a wide range of quantum algorithms.