Quantum algorithms are commonly designed within the circuit paradigm or through adiabatic evolution. Here we introduce \emph{Quantum Path Finder} (QPF), a distinct algorithm-design paradigm based on non-Abelian gauge dynamics in a constraint-protected degenerate manifold. Each Boolean variable is promoted to a qutrit whose additional state represents an unassigned variable. The problem Hamiltonian then defines a connected manifold of feasible partial assignments, and time-dependent local qutrit rotations generate coherent transport on this manifold. Unlike conventional adiabatic quantum computation, QPF does not require the state to follow an instantaneous eigenstate along a prescribed interpolation: adiabaticity with respect to the constraint gap protects the feasible manifold, while adiabatic following within that manifold is optional. The algorithmic task is therefore to design paths and interference in constraint space rather than only to engineer a sequence of gates or a ground-state interpolation. We illustrate the framework with three applications. For unstructured search, a two-level analysis and numerical evolution recover Grover-type scaling under explicitly stated assumptions. For complete $3$-XORSAT, the accessible gauge sector has a size-independent gap, in contrast to the exponentially closing gap of a conventional transverse-field adiabatic path. For satisfiable $3$-SAT instances, finite-size benchmarks demonstrate high satisfied-clause fractions at short classical comparison budgets, without claiming an equal-cost quantum advantage. We also outline a superconducting-qutrit implementation and discuss the conceptual relationship between QPF and nondeterministic Turing machine.
AI Summary
The paper asks whether coherent dynamics over feasible partial assignments can provide a framework for quantum constraint solving. Quantum Path Finder (QPF) adds an unassigned state to each Boolean variable, producing a qutrit encoding whose zero-energy manifold contains all nonviolating partial assignments and is connected by local assignment/unassignment moves. Local rotations of an isospectral constraint Hamiltonian induce a projected non-Abelian gauge Hamiltonian. Constraint-gap protection suppresses leakage; eigenstate following within the manifold is optional.
Three applications are studied. For unstructured search with $N=2^n$ strings and $M$ marked states, a boundary-coupling analysis gives an avoided-crossing gap $\Theta(\omega\sqrt{M/N})$ and local-adiabatic runtime $O(\operatorname{poly}(n)\sqrt{N/M}/\omega)$, conditional on isolated-crossing and finite-overlap assumptions; numerical evolution supports Grover-type scaling. For satisfiable complete $3$-XORSAT, a collective-spin reduction plus four shallow orbit states establishes a size-independent positive gap in the accessible permutation-invariant sector. The chain alone has gap at least $\omega/\sqrt2$, contrasting with exponential gap closure along the transverse-field interpolation studied. Ideal projected simulations of satisfiable $3$-SAT at clause density $m/n=6$, using $T=n^2$, report mean satisfied-clause fractions above approximately $0.97$.
The SAT comparisons use unequal quantum/classical resources and very short classical budgets; longer simulated annealing runs outperform the fixed quantum reference. Other stated limitations include unquantified leakage, noise and accumulated finite-constraint corrections, potentially many-body interactions, and encoding/readout overheads. The gap theorem does not extend to general XORSAT or SAT. A spin-1 formulation and superconducting-qutrit implementation outline are also provided.
Little sign of AI-generated textUnclear noveltyStrong assumptionsMissing comparison
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
Quantum algorithms are commonly designed within the circuit paradigm or through adiabatic evolution. Here we introduce \emph{Quantum Path Finder} (QPF), a distinct algorithm-design paradigm based on non-Abelian gauge dynamics in a constraint-protected degenerate manifold. Each Boolean variable is promoted to a qutrit whose additional state represents an unassigned variable. The problem Hamiltonian then defines a connected manifold of feasible partial assignments, and time-dependent local qutrit rotations generate coherent transport on this manifold. Unlike conventional adiabatic quantum computation, QPF does not require the state to follow an instantaneous eigenstate along a prescribed interpolation: adiabaticity with respect to the constraint gap protects the feasible manifold, while adiabatic following within that manifold is optional. The algorithmic task is therefore to design paths and interference in constraint space rather than only to engineer a sequence of gates or a ground-state interpolation. We illustrate the framework with three applications. For unstructured search, a two-level analysis and numerical evolution recover Grover-type scaling under explicitly stated assumptions. For complete 3-XORSAT, the accessible gauge sector has a size-independent gap, in contrast to the exponentially closing gap of a conventional transverse-field adiabatic path. For satisfiable 3-SAT instances, finite-size benchmarks demonstrate high satisfied-clause fractions at short classical comparison budgets, without claiming an equal-cost quantum advantage. We also outline a superconducting-qutrit implementation and discuss the conceptual relationship between QPF and nondeterministic Turing machine.
The paper asks whether coherent dynamics over feasible partial assignments can provide a framework for quantum constraint solving. Quantum Path Finder (QPF) adds an unassigned state to each Boolean variable, producing a qutrit encoding whose zero-energy manifold contains all nonviolating partial assignments and is connected by local assignment/unassignment moves. Local rotations of an isospectral constraint Hamiltonian induce a projected non-Abelian gauge Hamiltonian. Constraint-gap protection suppresses leakage; eigenstate following within the manifold is optional.
Three applications are studied. For unstructured search with N=2n strings and M marked states, a boundary-coupling analysis gives an avoided-crossing gap Θ(ωM/N) and local-adiabatic runtime O(poly(n)N/M/ω), conditional on isolated-crossing and finite-overlap assumptions; numerical evolution supports Grover-type scaling. For satisfiable complete 3-XORSAT, a collective-spin reduction plus four shallow orbit states establishes a size-independent positive gap in the accessible permutation-invariant sector. The chain alone has gap at least ω/2, contrasting with exponential gap closure along the transverse-field interpolation studied. Ideal projected simulations of satisfiable 3-SAT at clause density m/n=6, using T=n2, report mean satisfied-clause fractions above approximately 0.97.
The SAT comparisons use unequal quantum/classical resources and very short classical budgets; longer simulated annealing runs outperform the fixed quantum reference. Other stated limitations include unquantified leakage, noise and accumulated finite-constraint corrections, potentially many-body interactions, and encoding/readout overheads. The gap theorem does not extend to general XORSAT or SAT. A spin-1 formulation and superconducting-qutrit implementation outline are also provided.
We give a quantum algorithm for solving instances of the satisfiability problem, based on adiabatic evolution. The evolution of the quantum state is governed by a time-dependent Hamiltonian that interpolates between an initial Hamiltonian, whose ground state is easy to construct, and a final Hamiltonian, whose ground state encodes the satisfying assignment. To ensure that the system evolves to the desired final ground state, the evolution time must be big enough. The time required depends on the minimum energy difference between the two lowest states of the interpolating Hamiltonian. We are unable to estimate this gap in general. We give some special symmetric cases of the satisfiability problem where the symmetry allows us to estimate the gap and we show that, in these cases, our algorithm runs in polynomial time.
Combinatorial optimisation constitutes a central class of computational problems with broad relevance across science and industry, combining foundational theoretical interest with significant real-world impact. Many problems of practical importance admit concise mathematical formulations, yet resist efficient classical solution methods due to their NP-hard structure. Quantum computing offers several algorithmic paradigms that promise structural speedups for such problems. Most quantum and hybrid frameworks fall into one of the following three categories: algorithms based on continuous adiabatic evolution, such as quantum annealing; circuit-based variational quantum algorithms; circuit-based approaches based on Grover's algorithm. These three algorithmic families are conceptualised for different kinds and generations of quantum architectures, often studied in isolation from each other and from preexisting sophisticated classical methods. This thesis develops a unified, predominantly circuit-based treatment of quantum algorithms for combinatorial optimisation, with a particular focus on principled design transfers between near-term parametric algorithms and far-term fault-tolerant approaches. Starting from the Boolean circuit model, reversible and quantum circuit formulations are derived that allow for precise size and depth analysis of classical control logic, reversible embeddings, and quantum realisations of Boolean and pseudo-Boolean functions. These constructions form a common backbone for optimisation algorithms based on adiabatic evolution, variational principles, and amplitude amplification. Adiabatic quantum computation is analysed within this circuit framework, leading to explicit convergence conditions and resource bounds for discretised adiabatic evolutions driven by pseudo-Boolean cost functions of bounded degree. Variational quantum algorithms are then revisited with an emphasis on feasibility-preserving operations and mixing families. In this context, a novel class of exhaustive variational quantum algorithms is introduced, characterised by finite parameterisations that provably reach optimal solutions. These constructions naturally induce state-preparation routines that guarantee to generate superpositions of all feasible solutions. Finally, Grover’s algorithm and its generalisations are studied as optimisation methods, highlighting their structural dependence on feasible-state preparation and their conceptual proximity to variational and adiabatic approaches. By establishing explicit design transfer principles between these paradigms, this thesis provides a unified perspective on quantum optimisation algorithms, accompanied by concrete circuit constructions and quantitative resource analyses.
The discrete formulation of adiabatic quantum computing is compared with other search methods, classical and quantum, for random satisfiability (SAT) problems. With the number of steps growing only as the cube of the number of variables, the adiabatic method gives solution probabilities close to 1 for problem sizes feasible to evaluate via simulation on current computers. However, for these sizes the minimum energy gaps of most instances are fairly large, so the good performance scaling seen for small problems may not reflect asymptotic behavior where costs are dominated by tiny gaps. Moreover, the resulting search costs are much higher than for other methods. Variants of the quantum algorithm that do not match the adiabatic limit give lower costs, on average, and slower growth than the conventional GSAT heuristic method.
Quantum algorithm design plays a crucial role in exploiting the computational advantage of quantum devices. Here we develop a deep-reinforcement-learning based approach for quantum adiabatic algorithm design. Our approach is generically applicable to a class of problems with solution hard-to-find but easy-to-verify, e.g., searching and NP-complete problems. We benchmark this approach in Grover-search and 3-SAT problems, and find that the adiabatic algorithm obtained by our RL approach leads to significant improvement in the resultant success probability. In application to Grover search, our RL design automatically produces an adiabatic quantum algorithm that has the quadratic speedup. We find for all our studied cases that quantitatively the RL-designed algorithm has a better performance compared to the analytically constructed nonlinear Hamiltonian path when the encoding Hamiltonian is solvable, and that this RL-design approach remains applicable even when the nonlinear Hamiltonian path is not analytically available. In 3-SAT we find RL design has fascinating transferability---the adiabatic algorithm obtained by training on a specific choice of clause number leads to better performance consistently over the linear algorithm on different clause numbers. These findings suggest the applicability of reinforcement learning for automated quantum adiabatic algorithm design. Further considering the established complexity equivalence of circuit and adiabatic quantum algorithms, we expect the RL-designed adiabatic algorithm to inspire novel circuit algorithms as well. Our approach is potentially applicable to different quantum hardware from trapped ions and optical lattices to superconducting-qubit devices.
Implementing quantum gates as non-Abelian holonomies, a class of topologically protected unitary operators, is a particularly promising paradigm for the design of intrinsically stable quantum computers [1]. In contrast to dynamic phases, the geometric phase accumulated by a quantum system propagating through a Hilbert spaceHdepends exclusively on its path. In general, geometric phases can exhibit arbitrary dimensionality. Wilczek and Zee introduced the idea of multi-dimensional, non-Abelian geometric phases - so called holonomies [2]. Anandan later dropped the requirement of adiabaticity to create holonomies, that are truly time-independent [3]. Non-adiabatic holonomies rely on a subspaceHgeoof the Hilbert-space that is spanned by states{∣Φk⟩}kthat fulfill(Φk∣H^∣Φj⟩=0, whereH^is the system's Hamiltonian. Restricting the propagation toHgeoensures parallel transport and, thus, a purely geometric phase (see Fig. 1a) [4], [5]. Quantum optics constitutes a particularly versatile platform for quantum information processing, and in particular for the construction of non-adiabatic holonomic quantum computers: In addition to integration and miniaturization provided by the platform, the bosonic nature of photons also conveniently allows for multiple excitations of the same mode, readily expandingHgeoand enabling the synthesis of holonomies from higher symmetry groupsU(N)as larger and more capable computational units [6], [7].
Combinatorial optimization problems that arise in science and industry typically have constraints. Yet the presence of constraints makes them challenging to tackle using both classical and quantum optimization algorithms. We propose a new quantum algorithm for constrained optimization, which we call quantum constrained Hamiltonian optimization (Q-CHOP). Our algorithm leverages the observation that for many problems, while the best solution is difficult to find, the worst feasible (constraint-satisfying) solution is known. The basic idea of Q-CHOP is to enforce a Hamiltonian constraint at all times, thereby restricting evolution to the subspace of feasible states, and slowly “rotate” an objective Hamiltonian to trace an adiabatic path from the worst feasible state to the best feasible state. Q-CHOP thereby assigns qualitatively distinct roles to the constraint and objective functions of a constrained optimization problem. We additionally propose a version of Q-CHOP that can start in any feasible state. Finally, we benchmark Q-CHOP against the commonly-used adiabatic algorithm of quantum annealing with an objective function that penalizes constraint violation, and find that Q-CHOP consistently performs significantly better on a wide range of problems, including textbook graph problems, knapsack problems, combinatorial auctions, and a real-world financial use case of bond exchange-traded fund basket optimization.