PaperlayerView exact revision on arXiv

Source-linked AI summary

Error corrected quantum annealing with hundreds of qubits

Kristen L. Pudenz, Tameem Albash, Daniel A. Lidar

arXiv:1307.8190v1quant-ph

TL;DR

Quantum annealing requires error correction because thermal excitations, non-adiabatic transitions, and implementation inaccuracies can produce computational errors. This paper develops quantum annealing correction by combining encoding, penalties, and decoding, and demonstrates improved performance on processors using up to 344 superconducting flux qubits. Complete QAC achieved fidelity above 90% for all tested chain lengths at α = 1.

  • Problem

    Quantum annealing lacks established protection against computational errors caused by closing gaps, thermal excitations, and implementation inaccuracies.

  • Method

    Quantum annealing correction combines logical-qubit encoding, an energy penalty, and majority-vote decoding to address bit-flip errors.

  • Results

    Fidelity exceeded 90% for all tested chain lengths at α = 1 with complete QAC, improving significantly over the other strategies.

  • Takeaways & Limitations

    The demonstration supports noise-protected programmable quantum annealing using large superconducting-qubit processors.

Abstract

from arXiv · show

Quantum information processing offers dramatic speedups, yet is famously susceptible to decoherence, the process whereby quantum superpositions decay into mutually exclusive classical alternatives, thus robbing quantum computers of their power. This has made the development of quantum error correction an essential and inescapable aspect of both theoretical and experimental quantum computing. So far little is known about protection against decoherence in the context of quantum annealing, a computational paradigm which aims to exploit ground state quantum dynamics to solve optimization problems more rapidly than is possible classically. Here we develop error correction for quantum annealing and provide an experimental demonstration using up to 344 superconducting flux qubits in processors which have recently been shown to physically implement programmable quantum annealing. We demonstrate a substantial improvement over the performance of the processors in the absence of error correction. These results pave a path toward large scale noise-protected adiabatic quantum optimization devices.

I. INTRODUCTION

Quantum annealing applies quantum superposition and tunneling to difficult optimization problems, but large-scale operation requires error correction. This work develops and experimentally demonstrates correction for programmable quantum annealing using up to 344 superconducting flux qubits.

  • Quantum annealing seeks low-energy solutions by exploiting quantum superpositions and tunneling to escape local minima.
  • Programmable quantum annealers are physical realizations of quantum annealing and adiabatic quantum computation for optimization.
  • 344 superconducting flux qubits were used to experimentally demonstrate error correction in D-Wave processors implementing programmable quantum annealing.
  • The work addresses the limited applicability of existing error-correction demonstrations and adiabatic methods to programmable quantum annealers.

II. QUANTUM ANNEALING AND COMPUTATIONAL ERRORS

Quantum annealing encodes optimization problems in Ising-model ground states and evolves qubits toward those states. Small energy gaps, thermal excitations, and implementation inaccuracies can produce computational errors.

  • Many difficult optimization problems can be represented by the ground state of an Ising Hamiltonian.
  • Programmable quantum annealing replaces classical binary variables with quantum binary variables governed by a time-dependent Hamiltonian.
  • Adiabatic evolution reaches the target ground state with high fidelity when the minimum gap is sufficiently large relative to annealing time and temperature.
  • Hard problems can have polynomially or exponentially closing gaps, allowing non-adiabatic transitions and thermal excitations to create excited final states.
  • Even with a sufficiently large gap, inaccuracies in implementing the Ising Hamiltonian can leave the evolution in the wrong ground state.

III. QUANTUM ANNEALING CORRECTION

Quantum annealing correction combines encoding, an energy penalty, and post-readout decoding to protect against bit-flip errors. The encoded construction preserves the original problem’s ground state while increasing problem energy and enabling recovery from some excited states.

  • III. QUANTUM ANNEALING CORRECTION: Quantum annealing correction encodes the Ising problem, adds an energy penalty, and performs error correction using controllable pairwise Ising interactions.
  • III. QUANTUM ANNEALING CORRECTION: The encoded ground state is identical to the original unencoded Ising ground state when expressed in code states.
  • III. QUANTUM ANNEALING CORRECTION: Encoding increases the problem energy scale by n, with n = 3 in the D-Wave implementation, and majority-vote decoding corrects some non-code states.
  • III. QUANTUM ANNEALING CORRECTION: The repetition code has minimum Hamming distance n, so states with more than floor(n/2) bit-flip errors are undecodable.
  • III. QUANTUM ANNEALING CORRECTION: Figure 2 compares unprotected, classical repetition-code, energy-penalty, and complete QAC strategies on antiferromagnetic chains.
  • III. QUANTUM ANNEALING CORRECTION: The ferromagnetic penalty couples problem qubits to a penalty qubit, energetically penalizing bit-flip errors and favoring agreement within each logical qubit.

