PaperlayerView exact revision on arXiv

Source-linked AI summary

Approximating the quantum approximate optimization algorithm with digital-analog interactions

David Headley, Thorge Müller, Ana Martin, Enrique Solano, Mikel Sanz, Frank K. Wilhelm

arXiv:2002.12215v3quant-ph

TL;DR

Near-term combinatorial optimization motivates QAOA, a heuristic algorithm for noisy devices. This paper combines QAOA with digital-analog computation and finds that, for realistic device parameters, digital-analog errors do not adversely affect its performance, with variational QAOA retaining function in some regimes where non-variational sequences have low fidelity.

  • Problem

    QAOA addresses combinatorial optimisation on noisy, pre-error-correction devices, where near-term algorithms are expected to be heuristic rather than provably guaranteed.

    Source: §I · p. 1

  • Method

    The paper applies QAOA using digital-analog computation and examines its performance through simulations and analytical error bounds.

    Source: §I · p. 2, §IX · p. 11

  • Results

    For realistic device parameters, digital-analog errors do not adversely affect QAOA, and variational QAOA retains function in regimes where non-variational algorithms have low fidelity.

    Source: §I · p. 2, B. Variational Resilience of DA-QAOA… · p. 10

  • Takeaways & Limitations

    Digital-analog computation can reduce device-control complexity, and its errors can be non-fatal to variational algorithms.

    Source: §XI · p. 14

    Compilation time grows correspondingly large if an individual resource coupling becomes especially small.

    Source: §VI · p. 7

Abstract

from arXiv · show

The quantum approximate optimisation algorithm was proposed as a heuristic method for solving combinatorial optimisation problems on near-term quantum computers and may be among the first algorithms to perform useful computations in the post-supremacy, noisy, intermediate scale era of quantum computing. In this work, we exploit the recently proposed digital-analog quantum computation paradigm, in which the versatility of programmable universal quantum computers and the error resilience of quantum simulators are combined to improve platforms for quantum computation. We show that the digital-analog paradigm is suited to the variational quantum approximate optimisation algorithm, due to its inherent resilience against coherent errors, by performing large-scale simulations and providing analytical bounds for its performance in devices with finite single-qubit operation times. We observe regimes of single-qubit operation speed in which the considered variational algorithm provides a significant improvement over non-variational counterparts.

I. INTRODUCTION

The paper presents digital-analog QAOA as a fit for near-term optimization, arguing that its variational nature makes the added digital-analog errors less damaging. It describes how always-on resource interactions can implement the required problem Hamiltonians with reduced control requirements.

I. INTRODUCTION

  • QAOA is a discrete-time hybrid quantum-classical algorithm for combinatorial optimisation, motivated by the need for algorithms that can run on noisy, pre-error-correction devices.The introduction frames near-term algorithms as heuristic rather than provably guaranteed.Source: §I · p. 1
  • For realistic device parameters, the paper reports that digital-analog errors do not adversely affect QAOA, making the combination synergistic.The paper attributes the relative resilience of the approach to QAOA's variational nature.Source: §I · p. 2

II. THE DIGITAL-ANALOG QUANTUM COMPUTATIONAL PARADIGM

  • Digital-analog computation combines analog resource interactions with digital single-qubit operations; sDAQC alternates them, while bDAQC leaves the resource interaction on during gates.The proposed always-on scheme trades reduced device-control requirements for coherent errors from simultaneous operations.Source: Figure 1 · p. 2, §II · p. 3
  • The construction uses a fixed ZZ resource to simulate problem Hamiltonians, surrounding resource interactions with selected single-qubit X operations to realize distinct couplings.For an arbitrary Hamiltonian, the procedure uses n(n −1)/2 resource-interaction intervals, with adjacent X operations sometimes canceling.Source: §II · p. 3
  • The effective Hamiltonians are linearly dependent at n = 4, but the paper reports linear independence for n > 4.The authors characterize the four-qubit case as special and note that QAOA problems of interest exceed that size.Source: §II · p. 4
  • Negative compiled interaction times are experimentally impossible; the paper uses time periodicity to eliminate them for the stated problem classes.The introduction says any two-local problem can be solved with a homogeneous resource interaction, while periodic problems such as MAX-CUT and MAX-2-SAT can use heterogeneous interactions.Source: §I · p. 2, §II · p. 4

III. NEGATIVE DIGITAL-ANALOG BLOCK TIMES

