PaperlayerView exact revision on arXiv

Source-linked AI summary

Variational Quantum Linear Solver

Carlos Bravo-Prieto, Ryan LaRose, M. Cerezo, Yigit Subasi, Lukasz Cincio, Patrick J. Coles

arXiv:1909.05820v4quant-ph

TL;DR

Existing quantum linear-system algorithms are difficult to implement on near-term hardware because of their circuit-depth requirements. The paper introduces VQLS, a hybrid variational method with cost-based precision certification and efficient cost-estimation circuits. For the considered examples, VQLS was implemented up to 1024 × 1024 and showed favorable heuristic scaling, while finite-sampling effects remain unresolved.

  • Problem

    Previously proposed quantum linear-system algorithms require circuit depths that prevent near-term implementation on noisy quantum computers.

  • Method

    VQLS variationally prepares |x⟩ by optimizing a cost function measuring the closeness of A|x⟩ to |b⟩, with quantum circuits estimating the cost.

  • Results

    VQLS was implemented on Rigetti’s hardware for a 1024 × 1024 system, while considered examples showed at-worst linear scaling in κ, logarithmic scaling in 1/ε, and polylogarithmic scaling in N.

  • Takeaways & Limitations

    VQLS provides a near-term variational approach to the quantum linear-systems problem for the specific systems and simulations studied.

  • Takeaways & Limitations

    Finite-sampling effects remain unaccounted for in the training heuristics, and solution verification may require shot counts scaling as (κ/ε)^4.

Abstract

from arXiv · show

Previously proposed quantum algorithms for solving linear systems of equations cannot be implemented in the near term due to the required circuit depth. Here, we propose a hybrid quantum-classical algorithm, called Variational Quantum Linear Solver (VQLS), for solving linear systems on near-term quantum computers. VQLS seeks to variationally prepare $|x\rangle$ such that $A|x\rangle\propto|b\rangle$. We derive an operationally meaningful termination condition for VQLS that allows one to guarantee that a desired solution precision $ε$ is achieved. Specifically, we prove that $C \geq ε^2 / κ^2$, where $C$ is the VQLS cost function and $κ$ is the condition number of $A$. We present efficient quantum circuits to estimate $C$, while providing evidence for the classical hardness of its estimation. Using Rigetti's quantum computer, we successfully implement VQLS up to a problem size of $1024\times1024$. Finally, we numerically solve non-trivial problems of size up to $2^{50}\times2^{50}$. For the specific examples that we consider, we heuristically find that the time complexity of VQLS scales efficiently in $ε$, $κ$, and the system size $N$.

1 Introduction

Quantum linear-system algorithms promise favorable scaling but require hardware beyond the near term. VQLS addresses this gap with a hybrid variational approach designed for noisy quantum computers, supported by analytical guarantees, efficient scaling evidence, and a 1024 × 1024 hardware implementation.

  • Motivation: Quantum linear-system algorithms such as HHL offer logarithmic scaling in system size but depend on large-scale fault-tolerant quantum computers.HHL and later improvements provide favorable scaling in N, condition number κ, precision ε, and sparsity under stated assumptions.
  • Motivation: Variational hybrid quantum-classical algorithms reduce quantum circuit depth by shifting part of the computation to classical cost-function optimization.These methods use short-depth circuits and established classical optimizers, making them relevant to noisy intermediate-scale quantum devices.
  • VQLS approach: VQLS solves the quantum linear-systems problem by optimizing a cost function that measures global or local closeness between A|x⟩ and the normalized state |b⟩.The algorithm prepares the solution state variationally using a hybrid optimization loop.
  • VQLS approach: The VQLS cost functions have operational meaning as upper bounds on ε^2/κ^2, yielding a termination criterion that guarantees a desired solution precision ε.Efficient quantum circuits estimate the costs, while the paper argues that their estimation is difficult classically.
  • Evidence: At worst, numerical simulations indicate runtime scaling that is linear in κ, logarithmic in 1/ε, and polylogarithmic in N for the considered examples.The authors emphasize that these variational algorithms are heuristic, so rigorous complexity analysis remains difficult.
  • Evidence: 1024 × 1024: VQLS was successfully implemented on Rigetti’s quantum hardware for a particular linear system.The authors present this implementation as evidence that VQLS could provide a near-term approach to the quantum linear-systems problem.

