PaperlayerView exact revision on arXiv

Source-linked AI summary

Variational algorithms for linear algebra

Xiaosi Xu, Jinzhao Sun, Suguru Endo, Ying Li, Simon C. Benjamin, Xiao Yuan

arXiv:1909.03898v3quant-ph

TL;DR

Deep circuits and fault-tolerant hardware limit conventional quantum approaches to linear algebra. This paper instead uses variational Hamiltonian ground-state methods on NISQ devices, with adaptive search and verification, achieving 99.95% fidelity in an IBM experiment.

  • Problem

    Conventional quantum algorithms for linear algebra generally require deep circuits and fault-tolerant quantum computers, whereas current technology is challenging for such circuits.

  • Method

    The paper constructs Hamiltonians whose zero-energy ground states encode linear-system and matrix-vector-multiplication solutions, then applies variational methods with Hamiltonian morphing and adaptive ansätze.

  • Results

    99.95% fidelity with respect to the target state was achieved for a 2-dimensional linear system on an IBM Q device.

  • Takeaways & Limitations

    The algorithms are designed for NISQ hardware, especially sparse-matrix linear-algebra problems, and support solution verification and dynamic ansatz adjustment.

Abstract

from arXiv · show

Quantum algorithms have been developed for efficiently solving linear algebra tasks. However, they generally require deep circuits and hence universal fault-tolerant quantum computers. In this work, we propose variational algorithms for linear algebra tasks that are compatible with noisy intermediate-scale quantum devices. We show that the solutions of linear systems of equations and matrix-vector multiplications can be translated as the ground states of the constructed Hamiltonians. Based on the variational quantum algorithms, we introduce Hamiltonian morphing together with an adaptive ansatz for efficiently finding the ground state, and show the solution verification. Our algorithms are especially suitable for linear algebra problems with sparse matrices, and have wide applications in machine learning and optimisation problems. The algorithm for matrix multiplications can be also used for Hamiltonian simulation and open system simulation. We evaluate the cost and effectiveness of our algorithm through numerical simulations for solving linear systems of equations. We implement the algorithm on the IBM quantum cloud device with a high solution fidelity of 99.95%.

I. INTRODUCTION

The paper develops variational linear-algebra algorithms for NISQ devices, targeting tasks traditionally addressed by deep-circuit quantum algorithms. It constructs Hamiltonians whose ground states encode solutions and reports numerical and IBM-device evaluations.

  • Conventional quantum linear-algebra algorithms generally require long-depth circuits and fault-tolerant quantum computers, challenging current technology.
  • The proposed variational algorithms target linear systems of equations and matrix-vector multiplications using NISQ hardware.
  • The method constructs a many-body Hamiltonian whose ground state corresponds to the linear-algebra solution, then applies variational ground-state methods.
  • Numerical simulations evaluate linear-system instances with random matrices up to 64*64 and find polynomial scaling of circuit depth and computation time with matrix size and condition number.
  • 99.95% fidelity was achieved for a 2-dimensional linear system implemented on an IBM Q device.

II. VARIATIONAL ALGORITHMS FOR LINEAR ALGEBRA

The paper encodes matrix-vector multiplication and linear-system solutions as zero-energy ground states, then uses parameterized circuits and variational optimization to recover them. VQE can reach local minima, motivating verification and additional search strategies.

  • Matrix-vector multiplication: For matrix-vector multiplication, the normalized state proportional to M|v0⟩ is constructed as the ground state of a Hamiltonian, including for general non-Hermitian M.
  • Variational formulation: The variational state |φ(θ⃗)⟩ = U(θ⃗)|0⟩ converts ground-state preparation into minimizing the Hamiltonian expectation value.
  • VQE optimization: VQE gradient descent updates parameters using θ⃗_i+1 = θ⃗_i − a∇E_M(θ⃗_i), with time step a and T total steps.
  • Linear systems: For linear equations, the paper focuses on sparse, Hermitian, invertible matrices after noting that non-Hermitian matrices can be converted using an ancillary qubit.
  • Solution verification: The exact solutions are designed to have zero energy, enabling correctness verification after variational optimization.
  • Optimization limitation: Because VQE can terminate at local minima, multiple random initializations may be needed to find the global minimum, while short ansätze provide no guarantee.

