PaperlayerView exact revision on arXiv

Source-linked AI summary

Near-term quantum algorithms for linear systems of equations

Hsin-Yuan Huang, Kishor Bharti, Patrick Rebentrost

arXiv:1909.07344v2quant-phmath.NA

TL;DR

The paper addresses how to solve linear systems on near-term quantum hardware when existing approaches require unavailable resources and can encounter optimization plateaus. It analyzes variational methods and develops classical combination of variational quantum states with Ansatz-tree techniques. The approach provides provable solution guarantees and supports large simulated system sizes, while requiring efficient classical simulation cases for the reported experiments.

  • Problem

    Near-term quantum algorithms for linear systems must operate with limited hardware resources, and some variational methods encounter a plateau problem distinct from barren plateaus.

  • Method

    The paper combines variational quantum states classically through CQS and uses an Ansatz tree with gradient-based expansion and pruning heuristics.

  • Results

    The CQS approach provides provable guarantees, including an ϵ-close solution with single-run circuit depth O(κ log(κ/ϵ)) and one additional ancilla.

  • Takeaways & Limitations

    Classical combination can increase near-term ansatz expressiveness and trade quantum circuit depth for more classical experimental repetitions.

  • Takeaways & Limitations

    The reported numerical experiments use specially structured systems that can be simulated efficiently classically, so actual quantum advantage requires harder-to-simulate A or quantum-prepared b.

Abstract

from arXiv · show

Solving linear systems of equations is essential for many problems in science and technology, including problems in machine learning. Existing quantum algorithms have demonstrated the potential for large speedups, but the required quantum resources are not immediately available on near-term quantum devices. In this work, we study near-term quantum algorithms for linear systems of equations of the form $Ax = b$. We investigate the use of variational algorithms and analyze their optimization landscapes. There exist types of linear systems for which variational algorithms designed to avoid barren plateaus, such as properly-initialized imaginary time evolution and adiabatic-inspired optimization, suffer from a different plateau problem. To circumvent this issue, we design near-term algorithms based on a core idea: the classical combination of variational quantum states (CQS). We exhibit several provable guarantees for these algorithms, supported by the representation of the linear system on a so-called Ansatz tree. The CQS approach and the Ansatz tree also admit the systematic application of heuristic approaches, including a gradient-based search. We have conducted numerical experiments solving linear systems as large as $2^{300} \times 2^{300}$ by considering cases where we can simulate the quantum algorithm efficiently on a classical computer. These experiments demonstrate the algorithms' ability to scale to system sizes within reach in near-term quantum devices of about $100$-$300$ qubits.

I. INTRODUCTION

The paper studies near-term quantum approaches for solving linear systems, comparing variational ansätze and their optimization landscapes. It identifies a distinct plateau problem and proposes classical combination of variational quantum states, supported by Ansatz-tree methods and problem-specific access assumptions.

  • Motivation: Near-term quantum hardware lacks the low-decoherence, fully connected qubits required by many quantum algorithms for linear systems.This motivates algorithms designed for devices with limited quantum resources.
  • Problem setting: Linear systems solve Ax = b and arise broadly in engineering, science, and machine learning.The paper discusses square, rectangular, invertible, and constrained systems, including regression-style losses.
  • Variational approaches: Variational algorithms prepare shallow parameterized candidate states, measure a loss, and iteratively update parameters; the paper studies Agnostic and Alternating Operator ansätze.Agnostic ansätze omit explicit matrix information, whereas Alternating Operator ansätze use operators derived from A and |b⟩.
  • Optimization difficulty: Some linear systems give polynomial-parameter ansätze mostly flat landscapes with large loss, creating a plateau distinct from standard barren plateaus.The issue can affect properly initialized imaginary-time evolution and adiabatic-inspired optimization, despite their motivation to avoid barren plateaus.
  • CQS approach: Classical combination of variational quantum states combines multiple quantum states through classical pre- and post-processing, increasing ansatz expressiveness without additional quantum resources.The approach is paired with an Ansatz tree, whose nodes can represent candidate states and whose combinations are optimized classically.
  • Formulations and assumptions: The proposed losses include regression, regularized regression, and Hamiltonian formulations, with assumptions of efficient preparation of |b⟩ and decomposition of A into known unitaries.The Hamiltonian formulation connects solving the system with finding a unique ground state.

A. Details on variational algorithms for optimizing the Ansatz