2 Results

VQLS combines operationally certified cost functions, efficient quantum estimation, and variational ansätze to solve QLSPs on near-term hardware. Numerical studies indicate efficient heuristic scaling, while local costs improve trainability for larger systems and the cost estimates are classically hard.

  • Trainability: Local costs remain trainable through 50 qubits, whereas global-cost optimization becomes increasingly difficult as system size grows.For the studied QLSP, local-cost training reached systems of size 250 × 250.
  • Operational cost meaning: bCG and CG provide termination bounds linking the VQLS cost to the target precision ε and condition number κ.The paper derives bCG ≥ ε^2/κ^2 and CG ≥ bCG.
  • Cost evaluation: The Hadamard-Overlap Test estimates off-diagonal cost terms without controlling V, A_l, or U†, at the expense of doubling the qubit count.Diagonal γ_ll terms are estimated from all-zeros probabilities after applying U†A_lV.
  • Classical hardness: Estimating bCG, CG, bCL, or CL to precision ±δ = 1/poly(n) is DQC1-hard, suggesting these costs lack efficient classical simulation.The classical intractability claim relies on standard complexity assumptions concerning DQC1.
  • Ansatz: The fixed-structure hardware-efficient ansatz uses native single-qubit rotations and controlled-Z gates, with a gate structure suitable for hardware implementations.Its trainability can still become problematic for large-scale problems.
  • Noise resilience: VQLS cost functions are resilient to global depolarizing noise, and CL is also resilient to measurement noise under the analyzed models.More complicated noise models remain unanalyzed.
  • Noise resilience: Probabilistic Error Cancellation can certify termination conditions after training with polynomial overhead, allowing retraining or restart if verification fails.This verification overhead is not required during the training phase.
  • Heuristic scaling: For specific Ising-inspired and random sparse QLSPs, time-to-solution appears sub-linear in κ, logarithmic in 1/ε, and logarithmic or polylogarithmic in N.The random-matrix study additionally reports an apparent multiplicative dependence on κ and log(1/ε), while the observed κ behavior is example-specific.

3 Discussion

VQLS combines variational quantum-classical optimization with analytical certification, numerical scaling evidence, and a Rigetti implementation, while retaining sampling-related limitations.

  • VQLS scales at worst linearly in κ, logarithmically in 1/ε, and polylogarithmically in N for the considered examples.
  • The reported scaling results are heuristic, and finite-sampling effects on training remain unaccounted for.
  • A 1024 × 1024 linear system was successfully solved on Rigetti’s quantum hardware.
  • The hardware cost function fell below 10^-1 in each QPU run, but noise prevented it from reaching zero.
  • VQLS trades the gate complexity of non-variational algorithms for additional iterations of the variational loop as κ increases.
  • The paper identifies quantitative certification, trainability strategies, efficient cost-evaluation circuits, scaling heuristics, and hardware implementations as distinguishing aspects.

A Sparse Matrices

The sparse-matrix construction represents A as a short linear combination of unitaries using oracle-based operations, but its precision cost restricts applicability to matrices with d much smaller than N.

  • A d-sparse N-dimensional matrix is expressed through unitaries Ux, Uy, and S using a Szegedy-walk construction.
  • The first two registers use n qubits each, while the final two registers use one qubit each; the third register stores matrix elements temporarily.
  • The construction decomposes A into four unitaries with equal weights of d/4.
  • The oracle OA provides the nonzero column indices and matrix elements needed to implement the sparse-matrix operations.
  • Each unitary uses six queries to OA, while the controlled phase operations have gate complexity O(log N) = O(n).
  • Because the decomposition carries a prefactor proportional to d, the approach is restricted to sparse matrices where d ≪ N for a fixed cost precision.

B Faithfulness of the cost functions