III. IMPLEMENTATION WITH QUANTUM CIRCUITS

The implementation estimates variational energies and gradients with quantum circuits, using finite differences or quantum gradient-finding methods. Sparse matrix structure can keep measurement resources polynomial under the paper’s stated assumptions.

  • Gradient estimation: VQE gradients can be estimated with finite-difference formulae or recently proposed quantum gradient-finding methods.
  • Gradient estimation: Finite differences evaluate each gradient component around θ⃗ using a small perturbation δθ_i, while the normalized-state energy is E_M(θ⃗) = 1 − |⟨φ(θ⃗)|M|v0⟩|^2.
  • Quantum circuits: Hadamard or swap tests can evaluate the real and imaginary parts of circuit expectation values, and operator decompositions provide an alternative energy-measurement route.
  • Measurement cost: The measurement cost is small when the matrix has a polynomial number of local-operator terms or when its coefficient distribution can be sampled efficiently.
  • Sparse matrices: For sparse matrices, representing matrix elements as indexed nonzero terms and expanding them into unitary operators enables energy evaluation with quantum circuits.
  • Measurement cost: O(log(δ^-1)C^2/ε^2) samples estimate ⟨φ|M|ψ⟩ to accuracy ε with failure probability δ, where C is the coefficient-sum cost.

IV. SOLUTION VERIFICATION

The paper verifies variational solutions through their energy and overlaps with exact target states. For linear systems, it also uses a condition-number-dependent fidelity bound and an alternative residual-style test.

  • Matrix-vector multiplication: For matrix-vector multiplication, the solution fidelity satisfies |⟨φ(θ⃗_min)|v_M⟩|^2 = 1 − E_M(θ⃗_min).
  • Matrix-vector multiplication: A candidate matrix-vector solution is considered correct when its fidelity with the exact state is close to 1.
  • Linear systems: For linear systems, direct measurement of the inverse-matrix overlap is unavailable, so the paper derives a fidelity lower bound involving the condition number κ and Hamiltonian energy.
  • Linear systems: The linear-system solution can alternatively be verified by checking whether |v0⟩ ∝ M|φ(θ⃗_min)⟩, using an overlap ratio close to 1.

V. OPTIMISATION VIA HAMILTONIAN MORPHING

Hamiltonian morphing addresses VQE search difficulties by gradually transforming an initial Hamiltonian into the target while reusing previously optimized parameters. The method can adapt circuit expressivity when the ansatz cannot represent intermediate states.

  • Hamiltonian morphing: Hamiltonian morphing gradually varies HM−1(t) from an initial Hamiltonian with ground state |v0⟩ to the target Hamiltonian.It uses M(0)=I, M(T)=M, and M(t)=(1−t/T)I+t/T·M.
  • Hamiltonian morphing: At each discretized time step, parameters optimized for the previous Hamiltonian initialize the search for the next ground state.This continuation strategy transfers the parameters θ((n−1)δt) to the step at nδt.
  • Conditions: For positive matrices, sufficiently small δt and a powerful enough ansatz guarantee the exact solution through the adiabatic theorem.For general matrices, an extra qubit can make the Hamiltonian energy gap non-vanishing.
  • Adaptive ansatz: When the ansatz cannot represent states throughout the morphing path, high averaged energy signals the need for greater ansatz expressivity.The response is to choose a more powerful ansatz or adaptively change its structure by adding gates.
  • Adaptive ansatz: The circuit ansatz varies its depth by increasing the number of fixed-structure blocks, while reverse-order CNOT gates support finding the eigenstate at t=0.Single-qubit rotation parameters are updated during variational cycles.

VI. NUMERICAL SIMULATION

