Yun Shang

The Quantum Approximate Optimization Algorithm (QAOA) is constrained by an ansatz that follows a single, fixed evolution path, neglecting the potential computational advantage of coherently superposing multiple trajectories. We introduce a generalized ansatz based on the hybrid quantum walk (HQW), which incorporates a dynamical coin operator to superpose multiple Hamiltoniandriven paths coherently within a single circuit layer. QAOA emerges as a restrictive special case, corresponding to 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. Numerical experiments on Max-Cut and Maximum Independent Set problems show that HQW systematically outperforms QAOA in convergence speed, solution accuracy, and robustness. A dynamical Lie algebra analysis reveals that HQW generates a strictly larger Jordan-Lie algebra, providing an algebraic foundation for its enhanced expressivity. Our work establishes a path-superposition paradigm for quantum optimization, combining optimal control theory with algebraic structure to advance the design of quantum algorithms.

Quantum walks, both discrete and continuous, serve as fundamental tools in quantum information processing with diverse applications. This work introduces a hybrid quantum walk model that integrates the coin mechanism of discrete walks with the Hamiltonian-driven time evolution of continuous walks. Through systematic analysis of probability distributions, standard deviations, and entanglement entropy on fundamental graph structures (2-vertex circles, stars, and lines), we reveal distinctive dynamical characteristics that differentiate our model from conventional quantum walk paradigms. The proposed framework demonstrates unifying capabilities by naturally encompassing existing quantum walk models as special cases. Two significant applications emerge from this hybrid architecture: (1) We develop a novel protocol for perfect state transfer(PST) in general connected graphs, overcoming the limitations of previous graph-specific approaches. A PST on a tree graph has been implemented on a quantum superconducting processor. (2) We devise a quantum algorithm for multiplying $K$ adjacency matrices of $n$-vertex regular graphs with time complexity $O(n^2d_1\cdots d_K)$, outperforming classical matrix multiplication $(O(n^{2.371552}))$ when vertex degrees $d_i$ are bounded. The algorithm's efficacy for triangle counting is experimentally validated through the quantum simulation on PennyLane. These results establish the hybrid quantum walk as a versatile framework bridging discrete and continuous paradigms while enabling practical quantum advantage in graph computation tasks.

Quantum dynamic programming (QDP) holds promise for accelerating combinatorial optimization, yet its theoretical speedups often clash with the constraints of real hardware. We identify a fundamental tension: classical dynamic programming requires discriminating between subproblem solutions, a task at odds with the indistinguishability inherent to quantum superposition. We distill four key implementation challenges—step dependency, measurement reliance, subspace-specific thresholding, and recursive oracle expansion—that cause the practical complexity of hybrid QDP algorithms (e.g., Ambainis et al.’s TSP solver) to vastly exceed their theoretical estimates. To bridge this gap, we design efficient quantum state-preparation algorithms for Hamiltonian cycles and permutations, with the latter achieving optimal asymptotic resource overhead. Furthermore, by quantizing classical dynamic programming, we present a practically realizable quantum algorithm for TSP (QDP(search)), and rigorously analyze its complexity under our identified challenges. Combining state preparation with a quantum search that uses a shortcut of the Quantum Fourier Transform, we obtain the QDP(HC) algorithm, which achieves the lowest practical complexity among all currently implementable quantum TSP solvers. This work provides a critical reference for designing implementation-aware quantum algorithms on near-term hardware.