Beyond Single Trajectories: Optimal Control and Jordan-Lie Algebra in Hybrid Quantum Walks for Combinatorial Optimization

Authors per arXiv listing · arXiv:2604.25760 · new submission, quant-ph · score 8/10

Abstract

The Quantum Approximate Optimization Algorithm (QAOA) follows a single, fixed evolution path, overlooking the potential computational advantage of coherently superposing multiple trajectories. Here we overcome this limitation with a hybrid quantum walk (HQW) ansatz that superposes multiple Hamiltonian-driven paths coherently within each circuit layer via a dynamical coin operator. QAOA emerges as a special case of this framework with a static Pauli-X coin. Using Pontryagin's minimum principle, we derive the optimal form of the coin operator, demonstrating that it generally differs from a constant gate. A dynamical Lie algebra analysis reveals that HQW generates a strictly larger Jordan-Lie algebra, providing an algebraic foundation for its enhanced expressivity. Especially, we reveal the connection between the unique Jordan product negativity in HQW's DLA and its performance advantages. Numerical experiments on Max-Cut and Maximum Independent Set problems show that HQW systematically outperforms QAOA in convergence speed, solution accuracy, and robustness.

Executive summary

A Hybrid Quantum Walk (HQW) ansatz that generalises QAOA by superposing multiple Hamiltonian-driven evolution paths within each layer via a dynamical coin operator. QAOA is the special case where the coin is a static Pauli-X. Pontryagin's minimum principle is used to derive the optimal coin operator (generally not constant); a Dynamical Lie Algebra analysis shows HQW generates a strictly larger Jordan-Lie algebra than QAOA, with the Jordan-product negativity of the DLA correlating linearly (r = 0.96) with HQW's performance advantage. Numerical results on Max-Cut (50 random 8-vertex graphs) and MIS show HQW dominating QAOA in convergence speed, accuracy, and robustness, with average improvements of 11-28% in (1-r).

Main contribution

Two distinct technical contributions. (1) The HQW ansatz itself is shown to strictly subsume QAOA: when the coin operator is fixed to Pauli-X, HQW reduces to QAOA. Pontryagin's minimum principle is used to derive the optimal coin operator analytically, showing it generally takes three discrete values u(t) ∈ {0, 1/2, 1} corresponding to three dynamical phases (coin operation, mixer evolution, cost evolution). (2) A Dynamical Lie Algebra characterisation showing HQW generates a strictly larger algebra than QAOA — specifically a Jordan-Lie algebra with nonzero Jordan products i{H_c, H_b}. The Jordan-product negativity is shown to correlate linearly (r = 0.9605, p = 7.15e-11) with HQW's performance gain over QAOA on a fixed graph instance, providing an algebraic predictor of when HQW will outperform QAOA.

Key theorems / results / algorithms

QAOA as a special case of HQW (Sec. III): when the coin operator C is fixed to the Pauli-X gate, HQW reduces exactly to QAOA. Proof by direct algebraic manipulation.
Theorem (Optimal coin operator, Sec. IV): via Pontryagin's minimum principle, the optimal coin operator takes the form (n_x(t) X + n_y(t) Y + n_z(t) Z) ⊗ I with control parameter u(t) ∈ {0, 1/2, 1}, corresponding to three discrete dynamical phases. A static Pauli-X coin is generally suboptimal.
Theorem (DLA expressivity, Sec. V): the dynamical Lie algebra generated by HQW's elementary operators is strictly larger than QAOA's; specifically, HQW generates a Jordan-Lie algebra with nontrivial Jordan products i{H_c, H_b}, while QAOA's DLA is a standard Lie algebra.
Empirical theorem (Jordan-product negativity correlation, Sec. VI): HQW's relative improvement over QAOA correlates linearly with the Jordan-product negativity N_min of the DLA: y = 0.430 x − 0.010 with r = 0.9605 (p = 7.15e-11) across 50 random 8-vertex graphs.
Numerical results (Sec. VII): on 50 random 8-vertex Max-Cut graphs (18-23 edges), HQW improves average (1-r) by mean 11.63% (median 11.93%); on the harder denser set (24-28 edges), mean improvement is 28.26% (median 20.80%). On 50 best-performance comparisons, HQW never underperforms QAOA within tolerance 1e-6.

