PaperlayerView exact revision on arXiv

Source-linked AI summary

Variational quantum simulation of general processes

Suguru Endo, Jinzhao Sun, Ying Li, Simon Benjamin, Xiao Yuan

arXiv:1812.08778v4quant-ph

TL;DR

The paper develops variational procedures for solving linear equations, including an approach that does not assume matrix structure and another that assumes tensor-product structure. Linear equations can be solved with shallow quantum circuits, while resource estimation for linear algebra problems is left for future work.

  • Problem

    The paper addresses solving linear equations with an invertible matrix, including cases with and without assumed tensor-product structure.

  • Method

    The paper calculates M−1|v0⟩ by measuring coefficients and evolving variational parameters, with a separate structured-matrix approach based on tensor-product structure.

  • Results

    Linear equations can be solved with shallow quantum circuits requiring two or three controlled operations from an ancilla qubit.

  • Takeaways & Limitations

    The variational approach provides a shallow-circuit route to solving linear equations through parameter evolution and coefficient measurement.

  • Takeaways & Limitations

    Detailed resource estimation for linear algebra problems is left for future work because dissipative distance decrease may not hold for those problems.

Abstract

from arXiv · show

Variational quantum algorithms have been proposed to solve static and dynamic problems of closed many-body quantum systems. Here we investigate variational quantum simulation of three general types of tasks---generalised time evolution with a non-Hermitian Hamiltonian, linear algebra problems, and open quantum system dynamics. The algorithm for generalised time evolution provides a unified framework for variational quantum simulation. In particular, we show its application in solving linear systems of equations and matrix-vector multiplications by converting these algebraic problems into generalised time evolution. Meanwhile, assuming a tensor product structure of the matrices, we also propose another variational approach for these two tasks by combining variational real and imaginary time evolution. Finally, we introduce variational quantum simulation for open system dynamics. We variationally implement the stochastic Schrödinger equation, which consists of dissipative evolution and stochastic jump processes. We numerically test the algorithm with a six-qubit 2D transverse field Ising model under dissipation.

SUPPLEMENTARY MATERIALS: VARIATIONAL QUANTUM SIMULATION OF GENERAL PROCESSES

Variational real- and imaginary-time evolution map quantum-state dynamics onto parameter evolution using McLachlan’s principle. The required coefficients are measured with quantum circuits, including circuits tailored to gate-based trial states.

  • Real-time evolution: Real-time evolution uses a parametrised quantum circuit whose parameters evolve by minimising the distance from ideal Schrödinger dynamics.The trial state is prepared as |ϕ(θ⃗(t))⟩ = R_N(θ_N) ··· R_1(θ_1)|0̄⟩.
  • Imaginary-time evolution: Imaginary-time evolution applies the same variational procedure to the normalised Wick-rotated Schrödinger equation.The parameter evolution uses the matrix M from real-time evolution and a separately defined C term.
  • Circuit representation: The derivatives of parameterised gates decompose into unitary operators with complex coefficients, enabling efficient evaluation of trial-state derivatives.The decomposition supports measurement of the coefficient terms required by the variational equations.
  • Measurement: The supplementary derivation develops circuit constructions for the coefficient terms, including circuits associated with Fig. 4.These constructions use decompositions of operators into unitary components and Pauli operators.
  • Measurement: The quantities M, C, and V are expressed through measurable state overlaps and expectation values evaluated with quantum circuits.The overlap terms can be reduced to circuits involving unitary operators and Pauli operators.

DERIVATION FOR VARIATIONAL SIMULATION OF GENERALISED TIME EVOLUTION EQUATION

The generalised time-evolution derivation represents state and auxiliary-state dynamics with parametrised circuits, then evaluates the resulting coefficient matrices and vectors through measurable overlaps. The construction includes specialised circuits for the terms entering the parameter evolution.

  • Generalised evolution: Generalised time evolution is formulated by substituting parametrised states into the generalised evolution equation and deriving parameter dynamics.The derivation introduces circuit-prepared representations for both |v(θ⃗(t))⟩ and |v′(θ⃗′(t))⟩.
  • Coefficient evaluation: The coefficients M̃_k,j are decomposed into overlap terms involving circuit operators, Pauli operators, and real-part measurements.Each term is reduced to a measurable expression of the form Re(e^iθ⟨0̄|R†…|0̄⟩).
  • Coefficient evaluation: The fourth coefficient term is evaluated by measuring the expectation value of B†(t)B(t).The other terms are expressed as overlap measurements using the corresponding circuit decompositions.
  • Ṽ_k evaluation: The first and second terms of Ṽ_k are computed with separate quantum circuits shown in Figs. 6 and 7.The derivation expresses each term in a form suitable for circuit evaluation.
  • Ṽ_k evaluation: When the auxiliary state equals the variational state, Ṽ can instead be computed using Fig. 4(b), requiring only two controlled operations.This case includes open quantum simulation and solving linear equations.