Variational linear-system solvers prepare parameterized quantum states, measure a loss, and optimize circuit parameters, but their landscapes can become exponentially flat. The paper examines adiabatic-assisted and structure-aware Ansätze, including an Alternating Operator Ansatz, while numerical tests show adiabatic assistance improves accuracy in small systems.

  • Basic variational algorithms: A variational solver prepares |ψ(θ)⟩, estimates a loss function, and updates θ iteratively to improve the candidate solution.The basic loop consists of state preparation, loss estimation, and parameter optimization.
  • Basic variational algorithms: Imaginary time propagation updates parameters using θ(t + δt) ← θ(t) − M^-1(t)C(t)δt, based on estimates obtained from copies of |ψ(θ(t))⟩.The method directly propagates variational parameters instead of the quantum state.
  • Adiabatic-assisted VQE: Adiabatic-assisted VQE discretizes the Hamiltonian path and uses the optimized parameters from each step as the initial guess for the next.The interpolation runs from s = 0 to s = 1 through T adiabatic steps.
  • Agnostic Ansatz: For the agnostic Ansatz, average fidelity approaches unity as the number of adiabatic steps increases, with improvement over standard VQE in experiments up to N = 16.The Ansatz uses layered single-qubit rotations and CNOT gates without explicitly encoding A or b.
  • Alternating Operator Ansatz: The Alternating Operator Ansatz encodes A and b through four Hamiltonians and parameterized unitaries, but its performance depends on the difficulty of simulating those unitaries and optimizing their parameters.The four Hamiltonians are H1, H2, H3, and H4; the Ansatz alternates their unitaries across p layers.
  • Potential problems: For polynomial-sized parameterizations, gradients can be exponentially small, making the loss landscape flat even when a solution exists in the Ansatz.This plateau can occur for both regression and Hamiltonian loss functions and is distinct from the usual barren plateau problem.
  • Potential problems: Adiabatic evolution can remain at the initial state for all s ∈ [0, 1] when the variational landscape is flat, preventing convergence to the solution.The relevant terms become flat around the initial parameter in polynomial-sized variational spaces.
  • Potential problems: A pre-specified Ansatz can therefore be difficult for many linear systems, whereas Ansätze explicitly applying A may circumvent this plateau but still require convergence guarantees.The paper identifies the Alternating Operator Ansatz as one possible structure-aware choice requiring further study.

A. Main idea

CQS broadens the manipulable state space by combining variational quantum states classically, addressing both limited Ansatz expressivity and difficult parameter optimization. The approach shifts work toward classical processing and repeated measurements while reducing quantum resource requirements.

  • Motivation: Typical variational Ansätze may exclude the solution or contain parameters that are difficult to optimize.These are the two drawbacks that CQS is designed to address.
  • Classical combination: CQS combines states from multiple parameterized circuits into a hybrid vector whose coefficients and variational parameters remain classical.The vector x is not generally normalized and is never created directly on the quantum processor.
  • Evaluation: Expectation values for the hybrid vector are obtained through quantum measurements of pairwise state overlaps followed by classical post-processing.A modified Hadamard test estimates the required matrix elements using one additional ancilla.
  • Resource trade-offs: O(log(m)) ancilla qubits can be reduced to 1 when the larger m-state space is emulated through hybrid quantum-classical processing.The direct construction uses m controlled unitaries, whereas the hybrid approach uses a single additional ancilla and avoids creating the combined state on the quantum processor.
  • Resource trade-offs: For 300 variational states, CQS can reduce the gate count by 150 times, at the cost of many repeated quantum measurements.The reduced gate count enlarges the space of variational states that can be prepared within near-term hardware limits.
  • Optimization strategy: The overall strategy alternates convex optimization of combination coefficients with expansion by adding a new circuit and state.Iterations begin with one state and increment m after each expansion.

B. Optimization of combination parameters

The paper optimizes classical combination coefficients over quantum states, then constructs and expands an Ansatz-tree subspace to obtain guarantees and practical search heuristics for linear systems.

  • Combination-parameter optimization: Optimizing the combination coefficients over a fixed quantum-state subspace is a convex regression problem, unlike optimizing the underlying variational parameters.The coefficients can be optimized with standard convex quadratic programming once the kernel matrix and linear term are determined.
  • Combination-parameter optimization: The fixed-subspace approach can achieve a near-optimal solution, but finding its combination parameters is BQP-complete.This guarantee applies when the relevant solution is represented within the selected subspace.
  • Ansatz-tree construction: The Ansatz tree represents candidate subspace states generated from the unitaries in A and guarantees a near-optimal solution after sufficiently many nodes are included.The tree also supports systematic exploration, pruning, and expansion heuristics.
  • Ansatz-tree construction: Selecting all tree nodes to depth O(κ log(κ/ϵ)) guarantees a near-optimal solution under spectral-radius and condition-number assumptions.The required number of nodes can nevertheless scale exponentially with the condition number, motivating node-reduction strategies.
  • Ansatz-tree guarantees: The required tree depth can depend logarithmically on approximation accuracy, and Newton’s method improves the depth scaling to O(log(1/ϵ)).The prefactor matters because the number of included nodes grows exponentially with depth.
  • Gradient expansion heuristics: Gradient expansion starts from the root state, evaluates candidate gradient overlaps, and adds the child with the largest overlap to the subspace.A nonzero selected overlap guarantees improvement after coefficient optimization, while a larger overlap guarantees a larger loss decrease.

