Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization

I. INTRODUCTION

• Rather than assess heuristic performance, the paper compiles repeated bottleneck primitives for a fault-tolerant cost model, reporting leading-order Toffoli and ancilla complexity constants.It emphasizes Toffoli complexity because non-Clifford gates are substantially more costly than Clifford gates in the surface code.Source: §I · p. 4

A. Overview of results

• The overview covers amplitude amplification, QAOA, time-evolution and quantum-walk methods, and three quantum simulated-annealing variants across four optimization-problem families.New techniques include a logarithmic-factor reduction in Hamming-weight calculation, QROM-based arithmetic approximation, amplitude-estimation-based QAOA cost evaluation, qubitized adiabatic simulation, and improved constructions for simulated-annealing walks and oracles.Source: A. Overview of results · pp. 4–5

B. Organization of paper

• Section II compiles five oracle types for four problem Hamiltonians, while Section III explains their use in heuristic algorithms and provides query and overall resource complexities.The three simulated-annealing variants receive complete primitive compilations; the Szegedy-walk version is least efficient among the three studied.Source: B. Organization of paper · p. 6

A. Oracles for direct cost function evaluation

• Direct cost-function evaluation is one repeatedly queried oracle primitive, and the paper summarizes the leading complexity terms for its oracle implementations alongside the other oracle costs.The oracle circuits are tailored to four problem families, with their complexity estimates used in the later algorithm analysis.Source: A. Overview of results · p. 4, A. Oracles for direct cost function… · p. 8, Table IV · p. 9
• The oracle adds or subtracts each term coefficient according to its qubit-parity value, using two’s-complement arithmetic and returning an approximate energy in an output register.The approximation uses bdir bits; the direct oracle’s Toffoli complexity is denoted Cdirect.Source: §1 · pp. 9–10, A. Oracles for direct cost function… · p. 9

1. Direct energy oracle for L-term spin model and QUBO

• For L-term spin models, Toffoli gates enter only through the adder, and the oracle’s Toffoli and ancilla costs do not depend on Hamiltonian many-body order.Many-body order affects only the CNOT gates used to compute term parities.Source: §1 · p. 10
• For QUBO, the same reasoning applies, with L = N(N + 1)/2 terms and no obvious way to improve on the general complexity.The passage refers to equations for the resulting Toffoli and ancilla counts but does not provide their values here.Source: §1 · p. 10

2. Direct energy oracle for SK model

• The SK energy oracle uses fewer than N^2 Toffolis and logarithmic ancillas by summing bits in groups rather than using a large-ancilla tree sum.The grouped method has less than 2L Toffolis and logarithmic persistent and temporary ancilla costs; the alternative tree sum uses approximately N^2/2 ancillas.Source: §2 · pp. 10–11

3. Direct energy oracle for LABS model

• Repeating over the N values of k places the LABS Hamiltonian energy in the output register; Toffoli cost is driven primarily by computing Ek in steps 1 and 5.For N = 64–1024, the coefficient on N(N + 1) is less than 1.2, rather than 1.5.Source: §3 · p. 12
• For N ≥45, the LABS energy oracle costs less than 5N(N + 1)/4 Toffolis, with logarithmic ancillas.The numerically estimated coefficient on N(N + 1) is below 1.2 for N = 64–1024; the reported bound is slightly looser.Source: §3 · pp. 11–12

B. Energy difference oracles

• For higher-order Hamiltonians such as LABS and HL, computing an energy difference can use two direct-oracle applications, with Toffoli cost 2Cdirect and no additional ancillas.The second energy is computed in the same register while subtracting its terms, avoiding separate output registers and subtraction.Source: B. Energy difference oracles · p. 13

C. Oracles for phasing by cost function

• A phase oracle phases computational basis states in proportion to their cost-function energies, equivalent to unit-time evolution under a diagonal Hamiltonian.A reusable phase-gradient register applies the phase through addition; its one-time initialization cost is additive and expected to be negligible relative to repeated oracle calls.Source: C. Oracles for phasing by cost function · p. 14
• For LABS, summing tree sums gives a numerically estimated Toffoli cost no greater than 8N(N + 1)/5 for computing and uncomputing partial sums over N = 64–1024.The reported ratios are 1.35962, 1.38507, 1.45027, and 1.43186 for N = 64, 128, 256, and 1024, respectively.Source: C. Oracles for phasing by cost function · p. 15