Matrix evolution with normalised states

For normalised matrix-transformed states, the method tracks the state along an evolution from the input vector to the normalised output and measures the associated normalisation factor. The same framework yields a variational route to linear-system solutions, with a separate tensor-product approach.

  • Matrix evolution with normalised states: The normalised target state is |ψ(t)⟩ = M|v0⟩/∥M|v0⟩∥, obtained by extrapolating from the normalised input state.The resulting state evolution is represented within the generalised time-evolution framework.
  • Matrix evolution with normalised states: The normalisation factor N(t) is measured from expectation values of M† + M and M†M on the initial state.These measurements enter the derivative equation for the normalised state.
  • Solving linear equations: Linear equations seek |v_M−1⟩ = M−1|v0⟩ for an invertible matrix M, and the paper introduces general and tensor-product algorithms.The first algorithm does not assume matrix structure; the second assumes tensor-product structure.
  • Solving linear equations: The general linear-system algorithm converts the static inversion problem into dynamics from |v0⟩ at t = 0 to |v_M−1⟩ at t = T.The path is treated as a special case of generalised time evolution.
  • Solving linear equations: The coefficients can be measured while evolving the variational parameters, allowing M−1|v0⟩ to be computed with shallow circuits using two or three ancilla-controlled operations.A second approach realises matrix inversion with real- and imaginary-time evolution under tensor-product assumptions.

RESOURCE ESTIMATION

The resource analysis bounds simulation error by separating implementation error from algorithmic error and recursively accumulating their contributions over time. It also notes that the dissipative-distance assumption used in the bound does not generally apply to linear algebra problems.

  • RESOURCE ESTIMATION: The recursive error bound uses the triangle inequality and assumes that the evolution decreases the distance between states.This dissipative assumption is valid for real-time, imaginary-time, and open-system simulations, but depends on the problem for linear algebra tasks.
  • RESOURCE ESTIMATION: The algorithmic error is decomposed into implementation error from imperfect coefficients and algorithmic error from finite time steps and an insufficient ansatz.The implementation contribution uses exact versus measured coefficients, while the algorithmic contribution reflects discretisation and state-representation errors.
  • RESOURCE ESTIMATION: The total simulation error is upper bounded by summing implementation and algorithmic error contributions across the time steps.The accumulated terms are denoted εI and εA in the resource analysis.

Implementation error

Implementation error arises from noisy estimates of the coefficient matrices and vectors used to evolve the variational parameters. The analysis relates this error to measurement sampling and bounds the samples needed for a target implementation accuracy.

  • Implementation error: Implementation error comes mainly from imprecise estimates of ˜M and ˜V caused by physical error or shot noise.The exact and measured quantities are written as ˜M0, ˜V0 and ˜M, ˜V, respectively.
  • Implementation error: The measured parameter derivative differs from the exact derivative through perturbations δ˜M, δ˜V, and δ ˙⃗θ.The analysis expands the measured derivative around the exact values and uses a Taylor expansion under a small-perturbation condition.
  • Implementation error: The implementation error is bounded as a function of the coefficient-estimation perturbations and the number of measurement samples.For shot-noise-dominated errors, the number of samples Ns for each term determines the implementation-error relationship.
  • Implementation error: To achieve implementation error εI, the resource analysis derives a corresponding measurement requirement using bounds on ∥B∥max and ∆max.The derivation assumes the evolution in the analysed equation is normalised.

Algorithmic error

Algorithmic error is attributed to finite time steps and imperfections in the variational ansatz. The analysis bounds the required number of steps and the time step needed to suppress these contributions.

  • Algorithmic error: Algorithmic error consists of an ansatz-imperfection term and a finite-time-step term.The two contributions arise from imperfect state representation and discretising the evolution.
  • Algorithmic error: ∆2 is defined by the norm of the first-order ansatz error, while ∆3 combines overlaps between first- and second-order errors.These quantities characterize the error terms used in the algorithmic-error analysis.
  • Algorithmic error: Assuming the ansatz can always represent the target state, the required number of steps scales as NA = T/δt ≈ ∆(max)3 T^2.This scaling follows from the time-step requirement used to control the finite-step contribution.
  • Algorithmic error: To suppress the finite-time-step contribution to εA, the time step must satisfy δt ≈ εA^2.

