Source-linked AI summary
Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations
Andris Ambainis
TL;DR
Large linear systems pose a challenge because reading the full coefficient matrix can take time proportional to its size. This paper generalizes amplitude amplification to algorithms whose branches stop at different times, then applies it to quantum linear-system solving. The resulting algorithm improves the HHL running-time dependence from O(κ² log N) to O(κ log^3 κ log N), with κ dependence almost optimal under the stated complexity condition.
Problem
Accessing all or most entries of an N-by-N matrix can require Ω(N²) time, while the HHL algorithm’s running time for linear systems scales as O(κ² log N).
Source: §1 · p. 1Method
The paper generalizes amplitude amplification to handle computation branches that stop at different times and applies it to a quantum algorithm for linear systems.
Source: §1 · p. 1, §2.1 · p. 2, §2.2 · p. 3Results
O(κ log^3 κ log N) replaces the HHL running time O(κ² log N), and the κ dependence is almost optimal unless BQP = PSPACE.
Source: §1 · pp. 1–2Takeaways & Limitations
The variable-time amplification method is presented as a tool expected to be useful in building other quantum algorithms.
Source: §1 · p. 2The linear-systems result assumes eigenvalues lie in [1/κ, 1] for a known κ.
Source: §2.2 · p. 3
Abstract
from arXiv · showhide
We present two new quantum algorithms. Our first algorithm is a generalization of amplitude amplification to the case when parts of the quantum algorithm that is being amplified stop at different times. Our second algorithm uses the first algorithm to improve the running time of Harrow et al. algorithm for solving systems of linear equations from O(kappa^2 log N) to O(kappa log^3 kappa log N) where \kappa is the condition number of the system of equations.
1 Introduction
Linear systems are common in scientific computing, but accessing a large coefficient matrix can appear to require time proportional to its size. The paper introduces variable-time amplitude amplification and uses it to improve the condition-number dependence of a quantum linear-systems algorithm.
1 Introduction
- Accessing all or most entries of an N-by-N coefficient matrix can require Ω(N²) time, motivating quantum approaches to large systems.Source: §1 · p. 1
- The Harrow-Hassidim-Lloyd algorithm outputs a quantum state encoding the solution vector, rather than the solution as a conventional list [5].The passage notes applications of that algorithm to quantum algorithms for differential equations [7, 3].Source: §1 · p. 1
- The HHL algorithm’s running time depends on both N and κ; its κ dependence is worse than the stated classical dependence for sparse matrices [5, 8].The passages give O(κ² log N) for HHL and O(√(κN)) for the best classical sparse-matrix algorithm.Source: §1 · p. 1
- O(κ log^3 κ log N) is the paper’s improved running time for its quantum linear-systems algorithm.The method uses variable-time amplitude amplification, which can exploit computation branches that stop earlier.Source: §1 · pp. 1–2
- Ω(κ^{1−o(1)}) time is necessary to generate the solution state |x⟩ unless BQP = PSPACE, making the paper’s κ dependence almost optimal.The lower bound is attributed to Harrow et al. [5].Source: §1 · p. 2
2 Overview of main results
The overview presents variable-time amplitude amplification for algorithms with branches that stop at different times, then applies it to linear systems. The application adapts eigenvalue-estimation precision by branch and yields the paper’s improved running-time result.
2.1 Variable time amplitude amplification
- The theorem amplifies success for an algorithm whose branches stop at different times, with the target outcome distinguished from failure and unfinished computation.The output register uses 1 for the desired outcome, 0 for a stopped failure, and 2 for a branch still running.Source: §2.1 · p. 2
- The variable-time amplification result is useful when the average stopping time is substantially below the maximum stopping time.The passages contrast this with conventional amplification, which waits for all branches to stop, and state that the method is optimal up to a log Tmax factor.Source: §2.1 · p. 2
2.2 Systems of linear equations
- The linear-systems application assumes eigenvalues lie between 1/κ and 1, for known κ, and targets a similar running time across the general eigenvalue range.When eigenvalues have similar magnitudes, the overview says the running time becomes O(κ/ǫ); the general case is the stated challenge.Source: §2.2 · p. 3
- Eigenvalue estimation runs initially for O(1) steps, then doubles its runtime and precision until the estimate’s error meets the allowed relative error.Larger-eigenvalue branches can terminate earlier; applying variable-time amplification to this procedure gives the linear-systems result.Source: §2.2 · pp. 3–4
- The theorem gives a procedure for generating an approximation to the target state, with error at most ǫ, under a stated Hamiltonian-simulation cost condition.The overview identifies this as the result obtained by applying variable-time amplification to the adaptive eigenvalue-estimation algorithm.Source: §2.2 · p. 4
3 Variable-time amplitude amplification
This section formalizes algorithms with branches that stop at different times, presents tools used in the amplification analysis, and constructs a staged state-generation algorithm. Its construction continues computation only on unfinished branches and amplifies the final state.
3.1 Model
- The model separates stopped and unfinished branches in an outcome register and requires a branch’s stopped state to remain unchanged afterward.It defines success probability, stopping probabilities, an l2-average stopping time, and the maximum stopping time Tmax.Source: §3.1 · pp. 4–5
- The goal in the model is to amplify success to Ω(1) while accounting for both average and maximum stopping times.Source: §3.1 · p. 5
3.2 Tools
- The tools section defines successful state production through an output register whose measurement identifies the branch containing the desired state.It also invokes tighter analysis of amplitude amplification and a version of amplitude estimation.Source: §3.2 · p. 5
- The cited tighter amplification analysis increases success probability by nearly the square of the number of calls, avoiding a constant-factor penalty that compounds in nested amplification.The comparison is with the usual amplitude-amplification analysis.Source: §3.2 · p. 5
3.3 The state generation algorithm
- The state-generation algorithm builds successive stages for stopping times t_i = 2^i, using earlier stages to continue only the parts whose outcome register marks them unfinished.It defines an auxiliary B_i from the preceding A_i stage, then uses amplification and probability estimation as needed.Source: §3.3 · p. 6
- The final stage amplifies its output to constant success probability, while the analysis bounds its runtime using Tmax and the l2-average stopping time.The passage states that the runtime bound uses terms involving the stopping-time probabilities and that each relevant term is at most Tav.Source: §3.3 · pp. 6, 8
4 Faster algorithm for solving systems of linear equations
This section develops a linear-system solver using variable-time amplitude amplification and analyzes its output quality and running time, including stopping behavior through invariant-subspace analysis.
4.1 Unique-answer eigenvalue estimation
- A random shift H+δπ/2^n makes the eigenvalue estimate unique for all but a small random fraction of eigenvalues.Repeated standard eigenvalue estimation and majority voting are used to obtain the estimate with probability at least 1−ε.Source: §4.1 · pp. 8–9
4.2 Main algorithm
- Algorithm 5 applies variable-time amplitude amplification to Algorithm 4; its Fourier measurement yields |0⟩S with probability 1/m, adding an O(√m) runtime factor for constant success.Algorithm 5 maps the stage labels and Fourier-transforms S, outputting the state in I only when the measurement result is 0.Source: §4.2 · pp. 9–10
4.3 Proofs of Lemmas about the quality of output state
- Random thresholds make each eigenvector bad with probability O(ε), while Algorithm 4 reaches its critical estimation stage with probability at least 1−2(m−1)ε.The analysis sets the subroutine error to ε=Θ(εfinal/m) to target overall error at most εfinal.Source: §4.2 · p. 11, §4.3 · p. 14
4.4 Proofs of Lemmas about the running time of Algorithm 4
- After the critical stage ji, the probability of continuing k additional stages is bounded by ε^(k−1), giving a geometrically decaying tail in the running-time analysis.The analysis defines pstop,j as the probability of stopping after stage j and uses these stage probabilities to bound the l2-average running time.Source: §4.4 · p. 16
- The running-time proof treats each |vi⟩⊗HA⊗HS⊗HE subspace independently because it remains invariant, then takes a square root to finish.The preceding passage refers to the square of the l2-average number of steps, but its bound is incomplete in the supplied text.Source: §4.4 · p. 16
- The probability of stopping before stage ji is at most 2(ji − 1)ε ≤ 2(m − 1)ε, so stopping at stage ji or ji + 1 has at least constant probability.The proof considers each |vi⟩⊗HA⊗HS⊗HE subspace separately.Source: §4.4 · p. 16