The four VQLS cost functions are mutually bounded and faithful: they are nonnegative and vanish exactly when the prepared state solves the quantum linear systems problem.

  • The projector ordering ΠG ≥ ΠL implies the corresponding cost ordering bCG ≥ bCL and CG ≥ CL.
  • The global and local cost functions satisfy CG ≥ CL and nCL ≥ CG.
  • All four cost functions are nonnegative and vanish when A|x⟩ = |b⟩.
  • Conversely, if A|x⟩ ≠ |b⟩, then CG > 0 and all four cost functions are positive.
  • Assuming A has finite condition number, all four costs vanish precisely when |ψ⟩ ∝ |b⟩, corresponding to a QLSP solution.

C Cost evaluation circuits

VQLS uses short-depth Hadamard-based circuits to estimate its cost-function coefficients, including a Hadamard-Overlap Test that avoids controlling the main unitaries.

  • Short-depth circuits are presented for computing the VQLS cost functions, including the Hadamard-Overlap Test.
  • The Hadamard Test estimates the real and imaginary parts of β_ll′ through ancilla measurement probabilities and an optional phase gate.
  • The same circuits can estimate δ^(j)_ll′, with an additional random unitary Rj generating the required input state.
  • The Hadamard-Overlap Test computes γ_ll′ using one application each of U and V without controlling either unitary.
  • The Hadamard-Overlap Test uses 2n + 1 qubits and classical post-processing that scales linearly with n.
  • Bell-basis measurements with classical post-processing provide the expectation value of the SWAP operator used in the overlap calculation.

D Proof of Proposition 1

Proposition 1 establishes that estimating all four VQLS cost functions to inverse-polynomial precision is DQC1-hard. The proof reduces global costs to Hilbert–Schmidt overlap estimation and local costs to approximating the trace of a unitary.

  • DQC1-hardness applies to estimating bCG, CG, bCL, and CL within precision ±δ = 1/poly(n).
  • The global-cost proof reduces Hilbert–Schmidt inner-product magnitude estimation between two n-qubit circuits to a VQLS instance with A = 1.
  • For the local costs, a controlled-W construction encodes the real part of Tr W in the measurement probability of the first qubit.
  • Adding a phase gate on the first qubit allows the same circuit family to compute the imaginary part of Tr W.
  • Choosing U and V according to Eq. (50) makes local-cost estimation equivalent to approximating the real or imaginary part of Tr W, yielding DQC1-hardness.

E Variable ansatz optimization

The variable-structure ansatz alternates parameter optimization with circuit-layout growth. Gate insertions can improve expressivity and lower the cost, but unnecessary insertions may prevent successful minimization.

  • The optimization uses a variable-structure ansatz whose gate placement and gate types can change during optimization.
  • The inner loop fixes the gate structure and optimizes angles, while the outer loop changes the layout after a local minimum is reached.
  • The outer loop grows the circuit by inserting parametrized gates, then alternates with inner-loop optimization until termination.
  • Gate insertions may fail to increase expressivity or allow cost minimization, so accepting insertions only when they lower the cost avoids unnecessary circuit growth.

F Gradient-based optimization

The paper derives analytical VQLS cost gradients and shows they can be evaluated with the same Hadamard-based circuits used for cost estimation. This supports gradient-descent optimization while analyzing resilience to selected noise models.

  • Analytical gradients of the VQLS cost functions can be computed using the same circuits introduced for cost estimation.
  • Each trainable gate is parameterized by a single-qubit rotation, enabling derivatives of the ansatz unitary with respect to its angles.
  • Gradients of β_ll′ and γ_ll′ are obtained with the Hadamard-Overlap test and Hadamard test, respectively.
  • The local-cost gradients bCL and CL can also be computed with the circuits from Section C.
  • The normalized costs CG and CL are shown to be resilient to global depolarizing noise and measurement noise, while more complicated noise models remain unanalyzed.
  • Optimal Parameter Resilience preserves the cost-function minimizer, allowing noisy optimization to recover parameters for the correct solution state before error mitigation.

