PaperlayerView exact revision on arXiv

Source-linked AI summary

Limitations of optimization algorithms on noisy quantum devices

Daniel Stilck Franca, Raul Garcia-Patron

arXiv:2009.05532v1quant-ph

TL;DR

The paper develops a framework for comparing noisy near-term quantum devices with classical algorithms using noise convergence, Gibbs-state assignments, and classical sampling. It finds little chance of advantage for classical optimization when device topology mismatches the problem, unless noise rates decrease substantially, while quantum many-body problems may offer an opportunity window.

  • Problem

    Whether near-term quantum devices can outperform classical methods for problems whose favorable low-depth quantum states may be difficult to rule out remains an important open question.

  • Method

    The framework combines contractivity results, mirror descent, Gibbs-state assignments, and efficient classical algorithms for approximating cost functions at high noise levels.

  • Results

    The analysis suggests little chance of near-term quantum advantage for classical optimization when problem topology does not match device architecture, because required depths scale with system size.

  • Takeaways & Limitations

    Quantum many-body problems may provide an opportunity window when device topology matches the Hamiltonian and system correlation length is bounded.

  • Takeaways & Limitations

    Post-processing noise mitigation would not change the framework’s predictions, while the usefulness of primitive error correction remains an open question.

Abstract

from arXiv · show

Recent technological developments have focused the interest of the quantum computing community on investigating how near-term devices could outperform classical computers for practical applications. A central question that remains open is whether their noise can be overcome or it fundamentally restricts any potential quantum advantage. We present a transparent way of comparing classical algorithms to quantum ones running on near-term quantum devices for a large family of problems that include optimization problems and approximations to the ground state energy of Hamiltonians. Our approach is based on the combination of entropic inequalities that determine how fast the quantum computation state converges to the fixed point of the noise model, together with established classical methods of Gibbs state sampling. The approach is extremely versatile and allows for its application to a large variety of problems, noise models and quantum computing architectures. We use our result to provide estimates for a variety of problems and architectures that have been the focus of recent experiments, such as quantum annealers, variational quantum eigensolvers, and quantum approximate optimization. The bounds we obtain indicate that substantial quantum advantages are unlikely for classical optimization unless the current noise rates are decreased by orders of magnitude or the topology of the problem matches that of the device. This is the case even if the number of qubits increases substantially. We reach similar but less stringent conclusions for quantum Hamiltonian problems.

I. AN INTRODUCTION TO THE TECHNIQUE

The framework recasts noisy quantum optimization outputs as Gibbs states and combines noise convergence, mirror descent, and classical Gibbs sampling to assess when classical simulation is efficient.

  • Problem formulation: Optimization problems can be written as minimizing tr(ρH), including probability-distribution problems and many-body ground-state problems.Here H is a Hermitian operator encoding the cost function.
  • Gibbs-state representation: Every Hamiltonian has Gibbs states σβ = e−βH/Zβ, ranging from the fully mixed state at β = 0 to the ground state at β = ∞.The parameter β is inverse temperature.
  • Core technique: The approach combines relative-entropy convergence, mirror descent, and efficient classical Gibbs-state sampling.Mirror descent assigns a Gibbs state to each noisy computation output with approximately the same cost-function value.
  • Interpretation: The framework analyzes noisy computation paths as Gibbs-state paths toward the noise fixed point and identifies regions admitting efficient classical simulation.For depolarizing noise, the fixed point is the maximally mixed state.
  • Core technique: For every noisy circuit output, an equivalent Gibbs state can approximate its cost with error ϵ∥H∥, typically corresponding to relative energy error ϵ.Relative-entropy convergence bounds the Gibbs-state parameter using circuit depth and noise.

C. Certifying classical superiority

The paper derives energy lower bounds that certify when classical Gibbs-sampling methods outperform noisy quantum circuits, then applies them to Ising optimization and MAXCUT architectures.

  • Certification method: Relative-entropy variational bounds convert approximate partition-function calculations and noise-convergence estimates into lower bounds on noisy-device energy.These bounds can certify that a classical method outperforms the quantum circuit.
  • Architectural estimates: With p1 = 1.6 × 10−3, p2 = 6.2 × 10−3, and pm = 3.8 × 10−2, estimated circuit limits are Dc ≈300 for two-qubit-dominated circuits and Dc ≈700 for one-qubit-dominated circuits.
  • Architectural estimates: For the SK model, the bound predicts roughly 20 qubits as a three-round QAOA limit, while experiments found no advantage over random guessing at size 17.
  • Architectural estimates: Depths Dc ≈150 for SK instances were consistently outperformed by polynomial-time Gibbs states, with the method predicting classical superiority beyond 10 qubits.
  • Certification method: The rigorous arbitrary-instance bound and sharper instance-specific bound complement each other when estimating the computation cycles a noisy quantum computer can sustain.
  • Architectural estimates: For sparse MAXCUT graphs, QAOA layers still scale in depth with n, requiring noise rates roughly two orders of magnitude lower to become competitive with classical methods.Current heuristic methods handle graphs with 10^3−10^4 nodes, while SDP solvers handle 10^4-node instances in seconds on a laptop.

