PaperlayerView exact revision on arXiv

Source-linked AI summary

Super-Quadratic Quantum Speedups for Combinatorial Optimization via Tilted Walks

Guneykan Ozgul, Shouvanik Chakrabarti

arXiv:2609.40088v1quant-phcs.DSmath.OC

TL;DR

Quantum short-path algorithms can deliver super-quadratic speedups over exhaustive search, but a stronger classical conditioning-and-search baseline narrows that advantage. This paper introduces quantum tilted walks, which increase amplitude on high-value target states from application-specific initial states. The framework yields super-quadratic speedups over a classical algorithm exploiting the spectral-density condition, without requiring mixer-ground-state initialization.

  • Problem

    The paper asks how quantum algorithms can increase the probability of successful candidates before fixed postprocessing, while existing short-path guarantees require restrictive mixer and objective conditions for application-specific distributions.

    Source: §1.1 · p. 3

  • Method

    Quantum tilted walks use objective-biased mixer dynamics to increase target-state amplitude from application-specific initial states without requiring ground-state preparation or mixer-ground-state initialization.

    Source: §2.1 · p. 6, §2.3 · p. 13

  • Results

    Tilted walks provide a super-quadratic speedup over the classical algorithm designed to exploit the spectral-density condition and increase marked amplitude by a factor 2κn/2 up to an inverse-polynomial prefactor.

    Source: §2.1 · p. 6, §2.4 · p. 17

  • Takeaways & Limitations

    The analyzed theorem requires neither a log-Sobolev inequality nor a spectral-gap bound, but each application must control the normalization Eb.

    Source: §2.3 · p. 13

    For the maximum-independent-set setting analyzed in [Cha+25], no conditioning-and-search version is yet available, leaving the corresponding tilted-walk analysis as future work.

    Source: §2.4 · p. 17

Abstract

from arXiv · show

We introduce quantum tilted walks, a quantum algorithmic framework for solving exact combinatorial optimization problems. The framework applies an average of powers of a tilted Hamiltonian that biases the discriminant matrix of a base Markov chain (mixer) with the objective function. Our starting point is quantum short-path algorithms, which prepare the ground state of such a Hamiltonian and obtain super-quadratic speedups over exhaustive search for certain combinatorial optimization problems. Recently, Le Gall and Tamaki~(arXiv:2604.12131) developed a classical conditioning-and-search algorithm for weighted MAX-E$k$-LIN2 and weighted MAX-$k$-CSP. Under the same assumptions, their algorithm is only sub-quadratically slower than quantum short-path algorithms. Consequently, existing short-path algorithms do not establish a super-quadratic speedup over this stronger classical baseline. For maximization problems, we give conditions under which tilted walks increase the amplitude on the target state with high objective value when initialized from a starting state with lower objective value. This framework captures conditioning-and-search and yields super-quadratic speedups over it for the same problems. While our framework recovers quantum short-path algorithms as a special case, it neither requires ground-state preparation nor initialization in the ground state of the base mixer. We demonstrate these advantages on a synthetic optimization problem for which tilted walks achieve a super-quadratic speedup whereas the short-path algorithms do not.

1 Introduction

The introduction frames super-quadratic quantum advantage as increasing the amplitude of successful candidates before fixed postprocessing, beyond quadratic acceleration of classical subroutines. It introduces tilted walks as a framework that addresses short-path initialization constraints and yields super-quadratic speedups over conditioning-and-search for the named CSP families.

1.1 Motivation and background

  • Quadratic acceleration of classical subroutines alone gives at most a quadratic overall speedup, while fault-tolerant overheads can offset that gain.Improving scaling beyond quadratic can substantially reduce required resources and make quantum advantage more practical [Bab+21].Source: §1.1 · p. 2
  • Short-path algorithms prepare an objective-biased Hamiltonian's ground state from the mixer ground state, then amplify its overlap with the optimum.The approach was introduced by Hastings [Has18a] as an alternative to following an adiabatic interpolation to its end.Source: §1.1 · p. 2
  • Conditioning-and-search has a quadratically accelerated runtime with a smaller exponent than the proven short-path runtime, so short-path results do not establish a super-quadratic speedup over it.Le Gall and Tamaki [GT26] identify this classical algorithm using a spectral-density condition also used to analyze short-path algorithms.Source: §1.1 · pp. 2–3
  • The central question is whether a quantum algorithm can increase successful-candidate amplitudes before postprocessing in a coherent encoding of a candidate distribution.Conditioning-and-search fits this framework, as do heuristics such as simulated annealing.Source: §1.1 · p. 3
  • Short-path analysis requires an inverse-polynomial log-Sobolev constant and objective smoothness under the mixer, conditions that may not both hold for an application-specific candidate distribution.Using such a distribution can therefore require constructing a new mixer and establishing its spectral and regularity properties.Source: §1.1 · p. 3
  • Tilted walks give super-quadratic speedups over conditioning-and-search for weighted MAX-Ek-LIN2 and weighted MAX-k-CSP under the same assumptions.They also allow application-specific initial states without ground-state preparation or initialization in the mixer ground state.Source: §1.1 · p. 3