Negative digital-analog block times can be corrected using periodicity for homogeneous resources and a sign adjustment for relevant inhomogeneous cases. The correction is conditional, and alternatives are needed for targets outside the stated constraints.

III. NEGATIVE DIGITAL-ANALOG BLOCK TIMES

  • For a homogeneous resource, negative block times can be replaced by their values modulo 2π, but this may lengthen the schedule and increase error rates.The overhead can be large when a small negative interval is replaced by a time near 2π.Source: §III · p. 4
  • The proposed correction uses an additional idle block based on the common-eigenvector property of the matrix relating time blocks to the simulated Hamiltonian.Applying all possible two-qubit-X-surrounded blocks for equal times leaves a smaller homogeneous effective interaction.Source: §III · p. 4
  • For MAX-CUT and MAX-2-SAT, whose ZZ couplings are integer multiples of 1/2 or zero, reversing the target-Hamiltonian sign enables a positive idle-time correction with an inhomogeneous resource.The sign change is absorbed into the matrix defining the time blocks, making its relevant eigenvalue negative.Source: §III · p. 5
  • For targets outside the stated constraints, the authors suggest multiple DA sequences or more analog blocks, the latter requiring constrained quadratic programming.The approach decomposes arbitrary Ising Hamiltonians into resource-interaction blocks surrounded by single-qubit rotations.Source: §III · p. 5

IV. THE QUANTUM APPROXIMATE OPTIMISATION ALGORITHM

QAOA uses a hybrid quantum-classical loop to seek solutions to combinatorial optimisation problems. The section introduces low-order problem encodings and notes that near-term instances are small relative to classically tractable and competition-scale problems.

IV. THE QUANTUM APPROXIMATE OPTIMISATION ALGORITHM

  • A QAOA run alternates problem and driver Hamiltonians p times from |+⟩^n, then measures all qubits; a classical optimiser updates 2p parameters using the measured objective value.The expectation-value and parameter-update loop continues until a satisfactory string is found or a fixed run time ends.Source: Figure 3 · p. 5, §IV · pp. 5–6, Figure 4 · p. 5
  • MAX-CUT and MAX-2-SAT fit the section’s two-local setting: clauses involving at most two bits can be represented with ZZ interactions and single-qubit Z rotations.MAX-CUT clauses encode XOR edges; MAX-2-SAT includes four two-bit OR clause forms, represented with Z-type operators.Source: §IV · p. 6
  • Problems requiring terms higher than two are generally out of reach of NISQ computers, while reductions to MAX-CUT or MAX-2-SAT may increase clauses and variables substantially.The cited NP-completeness reductions are therefore described as unlikely to yield useful NISQ implementations.Source: §IV · p. 6
  • For instances small enough to fit on near-term quantum computers, classical brute force is easy; the paper says whether NISQ heuristics compete at 100–10,000 bits remains unknown.The largest QAOA problem cited here had 23 qubits, while the brute-force estimate for a supercomputer running a day is roughly 70–80 bits.Source: §IV · p. 6

V. DIGITAL ANALOG QAOA

DA-QAOA applies the digital-analog paradigm to approximate QAOA. The section describes two control schemes and how their single-qubit driving and resource-interaction times implement a layer.

V. DIGITAL ANALOG QAOA

  • In stepwise DA-QAOA, f, x_i, and z_i are controllable binary parameters; in banged DA-QAOA, f stays at 1 while only single-qubit parameters vary.The single-qubit terms are stronger than the resource interaction by α, expected typically between 10 and 1000 depending on architecture.Source: §V · p. 7
  • A driver interval lasts β/α, and each resource block uses single-qubit X rotations to steer the interaction toward the required problem Hamiltonian.A full X gate before and after a resource block takes Δt = π/α.Source: §V · p. 7
  • The layer’s total device time combines the nonnegative DA block times scaled by γ with the driving time β/α.The time-ordered device evolution also uses the previously determined control functions for the problem being solved.Source: §V · p. 7

VI. COMPILATION COSTS OF DA-QAOA

This section compares the on-device time and compilation costs of digital-analog QAOA with digital implementations, while cautioning that runtime indicates fidelity only for coherence-limited devices. Resource-coupling variation is usually manageable, but very weak individual couplings can sharply increase compilation time.