D. Oracles for linear combinations of unitaries

• For L-term Hamiltonians, qubitization uses a preparation oracle and a Hamiltonian selection oracle; two preparation queries and one selection query implement a walk encoding H’s eigenvalues.The walk eigenvalues are the arccosines of the problem-Hamiltonian eigenvalues divided by λ, and oracle repetitions scale proportional to λ.Source: D. Oracles for linear combinations of… · p. 16

1. LCU oracles for L-term Hamiltonian

• Unary iteration implements selection for an L-term Hamiltonian with L −2 Toffolis and ⌈log L⌉−1 extra ancillas when uncontrolled.When controlled by another ancilla, the stated cost is L −1 Toffolis and ⌈log L⌉ ancillas.Source: §1 · p. 17
• Coherent alias sampling provides a preparation strategy with Toffoli cost L + bLCU + log L + O(1), and selection uses L Toffolis.The strategy prepares approximate coefficients ˜wℓ in place of exact coefficients wℓ.Source: §1 · p. 17

2. LCU oracles for QUBO and using dirty ancilla

• Dirty QROAM combined with coherent alias sampling can reduce the Toffoli cost of preparing and uncomputing the LCU state, with uncomputation saving 4(bLCU −1)k Toffolis.The QROAM parameter k must be a power of two, so using the exact optimum slightly understates the cost.Source: §2 · p. 17
• For QUBO, two log-sized registers index i and j, and a contiguous index is computed for QROAM before being uncomputed afterward.The select operation uses two unary-iteration applications; computing and uncomputing the contiguous register costs O(log^2 N).Source: §2 · pp. 17–18
• The Toffoli-optimized implementation raises space complexity from N + O(bLCU) to N^(bLCU/2) + O(bLCU), so this tradeoff may be impractical.Choosing k = N/bLCU avoids increasing spatial complexity when N system qubits are available; Szegedy walks can use k = 2N/bLCU when 2N qubits are available during prepare.Source: §2 · p. 18

3. LCU oracles for the SK model

• For SK, because coefficients only determine signs, phase fixup replaces the usual coherent-alias-sampling inequality test and controlled swaps.This removes the cost 2(bLCU + 2 log N) + O(1) associated with those operations.Source: §3 · p. 20

4. LCU oracles for the LABS model

• For LABS, indexing i, j, and k directly avoids linear indexing of O(N^3) terms; the select operation uses four unary-iteration applications and costs 4N + 4 log N Toffolis.The normalization λ is large and contributes to the number of quantum-walk repetitions.Source: §4 · pp. 20–21

E. QROM-based function evaluation

• Piecewise linear function evaluation uses QROM to identify an interval and retrieve its slope and intercept; the number of intervals scales as O(2^(bfun/2)).Restricting interval sizes to powers of two increases the normalized interval-count constants by around 44%.Source: E. QROM-based function evaluation · pp. 21, 23, Figure 4 · p. 23
• In simulations of the SK technique on 16 qubits, angle error up to 0.01, incorporating β into the function, and low-precision output had little effect on success probability.The simulations averaged over 4096 random instances, with β increasing linearly over 50 steps from 0 to 1.2.Source: E. QROM-based function evaluation · p. 23, Figure 5 · p. 24

III. OPTIMIZATION METHODS

• The analysis expresses algorithm primitives in oracle costs and then Toffoli or T-gate costs, combining them with oracle estimates for four problem families.The reported resource tables use simplifying assumptions about the relative sizes of precision parameters.Source: §III · pp. 25–26, Table VI · p. 26, Table VII · p. 27
• The section reviews Trotter and LCU approaches to adiabatic optimization, Zeno-style phase randomization, and Szegedy- and qubitized-walk simulated annealing.It also outlines spectral-gap-amplified Hamiltonian methods; the Szegedy approach has O(1/∆) walk-step scaling versus the classical worst-case O(1/∆) transition bound, which the paper notes is loose for broad problem classes.Source: §III · p. 25

1. Combining amplitude amplification with quantum optimization heuristics

• Amplitude amplification can boost overlap on a low-energy subspace, but choosing the heuristic duration trades longer runs against fewer repetitions.The paper focuses on mean cost because the success probability may be unknown; with a known probability, duration can be optimized, sometimes to t = 0.Source: §1 · pp. 26, 28

2. Directly using amplitude amplification

