PaperlayerView exact revision on arXiv

Source-linked AI summary

QAOA for Max-Cut requires hundreds of qubits for quantum speed-up

G. G. Guerreschi, A. Y. Matsuura

arXiv:1812.07589v1quant-phcs.PF

TL;DR

The paper asks whether noisy, pre-error-corrected quantum computers can provide practical speedups on hard combinatorial problems. It realistically simulates noisy QAOA for Max-Cut and compares its cost with classical solvers, estimating a crossover only between several hundreds and a few thousands of qubits. The estimate is constrained by extrapolation uncertainty and other scope limitations.

  • Problem

    The paper examines what quantum-computer size is needed for practical speedup on real applications during the NISQ era, where qubit count, quality, coherence, and connectivity are limited.

  • Method

    The study simulates noisy QAOA for Max-Cut using compiled circuits, stochastic noise, sampling, and classical optimization, then compares experimental-time costs with AKMAXSAT.

  • Results

    The estimated QAOA–classical performance crossover occurs between several hundreds and a few thousands of qubits for Max-Cut on random 3-regular graphs.

  • Takeaways & Limitations

    Classical solvers remain very competitive until several hundreds of variables, while QAOA speedup in absolute time is estimated only beyond the crossover point.

  • Takeaways & Limitations

    The crossover estimate is highly uncertain because noisy simulations are limited to 20–24 qubits and extrapolation depends strongly on the fitting function.

Abstract

from arXiv · show

Computational quantum technologies are entering a new phase in which noisy intermediate-scale quantum computers are available, but are still too small to benefit from active error correction. Even with a finite coherence budget to invest in quantum information processing, noisy devices with about 50 qubits are expected to experimentally demonstrate quantum supremacy in the next few years. Defined in terms of artificial tasks, current proposals for quantum supremacy, even if successful, will not help to provide solutions to practical problems. Instead, we believe that future users of quantum computers are interested in actual applications and that noisy quantum devices may still provide value by approximately solving hard combinatorial problems via hybrid classical-quantum algorithms. To lower bound the size of quantum computers with practical utility, we perform realistic simulations of the Quantum Approximate Optimization Algorithm and conclude that quantum speedup will not be attainable, at least for a representative combinatorial problem, until several hundreds of qubits are available.

The Quantum Approximate Optimization Algorithm

QAOA uses a shallow, problem-specific variational circuit with few adjustable parameters to approximately solve combinatorial optimization problems such as Max-Cut. Its circuit alternates problem and mixing operations, with depth and parameter count controlled by p.

  • The Quantum Approximate Optimization Algorithm: QAOA is a hybrid quantum-classical algorithm combining shallow quantum circuits with classical optimization of the circuit parameters.The algorithm is designed for pre-error-corrected quantum devices.
  • The Quantum Approximate Optimization Algorithm: QAOA approximately maximizes the number of simultaneously satisfied constraints in combinatorial problems.The maximization form of SAT asks for the largest number of constraints that can be satisfied at once.
  • The Quantum Approximate Optimization Algorithm: Max-Cut assigns one of two colors to each vertex so that as many graph edges as possible connect differently colored vertices.The objective is represented by a Hermitian operator built from graph-edge terms.
  • The Quantum Approximate Optimization Algorithm: The QAOA circuit repeats two quantum-operation blocks p times, where p is an adjustable parameter.The variational state is generated by alternating exponentials of the problem and mixing operators.
  • The Quantum Approximate Optimization Algorithm: 2p parameters and circuit depth scale lightly with problem size, while circuit depth is approximately linear in p.The mixing operator is the sum of X Pauli matrices associated with graph vertices.
  • The Quantum Approximate Optimization Algorithm: The study uses random 3-regular graphs, each having exactly three edges per vertex.Results may differ for other graph types.

Compiling and scheduling the quantum circuits

QAOA circuits must be compiled into executable schedules that respect logical dependencies, qubit exclusivity, and hardware connectivity. The study uses square-grid connectivity and SWAP-based routing, treating circuit depth as the key decoherence-related metric.

  • Compiling and scheduling the quantum circuits: Limited hardware connectivity necessitates an additional compilation step before QAOA circuits can execute.The scheduler converts the logical circuit into a hardware-compatible schedule.
  • Compiling and scheduling the quantum circuits: Valid schedules enforce logical gate dependencies, exclusive qubit activation, and connectivity requirements for two-qubit gates.Each qubit can participate in at most one gate at a time.
  • Compiling and scheduling the quantum circuits: Square-grid connectivity is handled with SWAP operations that route qubits while minimizing overall circuit depth.Single-qubit rotations, controlled-phase gates, and SWAP gates are assumed to have equal duration.
  • Compiling and scheduling the quantum circuits: Circuit depth matters more than gate count when decoherence, rather than imperfect control pulses, is the main error source.A full schedule is provided for an 8-qubit QAOA instance with p = 4.