VI. COMPILATION COSTS OF DA-QAOA

  • On-device time indicates fidelity or solution quality only when the device is coherence-limited; contemporary processors are typically limited by two-qubit-operation errors instead.Comparing DAQC and DQC performance therefore requires device-specific error-mechanism analysis.Source: §VI · p. 7
  • Digital compilation needs at most the problem graph’s maximum vertex degree plus one time-steps, whereas DAQC time-averages its resource interaction across many time-blocks.For the illustrated 5-regular graph, the digital circuit has six time-steps; DA can be faster for sufficiently fast X gates.Source: §VI · p. 7, Figure 6 · p. 8
  • Small coupling deviations do not greatly affect compiled time, but an especially small individual coupling makes compilation time correspondingly large.The comparison scales couplings to give the resource Hamiltonians the same average coupling; the power-law cases assume qubits in a linear array.Source: §VI · p. 7
  • The compilation’s asymptotic scaling is at worst O(n^2), because simulating arbitrary Hamiltonians requires n(n −1)/2 interaction windows.Source: §VI · pp. 7–8
  • For an 8-qubit, 5-regular MAX-CUT instance, bDAQC takes 5tint versus sDAQC’s 5tint + 21tX, using 49 versus 50 single-qubit-X operations.The bDAQC compilation approximates the QAOA problem-Hamiltonian evolution; with infinitely fast X gates, it is equivalent to the other compilations.Source: Figure 6 · p. 8

VII. HIGH-CONNECTIVITY NISQ HARDWARE PLATFORMS FOR DA-QAOA

DA-QAOA hardware for a broad range of combinatorial problems needs high connectivity to avoid swaps. Candidate platforms differ in native connectivity and coupling homogeneity, both relevant to compilation time and near-term feasibility.

VII. HIGH-CONNECTIVITY NISQ HARDWARE PLATFORMS FOR DA-QAOA

  • A QAOA device handling a wide variety of combinatorial problems needs high connectivity to avoid swaps, since swaps add circuit depth and decoherence.The text expects swap-using algorithms to be out of reach for realistic near-term hardware, whether compiled digitally or into digital-analog blocks.Source: §VII · pp. 8–9
  • For random Erdős-Rényi MAX-CUT instances at filling factor 0.75, a homogeneous resource is competitive with idealized digital compilation, while inverse-power-law couplings require extremely large times.The homogeneous series is higher than idealized digital compilation for qubit numbers above 10; its periodicity can reduce idle time.Source: Figure 7 · p. 9
  • Superconducting solid-state architectures are described as poor current DA-QAOA candidates because of low connectivity, while Rydberg arrays and trapped-ion architectures offer native all-to-all interactions.Rydberg interactions are highly non-homogeneous; trapped-ion coupling profiles vary with the interaction mechanism.Source: §VII · p. 9
  • Trapped-ion systems have high-fidelity two-qubit operations and long coherence, but frequency crowding limits high-fidelity operation as many ions are loaded into a trap.Relaxing control over individual ion interactions allows trapped-ion platforms to perform exceptionally as simulators.Source: §VII · p. 9

VIII. RESULTS

The results section compares bDA-QAOA with standard QAOA on randomly generated problems, then examines its performance relative to expectations for a banged digital-analog algorithm. It attributes the observed performance boost to the algorithm’s variational freedom.

VIII. RESULTS

  • The results section compares bDA-QAOA performance with a standard QAOA circuit on selected randomly generated problems.Source: §VIII · p. 9
  • A second analysis examines whether bDA-QAOA performs better than expected for a banged digital-analog algorithm.Source: §VIII · p. 9
  • The section attributes the performance boost to bDA-QAOA’s variational freedom.Source: §VIII · p. 9

A. Performance of bDA-QAOA

With a nonproblem-specific resource Hamiltonian, bDA-QAOA performs similarly to error-free QAOA at high α, shows minor mean-approximation-ratio increases at intermediate α, and performs worse at low α. The low-α degradation is attributed to coherent-error-induced problem misspecification.

A. Performance of bDA-QAOA

  • When the resource Hamiltonian matches the problem Hamiltonian, simulations show no discernible net-negative impact relative to error-free QAOA.In this setting, no DA steering single-qubit operations are required.Source: A. Performance of bDA-QAOA · p. 10
  • At high α, bDA-QAOA matches error-free QAOA; at intermediate α it shows minor mean approximation ratio increases, while at low α it consistently performs worse.The low-α outcome is attributed to problem misspecification induced by coherent DAQC errors.Source: A. Performance of bDA-QAOA · p. 10
  • A nonproblem-specific resource Hamiltonian introduces coherent errors that make the ansatz less problem-specific and are expected to lower its approximation ratio at a given depth.Source: A. Performance of bDA-QAOA · p. 10

B. Variational Resilience of DA-QAOA to DA Errors