Detailed walkthrough

The setup (Sec. I–II) frames QAOA as a single fixed evolution path and notes that this single-path structure is an expressivity bottleneck. The Hybrid Quantum Walk (Aharonov et al. 2018; cited as ref [31]) unifies discrete coin-controlled walks with continuous-time Hamiltonian evolution: a unitary coin operator C acts on an auxiliary coin space and gates which Hamiltonian-driven evolution is applied at each step. The HQW ansatz is W(t) = e^{-iHt}(C ⊗ I) with H = sum_j |j>

Section III's "QAOA as a special case" theorem is technically straightforward but conceptually crucial. With a single coin qubit and the coin operator fixed to Pauli-X, the conditional Hamiltonian collapses to the standard alternating QAOA structure: the coin is just a "switch" that selects H_b or H_c at each layer. With a generic time-dependent coin, the switch becomes a coherent superposition over selections — multiple paths in superposition.

The optimal-coin derivation (Sec. IV) applies Pontryagin's minimum principle to the time-optimal control problem for HQW. The minimisation yields a control parameter u(t) restricted to {0, 1/2, 1}, with three corresponding Hamiltonians: (n_x X + n_y Y + n_z Z) ⊗ I (the coin operation), |0><0| ⊗ H_b (the mixer), and |1><1| ⊗ H_c (the cost). Critically, this discrete set is an emergent property of the optimal-control derivation — not an a priori restriction — and it is what makes the optimal coin generally non-constant. The connection to adiabatic evolution is made precise: QAOA is a discrete analog of standard quantum adiabatic evolution; HQW is a discrete analog of extended adiabatic evolution with an intermediate "catalyst" Hamiltonian.

The Dynamical Lie Algebra analysis (Sec. V) is the algebraic backbone. The DLA is the Lie algebra generated by the elementary operators of the ansatz; it bounds the expressivity. QAOA's DLA forms a standard Lie algebra with brackets like [H_c, H_b]. HQW's DLA additionally contains Jordan-product terms i{H_c, H_b} = i(H_c H_b + H_b H_c), making it a richer Jordan-Lie algebra. The dimension of HQW's DLA is strictly larger than QAOA's, providing an algebraic explanation for the expressivity advantage.

Section VI introduces "Jordan-product negativity" N_min — a scalar quantity computed from the eigenvalue structure of i{H_c, H_b} — and proves it characterises which graphs HQW outperforms QAOA on. The geometric interpretation (Fig. 4b): when N_min ≈ 0, the QAOA reachable manifold is nearly flat and HQW offers little advantage; when N_min ≪ 0, the HQW manifold becomes highly curved with transverse directions generated by the Jordan product, giving HQW access to state-space directions QAOA cannot reach. The empirical correlation (Fig. 4a) is r = 0.9605 with p = 7.15e-11 over 50 graphs — a remarkably strong predictor of when HQW will win.

The numerical experiments (Sec. VII) test on 50 random 8-vertex Max-Cut graphs in two density regimes (18-23 and 24-28 edges) and a single 8-vertex MIS instance. HQW dominates QAOA in average (1-r) — mean improvement 11.63% (sparser graphs) and 28.26% (denser). The convergence-speed plots (Fig. 12, 910) show HQW reaching the ground state at smaller p than QAOA. Best-performance scatter plots (Fig. s3, s4) confirm HQW essentially never underperforms QAOA within numerical tolerance. Larger-graph results (12-vertex Max-Cut, 10-vertex MIS in Fig. s9, s10) show the advantage persists at larger sizes.

