Beyond Stoquasticity: Structural Steering and Interference in Quantum Optimization

• URL: http://arxiv.org/abs/2509.16263v1
• Date: Thu, 18 Sep 2025 04:27:42 GMT
• Title: Beyond Stoquasticity: Structural Steering and Interference in Quantum Optimization
• Authors: Vicky Choi,
• Abstract summary: We present a theoretical analysis of the DIC-DAC-DOA algorithm, a non-stoquastic quantum algorithm for solving the Independent Set (MIS) problem.<n>The core of this speedup lies in the ability of the evolving ground state to develop both positive and negative amplitudes, enabled by the non-stoquastic XX-driver.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a theoretical analysis of the DIC-DAC-DOA algorithm, a non-stoquastic quantum algorithm for solving the Maximum Independent Set (MIS) problem. The algorithm runs in polynomial time and achieves exponential speedup over both transverse-field quantum annealing (TFQA) and classical algorithms on a structured family of NP-hard MIS instances, under assumptions supported by analytical and numerical evidence. The core of this speedup lies in the ability of the evolving ground state to develop both positive and negative amplitudes, enabled by the non-stoquastic XX-driver. This sign structure permits quantum interference that produces negative amplitudes in the computational basis, allowing efficient evolution paths beyond the reach of stoquastic algorithms, whose ground states remain strictly non-negative. In our analysis, the efficiency of the algorithm is measured by the presence or absence of an anti-crossing, rather than by spectral gap estimation as in traditional approaches. The key idea is to infer it from the crossing behavior of bare energy levels of relevant subsystems associated with the degenerate local minima (LM) and the global minimum (GM). The cliques of the critical LM, responsible for the anti-crossing in TFQA, can be efficiently identified to form the XX-driver graph. The resulting speedup can be attributed to two mechanisms: in the first stage, energy-guided localization within the same-sign block steers the ground state smoothly into the GM-supporting region, while in the second stage, the opposite-sign blocks are invoked and sign-generating quantum interference drives the evolution along an opposite-sign path. Finally, we derive scalable reduced models that provide a concrete opportunity for verification of the quantum advantage mechanism on currently available universal quantum computers.

Related papers

• Quantum Detection of Sequency-Band Structure [0.5729426778193398]
  We present a quantum algorithm for estimating the amplitude content of user-specified sequency bands in quantum-encoded signals.<n>The method employs a sequency-ordered Quantum Walsh-Hadamard Transform (QWHT), a comparator-based oracle that coherently marks basis states within an arbitrary sequency range.<n>This enables the detection of structured signal components, including both high- and low-sequency features, as well as the identification of rapid sign-change behavior associated with noise or anomalies.
  arXiv  Detail & Related papers  (2026-02-09T08:47:51Z)
• Exponential Quantum Speedup on Structured Hard Instances of Maximum Independent Set [0.0]
  We identify a family of classically hard maximum independent set (MIS) instances, and design and analyze a non-stoquastic adiabatic quantum optimization algorithm.<n>The algorithm runs in time and achieves an exponential speedup over both transverse-field quantum and state-of-the-art classical solvers.<n>This identifies a distinctive quantum mechanism underlying the speedup and explains why no efficient classical analogue is likely to exist.
  arXiv  Detail & Related papers  (2026-01-25T04:18:35Z)
• Continual Quantum Architecture Search with Tensor-Train Encoding: Theory and Applications to Signal Processing [68.35481158940401]
  CL-QAS is a continual quantum architecture search framework.<n>It mitigates challenges of costly encoding amplitude and forgetting in variational quantum circuits.<n>It achieves controllable robustness expressivity, sample-efficient generalization, and smooth convergence without barren plateaus.
  arXiv  Detail & Related papers  (2026-01-10T02:36:03Z)
• Scalable Quantum Walk-Based Heuristics for the Minimum Vertex Cover Problem [0.0]
  We propose a novel quantum algorithm for the Minimum Vertex Cover (MVC) problem based on continuous-time quantum walks (CTQWs)<n>In this framework, the coherent propagation of a quantum walker over a graph encodes its structural properties into state amplitudes.<n>We show that the CTQW-based algorithm consistently achieves superior approximation ratios and exhibits remarkable robustness with respect to network topology.
  arXiv  Detail & Related papers  (2025-12-02T17:04:57Z)
• Implementing a Universal Set of Geometric Quantum Gates through Dressed-State assisted STA [39.27725073249277]
  We analyze the implementation of single-qubit gates in a two-level system driven by a microwave field.<n>We show how the dynamical phase can be canceled to obtain purely geometric operations.<n>We extend the protocol to construct non two-qubit gates, highlighting its feasibility for scalable quantum information processing.
  arXiv  Detail & Related papers  (2025-09-10T16:14:34Z)
