PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm

Dong An, Lin Lin

arXiv:1909.05500v3quant-phmath.NA

TL;DR

The paper addresses how to solve QLSP with near-optimal dependence on condition number and target accuracy without relying on complicated VTAA. It uses gap-aware rescheduled AQC and connects the resulting complexity to QAOA, whose numerical runtime is often lowest among the compared methods, subject to optimization and measurement costs.

  • Problem

    QLSP solvers seek better dependence on κ and ε, while VTAA-based near-optimal methods can be complicated to implement.

  • Method

    The paper introduces gap-aware rescheduled AQC methods AQC(p) and AQC(exp), and uses their connection with AQC to motivate an optimally controlled QAOA approach.

  • Results

    AQC(exp) has runtime O(κ poly(log(κ/ε))), and numerical results rank QAOA at or below AQC(exp), AQC(p), randomization, and vanilla AQC when its optimizer is found.

  • Takeaways & Limitations

    Rescheduling makes AQC near-optimal in κ and ε, while QAOA can achieve the same asymptotic runtime bound and the lowest observed runtime.

  • Takeaways & Limitations

    QAOA's runtime advantage depends on finding its optimizer, while classical angle optimization and accurate objective estimation can require substantial cost.

Abstract

from arXiv · show

We demonstrate that with an optimally tuned scheduling function, adiabatic quantum computing (AQC) can readily solve a quantum linear system problem (QLSP) with $\mathcal{O}(κ~\text{poly}(\log(κ/ε)))$ runtime, where $κ$ is the condition number, and $ε$ is the target accuracy. This is near optimal with respect to both $κ$ and $ε$. Our method is applicable to general non-Hermitian matrices, and the cost as well as the number of qubits can be reduced when restricted to Hermitian matrices, and further to Hermitian positive definite matrices. The success of the time-optimal AQC implies that the quantum approximate optimization algorithm (QAOA) with an optimal control protocol can also achieve the same complexity in terms of the runtime. Numerical results indicate that QAOA can yield the lowest runtime compared to the time-optimal AQC, vanilla AQC, and the recently proposed randomization method.

1 INTRODUCTION

QLSP seeks efficient quantum preparation of a normalized solution state, but prior methods face unfavorable condition-number, accuracy, or implementation costs. The paper proposes rescheduled AQC methods that approach optimal scaling and extends the result to QAOA.

  • 1 INTRODUCTION: QLSP prepares the normalized state A^-1|b⟩/||A^-1|b⟩||2, while HHL and later LCU/QSP approaches motivate reducing dependence on κ and ε.The cited prior scalings include HHL's O(poly(n)κ^2/ε) and later O(κ^2 poly(log(κ/ε))) bounds.
  • 1 INTRODUCTION: VTAA reaches near-optimal κ and ε scaling but is complicated to implement, motivating alternative QLSP solvers.The paper positions rescheduled AQC as such an alternative.
  • 1 INTRODUCTION: The proposed rescheduled AQC family closes the gap between AQC and randomization, giving AQC(p) runtime O(κ/ε) and AQC(exp) runtime O(κ poly(log(κ/ε))).AQC(p) applies for 1 < p < 2, while AQC(exp) does not require an upper bound on κ.
  • 1 INTRODUCTION: AQC(exp) achieves near-optimal query scaling in both κ and ε while avoiding the complex VTAA routine.Its query complexity is O(dκ poly log(dκ/ε)).
  • 1 INTRODUCTION: QAOA inherits an O(κ poly(log(κ/ε))) runtime bound from the connection between QAOA and AQC.Both QAOA and AQC prepare approximate QLSP solutions in pure states and can be implemented on gate-based computers.

2 QUANTUM LINEAR SYSTEM PROBLEM AND VANILLA AQC

The paper reformulates QLSP as preparing a zero-energy eigenstate along an adiabatic path. Vanilla AQC follows this path with a runtime bound that is unfavorable in both condition number and accuracy.

  • 2 QUANTUM LINEAR SYSTEM PROBLEM AND VANILLA AQC: For Hermitian positive definite A, the construction assumes ||A||2=1 and uses one ancilla qubit to form a 2N-dimensional Hamiltonian.The general QLSP target is a normalized ε-approximation to A^-1|b⟩.
  • 2 QUANTUM LINEAR SYSTEM PROBLEM AND VANILLA AQC: QLSP is solved by preparing the zero-energy state |e_x⟩ of a constructed Hamiltonian H1, whose spectral gap is bounded below by 1/κ.The construction starts from H0 and H1 and uses an ancillary qubit to enlarge the matrix block.
  • 2 QUANTUM LINEAR SYSTEM PROBLEM AND VANILLA AQC: The adiabatic path interpolates between H0 and H1 through a strictly increasing scheduling function f(s), with f(s)=s defining vanilla AQC.The state |b̄⟩ remains in the null space throughout the interpolation.
  • 2 QUANTUM LINEAR SYSTEM PROBLEM AND VANILLA AQC: The adiabatic theorem keeps the evolving state near the desired eigenspace because orthogonality prevents transitions into the other zero-energy eigenstate.The invariant overlap with |b̄⟩ reduces the projector estimate to the desired path state |e_x(s)⟩.
  • 2 QUANTUM LINEAR SYSTEM PROBLEM AND VANILLA AQC: Vanilla AQC requires runtime T ≳ κ^3/ε under bounded derivative norms and the worst-case gap Δ ≥ κ^-1.This follows from the adiabatic error estimate used in the section.