• When used alone, amplitude amplification provides a quadratic advantage over classical brute-force search without exploiting problem structure.Each step computes and uncomputes the energy and tests whether it is below the target threshold.Source: §2 · pp. 28–29

B. The Quantum Approximate Optimization Algorithm

• QAOA alternates cost-Hamiltonian and driver evolutions, then estimates the objective to optimize its variational parameters.When suitable parameters can be inferred in advance, the outer-loop optimization can be omitted; fault-tolerant evaluation may use quantum methods beyond sampling, with additional resource costs.Source: B. The Quantum Approximate… · pp. 29–30

1. Amplitude estimation based direct phase oracle evaluation

• Direct phase-oracle evaluation estimates each cost-function term with a Hadamard test and combines the estimates to bound total error by ∆C.The method is expected to be preferable when error tolerance is small and the number of terms is modest; sampling can be preferable when variance is small, uncertainty is large, or L is large.Source: §1 · pp. 30–31

2. Amplitude estimation based LCU evaluation

• LCU-based amplitude estimation uses O(λ/ϵ) prepare-and-select invocations, a quadratic improvement over sampling, but added circuit costs can worsen its prefactor.The paper expects this approach often to beat direct phase evaluation in fault-tolerant settings when prepare and select costs are comparable to or below Uψ.Source: §2 · p. 32

1. Background on the adiabatic algorithm

• The adiabatic runtime depends on the minimum spectral gap; boundary-adabatic results bound the final state, while instantaneous theorems address the state during evolution.Improved paths for analytic Hamiltonians require small error tolerance on the order of ϵ ∈ O(∆) to realize their benefits.Source: §1 · p. 33
• Digitized adiabatic optimization chooses the number of Trotter steps from available resources, while the evolution time is selected heuristically when the spectral gap is unknown.Smaller T improves the continuous-time approximation for fixed step count but also makes remaining adiabatic less likely.Source: §1 · pp. 33–34
• Higher-order product formulas offer a finite-order gate-complexity trade-off for fixed error and evolution time, rather than favoring arbitrarily high order.The text also gives cost estimates for adiabatic sweeps under gap and error assumptions.Source: §1 · p. 34

• The proposed method stroboscopically simulates short-time qubitized walks, following the arccosine of the normalized Hamiltonian rather than the Hamiltonian directly.The authors expect the relevant eigenspectrum to lie in the arccosine’s linear region, but note that the effective duration of walk steps must be shrunk.Source: §2 · p. 35
• A parameter r lets repeated walk operations act as shorter time steps, generating an effective Hamiltonian whose eigenvalues approach ±E_k(t)/λ(t) as r increases.The section frames this as a simple alternative to Dyson-series simulation, which requires multiple time registers.Source: §2 · pp. 35–36
• The adiabatic walk-step bound depends on the minimum eigenvalue magnitude, an artifact of walk eigenvalues mapping to 1 and potentially changing gaps near zero.The stated bound concerns a maximum-rank Hamiltonian with gap Δ and error ϵ, but the supplied passage does not include the formula.Source: §2 · p. 36
• As time slices increase, the heuristic converges to the adiabatic path; unlike Trotter methods, its cost depends less strongly on Hamiltonian term count.Higher-order splitting and boundary cancellation can improve the stated 1/ϵ^(3/2) scaling to 1/ϵ^o(1) when Δ∈O(1); the authors expect some derivative and coefficient bounds to be loose.Source: §2 · p. 36

3. Zeno projection of adiabatic path via phase randomization

• Phase randomization replaces measurement in Zeno projection: discarded phase-estimation outcomes can be implemented by classically sampling an evolution time.The approach was proposed in; choosing a distribution whose Fourier-transform width is below the spectral gap keeps the state in the target ground-state component.Source: §3 · pp. 36–38
• Optimizing the evolution-time distribution gives ⟨|t|⟩Emax≈1.1580 using terms through a22, a 46th-order polynomial.The earlier suggested distribution gives ⟨|t|⟩∆≈2.648, while the triangle window gives ⟨|t|⟩∆≈2.333.Source: §3 · pp. 38–39

D. Szegedy walk based quantum simulated annealing