2 Results

The results establish amplitude-gain guarantees for quantum tilted walks, including for nonstationary initial states, and show super-quadratic speedups over conditioning-and-search for MAX-Ek-LIN2 and MAX-k-CSP. They also relate the framework to short-path algorithms and examine where tilted-walk guarantees differ from generalized short-path analysis.

2.1 Overview of Quantum Tilted Walks

  • Quantum tilted walks generalize discrete-time quantum walks and include generalized short-path algorithms as a special case, while averaging powers enables set-to-set amplitude bounds without ground-state projection.Unlike short-path amplification relative to the mixer’s ground state, the tilted-walk guarantee can amplify a qualifying candidate state; averaging preserves useful powers that may differ across target configurations.Source: §2 · p. 4, §2.1 · pp. 7, 9

2.2 Applications to Exact Optimization: Super-Quadratic Speedups over Conditioning-and-Search

  • For weighted MAX-Ek-LIN2 and weighted MAX-k-CSP, tilted walks achieve super-quadratic speedups over conditioning-and-search under the same assumptions as its classical analysis.The walk increases amplitude on successful configurations, reducing amplitude-amplification iterations; a constant κ reduces the runtime exponent beyond the ordinary quadratic quantum speedup.Source: §2 · p. 4, §2.2 · pp. 10–11

2 Results

  • Tilted walks allow initial states independent of the mixer’s stationary state and avoid ground-state preparation or a tilted-Hamiltonian spectral-gap lower bound.An example obtains exponential amplitude gain despite exponentially small overlap with the stationary state and exponentially small gaps for both the mixer and tilted Hamiltonian.Source: §2 · p. 4

2.1 Overview of Quantum Tilted Walks

  • Under regularity conditions and objective-value separation, tilted walks increase target-set amplitude by an exponential factor, up to an inverse-polynomial prefactor.The conditions require successful configurations to score above both the threshold defining the initial set and the stationary mean; when b* = Ω(1) and L = O(1/n), the gain is exponential in n.Source: §2.1 · pp. 6–7

2.2 Applications to Exact Optimization: Super-Quadratic Speedups over Conditioning-and-Search

  • For MAX-Ek-LIN2 and MAX-k-CSP, tilted walks reduce the quantum runtime exponent by a positive constant versus conditioning-and-search, yielding super-quadratic speedups; for weighted exact-k CSPs, the comparison condition holds when k ≥6.The MAX-k-CSP result assumes σB ≥γB, which holds in particular for weighted exact-k CSPs with k ≥6.Source: §2.2 · p. 12

2.3 Further Advantages of Quantum Tilted Walks

  • For nonstationary nonnegative initial states, under λφ > 0 and condition (40), tilted-walk powers can exponentially increase marked amplitude when M = Θ(n), Lφ = O(1/n), and each product ratio exceeds one by a constant.The guarantee needs no log-Sobolev inequality or spectral-gap bound; implementing the block encoding uses O(M) calls and does not require ground-state preparation.Source: §2.3 · pp. 13–15

2.3.1 An example with exponentially small spectral gaps

  • The constructed example has initial stationary overlap 2^-n, mixer and tilted-Hamiltonian gaps at most 2^-n/n, yet achieves exponential amplitude gain with M = ⌊n/20⌋; short-path analysis cannot certify efficient ground-state reflection.The example contrasts analytical guarantees, not optimization speedups: an element of the successful set can be written down directly.Source: §2.3.1 · pp. 15–16

2.4 Discussion

  • The analysis does not establish super-quadratic speedups over every classical algorithm; it identifies objective smoothness under the mixer as central and leaves harder nonstationary-state families and stronger normalization bounds for future work.The spectral-density condition is not assumed; the paper says it follows from pseudo-Lipschitzness. A conditioning-and-search baseline for the independent-set setting discussed in [Cha+25] remains an open question.Source: §2.4 · pp. 16–17