3 AQC(P) METHOD

AQC(p) slows the schedule near the smallest spectral gap, reducing the runtime dependence on the condition number. For 1 < p < 2, it attains linear κ scaling, while endpoint choices retain a logarithmic factor.

  • 3 AQC(P) METHOD: The schedule is designed to slow the Hamiltonian evolution when the gap approaches zero, improving accuracy without changing the adiabatic path.The schedule depends on the gap and is normalized so that f(1)=1.
  • 3 AQC(P) METHOD: As s approaches 1, the gap approaches κ^-1 and the AQC(p) dynamics correspondingly slows near the endpoint.This gap-aware schedule is the defining design choice of AQC(p).
  • 3 AQC(P) METHOD: AQC(p) removes the log(κ) dependence achieved by randomization when 1 < p < 2, reaching optimal κ scaling.The scheduling function, rather than the quantum Zeno or Monte Carlo mechanism itself, is identified as responsible for the favorable scaling.

4 AQC(EXP) METHOD

AQC(exp) uses a boundary-flat scheduling function to exploit exponentially small final-time adiabatic error, improving accuracy dependence while retaining near-linear condition-number scaling. Its universal schedule does not require prior knowledge of κ, but accurate schedule implementation is important.

  • AQC(exp) method: The AQC(exp) schedule makes the final-time error exponentially small in runtime under the stated smoothness assumptions.The general bound has the form c1 exp(−c2 T^α) for positive constants.
  • AQC(exp) motivation: T=O(κ^3 poly(log(κ/ε))) suffices for exponential accuracy dependence, but this intermediate bound restores cubic condition-number dependence.The bound follows from Δ*≥κ^-1.
  • AQC(exp) motivation: AQC(exp) slows Hamiltonian variation near the smallest gap by requiring all schedule derivatives to vanish at the path boundaries.For QLSP, the gap decreases monotonically and is smallest at the final time.
  • AQC(exp) results: AQC(exp) achieves an exponential ε-speedup over RM and AQC(p), while its universal schedule avoids requiring a bound on κ.The comparison reintroduces logarithmic κ dependence but favors AQC(exp) for high-fidelity preparation.
  • Practical caveat: AQC(exp) performance is sensitive to scheduling-function perturbations, requiring accurate classical computation and quantum control.The paper compares this sensitivity with finite-precision effects in adiabatic Grover search.

5 GATE-BASED IMPLEMENTATION OF AQC

The gate-based implementation realizes AQC through time-dependent Hamiltonian simulation, using either Trotter splitting or truncated Dyson expansion. The resulting costs are nearly linear in κ, although straightforward Trotterization can make gate complexity superlinear.

  • Hamiltonian simulation: Time evolution requires efficient simulation of the time-dependent Hamiltonian H(f(s)); truncated Dyson expansion provides a direct implementation without splitting.The implementation assumes query models for the matrix A and input state preparation.
  • Trotter implementation: Trotter splitting approximates the evolution with error O(poly(log(N))T^2/M), so ε-accuracy requires M=O(poly(log(N))T^2/ε) time slices.The step size is h=s/M.
  • Trotter implementation: O(κ^2) time slices are required in the stated scaling, causing Trotter-based gate complexity to grow superlinearly with κ.The paper notes that higher-order Trotter-Suzuki methods could improve this scaling but does not pursue them.
  • Implementation limits: Higher-order Trotter-Suzuki formulas and commutator-based error analysis are identified as possible improvements but are left for future work.
  • Computational costs: Both AQC(p) and AQC(exp) achieve almost linear dependence on κ, and AQC(exp) additionally provides an exponential ε-speedup.These costs are summarized for truncated-Dyson time-dependent Hamiltonian simulation.

6 QAOA FOR SOLVING QLSP