• The Szegedy-walk approach uses an arccosine mapping to improve spectral-gap scaling by a square root over the classical O(1/δ) bound.The quantum Gibbs state is an eigenstate of the block-encoded operation, and the walk's gap governs algorithm complexity.Source: D. Szegedy walk based quantum… · pp. 39–40
• Szegedy-walk cost is dominated by controlled state preparation, particularly computing transition probabilities from bit-flip energy differences.Moving controlled preparation to the end of a walk step can save a factor of two by retaining computed energy differences and probabilities until uncomputation.Source: D. Szegedy walk based quantum… · pp. 39, 42
• Imperfect state preparation slightly lowers the effective transition probabilities, which the authors expect to have only a minor effect on optimization.The procedure uses a success flag to control the swap, addressing preparation that is not exact.Source: D. Szegedy walk based quantum… · pp. 41–42
• Moving controlled preparation to the end changes β at the swap rather than the reflection and reduces the stated factor from 4 to 2.The resulting cost is given as 2(N + 1)Cdirect, 2NCdiff + 2NCfun.Source: D. Szegedy walk based quantum… · p. 43, Figure 9 · p. 43
• Including twice the state-preparation cost gives a total complexity with additional terms 2N log N + 8Nbsm + 18bsm^2 + O(N).The passage omits bsm log bsm from the order term because it is smaller than N for the parameter ranges considered.Source: D. Szegedy walk based quantum… · p. 43
• The total ancilla cost is NAdiff + NAfun + 5bsm + O(log bsm), using the worst case where N is not a power of 2.Persistent ancillas are multiplied by N, while temporary ancillas are reused; the temporary cost is 4bsm + O(log bsm) when N is not a power of 2.Source: D. Szegedy walk based quantum… · p. 43

• The improved walk implementation is intended for more general cost Hamiltonians, including high-connectivity cases where energy differences depend on most system qubits.The database method of is exponential in the number of qubits |N_j| on which a transition probability depends, making it unsuitable for these cases.Source: E. LHPST qubitized walk based quantum… · pp. 44–45
• The LHPST walk’s B operation uses one transition probability, whereas the Szegedy approach computes all transition probabilities for a state preparation.The database-based method of is useful for low-connectivity Hamiltonians, but not the cost Hamiltonians considered here.Source: E. LHPST qubitized walk based quantum… · p. 44
• A QROM can output the rotation angle before a phase-gradient rotation, reducing the stated Toffoli complexity to O(N2|N_j| + log(1/ϵ)).The preceding database procedure has overall cost O(N2|N_j|[|N_j| + log(1/ϵ)]).Source: E. LHPST qubitized walk based quantum… · p. 45

1. Rotation B

• Rotation B computes the energy difference, uses a piecewise-linear QROM approximation to obtain the transition angle, applies the ancilla rotation, and uncomputes the angle.The proposed low-precision approximation need only remain monotonic in the actual energy for the optimization setting described.Source: §1 · p. 45

2. Equal superposition V

• For N not a power of two, the equal-superposition procedure achieves highly accurate results with s = 7 at a cost of 4k + 1 Toffolis.The procedure uses binary encoding, which the authors say reduces ancilla cost relative to the unary encoding of.Source: §2 · p. 46, Figure 10 · p. 47

3. Controlled bit flip F

• The controlled bit flip F flips bit j of x when its control is |1⟩ and can be implemented with binary register M at Toffoli complexity N.When state preparation fails, the procedure flags failure and makes the net operation the identity; the resulting block encoding has an identity offset that shifts eigenvalues trivially.Source: §3 · p. 47

4. Reflection R

• A reflection about zero costs ⌈log N⌉ Toffolis and uses ⌈log N⌉ + 2 qubits for the index, control, and rotation ancillas.The reflection also includes ancillas for preparing the equal superposition and the flag qubit.Source: §4 · p. 48

5. Total costs

• One step of ˜UW costs 2Cdiff + 2Cfun + N + 2bdif + 9 log N + O(1) Toffolis; 8 log N can be omitted when N is a power of 2.Temporary ancillas are bounded by the larger of the energy-difference and function-evaluation requirements, in addition to the stated registers.Source: §5 · p. 48

F. Spectral gap amplification based quantum simulated annealing

• Quantum-walk steps can obtain spectral-gap amplification without simulating a time-dependent Hamiltonian, but the arccosine mapping gives no further square-root amplification.The approach may offer other scaling advantages, such as avoiding quantum signal processing for certain oracles.Source: F. Spectral gap amplification based… · pp. 48–49

1. The spectral gap amplification Hamiltonian