D. Numerical experiments

The numerical experiments test CQS-based search on both moderate random systems and exponentially large sparse systems. Gradient expansion converges substantially faster than breadth-first Ansatz-tree search, while the large-system experiments probe the proposed method beyond the plateau setting.

  • Gradient expansion converges quickly to the optimum, whereas breadth-first Ansatz-tree search becomes very slow after an initial rapid phase.The comparison uses randomly generated 256×256 systems; the breadth-first method includes every node layer by layer.
  • The 256×256 systems use Hermitian matrices formed from weighted sums of unitaries, with condition numbers on the order of system size.The construction selects Haar-random unitaries and random coefficients, using S = 10 and therefore 20 unitaries in the sum.
  • The sparse-system experiments range from 2^10 × 2^10 to 2^300 × 2^300, directly testing whether the CQS approach encounters the analyzed plateau issue.These systems use tensor products of Pauli operators, with S = 8 and |b⟩ = |0^n⟩.

E. Hamiltonian CQS approach and connection to previous results

The Hamiltonian CQS approach constructs solution approximations from time-evolved states and provides an alternative to direct Ansatz-tree decompositions. It offers provable accuracy and lower single-run depth in one comparison, while trading quantum depth for classical repetitions and simulation requirements.

  • Hamiltonian simulation generates an Ansatz subspace that is smaller than the direct Ansatz-tree subspace, but is less near-term.The reduced subspace size is the stated benefit, while Hamiltonian simulation increases near-term demands.
  • A Fourier approximation of 1/x yields a linear combination of unitaries e^(-iAt_j) that produces an ϵ-close solution through CQS.The Ansatz uses pre-specified evolution times and approximates A^-1 applied to |b⟩.
  • The Fourier-based construction has single-run depth O(κ log(κ/ϵ)) and requires only one additional ancilla for the Hadamard test.The solution is emulated quantum-classically rather than created directly on a quantum computer, avoiding many ancillas used by some existing approaches.
  • Compared with the random-sampling approach, the Hamiltonian CQS method achieves a roughly 100-times circuit-depth reduction at ϵ = 0.01, at the cost of more classical repetitions.The comparison concerns the stated circuit-depth expressions and does not count details of Hamiltonian simulation for H(s).
  • CQS classically combines multiple variational quantum states, increasing Ansatz expressiveness without additional quantum resources.The approach introduces classical combination parameters and is related conceptually to linear combinations used in quantum chemistry.
  • The Ansatz-tree strategy alternates subspace optimization with subspace growth, drawing inspiration from Krylov methods and coupled-cluster constructions.The method grows the subspace when the current solution is insufficient, while coupled-cluster Ansätze increase correlation order with preparation complexity.
  • Experiments reach 2^300 × 2^300 systems only for specially structured cases that permit efficient classical simulation.Actual quantum advantage requires nonsimulable unitary decompositions or a quantum-generated right-hand side, and performance under decoherence remains future work.

Appendix A: Measurements

The measurement appendix develops procedures for estimating overlaps, matrix-dependent loss terms, and related observables on a quantum computer. These procedures rely on swap tests, Hadamard tests, modified Hadamard tests, and concentration-based sampling guarantees.

  • Pauli-string expectation values can be estimated to additive accuracy ϵ using repeated Bernoulli measurements and concentration bounds.The measurement outcome is ±1, and the empirical positive-outcome frequency determines the expectation estimate.
  • The swap test estimates squared state overlap |⟨v|u⟩|^2 from measurements of an ancilla after controlled state exchange.The stated procedure uses multiple copies of the two n-qubit states.
  • The Hadamard test estimates the real and imaginary parts of a state overlap by choosing α = 1 or α = i before ancilla measurement.The method provides additive-accuracy estimates with a failure-probability guarantee.
  • Under the unitary decomposition assumptions, the Hamiltonian loss function can be estimated efficiently by measuring unitary-product and cross-term expectations.The construction estimates terms such as ⟨x|U_kU_l|x⟩ and ⟨b|U_k|x⟩, then combines them into the loss estimate.
  • The modified Hadamard test estimates matrix elements ⟨v0|O|v1⟩ when O = U†DU and diagonal entries of D are classically computable.It samples the ancilla outcome multiplied by a classically evaluated function of the computational-basis result.