The combination of optimal-control derivation + algebraic characterisation + tight empirical correlation is methodologically strong. The Jordan-product negativity gives a computable a-priori predictor of when HQW will help, which is the kind of diagnostic Y3-style end-to-end studies could borrow when picking ansatz families for portfolio QAOA.

Figures

Figure 1. Schematic of a p-step HQW. |0> ⊗ |s> = |0> ⊗ |+>^{⊗n} is the initial state; first qubit = coin state, other n qubits = position space. Each yellow area is a step that applies coin C_i then conditional Hamiltonian evolution e^{-i|1><1|⊗H_c gamma_i} e^{-i|0><0|⊗H_b beta_i}.

Figure 2. Correlation between Jordan-product negativity N_min and HQW performance advantage. Linear fit y = 0.430 x − 0.010, r = 0.9605, p = 7.15e-11.

Figure 3. Experimental results on an 8-vertex Max-Cut instance. (a) Expectation value of −H_C as a function of depth p (QAOA) or 2p steps (HQW), shaded regions = std over 100 random initialisations, dashed line = ground state energy. (b) Projection probabilities on first four eigenspaces of −H_C. HQW shows fastest growth in ground state probability with depth.

Figure 4. Experimental results on an 8-vertex MIS instance. Same quantities as Figure 3.

Figure 5. Scatter plot of average (1-r) for QAOA vs. HQW on 50 8-vertex graphs (18-23 edges). Diagonal = equal performance; both axes log scale.

Figure 6. Distribution of HQW relative improvement over QAOA across 50 8-vertex graphs (18-23 edges). Mean 11.63%, median 11.93%.

Figure 7. Same scatter plot for 50 8-vertex graphs (24-28 edges).

Figure 8. Distribution of HQW relative improvement over QAOA across 50 8-vertex graphs (24-28 edges). Mean 28.26%, median 20.80%.

Citations to Yuan's papers

No direct citation to any of Y1–Y6 found in bibliography.

Overlap with Y1–Y6

Y1. Direct method overlap. Y1's iterative warm-start QAOA modifies QAOA to improve it within the QAOA family. HQW modifies QAOA to a strictly larger ansatz family while keeping QAOA as a special case. Both are "QAOA+" methods aimed at NISQ-era combinatorial optimisation; the comparison "iterative warm-start vs. coin-controlled superposition" would be a natural follow-up benchmark.

Y3. Method overlap. Y3 found that ansatz/optimiser choice matters as much as anything else for end-to-end QAOA performance. HQW provides a new ansatz family that strictly dominates QAOA in expressivity, with an algebraic predictor (Jordan-product negativity) for when the dominance manifests. Plausibly worth replacing standard QAOA with HQW in Y3-style portfolio experiments and reporting the same noise-regime crossover analysis.

Y2. Light scope overlap. Y2 also designs a QAOA variant for a constrained problem. HQW does not yet handle hard constraints in the same way; combining HQW's coin-controlled superposition with Y2's hard-mixer for cardinality preservation could be a methodological extension worth exploring.

Recommended action for Yuan

Read Sec. IV–V carefully. The Pontryagin derivation of the optimal coin and the Jordan-Lie algebra characterisation are unusual machinery for a QAOA-variant paper and are worth understanding in detail — they suggest a roadmap for "expressivity by design" that is more principled than the usual "add more parameters" approach.
Adapt for portfolio QAOA (Y3) on small instances first. Compute the Jordan-product negativity for a small DGMVP instance to predict whether HQW would help; if positive, run a head-to-head comparison.
Cite in next QAOA-variant paper. When framing the next iteration of Y1's warm-started QAOA work, citing HQW as a complementary "ansatz expressivity" axis sharpens the contrast and helps situate the field landscape.
Consider a follow-up combining HQW + Y2's hard mixer. A coin-controlled superposition of cardinality-preserving evolutions on different sub-mixers could be a richer ansatz for cardinality-constrained portfolio QAOA — a clean joint paper.