2.5 Related work

  • Tilted walks analyze amplitude from Cb,M directly rather than preparing a tilted-Hamiltonian ground state, and insert this transformation between threshold-state preparation and local search to gain an additional exponent κ over conditioning-and-search [GT26].The framework builds on short-path work by Hastings [Has18a] [Has18b] [Has19], Dalzell et al. [Dal+23], and Chakrabarti et al. [Cha+25].Source: §2.5 · pp. 17–18

2.6 Organization

  • The paper defines the framework and assumptions, proves amplitude gain and controls normalization, applies the method to exact optimization, extends the bound to nonstationary states, and develops block encodings and error handling.The final steps also address unknown normalization and optimum values.Source: §2.6 · p. 18

3 The Quantum Tilted Walk Framework

The framework tilts a Markov-chain discriminant operator with a normalized objective, then averages its powers to increase amplitude on high-value target states. Its analysis relies on objective regularity, mixer log-Sobolev conditions, and specified quantum access assumptions.

3 The Quantum Tilted Walk Framework

  • The normalized tilted operator Db is formed from Hb = D + bG, and Cb,M averages powers of Db before projection onto a target state.G is the normalized objective; the construction is specified for a nonempty starting set T and target set S.Source: §3 · pp. 18–19
  • The path expansion can accumulate contributions from exponentially many paths, but its gain must be balanced against an energy term that can also grow exponentially.The passage notes that this tradeoff can be non-vacuous in certain cases.Source: §3 · p. 19
  • Quantum maximum finding on Cb,M|T⟩ gives a super-quadratic speedup over brute-force search for a choice of b and M.The passage states this result without specifying the parameter values.Source: §3 · p. 19
  • The analysis assumes bounded one-step objective variation and pseudo-Lipschitzness, with the mixer satisfying a log-Sobolev inequality.For the normalized objective, the stated regularity bounds are L2(G) = O(1/n) and pseudo-Lipschitz constant L = O(1/n), given the lemma's conditions.Source: §3 · pp. 20–21
  • The algorithm assumes coherent access to exact objective and transition-rule oracles, and the analysis initially treats block-encoding and algorithmic steps as ideal.The paper says Section 7 provides construction, normalization, and error analysis for the actual implementation.Source: §3 · p. 21

4 Amplitude Gain from Quantum Tilted Walks

The amplitude analysis lower-bounds the path contributions before normalization, upper-bounds the tilted operator's maximum eigenvalue, and combines the bounds by choosing the bias and averaging walk powers. Under stated objective-value and regularity conditions, this yields exponential amplitude amplification.

4.1 Lower Bound on the Amplitude Before Normalization

  • Pseudo-Lipschitzness lower-bounds the unnormalized amplitude by expanding (D + bG)^m into nonnegative path contributions.Theorem 4.2 applies when T contains Tη and S is nonempty; the η-filter is used for analysis, not in the algorithm.Source: §4.1 · p. 22

4.2 Upper Bound on the Maximum Eigenvalue

  • The maximum-eigenvalue bound controls normalization using the mixer’s log-Sobolev inequality and an upper bound on G’s one-step quadratic variation.The section uses this bound to control the normalization cost accumulated by powers of Db.Source: §4.2 · p. 25

4.3 Combining the Amplitude and Normalization Bounds

  • Choosing b balances objective-driven amplitude growth against normalization cost, while averaging powers lets configurations in S contribute at suitable walk lengths.The theorem selects b and M under objective-value, regularity, and log-Sobolev conditions.Source: §4.3 · pp. 26–28
  • Under Theorem 4.6's stated conditions, the amplitude |⟨S|T⟩| is amplified by a factor exp(Θ(n)), giving an exponential improvement over direct search from warm state |T⟩ for an element of S.Source: §4.3 · pp. 27, 29

4.4 Discussion

  • The method relies on walk-like behavior rather than projecting onto the tilted Hamiltonian’s ground state, because finite power averages can retain contributions from other eigenstates.The discussion says a single large power approximating a projector does not give the same result.Source: §4.4 · p. 29

5 Applications to Optimization

This section applies quantum conditioning-and-search based on tilted walks to weighted MAX-Ek-LIN2 and weighted MAX-k-CSP. It presents the classical framework and gives applications with super-quadratic speedups over classical conditioning-and-search.

5.1 Overview of the Conditioning-and-Search Algorithm

  • Classical conditioning-and-search [GT26] repeatedly samples from an objective-threshold set and searches a neighborhood, with success analyzed through a successful subset that need not be found by the algorithm.For uniform sampling from the threshold set, the success probability is the successful-set fraction.Source: §5.1 · p. 29