• Hybrid Reward-Driven Reinforcement Learning for Efficient Quantum Circuit Synthesis [0.0]
  A reinforcement learning framework is introduced for the efficient synthesis of quantum circuits.<n>The framework combines a static, domain-informed reward that guides the agent toward the target state with customizable dynamic penalties.<n> Benchmarking on graph-state preparation tasks for up to seven qubits, we demonstrate that the algorithm consistently discovers minimal-depth circuits.
  arXiv  Detail & Related papers  (2025-07-22T14:39:20Z)
• QAMA: Scalable Quantum Annealing Multi-Head Attention Operator for Deep Learning [48.12231190677108]
  Quantum Annealing Multi-Head Attention (QAMA) is proposed, a novel drop-in operator that reformulates attention as an energy-based Hamiltonian optimization problem.<n>In this framework, token interactions are encoded into binary quadratic terms, and quantum annealing is employed to search for low-energy configurations.<n> Empirically, evaluation on both natural language and vision benchmarks shows that, across tasks, accuracy deviates by at most 2.7 points from standard multi-head attention.
  arXiv  Detail & Related papers  (2025-04-15T11:29:09Z)
• Characterizing randomness in parameterized quantum circuits through expressibility and average entanglement [39.58317527488534]
  Quantum Circuits (PQCs) are still not fully understood outside the scope of their principal application.<n>We analyse the generation of random states in PQCs under restrictions on the qubits connectivities.<n>We place a connection between how steep is the increase on the uniformity of the distribution of the generated states and the generation of entanglement.
  arXiv  Detail & Related papers  (2024-05-03T17:32:55Z)
• Exploiting many-body localization for scalable variational quantum simulation [1.4509156851822589]
  Variational quantum algorithms (VQAs) represent a promising pathway toward achieving practical quantum advantage on near-term hardware.<n>We demonstrate that initializing a hardware-efficient, Floquet-structured Ansatz within the many-body localized (MBL) phase mitigates barren plateaus and enhances algorithmic trainability.
  arXiv  Detail & Related papers  (2024-04-26T17:40:20Z)
• Neutron-nucleus dynamics simulations for quantum computers [49.369935809497214]
  We develop a novel quantum algorithm for neutron-nucleus simulations with general potentials. It provides acceptable bound-state energies even in the presence of noise, through the noise-resilient training method. We introduce a new commutativity scheme called distance-grouped commutativity (DGC) and compare its performance with the well-known qubit-commutativity scheme.
  arXiv  Detail & Related papers  (2024-02-22T16:33:48Z)
• Mitigating Errors on Superconducting Quantum Processors through Fuzzy Clustering [38.02852247910155]
  A new Quantum Error Mitigation (QEM) technique uses Fuzzy C-Means clustering to specifically identify measurement error patterns. We report a proof-of-principle validation of the technique on a 2-qubit register, obtained as a subset of a real NISQ 5-qubit superconducting quantum processor. We demonstrate that the FCM-based QEM technique allows for reasonable improvement of the expectation values of single- and two-qubit gates based quantum circuits.
  arXiv  Detail & Related papers  (2024-02-02T14:02:45Z)
• Quantum amplitude damping for solving homogeneous linear differential equations: A noninterferometric algorithm [0.0]
  This work proposes a novel approach by using the Quantum Amplitude Damping operation as a resource, in order to construct an efficient quantum algorithm for solving homogeneous LDEs. We show that such an open quantum system-inspired circuitry allows for constructing the real exponential terms in the solution in a non-interferometric.
  arXiv  Detail & Related papers  (2021-11-10T11:25:32Z)
• Locally Suppressed Transverse-Field Protocol for Diabatic Quantum Annealing [0.5735035463793007]
  We present the locally suppressed transverse-field (LSTF) protocol, a method for making stoquastic optimization problems compatible with DQA. We show that, provided an optimization problem intrinsically has magnetic frustration due to inhomogeneous local fields, a target qubit can always be manipulated to create a double minimum. Such a double energy minimum can be exploited to induce diabatic transitions to the first excited state and back to the ground state.
  arXiv  Detail & Related papers  (2021-05-24T09:09:27Z)
• Essentiality of the Non-stoquastic Hamiltonians and Driver Graph Design in Quantum Optimization Annealing [0.0]
  A non-stoquastic Hamiltonian can be stoquastic or properly non-stoquastic when its ground state has both positive and negative amplitudes. We show how to design an appropriate XX-driver graph with an appropriate XX-coupler strength without knowing the prior problem structure. The speedup is exponential in the original AC-distance, which can be sub-exponential or exponential in the system size.
  arXiv  Detail & Related papers  (2021-05-05T15:21:34Z)
• Preparation of excited states for nuclear dynamics on a quantum computer [117.44028458220427]
  We study two different methods to prepare excited states on a quantum computer. We benchmark these techniques on emulated and real quantum devices. These findings show that quantum techniques designed to achieve good scaling on fault tolerant devices might also provide practical benefits on devices with limited connectivity and gate fidelity.
  arXiv  Detail & Related papers  (2020-09-28T17:21:25Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.