Quantum simulations with realistic noise

The study simulates noisy quantum circuits by adapting qHiPSTER with stochastic single-qubit noise gates that model decoherence and dissipation. It estimates QAOA costs through repeated noisy-state simulations and samples, while comparing them with classical solver costs.

  • Quantum simulations with realistic noise: Quantum-system simulation requires memory and operations that scale exponentially with the number of qubits.The adapted qHiPSTER simulator targets large parallel architectures.
  • Quantum simulations with realistic noise: The noise model applies independent single-qubit decoherence and dissipation between circuit gates through stochastic perturbations.Averaging stochastic pure-state trajectories is mathematically equivalent to obtaining the final density matrix.
  • Quantum simulations with realistic noise: The simulator accounts for parallel gates by extending noise-gate implementation to optimized schedules, reducing the number of noise gates simulated.The resulting pure-state simulation is repeated once per noise gate.
  • Quantum simulations with realistic noise: 10000 samples estimate the QAOA cost function at each variational iteration.Figure 1 separates classical simulation operations from experimental quantum-device operations.
  • Quantum simulations with realistic noise: Figure 2 compares AKMAXSAT with experimental QAOA costs at p = 4 and p = 8 on random 3-regular graphs.The extrapolated QAOA trends use 95% confidence intervals and should be interpreted qualitatively because they derive from small systems.

Computational time cost of QAOA

The study estimates QAOA’s experimental time per Max-Cut instance by combining realistic circuit execution costs with repeated parameter optimization and sampling. It uses Nelder-Mead optimization and aggressive superconducting-device timing assumptions.

  • Computational time cost of QAOA: QAOA computational cost is measured as the average experimental time to solve one noisy instance, not the classical time required to simulate it.The average uses 40 instances at each problem size.
  • Computational time cost of QAOA: Nelder-Mead is used because QAOA has relatively few parameters and gradient estimation has high sampling cost.The method is gradient-free and uses reflection, expansion, contraction, and shrinkage parameters.
  • Computational time cost of QAOA: Each instance uses randomized optimization runs because each run is substantially a local optimization and may require hundreds of variational iterations.Each run is limited to 300 simplex updates and may stop earlier after 10p unchanged updates.
  • Computational time cost of QAOA: 20 optimization runs, hundreds of function evaluations per run, and 10000 statistical repetitions determine the number of coherent quantum-computation repetitions per instance.This multiplicative structure makes sampling and optimization part of the experimental cost.
  • Computational time cost of QAOA: A single repetition lasts for state preparation, sequential gate operations, and measurement.The study expresses this duration using preparation time, circuit depth, average gate duration, and measurement time.
  • Computational time cost of QAOA: The timing assumptions are TP + TM = 1 µs, TG = 10 ns, T2 = 100 µs, and T1 = 200 µs.These values are described as realistic but aggressive projections for superconducting circuits.

Classical alternative

The study uses AKMAXSAT as a state-of-the-art classical baseline for comparing QAOA on Max-Cut. Max-Cut instances are reduced to Max-2-SAT so the solver can address the same problem family.

  • AKMAXSAT is selected as an openly available, state-of-the-art Max-SAT solver used in quantum-optimization benchmarks.
  • Any Max-Cut instance can be reduced to Max-2-SAT by mapping vertices to binary variables and edges to two constraints.
  • The classical timing is averaged over 400 Max-Cut instances, with each instance run separately on one of 68 processor cores.

Comparison and performance crossover

QAOA remains slower than classical solving at small sizes, and extrapolation places a possible crossover only at hundreds to thousands of qubits. This estimate is constrained by limited simulation sizes, approximate-solution quality, circuit depth, and differing benchmarking assumptions.

  • 20 qubits of QAOA takes enough time for AKMAXSAT to solve graphs with about 20 times more nodes, implying no advantage without hundreds of qubits.The comparison uses relatively weak noise with T2 = 10,000 × TG and about 100 × TM.
  • Several hundreds to a few thousand qubits are estimated for a quantum–classical performance crossover, based on exponential QAOA-cost extrapolation with a 95% confidence interval.
  • Extrapolation beyond 20–24 qubits may be unreliable because noisy simulations are computationally demanding and results depend strongly on the fitting function.
  • QAOA is not guaranteed to find the best solution, so computational time must be considered alongside approximate-solution quality.For 20 qubits and p = 4, the final-state overlap with the global solution is around 10%.
  • The fitted exponential coefficient rises from 0.0141 at p = 4 to 0.0159 at p = 8, potentially compromising speedup before crossover.The corresponding AKMAXSAT coefficient is 0.0409.
  • A contrasting study separates parameter optimization from solving each instance, making its comparison base different from this study’s benchmark.