III. VARIATIONAL QUANTUM EIGENSOLVERS

For VQE, classical thermal-state approximation is combined with noisy-circuit bounds to constrain achievable energies and the correlation lengths of prepared ground states.

  • VQE framework: VQE combines a classical variational procedure with quantum-circuit state preparation and energy measurement.
  • Classical comparison: For suitable local lattice Hamiltonians, classical methods can approximately compute partition functions in quasi-polynomial time over an allowed inverse-temperature range.
  • Implications: The resulting VQE depth bound has the same scaling as the optimization bound, so reducing noise is more important than increasing system size when VQE-layer depth scales with system size.
  • Implications: Noise limits the maximum correlation length ξ of ground states prepared by near-term circuits; when D < ξ, the output is far from the actual ground state in trace distance.

IV. NOISY QUANTUM ANNEALERS

The quantum-annealing analysis extends entropy-decay and Gibbs-state techniques to continuous-time noisy evolution, where dissipation drives states toward a fixed point.

  • Annealing model: Quantum annealers seek the ground state of a classical Ising Hamiltonian by adiabatically evolving from the ground state of a transverse-field Hamiltonian.
  • Annealing model: The spectral gap along the annealing path determines the required evolution speed, with rigorous runtimes generally scaling at least linearly in qubit number and inversely quadratically with the gap.
  • Noise model: The noisy continuous-time evolution is modeled by a time-dependent Lindbladian combining coherent dynamics with a time-independent dissipative thermalization term.
  • Noise model: The considered local noise has a product-state fixed point, while modified logarithmic Sobolev inequalities quantify relative-entropy decay toward that state.
  • Analysis: Theorem 1 bounds relative entropy after time t by an exponentially decaying initial contribution plus a term determined by the time-dependent Hamiltonian and fixed point.

B. Noise model

The noise model combines amplitude damping, dephasing, and control errors, driving the computation toward a noise-dependent fixed point. Bounds based on this convergence imply stringent limits on noisy adiabatic optimization, with current annealer estimates favoring only very short annealing times.

  • Noise sources: Amplitude damping, dephasing, and control errors are the principal noise sources considered for current quantum annealers.The fixed point depends on the amplitude-damping rate r1, dephasing rate r2, and control-error rate r3.
  • Noise fixed point: When r1 ≫ r3, the noise fixed point is essentially |0⟩, whereas r3 ≫ r1 yields a state close to maximally mixed.The corresponding modified log-Sobolev constant is α(r1, r3) = r1 + 2r3.
  • Adiabatic evolution: The analysis bounds relative entropy after evolving the initial |+⟩⟨+|⊗n state under the interpolating path for time T.The bound is applied to the noisy evolution generated along Hs.
  • Classical simulation: The noisy output energy can be approximated by sampling a classical Ising Gibbs state when λ ≤ f(γ, r, T, Γ)n.The approximation reaches energy accuracy ϵHI, and the same Ising mixing-time bounds can be reused.
  • Implications: The resulting bounds impose stringent constraints on noisy adiabatic quantum computers optimizing classical Ising Hamiltonians.Figure 2 illustrates the behavior of the bound.
  • Implications: For a commercially available annealer, the maximal useful annealing time is estimated at roughly 200µs, with a potential-advantage window requiring very short annealing times.The discussed experimental findings used 5µs and 20µs annealing times.

V. CONCLUSION AND OUTLOOK

The paper develops a framework combining noise-contraction bounds with Gibbs-state methods to assess noisy quantum optimization. It concludes that classical optimization advantages are unlikely without substantially lower errors or topology matching, while quantum many-body settings remain an open opportunity.

  • Framework: The framework combines noise contractivity, mirror descent, and Gibbs-state assignments to quantify noisy quantum-computation effects on optimization.These ingredients connect noisy evolution to classically analyzable states.
  • Framework: A second technique certifies when a classical algorithm outperforms a noisy quantum device at a specified depth or number of cycles.It uses a lower bound on the noisy device’s achievable energy and can sharpen estimates for specific instances.
  • Classical optimization: Noise rates would need to decrease two orders of magnitude before topology-mismatched classical optimization proposals become potentially competitive with state-of-the-art classical methods.The conclusion links topology mismatch to depths scaling with system size.
  • Quantum many-body problems: Near-term devices may have an opportunity window for quantum many-body problems when architecture topology matches the Hamiltonian and correlation length is bounded.Whether such examples resist efficient classical simulation remains an open problem.
  • Limitations: The bounds are extremely conservative: practical Gibbs samplers may reach higher β, and state-independent entropy-contraction estimates may understate contraction.The method also struggles when amplitude damping makes the fixed point nearly pure and requires further analysis for nonuniformly contracting noise.
  • Outlook: Post-processing measurement outcomes to mitigate noise would not change the framework’s predictions because of the data-processing inequality.The paper points to primitive error correction and annealer embeddings as directions for further investigation.
  • Outlook: The technique may extend to analog quantum simulators, with the continuous-time result serving as a first step.Extensions to Fermionic problems are identified as future work.