The paper formulates QAOA for QLSP by optimizing alternating Hamiltonian-evolution angles, connecting the ansatz to discretized AQC. With sufficiently many layers and optimal parameters, QAOA inherits near-linear condition-number scaling, while optimization and measurement costs remain important caveats.

  • 6 QAOA FOR SOLVING QLSP: QAOA uses a parameterized alternating-evolution state, initialized as |e_b⟩, with angles optimized classically to approximate the QLSP target.Each layer applies time-independent evolutions under H0 and H1, which can be implemented through block-encodings and quantum singular value transformation.
  • 6 QAOA FOR SOLVING QLSP: With sufficiently large P and optimal angles, QAOA achieves runtime at most O(κpoly(log(κ/ε))); numerical results suggest the same scaling with much smaller P.The bound relies on the optimal Trotter splitting method being a special QAOA case and on sufficiently accurate parameter optimization.
  • 6 QAOA FOR SOLVING QLSP: The QAOA objective can be minimized without knowing the exact solution, while the initial state and invariant state structure prevent transition into the unwanted null-space state.The variational objective uses the expectation value of H1-related operators, and the ansatz preserves zero overlap with |b̄⟩.
  • 6 QAOA FOR SOLVING QLSP: The Trotter splitting method is a special QAOA ansatz, so optimized QAOA can match or outperform discretized AQC with the best scheduling function.QAOA also uses only 2P time-independent Hamiltonian simulations once its parameters are known.
  • 6 QAOA FOR SOLVING QLSP: Classical angle optimization may become trapped at local optima, require many iterations, and diminish runtime gains; estimating the objective may require O(κ^4/ε^4) measurements.The optimization cost is difficult to know in advance, and the objective must be measured to precision O(ε^2/κ^2).

7 GENERALIZATION TO NON-HERMITIAN MATRICES

The AQC construction extends from Hermitian positive definite systems to indefinite Hermitian and general non-Hermitian matrices by enlarging the Hilbert space. The same scheduling families retain O(κ/ε) runtime for 1 < p < 2, with additional ancilla and dimension costs.

  • 7 GENERALIZATION TO NON-HERMITIAN MATRICES: For indefinite Hermitian matrices, the method enlarges the Hilbert space to dimension 4N, requiring two ancilla qubits to handle the altered Hamiltonian construction.The resulting Hamiltonians have a two-dimensional zero-energy subspace containing the desired solution state and an invariant auxiliary state.
  • 7 GENERALIZATION TO NON-HERMITIAN MATRICES: The same schedules apply because the generalized Hamiltonian gap remains proportional to the Hermitian positive definite case.The lower-bound gap is defined from the condition number and supports reuse of the AQC(p) and AQC(exp) schedules.
  • 7 GENERALIZATION TO NON-HERMITIAN MATRICES: For any 1 < p < 2, AQC(p) prepares an ε-approximation for indefinite Hermitian systems with runtime T = O(κ/ε).At p = 1 or 2, the bound becomes T = O(κlog(κ)/ε).
  • 7 GENERALIZATION TO NON-HERMITIAN MATRICES: The numerical-scaling table reports runtime dependence on condition number and accuracy for the Hermitian positive definite example.Its scope is limited to the Hermitian positive definite numerical example.
  • 7 GENERALIZATION TO NON-HERMITIAN MATRICES: A general square matrix is embedded into a Hermitian problem of dimension 2N, producing a total Hilbert-space dimension of 8N and requiring three ancilla qubits.The extended Hermitian matrix preserves the condition number, and its solution state encodes the original solution.

8 NUMERICAL RESULTS

Numerical experiments compare rescheduled AQC variants, QAOA, RM, and vanilla AQC on Hermitian positive definite and non-Hermitian systems. QAOA achieves the lowest overall runtime, while AQC(exp) and QAOA show polylogarithmic accuracy dependence and the methods generalize to non-Hermitian matrices.

  • Hermitian positive definite example: The Hermitian positive definite experiments measure runtime versus condition number at fidelities 0.99 and 0.999, and versus accuracy at κ = 10.The corresponding results are shown in Figure 1.
  • Hermitian positive definite example: QAOA has the smallest runtime overall for the Hermitian positive definite example, with runtime approximately linear in κ.The comparison includes AQC(p), AQC(exp), RM, and vanilla AQC.
  • Hermitian positive definite example: QAOA's accuracy scaling is O(log^1.5(1/ε)), whereas AQC(exp) depends polylogarithmically on ε and AQC(p) and RM scale as O(1/ε).AQC(exp) eventually outperforms AQC(p) when ε is sufficiently small, while QAOA has the smallest preconstant.
  • Non-Hermitian example: For non-Hermitian matrices, QAOA again achieves optimal runtime performance, while optimal AQC(p) scales as O(κ/ε) and QAOA and AQC(exp) scale as O(κpoly(log(κ/ε))).These results are reported from Figure 2 and Table 3.

9 DISCUSSION

