PaperlayerView exact revision on arXiv

Source-linked AI summary

Different Strategies for Optimization Using the Quantum Adiabatic Algorithm

Elizabeth Crosson, Edward Farhi, Cedric Yen-Yu Lin, Han-Hsuan Lin, Peter Shor

arXiv:1401.7320v1quant-ph

TL;DR

This numerical study examines whether strategies can improve QAA success on hard 20-qubit MAX 2-SAT instances with a unique optimum. It tests shorter evolution, excited-state initialization, and random local Hamiltonian terms; all three are reported to raise success on the selected hard instances. The authors caution that the strategies' value at larger bit counts remains uncertain.

  • Problem

    The study asks how to improve QAA success on hard, fixed-size instances, setting aside how runtime for a target success probability scales with input size.

    Source: §I · p. 2

  • Method

    The authors numerically studied QAA on 20-bit MAX 2-SAT instances with unique optima and tested shorter evolution, first-excited-state initialization, and random local Hamiltonian terms mid-evolution.

    Source: §II · p. 2, §I · p. 2

  • Results

    All 137 selected hard instances improved under shorter evolution, with minimum and median P(Tmax)/P(100) improvements of 108 and 809.

    Source: §III · p. 6

  • Takeaways & Limitations

    The three tested strategies consistently increased success probability on the selected hard instances, but the study does not establish their value at larger bit counts.

    Source: §I · p. 2, §VI · p. 16

    At n=20, the strategies' algorithmic value is uncertain because typical instances may already have low success at higher bit counts, even if the hardest cases improve.

    Source: §VI · p. 16

Abstract

from arXiv · show

We present the results of a numerical study, with 20 qubits, of the performance of the Quantum Adiabatic Algorithm on randomly generated instances of MAX 2-SAT with a unique assignment that maximizes the number of satisfied clauses. The probability of obtaining this assignment at the end of the quantum evolution measures the success of the algorithm. Here we report three strategies which consistently increase the success probability for the hardest instances in our ensemble: decreasing the overall evolution time, initializing the system in excited states, and adding a random local Hamiltonian to the middle of the evolution.

I. INTRODUCTION

The Quantum Adiabatic Algorithm encodes a classical optimization cost in a problem Hamiltonian and evolves a prepared state toward its ground state. This study fixes n=20 and examines three strategies for improving success on hard instances.

I. INTRODUCTION

  • The Quantum Adiabatic Algorithm encodes a classical cost function in a problem Hamiltonian whose ground state represents the minimizing bit string.The system begins in the ground state of a beginning Hamiltonian, traditionally HB, whose ground state is the uniform superposition of computational-basis states.Source: §I · p. 1
  • For a unique minimizing string w, the probability of obtaining w at the end of evolution measures success on that instance.The paper studies this probability rather than runtime scaling with input size.Source: §I · p. 2
  • The system evolves under a time-dependent Hamiltonian, and sufficiently long evolution from the ground state of HB yields large overlap with the ground state of HP.The adiabatic approximation requires a runtime bound involving the minimum gap between the ground state and first excited state.Source: §I · pp. 1–2
  • At n=20, three strategies increased success probability for every hard instance generated: shorter evolution, first-excited-subspace initialization, and random local Hamiltonian terms mid-evolution.The authors set aside the question of how runtime scales with input size.Source: §I · p. 2

II. INSTANCE SELECTION

The authors selected unique-optimum 20-bit MAX 2-SAT instances that were difficult for the QAA at T=100. A mean-field filter helped identify hard cases, which were rare in a separate 15,000-instance population.

II. INSTANCE SELECTION

  • Each candidate contained 60 distinct clauses over pairs of distinct bits, and was retained only if it had a unique assignment minimizing violated clauses.Unique optima avoided zero energy gaps from degenerate ground states and success probabilities that depend on the number of optimal solutions.Source: §II · p. 2
  • 137 instances met the hard-case cutoff P(100)<10^-4 after 202,078 instances were generated and screened.A mean-field approximation filtered candidates before numerical integration of the Schrödinger evolution; a separate 15,000-instance population showed that over half had P(100)>0.95.Source: §II · pp. 2–3, Figure 1 · p. 3

III. THE HARE BEATS THE TORTOISE

For these hard instances, shorter evolutions raise success probability: optimizing the evolution time improves every instance, and a fixed T = 10 also improves all. The results are linked to how the system moves through an avoided crossing.

