← Latest papers
⚛️ quantum physics

Faster than square-root run-time in adiabatic quantum algorithms for Exact Cover 3

This paper proposes a novel quantum algorithm for the NP-complete Exact Cover 3 problem that combines sequential and adiabatic computing techniques to achieve a run-time scaling significantly faster than Grover's square-root bound, ranging from approximately N1/3N^{1/3} to N1/4N^{1/4} depending on the problem's structural connectivity.

Original author: Gernot Schaller, Ralf Schützhold

Published 2026-11-19
📖 1 min read🧠 Deep dive

Original author: Gernot Schaller, Ralf Schützhold

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the author. For technical accuracy, refer to the original paper. Read full disclaimer

Technical Summary: Faster than Square-Root Run-time in Adiabatic Quantum Algorithms for Exact Cover 3

Problem Definition
The paper addresses the Exact Cover 3 (EC3) problem, a specific subclass of 3-satisfiability (3-SAT) problems known to be NP-complete. The problem is defined on nn bits zμ∈{0,1}z_\mu \in \{0, 1\} and seeks a unique solution sequence ww that satisfies mm constraints (clauses) of the form zμ+zν+zρ=1z_\mu + z_\nu + z_\rho = 1. The authors focus on the "hard" regime where the solution is unique (or very few solutions exist), typically occurring when the ratio of clauses to bits (m/nm/n) falls between 60% and 80%. The study assumes a specific structural constraint where almost all bits are involved in exactly two clauses, and no pair of bits shares more than one clause, which represents the most relevant case for complexity analysis.

Methodology
The authors propose a novel adiabatic quantum algorithm that deviates from the conventional interpolation scheme used in standard adiabatic quantum computing.

  1. Hamiltonian Construction: The target Hamiltonian H^EC3\hat{H}_{EC3} is constructed such that its ground state encodes the solution to the EC3 problem. This Hamiltonian is non-negative and corresponds to a frustrated anti-ferromagnet with local fields.
  2. Two-Step Scheme: Instead of interpolating directly from a simple initial Hamiltonian H^in\hat{H}_{in} to the full problem Hamiltonian H^out\hat{H}_{out} (as in the standard scheme H^(t)=[1−f(t)]H^in+f(t)H^out\hat{H}(t) = [1-f(t)]\hat{H}_{in} + f(t)\hat{H}_{out}), the authors split the set of mm clauses into two disjoint subsets:
    • Subset 1 (m1m_1): A set of non-overlapping clauses (no shared qubits).
    • Subset 2 (m2m_2): The remaining clauses, which overlap with the first set.
  3. Initial State Preparation: The algorithm begins by implementing only the first subset of clauses (H^EC31\hat{H}_{EC3}^1). The initial state ∣ψin⟩|\psi_{in}\rangle is prepared within the ground-state manifold (kernel) of H^EC31\hat{H}_{EC3}^1. This state is a reduced superposition of all computational basis states satisfying the first m1m_1 clauses. For each triple of qubits in a clause, the state is a W-state superposition of the three valid solutions; for uninvolved qubits, it is a plus state. A mixing Hamiltonian H^mix\hat{H}_{mix} is added to stabilize this state as the unique ground state.
  4. Adiabatic Evolution: The system evolves by slowly switching on the second subset of clauses (H^EC32\hat{H}_{EC3}^2) while simultaneously reducing the mixing term H^mix\hat{H}_{mix}. The evolution follows the path:
    H^(t)=H^EC31+[1−f(t)]H^mix+f(t)H^EC32 \hat{H}(t) = \hat{H}_{EC3}^1 + [1-f(t)]\hat{H}_{mix} + f(t)\hat{H}_{EC3}^2
    The goal is to stay in the instantaneous ground state, transitioning from the reduced superposition ∣s~⟩|\tilde{s}\rangle to the final unique solution ∣w⟩|w\rangle.

Key Contributions and Results
The primary contribution is the derivation of a quantum run-time scaling that is significantly faster than the square-root scaling (N→N1/2N \to N^{1/2}) characteristic of the Grover search algorithm.

  • Energy Gap Analysis: The authors analyze the minimum energy gap ΔEmin\Delta E_{min} at the avoided level crossing between the ground state and the first excited state. They approximate this transition as a Landau-Zener problem within a two-mode subspace spanned by the initial reduced state ∣s~⟩|\tilde{s}\rangle and the final solution ∣w⟩|w\rangle.
  • Scaling Derivation: The off-diagonal matrix elements driving the transition scale as O(1/N1)O(1/\sqrt{N_1}), where N1N_1 is the number of solutions to the first subset of clauses. Consequently, the minimum gap scales as ΔEmin∼O(1/N1)\Delta E_{min} \sim O(1/\sqrt{N_1}). Since the required adiabatic run-time scales linearly with the inverse of the gap (O(1/ΔE)O(1/\Delta E)), the run-time scales as O(N1)O(\sqrt{N_1}). This dependence on N1N_1 rather than the total search space N=2nN = 2^n allows for a significant speed-up.
  • Run-time Improvements:
    • By selecting m1≈m/4m_1 \approx m/4 non-overlapping clauses, the number of valid states N1N_1 is reduced to approximately (0.85)nN(0.85)^n N. This results in a run-time scaling of N→N1/3N \to N^{1/3}.
    • If the problem structure allows for a larger set of non-overlapping clauses (up to m1≤n/3m_1 \le n/3), the scaling improves to approximately N→N1/4N \to N^{1/4}.
    • The paper notes that allowing for finite clusters of clauses in the first set can further improve the reduction factor, potentially yielding even faster run-times depending on graph connectivity.

Significance and Claims
The paper claims that by intertwining ideas from sequential and adiabatic quantum computing, it is possible to bypass the limitations of conventional adiabatic schemes which are often argued to be limited to Grover-like square-root speed-ups due to Anderson-like localization or small energy gaps.

  • Analytical Advantage: The authors emphasize that their analytical estimation of the minimum gap avoids the shortcomings of numerical approaches, which are limited to small system sizes and may miss the "hard" instances required for NP-completeness.
  • Resource Efficiency: The proposed algorithm scales linearly in space (O(n)O(n) qubits), comparable to classical brute-force search but with a vastly superior run-time. It is contrasted with classical recursive algorithms (like "dancing links") which achieve sub-linear run-times but require super-linear space.
  • Robustness: The authors suggest that the two-step procedure, by increasing the energy gap ΔE\Delta E, may render the algorithm more robust against decoherence and environmental noise compared to sequential quantum algorithms, even without active error correction.

The work concludes that for the EC3 problem class, adiabatic quantum algorithms can achieve run-times ranging from the cube root to the fourth root of the search space size, representing a substantial improvement over standard quantum search bounds.

Drowning in papers in your field?

Get daily digests of the most novel papers matching your research keywords — with technical summaries, in your language.

Try Digest →