The discussion concludes that rescheduling AQC improves QLSP complexity from the unfavorable vanilla-AQC scaling, with AQC(exp) achieving near-linear condition-number and polylogarithmic precision dependence. The connection between AQC and QAOA extends this complexity bound to QAOA, whose numerical runtime can be especially small.

  • 9 DISCUSSION: AQC(exp) achieves O(κpoly(log(κ/ε))) complexity, providing near-linear spectral-gap dependence and polylogarithmic precision dependence.The discussion identifies this as the first adiabatic example with both properties simultaneously.
  • 9 DISCUSSION: For relatively large ε, AQC(p) has O(κ/ε) runtime, while AQC(exp) is more advantageous for highly accurate calculations with small ε.The two schedules therefore favor different accuracy regimes.
  • 9 DISCUSSION: QAOA inherits an O(κpoly(log(κ/ε))) runtime bound from its close connection with AQC and can be implemented on gate-based quantum computers.The numerical ordering is QAOA ≲ AQC(exp) ≲ AQC(p) < RM < vanilla AQC, subject to optimizer and accuracy qualifications.
  • 9 DISCUSSION: The accuracy analysis relates density-matrix error and fidelity through the desired eigenpath and the projector onto the zero-eigenvalue eigenspace.The fidelity is bounded below by 1 − η^2(s), while the density-matrix 2-norm error is bounded above by η(s).

C DIFFERENCE BETWEEN THE SCALINGS OF AQC(P) AND RM WITH RESPECT TO INFIDELITY

AQC(p) and RM have the same O(1/ε) scaling in density-matrix error, but their fidelity dependence differs. Because AQC's infidelity equals the square of its 2-norm error, AQC(p) requires less runtime than RM for a desired fidelity in the reported analysis.

  • C DIFFERENCE BETWEEN THE SCALINGS OF AQC(P) AND RM WITH RESPECT TO INFIDELITY: AQC(p) requires T = O(κ/(1 − F)) to reach infidelity 1 − F, whereas RM requires eO(κ/(1 − F)).The difference explains the larger RM pre-constant observed numerically at the same desired fidelity.
  • C DIFFERENCE BETWEEN THE SCALINGS OF AQC(P) AND RM WITH RESPECT TO INFIDELITY: Although AQC(p) and RM both scale linearly with density-matrix error ε, AQC(p) can be much faster when the target is specified by fidelity.The observed advantage follows from the different conversion between error and infidelity.
  • C DIFFERENCE BETWEEN THE SCALINGS OF AQC(P) AND RM WITH RESPECT TO INFIDELITY: For AQC(p) and AQC(exp), infidelity is exactly the square of the density-matrix 2-norm error, while RM has a different scaling relation.This relation is verified numerically at κ = 10.

D PROOF OF THEOREM 1 AND THEOREM 3

The proofs of Theorem 1 and Theorem 3 analyze the error bound by tracking Hamiltonian derivatives and a lower bound on the spectral gap under a change of variables. For 1 < p < 2, the leading error term is O(κ/T).

  • D PROOF OF THEOREM 1 AND THEOREM 3: The analysis changes variables to compute the remaining terms of η(s) after isolating a positive constant independent of s, Δ, and T.The limiting cases p = 1 and p = 2 are treated separately after the 1 < p < 2 analysis.
  • D PROOF OF THEOREM 1 AND THEOREM 3: For 1 < p < 2, the leading term of the error bound is O(κ/T).The proof analyzes the κ-dependence of the terms in η(s).

E PROOF OF THEOREM 2 AND THEOREM 4

The proof develops explicit derivative and resolvent bounds for the AQC(exp) scheme, establishing its adiabatic error bound and the runtime sufficient for an ε-approximation to QLSP.

  • AQC(exp) error bound: Theorem 6 bounds the final-time adiabatic error of AQC(exp) under the condition κ > e.The bound is stated for the overlap of the evolved state with the zero-eigenspace projector at the final time.
  • Runtime consequence: For κ > e and 0 < ε < 1, Corollary 7 gives a runtime sufficient to prepare an ε-approximation of the QLSP solution using AQC(exp).The corollary states the required runtime asymptotically in its conclusion.
  • Truncated expansion: The construction uses truncated series and establishes matching boundary values for the truncated and full projector expansions.The proof then relates these boundary properties to the adiabatic error.
  • Technical setup: The proof uses a Hamiltonian path with endpoint derivatives vanishing and a spectral gap bounded below along the path.These properties support the derivative estimates used in the adiabatic analysis.
  • Resolvent estimates: Bounding resolvent derivatives provides the main improvement over the general adiabatic bound.The resolvent estimate is used as a key intermediate step in controlling the derivatives entering the error analysis.
Loading 1909.05500v3…