IV. BENCHMARKING USING ANTIFERROMAGNETIC CHAINS

Antiferromagnetic chains provide a benchmark with simple, doubly degenerate ground states, allowing the experiment to isolate components of quantum annealing correction. The study compares unprotected, classical repetition, energy-penalty, and complete QAC strategies.

  • IV. BENCHMARKING USING ANTIFERROMAGNETIC CHAINS: Antiferromagnetic chains have two degenerate ground states with neighboring spins pointing in opposite directions.
  • IV. BENCHMARKING USING ANTIFERROMAGNETIC CHAINS: The unprotected strategy uses a single N-qubit antiferromagnetic chain without encoding or penalty.
  • IV. BENCHMARKING USING ANTIFERROMAGNETIC CHAINS: The classical strategy uses three parallel unpenalized chains and majority-vote decoding to form each logical bit.
  • IV. BENCHMARKING USING ANTIFERROMAGNETIC CHAINS: The energy-penalty strategy uses encoded chains with a penalty, while complete QAC adds majority-vote decoding.

V. KEY EXPERIMENTAL RESULTS – SUCCESS PROBABILITIES

Complete QAC substantially improves success probabilities over unprotected and partial strategies, achieving fidelity above 90% across all tested chain lengths at α = 1. Decoding is necessary because the energy penalty alone is insufficient.

  • Fidelity exceeds 90% for all chain lengths with complete QAC at α = 1, outperforming the three other strategies.
  • Relative improvement from QAC is highest at low α values.
  • Energy penalty alone is insufficient and must be supplemented by majority-vote decoding.
  • Success probability improves significantly across a range of α values, while unprotected chains follow a Lorentzian-like dependence on chain length.

VI. OPTIMIZING THE PENALTY SCALE β

The penalty strength β must balance gap enhancement against penalty domination and spectral reordering. Consequently, the optimal β depends on α, chain length, and whether decoding is used.

  • Increasing β enlarges the relevant excitation gap and shifts it earlier, but β ≪ α is ineffective while β ≫ α overwhelms the problem scale.
  • Without decoding, the optimum is expected near βopt ∼ α, whereas QAC requires a significantly lower βopt than EP.
  • QAC’s optimal β decreases with increasing α and chain length as domain-wall errors increasingly flip entire logical qubits, producing undecodable errors.

VII. ERROR MECHANISMS

Domain-wall errors explain declining success on longer chains and expose a limitation of majority-vote decoding. Decodability tracks Hamming distance more strongly than final-state energy, allowing some relatively high-energy states to remain decodable.

  • Most observed states are correctly decoded or differ from the ground state by only a few flipped bits, while a periodic pattern emerges at Hamming distance d ≥ 20.
  • Period-four structure reflects flipping integer multiples of logical qubits, with one flipped logical qubit triggering a cascade through neighboring qubits.
  • Flipped penalty qubits are essentially perfectly correlated with d = 3 errors in the 86-chain experiments.
  • Figure 4 compares EP and QAC success probabilities across β and chain length for α = 0.3, 0.6, and 1, with white dots marking optimal β values.
  • Majority-vote decoding corrects d = 1 errors but mishandles d = 2 errors and cannot decode dominant d = 3 domain-wall errors, which become logical errors.
  • Small Hamming distance correlates more strongly with decodability than final-state energy, so relatively high-energy final states can remain decodable.

VIII. CONCLUSION AND OUTLOOK

QAC reduces errors in programmable quantum annealing by combining encoding, energy penalties, and decoding. The conclusion identifies unknown-solution problems, stronger codes, and fault tolerance as key directions for extending the approach.

  • Conclusion: QAC significantly improves programmable quantum annealing performance on antiferromagnetic chains dominated by logical domain-wall errors.The conclusion attributes the improvement to the complete combination of encoding, an optimized penalty, and decoding.
  • Conclusion: Complete QAC combines increased problem energy scale, an optimum penalty strength β, and decoding of excited states to reduce errors.The complete strategy outperforms approaches that omit one or more of these steps.
  • Outlook: The demonstrated benchmark uses antiferromagnetic chains, while extending QAC to problems whose correct solution is unknown remains future work.The authors specifically identify decoding optimization as desirable in that setting.
  • Outlook: More efficient QAC-compatible codes are needed to handle larger-weight errors.The paper presents this as an important venue for future studies.
  • Outlook: Ultimately, scalable quantum annealing is linked to incorporating fault-tolerant error-correction techniques.The authors present this as a long-term goal rather than a demonstrated capability of the current work.