Numerical simulations examine how circuit depth, matrix size, and condition number affect success probability and computation time. The simulations also motivate adaptive ansatz design for general matrices.

  • For fixed 64 × 64 matrices, larger circuit depth generally increases success probability, while minimum depth for 100% success varies linearly with condition number.Success means fidelity above 99%, evaluated over 4940 random trials for each case.
  • With κ = 10^n, the minimum depth for 100% success increases super-linearly with the number of qubits.The simulations vary matrix size as 2^n × 2^n while increasing circuit depth until success probability reaches 1.
  • The fitted computation-time relation is y = 0.0024x^3.1, where y is computation time and x is matrix size.The fit uses the minimum circuit depth achieving 100% success.
  • The super-linear depth dependence is attributed to general solution states that may not be preparable with shallow circuits despite fixed condition numbers.Unitary transformations preserve eigenvalues and condition number while potentially producing more difficult solution states.
  • The chosen ansatz is not optimal, and the authors leave restricted practical cases and more advanced circuit morphing for future work.They suggest matrix-informed ansätze, circuit compiling, and dynamically varying the ansatz as possible improvements.

VII. IMPLEMENTATION ON THE IBM QUANTUM MACHINE

The authors implement the variational linear-equation algorithm on IBM’s ibmq-ourense processor and track energy and fidelity during optimization. The experiment reaches 99.95% fidelity despite noise-related fluctuations in measured energy.

  • The experiment uses IBM’s five-qubit ibmq-ourense processor, with reported T2 times and single-qubit, CNOT, and readout error rates.The circuit is implemented through Qiskit.
  • The example starts from |v0⟩ = |0⟩ and prepares the trial state with a single-qubit rotation whose angle is updated by gradient descent.Each observable’s expectation value aggregates 8192 runs.
  • Measured energy decays rapidly but fluctuates between 0.05 and 0.1, mainly because of circuit noise, especially readout error.Energies computed from the experimentally discovered rotation angles nearly follow the exact evolution.
  • The experimentally prepared state reaches 99.95% fidelity with the target state.The fidelity curve nearly overlaps the reference curve obtained from exact evolution.

VIII. APPLICATIONS

The paper extends matrix-vector multiplication to Hamiltonian and open-system simulation, using variational updates to approximate real- and imaginary-time evolution with reduced measurement cost.

  • VIII. APPLICATIONS: Trotterization has circuit depth that increases with evolution time, motivating an alternative variational matrix-vector approach for long-time dynamics.
  • VIII. APPLICATIONS: Variational matrix-vector multiplication applies M ≈ 1 − iHδt at each step to update a parameterised state for real-time simulation.The same framework applies to imaginary-time evolution using M ≈ 1 − Hδτ.
  • VIII. APPLICATIONS: The algorithm reduces measurements per time step from O(L^2) to O(L) for the simulation procedure described.
  • VIII. APPLICATIONS: For open-system evolution, matrix-vector multiplication implements quantum jump processes involving jump operators acting on complicated many-qubit states.The paper connects this use to stochastic Schrödinger trajectories for Lindblad dynamics.
  • VIII. APPLICATIONS: The paper notes that singular value decomposition may also be addressed with a suitable cost function, but does not develop it here.

IX. DISCUSSION

The discussion presents variational linear-algebra algorithms for NISQ devices, emphasizing Hamiltonian ground-state reformulation, solution verification, and numerical scaling results. It also identifies limited matrix sizes and non-optimal ansätze as important scope boundaries.

  • IX. DISCUSSION: The algorithms target linear systems and matrix-vector multiplication on NISQ devices by encoding each solution as a Hamiltonian ground state.
  • IX. DISCUSSION: Zero ground-state energy enables solution verification and dynamic ansatz adjustment until the desired accuracy is achieved.
  • IX. DISCUSSION: Hamiltonian morphing is introduced to avoid local minima and accelerate the ground-state search.
  • IX. DISCUSSION: Within small numerical experiments using non-optimal ansätze, circuit depth scales linearly with condition number and super-linearly with qubit count.The simulations used randomly chosen matrices with a small range of matrix sizes because of computational limitations.
  • IX. DISCUSSION: The appendix establishes that M|v0⟩ and M^-1|v0⟩ are lowest-energy states of constructed Hamiltonians, enabling variational methods to recover the linear-algebra solutions.
  • IX. DISCUSSION: The solution-fidelity bound depends on the Hamiltonian energy and condition number, with the energy gap satisfying E1 ≥ 1/κ^2.