SUPPLEMENTARY INFORMATION

The supplementary information develops the local-depolarizing-noise case and reviews relative-entropy tools used to prove the main bounds.

  • Supplementary scope: The supplement proves and discusses the bounds for local depolarizing noise while reviewing relative-entropy properties and contrasting them with trace-distance convergence.It also notes that analogous arguments apply beyond the maximally mixed fixed point in some propositions.

A. Relative entropy fundamentals

The supplementary material establishes relative-entropy facts, contraction bounds, and variational energy inequalities used to connect noisy quantum outputs with classical simulation and performance certification.

  • Relative-entropy fundamentals: Relative entropy is introduced for a full-rank reference state, alongside its data-processing and strong data-processing inequalities.Strong data processing captures strict contraction under a quantum channel.
  • Trace-distance comparison: Pinsker’s inequality converts relative-entropy bounds into trace-distance bounds, but the resulting convergence scaling differs from energy-approximation scaling.For a maximally mixed fixed point, trace-distance convergence can require logarithmic depth while energy approximation may need only constant depth.
  • Trace-distance comparison: Logarithmic time is genuinely necessary for the output to become close to maximally mixed, showing that the energy analysis is qualitatively different from mixing-to-maximally-mixed analysis.A similar distinction holds for the time needed for the output to become separable.
  • Variational energy bounds: The variational formulation of relative entropy lower-bounds the output energy of a noisy quantum device using partition-function information and entropy-convergence bounds.The resulting proposition applies to any reference state σ > 0 and β > 0.
  • Variational energy bounds: In the β →∞ limit, the variational inequality reduces to the lower bound tr(ρH) ≥ E0, where E0 is the ground-state energy.This connects the finite-temperature formulation to ground-state-energy approximation.
  • Circuit-depth bounds: For noisy depolarizing circuits, choosing Dmax = −log(ϵ−1)/log(1 − p) generally keeps the output energy within O(ϵn) of the maximally mixed-state energy.Estimating this bound requires partition-function evaluation, which is efficient below a critical temperature in many models.

C. Proof of Lemma 2 for maximally mixed states

The paper combines relative-entropy bounds with classical optimization methods to certify when noisy quantum circuits cannot outperform classical algorithms. Applications to MAXCUT, QAOA, and ground-state preparation show that circuit depth, noise, topology, and correlation length constrain achievable advantage.

  • Worked-through example: For MAXCUT on 3-regular graphs, SDP methods outperform the noisy circuit when the output relative entropy density is below approximately 0.4.Under the stated depolarizing-noise assumptions, the corresponding guaranteed-outperformance depth is roughly D ≃70.
  • Worked-through example: For larger MAXCUT instances, SDP is expected to outperform three QAOA rounds around system size 30 under a conservative relative-entropy-density threshold of 0.3.The estimate assumes each QAOA round has depth scaling like n and extrapolates thresholds observed around 0.35–0.4 for systems up to 20 qubits.
  • Correlation length and required circuit depth: States with long correlation lengths require circuit depth at least linear in the correlation length to reproduce ground states faithfully.At depths D ≤ ξ/2, the circuit is guaranteed to remain a constant distance from the ground state; low-energy short-correlation excited states are not excluded.
  • Correlation length and required circuit depth: For some Ising instances, QAOA requires at least logarithmic depth to beat polynomial-time classical approximation algorithms, while noisy implementations can remain inferior even as noise decreases with system size.The paper also reports that ten QAOA rounds with depth mildly scaling in n would require extremely low noise rates to avoid certified classical superiority.
  • Correlation length and required circuit depth: Noisy circuits are more realistically expected to prepare short-correlation-length states, which tensor-network methods simulate efficiently and sequential preparation can produce more noise-robustly.This limits the prospects for noisy quantum advantage in optimizing ground states of local Hamiltonians.

VIII. GENERAL CIRCUITS