Resource estimation

The resource estimate counts individual quantum circuits and total measurements needed to control implementation and algorithmic errors. It is explicitly described as a pessimistic asymptotic estimate, with potentially lower practical costs after measurement optimization.

  • Resource estimation: At each time step, NI counts the individual quantum circuits required by the variational algorithm.The count includes circuits used to populate the coefficient matrix ˜M and vector ˜V.
  • Resource estimation: The circuit count depends on the number of parameters, derivative terms, and Pauli decompositions of Aj(t), B(t), and B†(t)B(t).The estimate also includes the number of Aj(t) matrices appearing on the right-hand side of the evolution equation.
  • Resource estimation: Ntot is the total number of measurements required to reduce shot-noise implementation error to εI and algorithmic error to εA.The total-error case sets εI = εA = ε/2.
  • Resource estimation: The resource estimate is a pessimistic asymptotic bound, and realistic requirements may be lower with optimized measurement schemes.

Resource estimation for matrix multiplication via singular value decomposition method

The resource analysis examines singular-value-decomposition-based matrix multiplication, including approximation error, trace-norm bounds, and conditions governing the output norm.

  • Scope: The resource analysis for matrix multiplication is provided, while detailed resource estimates for the other variational linear-algebra algorithms are deferred to future work.The stated resource analysis focuses on the singular value decomposition method used in open-system simulation.
  • SVD-based construction: The method decomposes M into unitary factors U and V and a non-negative diagonal factor D, approximating each through variational real or imaginary time simulation.The diagonal factor is approximated by Dα, while U, V, and D are represented through exponentials of Hermitian generators.
  • Approximation error: The approximation analysis bounds how replacing D with Dα propagates into the resulting state, using trace-norm estimates for the two error terms.The first term is bounded separately, followed by a bound for the second term involving Δα.
  • Output-norm condition: C = ⟨v| D2 |v⟩ determines the norm after matrix multiplication and can be experimentally measured to identify cases with exponentially small output norm.When C is exponentially small, the output vector is treated as a zero vector.
  • Accuracy condition: When C ≥ 1/Poly(n), choosing α = ln(2/CεD)/2 yields the stated accuracy condition for approximating D.The analysis also notes that α may remain constant even when C is exponentially small, but such cases should be detected at the beginning.

Resource analysis

The resource analysis separates implementation, algorithmic, measurement, and open-system trajectory errors, then combines their contributions to estimate total measurement cost.

  • Matrix multiplication: The implementation and algorithmic errors are quantified separately for the variational matrix-multiplication procedure.The resource expressions use the costs of the unitary and diagonal components, summarized through TSV D = TU + TV + TD.
  • Measurement resources: The total measurement number is chosen to suppress shot noise to εI and algorithmic error to εA.The measurement estimate also depends on the largest Pauli-term count NH appearing in the decompositions of HU, HV, and HD.
  • Open-system errors: Open-system simulation has three error sources: finite trajectory sampling, approximation of continuous and jump evolution, and errors in estimating jump probabilities and times.The continuous evolution uses generalised time evolution, while jump processes use matrix multiplication.
  • Error control: The trajectory-sampling error can be reduced with a number of samples proportional to a polynomial function of inverse accuracy, while the other two errors use the corresponding subroutine analyses.The jump count is analyzed separately to complete the resource estimate.

Number of jumps

The jump-process analysis estimates trajectory cost from continuous evolution, jump events, and random-trajectory sampling, with jump counts controlled by Lindblad-operator structure.

  • Trajectory cost: Each stochastic Schrödinger trajectory combines continuous evolution with jump processes, and both components have costs polynomial in evolution time and system size.Each jump is simulated using variational real and imaginary time evolution.
  • Average jump count: For physical systems with polynomially bounded Lindblad norms and term counts, the averaged number of jumps follows the resulting polynomial resource scaling.The cited analysis derives the average jump count from the Lindblad-operator norms and number of terms.
  • Overall scaling: The jump-process analysis therefore connects Lindblad structure and trajectory parallelism to the overall resource estimate for open-system simulation.The resource accounting includes both the average number of jumps and the number of sampled trajectories.
  • Local dissipation: The number of jumps is much fewer when every Lindblad operator acts only on a constant-size subsystem.This is a structural condition that reduces the jump-process burden.
  • Trajectory sampling: Suppressing observable sampling error to ϵ = 1/M requires M random trajectories, multiplying the overall cost by M.Because trajectories are exactly parallel, this overhead can be reduced by a constant factor.
Loading 1812.08778v4…