III. THE HARE BEATS THE TORTOISE

  • For instance #1, success peaked at T = 12 with P(Tmax) = 0.05, versus P(100) = 5 × 10^-5 and P(200) = 5 × 10^-6.Figure 2 plots success probability against total evolution time.Source: §III · p. 4, Figure 2 · p. 4
  • During slow evolution, instance #1 follows the ground state before an avoided crossing near s = 0.66, then follows the first excited state with virtually no overlap with |w⟩.With rapid evolution, amplitude leaks into the first excited state before the crossing, increasing the final ground-state probability.Source: §III · pp. 4, 6, Figure 3 · p. 5, Figure 4 · p. 5
  • 108 minimum and 809 median improvement in P(Tmax)/P(100) occurred across the 137 hard instances, with every instance improved.Figure 6 compares P(Tmax) with P(100).Source: §III · p. 6, Figure 6 · p. 7
  • Although optimizing T improved all 137 instances, estimating each instance's Tmax in advance may not be efficient.Figure 7 shows the distribution of Tmax for these instances.Source: §III · p. 7, Figure 7 · p. 7
  • 15 minimum and 574 median improvement in P(10)/P(100) occurred across the instances, so a fixed short evolution improved every case.Figure 8 compares P(10) with P(100).Source: §III · p. 8, Figure 8 · p. 8

IV. GOING LOWER BY AIMING HIGHER

The authors directly test first-excited-state initialization on the 137 hard instances, finding average success near the probability-conservation ceiling for most instances.

IV. GOING LOWER BY AIMING HIGHER

  • The strategy initializes the system in each of the 20 first excited states of HB and evaluates success for the 137 hard instances.The paper reports both average success over the 20 states and each instance’s maximum success.Source: §IV · p. 8
  • Average success probability was near 1/20 for most hard instances, saturating the probability-conservation upper bound across the 20 orthonormal initial states.The sum of the success probabilities for those initial states cannot exceed 1.Source: §IV · pp. 9–10
  • The approach builds on a related strategy using random low-energy states [2], and quantifies its viability for hard 20-bit MAX 2-SAT instances.The paper also situates nonadiabatic state transfer across a phase transition in prior quantum-control work [3].Source: §IV · p. 10

V. THE MEANDERING PATH MAY BE FASTER

The authors add randomly chosen local Hamiltonians to the adiabatic path and test three path-change types. All three improve effective success probability across the hard instances, with complex changes typically giving the largest increase.

V. THE MEANDERING PATH MAY BE FASTER

  • The standard straight path from HB to HP is modified by adding a random HE, constrained to local terms on HP’s interaction graph without instance-specific information.The authors use this constraint to explore path changes without supplying information specific to each instance.Source: §V · p. 10
  • The stoquastic category uses zero-diagonal local terms with real, non-positive off-diagonal matrix elements.Its local terms are sampled from normalized combinations of the specified one- and two-qubit Pauli operators.Source: §V · p. 10
  • The other tested categories were zero-diagonal general complex changes and diagonal changes built from local terms.The complex category uses combinations of one- and two-qubit Pauli operators; the diagonal category uses Iσz, σzI, and σzσz.Source: §V · pp. 10–11
  • For instance #1, a particularly successful complex HE eliminated the avoided crossings seen in the original path.The instance had P(100) = 5 × 10^-5 before path change.Source: §V · p. 11, Figure 11 · p. 11
  • The evaluation used 25 independent trials of each path-change type per instance, with each path change selected independently.The authors simulated the 137 hard instances, all of which had P(100) < 10^-4 without HE.Source: §V · p. 12
  • Stoquastic changes almost always raised success above 10^-4 but rarely brought it near 1 across the randomly sampled trials.The comparison concerns maxima over 25 path-change trials per instance.Source: §V · pp. 12–13, Figure 13 · p. 13
  • All three path-change types raised effective success probability for all 137 hard instances, with complex changes typically producing the largest increase.Effective success probability is defined as 1 minus the geometric mean of failure probabilities across trials.Source: §V · pp. 13–14
  • Higher success probability correlated with larger minimum spectral gaps, while large gaps with low success probability were nearly absent.The comparison used random trials and the most successful trial of each type for every instance; the plots use different scales for these groups.Source: §V · pp. 14–15, Figure 15 · p. 15

VI. CONCLUSION

The conclusion reports three strategies that improve success on the selected hard 20-bit MAX 2-SAT instances. It also notes that the strategies did not improve QAA Grover search at 20 qubits and that the scope of the results limits their broader algorithmic implications.

VI. CONCLUSION

  • On the selected hard 20-bit MAX 2-SAT instances, shorter evolution, first-excited-state initialization, and random local path changes all increased success probability.The 137 instances were selected from over 200,000 generated instances because their baseline success probability at T = 100 was below 10^-4.Source: §VI · p. 16
  • The strategies did not improve the QAA version of Grover search at n = 20 qubits.The authors use this test to guard against the possibility that their MAX 2-SAT results reflect low-bit-number phenomena.Source: §VI · p. 16
  • The results cover selected very-low-success instances, and their algorithmic value may be limited if gains only bring these cases up to typical instances that themselves have low success.The authors call for testing at higher bit number on a quantum computer, where classical simulations are unavailable.Source: §VI · p. 16

Related papers

Loading 1401.7320v1…