5.2 Quantum Conditioning-and-Search

  • Quantum conditioning-and-search uses tilted amplitude on successful centers to guide local quantum search and finds a maximizer with bounded error when Theorem 5.1’s amplitude condition holds.It prepares a threshold state, applies the tilted-walk transformation, marks centers whose restricted Hamming neighborhoods contain a maximizer, and amplifies those centers.Source: §5.2 · pp. 30–31

5.3 Application to MAX-Ek-LIN2

  • Under the stated MAX-Ek-LIN2 assumptions, tilted walks achieve a super-quadratic improvement over the classical conditioning-and-search runtime, by a factor of 2^(-κA n/2) with κA > 0 independent of n.The classical exponent is at least 1/(2k), while γA < 1/(2k).Source: §5.3 · p. 35

5.4 Application to Max-k-CSP

  • When Hmin is known and η ∈ (0,1) is fixed, conditioning-and-search finds an optimum of any weighted MAX-k-CSP instance with high probability; Corollary 5.4 gives an explicit weighted runtime exponent.Corollary 5.4 is Corollary 4.7 of Ref. [GT26].Source: §5.4 · p. 37
  • Under Theorem 5.5’s assumptions, Algorithm 1 uses restricted Hamming-ball search on light coordinates to find a maximizer with bounded error and achieve a super-quadratic speedup over conditioning-and-search.The theorem’s comparison has an additional improvement κB, which remains positive and independent of n.Source: §5.4 · pp. 38, 39, 41
  • For weighted exact-k CSPs with k ≥6, σB ≥ γB, satisfying the condition that yields the super-quadratic comparison.The proof uses Σ = kW, Hmax ≤W, and h(t) ≥2t to establish the condition.Source: §5.4 · pp. 39, 41

6 Tilted Walks from Nonstationary Initial States

Tilted walks extend amplitude-gain analysis to nonnegative initial states that need not be stationary for the mixer. The section gives conditions for this gain, translates them to conditioned stationary states, and compares the resulting guarantee with generalized short-path analysis.

6.2 Amplitude Gain from a Nonnegative Initial State

  • Theorem 6.1 bounds marked amplitude from a normalized nonnegative initial state using pointwise amplitude retention and objective-change conditions under its induced kernel.It assumes neither a log-Sobolev inequality nor a spectral-gap bound, but applications must control the normalization E_b.Source: §6 · p. 41, §6.1 · p. 42, §6.2 · p. 43
  • When each factor in the product bound is at least 1 + δ for constant δ > 0, the marked-amplitude gain is exponential without a lower bound on the tilted-Hamiltonian gap.The sufficient positive-rate condition requires an upper bound on E_b.Source: §6.2 · p. 44

6.3 Conditioned Stationary States

  • For a stationary distribution conditioned on A, the retention parameter is the minimum one-step probability of staying in A, and the induced kernel is the chain conditioned to stay there.Theorem 6.1 can retain the original mixer, whereas applying generalized short-path analysis with this initial state would require a chain stationary on the conditioned distribution and its spectral and regularity bounds.Source: §6.3 · p. 45

6.1 How the Mixer Acts on the Initial State

  • The two amplitude-gain theorems cover different cases: Theorem 6.1 requires positive retention throughout a conditioned set, while Theorem 4.6 can handle threshold states with vanishing one-step retention.The latter controls paths that enter the threshold set.Source: §6.3 · p. 45

6.4 Stationary Overlap and the Top-Eigenvalue Gap

  • Small stationary overlap together with little pointwise amplitude loss is possible only when the mixer’s top-eigenvalue gap is correspondingly small.The section presents this as a necessary condition, not a construction.Source: §6.4 · p. 46

6.5 A Concrete Comparison with the Generalized Short-Path Algorithm

  • The constructed example has exponentially small mixer and tilted-Hamiltonian spectral gaps, yet Theorem 6.1 certifies an exponential amplitude gain.The example compares sufficient conditions of the two analyses; its successful set is easy to construct, so it does not establish a speedup for a hard optimization problem.Source: §6.5 · pp. 47, 49

7 Implementation Details

Section 7 accounts for errors introduced during algorithm implementation and describes construction of block encodings for the discriminant and objective.

7 Implementation Details

  • The implementation analysis accounts for errors introduced at each algorithm step.Source: §7 · p. 49

7.1 Constructing the block encoding

  • The discriminant and objective block encodings are constructed from the two access oracles in Equation (70).Source: §7.1 · p. 49

P SWAP UP. (306)