G.1 Global Cost

The noise analysis models depolarizing effects through layer-dependent attenuation of estimated quantities and shows that the noisy local cost remains faithful under stated assumptions. Its minimum is attained exactly when the QLSP condition is satisfied, provided the ansatz can express the solution.

  • Global depolarizing noise: Global depolarizing noise transforms a state as ρ → qρ + (1−q)1/d, producing q^L attenuation after L noisy circuit layers.
  • Global depolarizing noise: Assuming equal noise effects on real and imaginary components, estimated β_ll′ and γ_ll′ acquire attenuation factors determined by their circuit depths.
  • Faithfulness of the local cost: The noisy local-cost analysis defines a normalized state |χ̂⟩ = |χ⟩/√μ and bounds the cost using the largest eigenvalue of the relevant noisy reduced state.
  • Faithfulness of the local cost: The lower bound is achievable when |x⟩ solves the QLSP, because A|x⟩ ∝ |b⟩ implies |χ̂⟩ = |0⟩ and reaches the noisy minimum.
  • Faithfulness of the local cost: Reaching the noisy minimum conversely forces every reduced qubit state of |χ̂⟩ to be |0⟩⟨0|, hence |χ̂⟩ = |0⟩ and A|x⟩ ∝ |b⟩.
  • Faithfulness of the local cost: Thus the noisy local cost is faithful and exhibits Optimal Parameter Resilience under global depolarizing noise when the ansatz can express the true solution.
  • Measurement noise: Symmetric measurement noise can be modeled as local depolarizing noise, or as global depolarizing noise when only one qubit is measured.

A Supplementary Note 1 – Additional Implementations

Supplementary simulations of 8×8 systems find efficient condition-number scaling across matrices with different minimum-eigenvalue degeneracies and across all four cost functions.

  • Additional numerical simulations: 1000 VQLS runs were averaged for each data point while training bCG, CG, bCL, and CL.The certification procedure used the operational meanings of the cost functions to upper-bound ε.
  • Additional numerical simulations: Efficient κ scaling holds for the three 8×8 problems regardless of minimum-eigenvalue degeneracy g.The cases use g = 1, 2, and 4 to test whether degeneracy affects VQLS performance.
  • Additional numerical simulations: All four cost functions perform similarly for A3, while unnormalized costs perform slightly better for A1 and A2.The comparison covers both normalized and unnormalized cost-function variants.

A.2 Implementation with QAOA Ansatz

The QAOA implementation addresses worsening conditioning by increasing circuit depth or scaling selected driver-evolution parameters, which can improve optimization landscapes and yields sub-exponential κ scaling in the tested example.

  • QAOA scaling: For fixed ε, poorly conditioned matrices generally require more QAOA layers, but longer driver-Hamiltonian evolution can alleviate this requirement.The longer evolution is implemented by scaling odd-indexed parameters with a value that grows with κ.
  • QAOA scaling: Sub-exponential κ scaling was observed for each of three tested ε values as κ varied from 100 to 10^3.The experiment used 100 random initializations for a three-qubit QLSP based on matrix A2.

A.3 Implementations on Rigetti’s quantum computer

Supplementary implementations extend VQLS to Rigetti hardware and problem sizes up to 32×32, while additional simulations and observable comparisons assess cost reduction, solution quality, and optimization behavior.

  • Additional simulations: Supplementary time-to-solution experiments average 1000 VQLS instances while comparing bCG, CG, bCL, and CL across matrices A1, A2, and A3.The figure reports time-to-solution against κ for the three specified matrices.
  • Rigetti implementations: The local cost function CL reached ∼7 × 10^-2 in every hardware run, but device noise prevented further reduction.This cost produced only a trivial ε bound, although observable measurements indicated a high-quality solution.
  • Rigetti implementations: Cost values were ≲0.1 for every tested linear system except the 2×2 case with A = 1 + 0.25Z and |b⟩ = X|0⟩.For that case, relaxation toward |0⟩ likely degraded the result because the exact solution is |1⟩.
Loading 1909.05820v4…