Appendix B: Optimisation methods searching for⃗θmin

The appendix describes imaginary-time parameter updates and measurement strategies for variational optimisation, including sparse-matrix decompositions that keep measurement costs polynomial under stated sampling assumptions.

  • Appendix B: Optimisation methods searching for⃗θmin: Imaginary-time evolution updates parameters using McLachlan’s variational principle and is equivalent to quantum natural gradient descent for pure states.
  • Appendix B: Optimisation methods searching for⃗θmin: Imaginary-time evolution suppresses higher-energy components exponentially, so the long-time state approaches the Hamiltonian ground state.
  • Appendix B: Optimisation methods searching for⃗θmin: With sufficiently small time steps, the updated variational state yields the solutions M|v0⟩ or M^-1|v0⟩.
  • Appendix B: Optimisation methods searching for⃗θmin: A general matrix can be expanded into tensor products of unitary operators using single-qubit operator decompositions.
  • Appendix B: Optimisation methods searching for⃗θmin: For sparse matrices, nonzero matrix elements can be sampled to estimate matrix expectation values with polynomial measurement resources.
  • Appendix B: Optimisation methods searching for⃗θmin: Hoeffding’s inequality gives O(log(δ^-1)C^2/ε^2) samples to estimate ⟨φ|M|ψ⟩ within accuracy ε and failure probability δ.

Appendix D: Circuit implementation of ∇EM−1

The appendix implements gradients for the inverse-matrix Hamiltonian with ancilla-based circuits and Pauli decompositions, while compilation produces a compact high-fidelity circuit for the target state.

  • Appendix D: Circuit implementation of ∇EM−1: Gradients for EM^-1 are evaluated by decomposing M and M†M into Pauli terms and decomposing the state derivative similarly.
  • Appendix D: Circuit implementation of ∇EM−1: The derivative terms are measured with ancilla-based circuits, including circuits corresponding to Figures 6(a), 6(b), and 6(c).
  • Appendix D: Circuit implementation of ∇EM−1: Figure 6 uses the first qubit as an ancilla and the second as the data-qubit register; real parts are obtained by measuring ⟨X⟩ for a specified ancilla initialization.
  • Appendix D: Circuit implementation of ∇EM−1: 126 parameters produce a compiled circuit with fidelity higher than 99.9% for the target state.The compiled circuit is described as more compact than the original realization.

Appendix E: Example with a more compact circuit

This appendix illustrates a more compact-circuit example for a 64×64 complex linear system and shows how the variational energy can be evaluated from Pauli measurements. The same matrix-vector multiplication machinery is also used to realize quantum jumps in open-system simulation.

  • Compact circuit example: For a complex 64×64 matrix with condition number κ = 60, the target state requires circuit depth 8 rather than depth 7.Quantum compiling can realize the target with half as many parameters, while maintaining fidelity higher than 99.9%.
  • Compact circuit example: The circuits in Figure 8 evaluate the imaginary parts of expectation values involving Z and X, respectively.These correspond to the second and third Pauli terms in the Hamiltonian.
  • Compact circuit example: The linear-system target is the normalized state |vM −1⟩= M −1|v0⟩ ∥M −1|v0⟩∥.The example considers the matrix-inverse solution state for the input vector |v0⟩.
  • Compact circuit example: With |v0⟩= |0⟩, the effective Hamiltonian becomes HM −1 = 1.25I − Z + 0.75X for the example matrix.The Hamiltonian is expressed as a linear combination of Pauli terms before evaluating the variational state.
  • Compact circuit example: The variational energy is obtained by directly measuring ⟨vm|Z|vm⟩ and ⟨vm|X|vm⟩.The identity contribution is included in E = ⟨vm|(1.25I − Z + 0.75X)|vm⟩.
  • Open-system simulation: In open-system simulation, the matrix-vector multiplication realizes the quantum-jump process, providing an alternative solution for the simulation.The jump maps the state to Lk |ψ(t)⟩/∥Lk |ψ(t)⟩∥ when a jump occurs.
Loading 1909.03898v3…