This section constructs block encodings for averaged powers of the tilted walk and implements quantum conditioning-and-search. It also addresses unknown parameters through slack normalization, an outer interval procedure, and an exact bitwise search for Hmax, with polynomial overhead that preserves the stated exponential runtime bounds.

P SWAP UP. (306)

  • For every M ≥ 1, the construction block-encodes Cb,M with error ϵbM using O(M) calls to Ub and U†b.The construction applies polynomial transformations to the Hermitian block encoding of Db; the error bound combines transformation error with the error from replacing Db by its encoded approximation.Source: P SWAP UP. (306) · pp. 51–52

7.2 Implementation of the Quantum Conditioning-and-Search

  • Fixed-point amplitude amplification prepares states meeting the encoded-walk and marking conditions, after which quantum maximum finding in the selected radius-r ball returns an optimum.The procedure prepares Tη, applies the block encoding of Cb,M, and computes gr(x); the final maximum-finding cost is no larger than the corresponding earlier term.Source: §7.2 · p. 53

7.3 Resolving unknown parameters

  • Slack normalization decreases marked amplitude by at most a constant factor while preserving exponential runtime bounds; inverse-polynomial slack with Mδsv = o(n) incurs only a factor 2^-o(n).The spectral slack also enables uniform singular-value amplification while preserving polynomial implementation overhead.Source: §7.3 · p. 55
  • An outer interval search determines Hmax without exhaustive search, and the candidate routine at the correct interval has the same exponential runtime bound as with known Hmax.At the correct interval, the marked-amplitude lower bound differs from the known-Hmax bound by at most a factor 2^o(n); amplitude detection distinguishes it from preceding intervals, where the marked amplitude is zero.Source: §7.3 · pp. 55–57
  • O(log(W/δH)) amplitude tests recover Hmax exactly by bitwise binary search because H has an exact binary representation.The search tests thresholds within the first nonempty interval, marking all successful centers when the threshold is at most Hmax and none otherwise.Source: §7.3 · p. 57
  • After recovering Hmax, the algorithm constructs the exact normalization of G, runs the main tilted-walk algorithm once, and verifies its assignment by evaluating H.Source: §7.3 · p. 57
  • Polynomial-size search overhead and bounded total error leave the exponential runtime bounds unchanged, while the O(ξ) perturbation contributes only 2o(n).Inverse-polynomial failure probability per test and a union bound give bounded total error.Source: §7.3 · p. 57

8 Conclusion

The conclusion presents quantum tilted walks as a direct successful-set amplitude bound that generalizes ordinary walk powers and recovers generalized short-path algorithms as a special case. It reports super-quadratic speedups over conditioning-and-search for two weighted CSP families, while distinguishing the synthetic example from a hard optimization result.

8 Conclusion

  • Averaging powers of the tilted operator directly bounds successful-set amplitude without requiring approximation of the tilted-Hamiltonian ground-state projector or a lower bound on its spectral gap.At zero bias the construction reduces to an average of ordinary walk powers; sufficiently large powers recover generalized short-path algorithms.Source: §8 · p. 57
  • Under the stated assumptions, tilted walks obtain super-quadratic speedups over classical conditioning-and-search for weighted MAX-Ek-LIN2 and weighted MAX-k-CSP.Source: §8 · p. 57
  • The framework replaces stationarity with pointwise amplitude-retention and objective-change conditions, but the illustrative example’s target is easy to construct and is not a hard optimization result.Source: §8 · pp. 57–58

AI Usage Disclosure

The authors used large language models for writing, grammar, and technical audits, then separately checked all AI-generated outputs and retain responsibility for the draft’s statements.

AI Usage Disclosure

  • Large language models assisted with writing and grammar and audited technical material for rigor and completeness.Source: AI Usage Disclosure · p. 58
  • The authors separately checked all AI-generated outputs and remain responsible for the correctness of every statement in the draft.Source: AI Usage Disclosure · p. 58

Disclaimer

The paper is informational, not investment research or advice, and JPMorgan Chase and its affiliates disclaim warranties and liability for its contents and potential effects.

Disclaimer

  • JPMorgan Chase and its affiliates make no express or implied warranty and accept no liability concerning the paper’s information or potential legal, compliance, tax, or accounting effects.Source: Disclaimer · p. 58
  • The paper is not investment research or advice, a transaction recommendation or solicitation, or intended to evaluate the merits of participating in a transaction.Source: Disclaimer · p. 58
  • The paper was prepared for informational purposes by JPMorgan Chase’s Global Technology Applied Research center, not its Research Department or affiliates.Source: Disclaimer · p. 58
Loading 2609.40088v1…