Appendix B: Potential problems for local loss function in the presence of entangling gates

The appendix shows that, under its random-circuit assumptions, the local loss landscape can become exponentially flat around a variational point. The loss concentrates near 1/2 while its gradient becomes exponentially small.

  • The analysis assumes a random quantum circuit for the right-hand-side preparation and bounds the derivative norm by a constant.These assumptions support the moment and concentration estimates used for the loss and gradient.
  • For the analyzed Hermitian-unitary setting, the local loss remains exponentially close to 1/2 across even a very large set of randomly selected parameter values.The stated guarantee applies to as many as exponentially many parameter choices.
  • The gradient is exponentially small with high probability, making the optimization landscape locally flat around the selected parameter point.The bound follows from the random unitary’s two-design property and assumptions on the Ansatz derivative.

Appendix C: Detailed analysis on optimizing combination coefficients

The appendix analyzes measurement requirements, approximation error, and computational complexity for optimizing CQS combination coefficients. It also establishes that this optimization problem is BQP-complete.

  • Measurement procedure: Each Q and r entry is estimated from quantum measurements using Hadamard-test-based sampling of unitary decompositions.The measurement procedure estimates matrix elements of V†V and A†b, with sample magnitudes bounded by O(1).
  • Approximate optimization: The resulting estimates Q̂ and r̂ define an approximate quadratic optimization problem whose solution ẑ is compared with the exact minimizer z*.The analysis uses perturbation bounds relating ẑ−z* to errors in Q̂ and r̂.
  • Measurement complexity: The total measurement complexity is derived by independently estimating all entries of Q and r and applying concentration and random-matrix bounds.The proof uses bounded samples, variance scaling as O(1/T), and aggregate estimates over all entries.
  • Computational complexity: Optimizing two CQS combination coefficients is BQP-complete when A has an efficient unitary decomposition and the relevant states can be prepared by quantum circuits.The hardness reduction encodes measurement probabilities P0 and P1 into the optimal coefficients α1 and α2.

Appendix D: Provable guarantee for the Ansatz tree approach

The appendix proves approximation and descent guarantees for Ansatz-tree methods by representing solutions through polynomial combinations of matrix powers applied to b. These guarantees depend on spectral-radius and condition-number assumptions.

  • Relation to prior analysis: The guarantees extend known polynomial-approximation results for solving linear systems and rely on selecting suitable Ansatz-tree nodes.The appendix explicitly identifies one proposition as a simple extension and variation of prior polynomial-approximation results.
  • Polynomial representation: Polynomial combinations of A^k|b⟩ approximate the inverse action needed to solve Ax=b under bounded spectral radius and condition number.Chebyshev polynomial approximation yields an inverse approximation over the eigenvalue domain bounded away from zero.
  • Spectral analysis: Diagonalizing A reduces the regularized loss to independent scalar terms, whose analytic minimizers determine the optimal coordinates in the eigenbasis.For each eigenvalue λ_i, the optimal coordinate is given explicitly as 2λ_i b̃_i/(2λ_i^2+1).
  • Approximation guarantee: An Ansatz tree with depth O(κ log(κ/ϵ)) contains a subspace sufficient to achieve ϵ-accurate approximation under ρ(A)≤1 and ρ(A^-1)≤κ.The resulting approximation can achieve ϵ^2 residual error because the exact solution has zero residual.

Appendix E: Experiments on solving linear systems using Agnostic Ans¨atze

The experiments evaluate real-valued Agnostic Ansätze built from tunable y rotations and CNOT connectivity patterns. Performance improves with circuit depth for most topologies, while AAVQE improves accuracy over standard VQE.

  • Ansatz construction: The Agnostic Ansatz uses tunable single-qubit y rotations and CNOT gates, restricting the search to the real subspace.The experiments compare star, line, ring, and complete-graph CNOT patterns.
  • Experimental setup: Random linear systems with N=2, 4, 8, and 16 are evaluated on a Rigetti quantum virtual machine using mean fidelity-based accuracy over 100 runs.Mean accuracy is the average fidelity between the output vector and the solution.
  • Standard VQE: For N=16 standard VQE, line, ring, and complete-graph Ansätze reach unit mean accuracy at 20 layers, whereas the star graph levels at 0.6.The star topology improves initially but then plateaus, unlike the other tested connectivity patterns.
  • Adiabatic-assisted VQE: For N=8, AAVQE with six adiabatic steps improves mean accuracy by roughly 10% over standard VQE averaged across topologies and layer depths.At six adiabatic steps, the mean accuracy becomes close to unity and the standard deviation falls below 10^-2.
Loading 1909.07344v2…