The framework constructs Gibbs states that match a noisy circuit’s energy for a target Hamiltonian, using relative entropy and mirror-descent updates. Matching the target energy does not generally imply reproducing the noisy output for other observables.

  • Generalization: Generalization beyond the maximally mixed fixed point enables the method to handle broader noise models and target states.The construction uses a full-rank fixed point σ and relative entropy D(Φ(ρ)||σ).
  • Energy approximation: The framework seeks a Gibbs state whose energy is within ε∥H∥ of the noisy circuit’s output for a target Hamiltonian.The state is treated as performing approximately as well as the noisy output for optimizing H.
  • Construction: Mirror descent updates the Gibbs Hamiltonian until the resulting state enters the set of states with approximately matching target energy.Each update moves the Gibbs state closer to the target in relative entropy while the energy condition remains unmet.
  • Limitation: The resulting Gibbs state need not approximate the noisy output for observables other than the target Hamiltonian.Additional expectation values would be required to ensure convergence beyond the energy observable.
  • Approximation guarantee: A sufficiently large update parameter can additionally guarantee a good global approximation to the noisy output.This occurs when the required λ is of order D(Φ(ρ)||σ0).

B. Entropic convergence in quantum circuits

The circuit analysis bounds relative-entropy convergence toward a noise channel’s fixed point using strong data-processing inequalities. The bounds extend to continuous-time evolutions and are especially effective for high-temperature fixed points or evolutions that approximately preserve the fixed point.

  • Discrete-time circuits: A strong data-processing inequality for the noise channel yields relative-entropy decay bounds through arbitrary interspersed quantum channels.The bound applies when the noise channel has fixed point σ and inequality constant α > 0.
  • Discrete-time circuits: The discrete-time result is useful when the fixed point is a high-temperature Gibbs state or when late-time circuit evolution approximately preserves it.In the doubly stochastic case, the fixed point is maximally mixed and D∞(Φ(σ)||σ)=0.
  • Continuous-time evolution: The framework generalizes from quantum circuits to quantum annealers with uniform noise and continuous-time Lindbladian evolution.The continuous-time extension uses fixed dissipative dynamics with a time-dependent Hamiltonian.
  • Continuous-time evolution: The continuous-time theorem performs well when the fixed point is high temperature or the Hamiltonian approximately commutes with it.In the commuting case, the evolution leaves the fixed point approximately invariant at the end of the computation.
  • Continuous-time evolution: Early-time contributions to the convergence bound can be exponentially suppressed, even for Gibbs states at very high inverse temperature.This behavior is illustrated for annealers preparing the ground state of a classical Hamiltonian with a diagonal fixed point.

B. Noise model for adiabatic quantum computation

The adiabatic-noise model combines amplitude damping, dephasing, and control errors in a local, uniform Lindbladian. Its fixed point and convergence rate depend primarily on the amplitude-damping and control-error rates under the stated assumptions.

  • Model assumptions: The model assumes no qubit cross-talk and represents each local Lindbladian term as acting on one qubit.The control error is modeled by white noise, while two-qubit control errors are set to zero.
  • Noise terms: The local noise model includes amplitude damping, dephasing, and control-error contributions with uniform rates r1, r2, and r3.The same rates are assumed on every qubit.
  • Fixed point: The fixed point approaches |0⟩ when r1 ≫ r3, becomes nearly maximally mixed when r3 ≫ r1, and is intermediate when r1 ≃ r3.The fixed point is obtained by solving Li(σ)=0 for the local evolution.
  • Convergence: The MLSI constant is α(r1,r3)=r1+2r3, while the dephasing rate r2 does not affect the fixed point or relative-entropy convergence.The analysis is therefore insensitive to r2 in its asymptotic convergence estimate.
  • Limitation: The convergence analysis is suboptimal at small times because the initial state is sensitive to dephasing, whereas late-time states are mostly diagonal.At large times, the convergence rate is of order r1+2r3 under the model.

C. Computations required for linear path

For a linear Hamiltonian path, the analysis bounds relative entropy after continuous-time evolution by combining commutation properties, the fixed-point parametrization, and the noise rates. The resulting expression depends on the evolution time and rates through exponential decay terms.

  • Path setup: Because HI commutes with the fixed point σ, the relative-entropy bound simplifies along the linear path.The initial state is |+⟩⟨+|⊗n and the fixed point is a tensor product determined by the noise model.
  • Derivation: The bound is obtained by integrating the continuous-time inequality and applying triangle inequalities to the commutator terms.The calculation uses that σ commutes with the Zi terms.
  • State parametrization: The fixed point is reparametrized using γ, allowing the commutator norm with Xi to be written as 2 sinh(γ).This substitution collects the state dependence into a single parameter.
  • Resulting bound: The relative entropy after time T is bounded by an expression whose noise dependence includes 1−e^−(r1+2r3)T and related exponential terms.The bound is denoted nf(γ, r, T, Γ) before being simplified in terms of the noise rates.
Loading 2009.05532v1…