QAOA’s classical optimizer can accommodate some coherent errors introduced by bDAQC, but its ability to recover performance depends on the single-qubit speed regime. At sufficiently low α, the authors interpret the loss of recovery as a barren-plateau effect.

B. Variational Resilience of DA-QAOA to DA Errors

  • QAOA’s classical optimizer can compensate for systematic coherent over- or under-rotations, motivating its expected error tolerance.The bDAQC ansatz changes the operators, so parameters optimal for ideal QAOA need not remain optimal for bDAQC.Source: B. Variational Resilience of DA-QAOA… · p. 10
  • At intermediate α, variational freedom lets QAOA retain performance despite DA-induced coherent errors that impair a fixed gate sequence.At high α, both approaches perform similarly; at sufficiently low α, even parameter optimization fails to recover performance.Source: B. Variational Resilience of DA-QAOA… · p. 10
  • At low enough α, gradients become prohibitively small and the approximation ratio varies little across parameter choices.The authors interpret this as the DA-QAOA ansatz losing specificity to the problem Hamiltonian and behaving no better than a random-circuit ansatz.Source: B. Variational Resilience of DA-QAOA… · p. 10

IX. ANALYTICAL FIDELITY BOUNDS FOR bDA-QAOA

The section bounds the fidelity loss from banged digital-analog QAOA relative to error-free QAOA. Under the considered homogeneous-resource analysis, high fidelity for large n requires single-qubit gates to speed up approximately quadratically with qubit count.

IX. ANALYTICAL FIDELITY BOUNDS FOR bDA-QAOA

  • The fidelity bound compares bDA-QAOA states with error-free QAOA states using a Trotter-error bound for sequential versus simultaneous Hamiltonian evolution.The digital-analog case reverses the usual Trotterization roles: sequential evolution is ideal and simultaneous evolution introduces error; the bound allows arbitrarily large time steps.Source: §IX · pp. 10–11
  • The bound accounts for n(n + 1)/2 + 2 error-producing periods, including single-qubit-operation blocks, an idle block, and the driver.The blocks contain differing numbers of active single-qubit rotations, and each block takes time t = π/α.Source: §IX · p. 11
  • Figure 9 compares optimized bDA-QAOA with bDA-QAOA at parameters optimized for error-free QAOA, highlighting regimes where variational freedom accounts for differences from the ideal algorithm.Figure 8 instead plots the percentage difference in mean approximation ratio between bDA-QAOA and error-free QAOA across 50 MAX-CUT problems with pclause = 0.7.Source: Figure 8 · p. 11, Figure 9 · p. 12
  • For large n, single-qubit gates must speed up approximately as the number of qubits squared to maintain high fidelity with the ideal QAOA state.The estimate assumes a homogeneous resource Hamiltonian; heterogeneous resources can be handled by summing Pauli-string terms with their non-unit prefactors.Source: §IX · p. 13

X. SENSITIVITY TO OTHER ERRORS

The section assesses how other NISQ errors affect digital-analog QAOA. Single-qubit errors remain consequential, while avoiding direct two-qubit gates reduces sensitivity to two-qubit control errors compared with compiled QAOA.

X. SENSITIVITY TO OTHER ERRORS

  • Single-qubit decoherence and rotation-axis errors have full impact, while some rotation-angle errors can be accommodated by classical optimization.The authors characterize single-qubit errors as having the same, if somewhat smaller, impact as in compiled gate-model QAOA.Source: §X · p. 13
  • Avoiding direct two-qubit gates removes their control errors and fast-control noise entry points, but problem-Hamiltonian entanglement can still accelerate decay.The authors say sensitivity to two-qubit errors is lower than in compiled QAOA; an n-qubit GHZ state dephases in time T2/n.Source: §X · pp. 13–14
  • The authors expect coherent-over-rotation errors to be represented by measured fidelity because the problem Hamiltonian randomizes states and structured interference is unlikely.This is presented as an expectation about the error estimate, not as a general guarantee.Source: §X · p. 14

XI. CONCLUSION

The conclusion presents digital-analog computation as an alternative to standard gate-based quantum computing that can reduce control complexity while introducing errors that need not be fatal to variational algorithms.

XI. CONCLUSION

  • Digital-analog computation may reduce the complexity of controlling system evolution, while its own errors can remain non-fatal to variational algorithms.The conclusion frames this as a possibility for an alternative computational model, rather than a claim of error-free operation.Source: §XI · p. 14
Loading 2002.12215v3…