• The amplified Hamiltonian is specialized to single-bit flips, and preparing its minimum-energy configuration yields a sample from the distribution produced by sufficiently long simulated annealing.The construction uses a lower bound on the original Hamiltonian’s spectral gap.Source: §1 · p. 49

2. Implementing the Hamiltonian

• The amplified-Hamiltonian implementation has Toffoli cost 2Cdiff + 2Cfun + 2bsm + N + 14 log N + O(brot).Its ancilla cost is Adiff + Afun + max(Bdiff, Bfun) + 2 log N + bsm + O(1).Source: §2 · p. 52

IV. ERROR-CORRECTION ANALYSIS AND DISCUSSION

• The estimates cover primitive implementations for SK and LABS under surface-code assumptions, including physical error rates of 10^-3 or 10^-4 and chosen precision parameters.The analysis assumes serial CCZ-state distillation; many free precision parameters are set to 20 bits, with b_fun = b_sm = 7.Source: §IV · pp. 53–54
• Cross-algorithm step costs are difficult to compare, and Trotter or qubitized-walk heuristics lack a clear classical analogue for benchmarking.Even Trotter and Hamiltonian-walk comparisons are qualified because precision choices differ and heuristic evolution need not be precise.Source: §IV · pp. 54, 56
• For simulated annealing, LHPST and Szegedy have the same gap, while spectral-gap amplification is less efficient after accounting for its √N Hamiltonian cost increase.The number of steps is governed by the spectral gap; the larger λ-value raises the spectral-gap-amplified approach's per-step cost.Source: §IV · p. 54
• At N = 512, 2×10^5 quantum simulated annealing steps—about a day of runtime—match roughly four CPU-minutes under an exactly quadratic step advantage.The comparison estimates about one-hundred million times more classical updates per core-hour than quantum updates for this instance.Source: §IV · p. 55
• For N = 512 SK, the estimated crossover is about 7×10^7 steps, requiring about one year of quantum runtime under assumptions favorable to quantum computing.The analysis compares against a single classical core and does not adjust surface-code distance for runtimes longer than an hour.Source: §IV · pp. 55–56
• Amplitude amplification remains uncompetitive in the estimates: even with quadratically fewer steps, it would need roughly billions of qubithours of state distillation to match one classical core-hour.The passage estimates only ten to three thousand amplification steps using one-hundred thousand to one-million qubithours.Source: §IV · p. 56
• For LABS, the estimated amplitude-amplification crossover is M = 62, corresponding to about 2×10^9 queries and roughly 116 years.This comparison uses the best-known classical scaling of Θ(1.73^N) and is favorable to quantum computing by comparing against one classical core.Source: §IV · p. 56
• The authors conclude that meaningful early fault-tolerant impact may require better-than-quadratic speedups or significant improvements in error correction.Their resource estimates are discouraging because of the constant-factor slowdown between error-corrected quantum and classical computation.Source: §IV · p. 57

Appendix A: Addition for controlled rotations

• A controlled phase rotation can be implemented with b_grad − 2 Toffolis by using a control qubit to select addition or subtraction with Clifford gates.For a classically given rotation angle, the cost is b_grad − 3 Toffolis; the passage also notes controlled addition alone would have twice the complexity of addition.Source: Appendix A · pp. 59–60
• Writing an n-bit constant as at most ⌈(n + 1)/2⌉ signed powers of two gives a multiplication cost of at most (b_grad − 2)(n + 2)/2 additions.The omitted-bit error is bounded by (n + 2)π/2^b_grad; the passage says b_grad should be chosen so this error is at most ε.Source: Appendix A · p. 60, Figure 14 · p. 62

1. Derivatives of matrix logarithms of unitary matrices

• The matrix-logarithm integral representation converges for unitary A only when A has no eigenvalue equal to −1.The derivatives of the effective Hamiltonian are used to bound discretization error; the effective gap can scale as Ω(min(Δ, min_k |E_k|)/λ) because eigenvalue mapping may introduce degeneracies.Source: §1 · pp. 62, 65
• With sufficiently many steps, the walk operator can replace a Trotterized sequence for adiabatic state preparation and make the diabatic error arbitrarily small.The authors caution that the bounds in this analysis are extremely loose.Source: §1 · p. 65

Appendix C: In-place binary to unary conversion