DISCUSSION

The paper distinguishes artificial quantum-supremacy milestones from practical computational advantage and evaluates realistic QAOA performance on Max-Cut. It concludes that classical solvers remain competitive until hundreds of variables, while multi-device parallelism has important limits.

  • Quantum supremacy targets tasks designed to be infeasible for classical machines, whereas practical users seek faster solutions or better approximate solutions.
  • The simulations model QAOA for Max-Cut with noisy circuits decomposed into one- and two-qubit gates scheduled on a two-dimensional square grid.
  • Classical solvers remain competitive until several hundreds of variables, with QAOA’s absolute-time crossover estimated between several hundreds and a few thousand qubits.
  • Multiple quantum devices can parallelize instances and optimization runs, but sequential function evaluations and calibration differences limit useful parallelism.

I. CONVERGENCE OF SIMULATIONS WITH NOISE

The simulations model realistic noise and hardware connectivity by averaging stochastic perturbations and compiling QAOA circuits onto a square grid. Convergence requires hundreds of noise realizations, while extra physical qubits can be omitted under the assumed uncorrelated noise model.

  • Noise simulation: Noise is modeled by adding stochastic noise gates to ideal circuits and averaging many perturbations to capture decoherence and relaxation.Each perturbation adds one noise gate per algorithmic gate, doubling simulator operations before the averaging overhead.
  • Noise simulation: Several hundred stochastic perturbations are needed for convergence at realistic noise levels.At TG/T2 = 500, approximately 400 realizations reach the same asymptotic value across random seeds.
  • Noise assumptions: The noise level is parameterized by T2/TG, with superconducting-device values T2 = 100 µs, T1 = 200 µs, and TG = 10 ns corresponding to T2/TG = 10000.The model assumes T1 is twice T2.
  • Circuit scheduling: Circuit schedules encode physical-qubit placement and clock cycles, using positive entries for algorithm gates and negative entries for routing SWAP gates.The schedule must respect gate dependencies, exclusive qubit activation, and connected-qubit constraints.
  • Additional qubits: For two-dimensional grids, routing may involve ancilla qubits, but the simulation retains only the N logical qubits when noise lacks spatial or temporal correlations.Logical and ancilla registers remain separable through SWAP operations under the stated model.

V. STATISTICS FOR QAOA RESULTS

QAOA runtime statistics average the costs of multiple randomized optimization runs across Max-Cut instances. Reported error bars quantify variation in per-instance cost, and the standard deviations are smaller than the plotted markers.

  • Cost estimation: Each Max-Cut instance cost sums multiple randomized optimization runs, retaining the run with the best approximation ratio.Multiple starts help avoid being misled by local maxima, although all runs contribute to the total cost.
  • Cost estimation: 40 instances are averaged at each system size because optimization landscapes produce different costs even for graphs with the same number of qubits.Variation reflects differences in smoothness and the number of local maxima.
  • Uncertainty: The reported error bar is derived from the statistical deviation of single-instance costs around the average.The supplied passage introduces the standard-error calculation but does not include its complete equation.
  • Uncertainty: The standard deviation for each plotted point is smaller than the marker in Figure 2, so the values are reported separately in Table I.Table I gives average single-instance QAOA costs and corresponding standard deviations in seconds.

VI. AKMAXSAT RUNNING TIMES

AKMAXSAT solves Max-Cut by reducing graph edges to pairs of Boolean clauses and is benchmarked through averaged absolute runtimes. The resulting runtime data are fitted exponentially as graph size increases.

  • Max-Cut reduction: Each Max-Cut edge becomes two Max-2-SAT clauses, so a graph with E edges yields 2E clauses.Both clauses are satisfied exactly when the edge is cut.
  • Max-Cut reduction: The Boolean reduction assigns one binary variable to each graph vertex and uses complementary clauses to encode whether an edge is cut.For an edge between x1 and x2, the clauses are (x1 ∨ x2) and (¬x1 ∨ ¬x2).
  • Runtime benchmark: AKMAXSAT runtime is measured as absolute time for one Max-Cut instance, averaged over 400 instances on a single Intel Xeon Phi 7250 node.The benchmark uses 68-core Knights Landing hardware.
  • Runtime scaling: An exponential fit describes AKMAXSAT computational cost as the number of graph nodes increases, with regression value R2 = 0.9963.The node count corresponds to the logical-qubit count used by QAOA.
Loading 1812.07589v1…