Appendix B: Proof that the encoded graph is non-planar

The encoded graph is shown to be non-planar by identifying a subgraph homeomorphic to K3,3. Path contractions transform an 18-qubit graph section into the required complete bipartite form.

  • Proof strategy: A subgraph homeomorphic to K3,3 is sufficient to prove that the encoded graph is non-planar.The proof uses paths within the graph as edges of the relevant subgraph.
  • Construction: The construction begins with an 18-qubit section of the regular encoded graph.The selected section is the starting point for the path-contraction sequence.
  • Construction: Repeatedly removing two edges and an intervening vertex, then replacing them with one edge, condenses paths in the encoded graph.These are the allowed moves used to preserve the relevant graph structure.

Appendix C: A classical independent errors model

The appendix models success decay in antiferromagnetic chains using independent classical kink errors, then shows that this explanation is insufficient and motivates an adiabatic master equation.

  • Independent-errors model: In an antiferromagnetic chain, errors are modeled as kinks, each representing a disagreement between neighboring spins.There are N−1 possible kink locations, and each kink costs energy 2α.
  • Independent-errors model: A state with k kinks has energy EN(k) = α(−N + 1 + 2k), with degeneracy determined by choosing kink locations.The model counts configurations by placing k kinks among N−1 nearest-neighbor slots.
  • Independent-errors model: The no-kink probability is obtained from the classical thermal-equilibrium distribution over kink configurations.The appendix derives this probability from the chain’s energies and degeneracies.
  • Model assessment: The classical independent-errors model misses the experimentally observed initial quadratic decay of success probability.The discrepancy indicates that uncorrelated classical errors do not capture the relevant mechanism.
  • Model assessment: An adiabatic master equation is introduced to capture the different error mechanism suggested by the data.The master-equation approach is developed in a later appendix section.

Appendix D: Comparison between the DW1 and DW2

The appendix compares DW1 and DW2 hardware, encoded graphs, schedules, and error-model results. DW1 broadly agrees with DW2, but missing penalty qubits, larger control errors, and smaller scale limit its performance and visible trends.

  • Encoded graphs: The encoded DW1 graph excludes logical qubits with defective data qubits and omits their corresponding couplings.These exclusions are marked by grey symbols in the encoded-graph figure.
  • Performance comparison: QAC outperforms the unprotected case at every tested problem scale α in the U and QAC comparison.The comparison is collected for α = 1, 0.6, and 0.3.
  • Performance comparison: DW1 results broadly agree with DW2, but missing penalty qubits and larger control errors produce lower success probabilities overall.DW1’s limit of at most 16 logical qubits also hides some larger-scale QAC trends.
  • Master-equation comparison: The adiabatic master equation reproduces the initial quadratic success-probability decay that the classical kink model misses.The calculation is compared directly with DW2 data for unprotected antiferromagnetic chains.

Appendix F: The role of the penalty qubit

The appendix analyzes how penalty qubits affect excitation gaps, error suppression, and decoding in encoded quantum annealing. Penalty terms can enlarge gaps and shift their minima, while decoding determines whether excited states remain recoverable.

  • The role of the penalty qubit: Penalty-coupled problem qubits have a smaller single-bit-flip probability than uncoupled problem qubits in simulations.This directly attributes error suppression to the penalty qubits.
  • The role of the penalty qubit: Low-lying excited states can decode to the correct ground state, keeping decoded success nearly constant even as physical ground-state probability changes.This explains why excitation does not always reduce the decoded outcome.
  • The role of the penalty qubit: At β ≥ 0.6, the two-penalty model’s first excited state becomes fully ferromagnetic and decodes to the incorrect ground state.The corresponding large drop occurs in decoded success probability rather than necessarily in physical ground-state probability.
  • The role of α: Increasing α shifts the minimum gap earlier in the evolution and increases its size for antiferromagnetically coupled chains.For linear schedules, smin = 1/(1 + α), and the numerical chain simulations verify both effects.
  • A single logical qubit: The penalty perturbation contributes positively to the gap throughout the evolution and shifts the minimum gap earlier for finite ω0.This result is shown for the single-logical-qubit model.
  • Three qubit pairs coupled to a penalty qubit: For coupled logical-qubit models, the penalty term increases the gap, while numerical antiferromagnetic-chain results also show a shift of the minimum gap to earlier times.The simpler incomplete model shifts the gap slightly right, so it does not reproduce the chain result’s timing shift.
Loading 1307.8190v1…