• B2UN converts a binary-encoded integer k into its one-hot unary encoding on N bits.The circuit is built recursively for power-of-two N, then adapted to other sizes.Source: Appendix C · p. 66
• At each recursion, the most significant input bit controls swaps that place the smaller unary encoding in the appropriate half of the output register.CNOTs then erase an extra qubit, with a final CNOT handling the k = 0 and k = N/2 cases.Source: Appendix C · p. 66
• For N that is not a power of two, the construction removes operations involving deleted qubits because the corresponding output qubits would be zero.The described modification applies the recursive circuit for the next power of two and omits unnecessary gates.Source: Appendix C · p. 67
• The circuit's only non-Clifford gates are controlled-swaps, each implementable with one Toffoli and two CNOTs.The passage introduces a count of controlled-swaps but does not provide its value in the supplied text.Source: Appendix C · p. 67

Appendix D: Cost of multiplication

• Schoolbook multiplication reduces a product to bit-controlled additions of shifted copies of one input.Multiplication by a power of two is implemented by a bit shift, while multiplication by a single bit uses that bit to control addition.Source: Appendix D · p. 67

2. Methods for addition

• For adding a classical constant to a quantum register, the constant's bits can serve as classical controls, avoiding quantum storage of that constant.The resulting adder has Toffoli cost equal to the number of bits minus 2 and uses one fewer ancilla than bits.Source: §2 · p. 68, Figure 18 · p. 69

3. Multiplying two integers

• Multiplying two quantum integers with d_A and d_B bits uses 2d_A d_B − d_A Toffolis and 2d_A − 1 temporary ancillas.When one input is classical, the passage gives a cost of at most d_A d_B Toffolis, reducible to d_A times the Hamming weight of the classical input when that weight is known.Source: §3 · pp. 69–70

4. Multiplying an integer to a real number

• When one input is real-valued, the product is approximated by truncating its binary expansion to meet the error tolerance ε.For real κ multiplied by integer λ, the text specifies d_A = ⌈d_B log(d_B/ε)⌉ bits and d_A − 1 ancillas.Source: §3 · p. 70, §4 · pp. 70–71

5. Multiplying two different real numbers

• The multiplication procedure approximates κλ within ε by accumulating truncated, shifted contributions in an output register.The inputs are real numbers in [0,1), and the procedure uses repeated additions.Source: §5 · p. 71
• With dA = dB = d, multiplication uses d^2 − d − 1 Toffoli gates, and the chosen d is checked against the error tolerance ε.The figure states that a ratio below 1 guarantees multiplication error less than ε.Source: §5 · p. 71, Figure 19 · p. 72

6. Squaring a real number

• Symmetry combines equal off-diagonal products, so the squaring sum contains only about half as many terms.The diagonal terms are handled separately.Source: §6 · p. 73
• In both odd and even cases, squaring has complexity less than d^2/2.Source: §6 · p. 74
• The squaring ancilla cost is half that of multiplication: at most d − 2 for even d and d − 1 for odd d.Source: §6 · p. 75

1. Heuristic variant of the shortest path algorithm

• Hastings’ shortest path algorithm rigorously achieves super-Grover speedups for certain problems, including arbitrary MAX-2-LIN2 instances [75].Source: §1 · p. 75
• The shortest path algorithm applies amplitude amplification to an adiabatic-style evolution under a time-dependent Hamiltonian, targeting low-energy outcomes.Its construction initializes in the uniform superposition and uses phase estimation and a direct energy oracle to flag outcomes.Source: §1 · p. 76
• Random-duration evolution can replace phase estimation because its measured result is unused, eliminating phase-estimation ancillas and controls.The duration distribution can suppress phase-measurement errors as large as the energy gap.Source: §1 · p. 76
• The heuristic variant’s average success probability is at least Hastings’ stated overlap bound, but a single chosen evolution time may yield below-average success [9].The heuristic version can use fixed rounds of amplitude amplification with heuristically chosen parameters.Source: §1 · p. 77

2. Quantum enhanced population transfer

• Quantum-enhanced population transfer starts from a low-energy bitstring and seeks a similarly energetic state at Hamming distance O(N), addressing trapping in non-ergodic energy landscapes.The proposed procedure turns on a transverse field, evolves under a fixed Hamiltonian, then measures and checks the observed state's energy.Source: §2 · p. 77
• For a worst case with M states of energy −1 and 2^N − M states of energy 0, the procedure succeeds with high probability in time O(√(2^N/M)).Unlike Grover search, it does not require fine-tuning the transverse field or computation time.Source: §2 · p. 77