Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.11262

Gap Sensitivity and Bottleneck Migration in Sparse Constraint-Preserving Quantum Annealing

Aruna Gupta, S. R. Hassan

quant-phSubmitted Oct 8, 2026• Announced Oct 9, 2026• 0 citations
arXivHTMLPDF

Abstract

Constraint-preserving exchange drivers allow many coupling graphs that preserve the same feasible sector, but exhibit different minimum gaps along an annealing path. We derive an exchange-resolved sensitivity of the normalised minimum gap for fixed-cardinality Laplacian drivers sharing a Dicke ground state, and apply it to identify locally favourable modifications of the driver. Numerical experiments indicate this sensitivity reliably predicts beneficial infinitesimal changes, but its reliability decreases when the same direction is extended to a finite edge replacement. The gap landscape tracking reveals one mechanism of this loss of reliability. Improving the active bottleneck can expose a competing minimum, with a more extensive reorganisation of the low-energy subspace. We call this the "repair-and-expose" mechanism and observe it in both dense quadratic and sparse frustrated objective families. This motivates relinearizing the response when competing minima become co-active. In the tested oracle setting, a tied-minimum max-min update is substantially more reliable than continuing the original direction or optimizing only the incoming minimum. Supporting finite-size search and selector tests show that this local information can remain useful beyond the infinitesimal limit, while its practical extraction depends on the driver geometry and identification of the relevant low-energy competitors. These results connect local exchange-resolved gap sensitivity to bottleneck migration and conditional driver redirection.

AI Summary

The paper asks how changing the exchange graph of a fixed-cardinality, constraint-preserving annealing driver affects the minimum gap when connected drivers share the same Dicke ground state. It studies Laplacian drivers normalized by their sector bandwidth. Using Hellmann–Feynman and envelope arguments, it derives an exchange-resolved minimum-gap derivative: a ground–excited-state Dirichlet-energy contrast with a bandwidth-normalization correction. At tied minima, the directional response is the minimum response across active branches, motivating max–min relinearization. Numerical tests primarily use 30 dense quadratic objectives at $N=6$, $K=3$, with five edge budgets and 900 starting records. Of these, 798 admit an oracle-selected positive direction; all improve the re-minimized gap at step sizes $10^{-3}$ and $10^{-2}$, but only 662/798 (82.96%) improve after complete edge replacement. Resolved bottleneck switching occurs on 421/798 paths; 420 first switches occur above the initial gap, illustrating “repair-and-expose.” At 279 interior switching events, protecting all active minima improves 278 cases and abstains once, whereas continuing the original direction harms 171. A second, sparse frustrated family reproduces the qualitative mechanism, with switching on 188/809 paths. Supporting exhaustive search finds modest sensitivity-guided advantages over candidate-evaluation-matched random search at larger tested budgets; classical selectors perform inconsistently. The stated scope is finite-size mechanism identification: exact normalization, oracle eigenstates, numerical gap location, and conditioned selector samples limit practical conclusions. The results do not establish scalable driver design, global convergence, finite-time speedup, or quantum advantage.

Some signs of AI-generated textIncrementalSmall numerics onlyStrong assumptions

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

Ground-State Sampling Correspondence between Penalty-Based and Constrained Quantum Annealing

Shunta Ide, Shu Tanaka

Quantum annealing generally samples degenerate ground states with nonuniform probabilities. This unfair sampling depends on how the driver Hamiltonian couples these states near the end of annealing. For combinatorial optimization problems with a cardinality constraint, the penalty method and constrained quantum annealing (CQA) differ in these couplings. The transverse-field driver of the penalty method does not directly couple feasible ground states, whereas the fully connected XY driver of CQA couples pairs of them related by a single spin exchange. We investigate how this difference affects ground-state sampling, using closed-system simulations of random graph bipartitioning instances together with degenerate perturbation theory. For the instances studied, the conditional ground-state distribution of penalty-based quantum annealing approaches that of CQA at sufficiently large penalties and long annealing times. This convergence can be explained by the effective Hamiltonian of penalty-based quantum annealing, in which virtual single-spin flips to infeasible states generate a second-order interaction proportional to the CQA driver projected onto the feasible ground-state manifold, which is the leading term of the effective Hamiltonian of CQA. In the numerical simulations, the Jensen--Shannon divergence between the conditional ground-state distributions of penalty-based quantum annealing and CQA decreases approximately as the inverse square of the penalty-to-objective energy ratio, consistent with the perturbative analysis. This correspondence between the effective Hamiltonians extends to equal-weight fixed-magnetization constraints under the same perturbative conditions, providing a common mechanism for sampling bias in the two implementations.

quant-pharXiv:2610.26687•Oct 20, 2026•0 citations

Driver Hamiltonians for constrained optimization in quantum annealing

Itay Hen, M. S. Sarandy

One of the current major challenges surrounding the use of quantum annealers for solving practical optimization problems is their inability to encode even moderately sized problems, the main reason for this being the rigid layout of their quantum bits as well as their sparse connectivity. In particular, the implementation of constraints has become a major bottleneck in the embedding of practical problems, because the latter is typically achieved by adding harmful penalty terms to the problem Hamiltonian, a technique that often requires an all-to-all connectivity between the qubits. Recently, a novel technique designed to obviate the need for penalty terms was suggested; it is based on the construction of driver Hamiltonians that commute with the constraints of the problem, rendering the latter constants of motion. In this work we propose general guidelines for the construction of such driver Hamiltonians given an arbitrary set of constraints. We illustrate the broad applicability of our method by analyzing several diverse examples, namely, graph isomorphism, not-all-equal three-satisfiability, and the so-called Lechner-Hauke-Zoller constraints. We also discuss the significance of our approach in the context of current and future experimental quantum annealers.

arXiv:1602.07942•Physical Review A•Jun 13, 2016•73 citations

Parity Mapping for Quantum Optimization on Frustrated Ising Rings

Ruiyi Wang, Anita Weidinger, Glen Bigan Mbeng +2 more

The frustrated Ising ring is one of the simplest models exhibiting exponential closing spectral gaps, making it a paradigmatic and challenging benchmark for quantum annealing (QA). Ground-state preparation for this model has therefore been studied extensively in both continuous-time QA and digitized protocols such as the Quantum Approximate Optimization Algorithm (QAOA). Here, we use the frustrated Ising ring to investigate how the parity mapping affects the performance of both QA and QAOA. For QA, finite-size calculations show that the parity mapping increases the minimum spectral gap under the energy normalization used in this work, thereby enabling faster continuous-time ground state preparation protocols. An ideal implementation of Parity-QA, with a single global constraint, shows no evidence of exponential gap closing over the accessible system sizes, whereas a hardware-motivated decomposition into local constraints restores the exponential decrease, albeit with a smaller fitted exponent than conventional QA. For the digitized protocol, we find that the number of Parity-QAOA layers required to prepare the exact ground state remains constant over the simulated sizes, improving upon the quadratic scaling required by conventional QAOA. To investigate the role of constraints in Parity-QAOA, we further consider a modified Ising ring instance in which the constraint term is essential for preparing the target ground state. We then compare the corresponding resource requirements with those of conventional QAOA.

quant-pharXiv:2608.12213•Aug 13, 2026•2 citations

Enhancement of quantum annealing via n -local catalysts

Roopayan Ghosh, Luca A. Nutricati, Natasha Feinstein +2 more

The potential quantum speedup in solving optimization problems via adiabatic quantum annealing is often hindered by the closing of the energy gap during the anneal, especially when this gap scales exponentially with system size. In this work, we alleviate this bottleneck by demonstrating that for the NP-complete Maximum Weighted Independent Set (MWIS) problem, an informed choice of n -local catalysts (operators involving n qubits) can reopen the gap during the annealing process. By analyzing first-order phase transitions in toy instances of the MWIS problem, we first identify direct-tunneling catalysts that effectively eliminate the transition and provide an analytical discussion on when the sign of the catalyst influences its impact. We then reveal that n -local catalysts exponentially improve gap scaling and in certain scenarios are as effective as direct-tunnel coupling between two minima. Utilizing this understanding, we show that they also increase the efficiency of ground-state preparation via adiabatic quantum annealing in random graphs and analytically demonstrate the necessity of their placement across unfrustrated loops in the graph for effective performance in MWIS problems. Additionally, using a circuit implementation of the n -local catalyst (requiring 2 n nearest-neighbor gates), we demonstrate that both the circuit depth and the total number of gates required to solve the problem are reduced by several orders of magnitude when compared to the discrete-time version of traditional quantum annealing using local drivers. Our analysis suggests that nonlocal quantum fluctuations entangling multiple qubits as a catalyst are key to achieving the desired quantum advantage.

arXiv:2409.13029•Physical Review Research•Feb 9, 2026•19 citations

Mapping Constrained Optimization Problems to Quantum Annealing with Application to Fault Diagnosis

Zhengbing Bian, Fabián A. Chudak, Robert B. Israel +3 more

Current quantum annealing (QA) hardware suffers from practical limitations such as finite temperature, sparse connectivity, small qubit numbers, and control error. We propose new algorithms for mapping boolean constraint satisfaction problems (CSPs) onto QA hardware mitigating these limitations. In particular we develop a new embedding algorithm for mapping a CSP onto a hardware Ising model with a fixed sparse set of interactions, and propose two new decomposition algorithms for solving problems too large to map directly into hardware. The mapping technique is locally-structured, as hardware compatible Ising models are generated for each problem constraint, and variables appearing in different constraints are chained together using ferromagnetic couplings. In contrast, global embedding techniques generate a hardware independent Ising model for all the constraints, and then use a minor-embedding algorithm to generate a hardware compatible Ising model. We give an example of a class of CSPs for which the scaling performance of the D-Wave hardware using the local mapping technique is significantly better than global embedding. We validate the approach by applying D-Wave's QA hardware to circuit-based fault-diagnosis. For circuits that embed directly, we find that the hardware is typically able to find \emph{all} solutions from a min-fault diagnosis set of size N using 1000N samples, using an annealing rate that is 25 times faster than a leading SAT-based sampling method. Further, we apply decomposition algorithms to find min-cardinality faults for circuits that are up to 5 times larger than can be solved directly on current hardware.

arXiv:1603.03111•Frontiers in ICT•Jul 27, 2016•91 citations

Improving the efficiency of quantum annealing with controlled diagonal catalysts

T Hattori, Shu Tanaka

Quantum annealing is a promising algorithm for solving combinatorial optimization problems. It searches for the ground state of the Ising model, which corresponds to the optimal solution of a given combinatorial optimization problem. The guiding principle of quantum annealing is the adiabatic theorem in quantum mechanics, which guarantees that a system remains in the ground state of its Hamiltonian if the time evolution is sufficiently slow. According to the adiabatic theorem, the annealing time required for quantum annealing to satisfy the adiabaticity scales inversely proportional to the square of the minimum energy gap between the ground state and the first excited state during time evolution. As a result, finding the ground state becomes significantly more difficult when the energy gap is small, creating a major bottleneck in quantum annealing. Expanding the energy gap is one strategy for improving the performance of quantum annealing; however, its implementation in actual hardware remains difficult. This study proposes a method for efficiently solving instances with small energy gaps by introducing additional local terms to the Hamiltonian and exploiting the diabatic transition remaining in the small energy gap. The proposed method achieves an approximate quadratic speedup of the exponential scaling exponent in time to solution compared to the conventional quantum annealing. In addition, we investigate the transferability of the parameters obtained with the proposed method.

arXiv:2503.15244•Physical Review A•Feb 3, 2026•4 citations
Constraint-preserving exchange drivers allow many coupling graphs that preserve the same feasible sector, but exhibit different minimum gaps along an annealing path. We derive an exchange-resolved sensitivity of the normalised minimum gap for fixed-cardinality Laplacian drivers sharing a Dicke ground state, and apply it to identify locally favourable modifications of the driver. Numerical experiments indicate this sensitivity reliably predicts beneficial infinitesimal changes, but its reliability decreases when the same direction is extended to a finite edge replacement. The gap landscape tracking reveals one mechanism of this loss of reliability. Improving the active bottleneck can expose a competing minimum, with a more extensive reorganisation of the low-energy subspace. We call this the "repair-and-expose" mechanism and observe it in both dense quadratic and sparse frustrated objective families. This motivates relinearizing the response when competing minima become co-active. In the tested oracle setting, a tied-minimum max-min update is substantially more reliable than continuing the original direction or optimizing only the incoming minimum. Supporting finite-size search and selector tests show that this local information can remain useful beyond the infinitesimal limit, while its practical extraction depends on the driver geometry and identification of the relevant low-energy competitors. These results connect local exchange-resolved gap sensitivity to bottleneck migration and conditional driver redirection.
The paper asks how changing the exchange graph of a fixed-cardinality, constraint-preserving annealing driver affects the minimum gap when connected drivers share the same Dicke ground state. It studies Laplacian drivers normalized by their sector bandwidth. Using Hellmann–Feynman and envelope arguments, it derives an exchange-resolved minimum-gap derivative: a ground–excited-state Dirichlet-energy contrast with a bandwidth-normalization correction. At tied minima, the directional response is the minimum response across active branches, motivating max–min relinearization.
Numerical tests primarily use 30 dense quadratic objectives at N=6N=6N=6, K=3K=3K=3, with five edge budgets and 900 starting records. Of these, 798 admit an oracle-selected positive direction; all improve the re-minimized gap at step sizes 10−310^{-3}10−3 and 10−210^{-2}10−2, but only 662/798 (82.96%) improve after complete edge replacement. Resolved bottleneck switching occurs on 421/798 paths; 420 first switches occur above the initial gap, illustrating “repair-and-expose.” At 279 interior switching events, protecting all active minima improves 278 cases and abstains once, whereas continuing the original direction harms 171. A second, sparse frustrated family reproduces the qualitative mechanism, with switching on 188/809 paths.
Supporting exhaustive search finds modest sensitivity-guided advantages over candidate-evaluation-matched random search at larger tested budgets; classical selectors perform inconsistently. The stated scope is finite-size mechanism identification: exact normalization, oracle eigenstates, numerical gap location, and conditioned selector samples limit practical conclusions. The results do not establish scalable driver design, global convergence, finite-time speedup, or quantum advantage.
Quantum annealing generally samples degenerate ground states with nonuniform probabilities. This unfair sampling depends on how the driver Hamiltonian couples these states near the end of annealing. For combinatorial optimization problems with a cardinality constraint, the penalty method and constrained quantum annealing (CQA) differ in these couplings. The transverse-field driver of the penalty method does not directly couple feasible ground states, whereas the fully connected XY driver of CQA couples pairs of them related by a single spin exchange. We investigate how this difference affects ground-state sampling, using closed-system simulations of random graph bipartitioning instances together with degenerate perturbation theory. For the instances studied, the conditional ground-state distribution of penalty-based quantum annealing approaches that of CQA at sufficiently large penalties and long annealing times. This convergence can be explained by the effective Hamiltonian of penalty-based quantum annealing, in which virtual single-spin flips to infeasible states generate a second-order interaction proportional to the CQA driver projected onto the feasible ground-state manifold, which is the leading term of the effective Hamiltonian of CQA. In the numerical simulations, the Jensen--Shannon divergence between the conditional ground-state distributions of penalty-based quantum annealing and CQA decreases approximately as the inverse square of the penalty-to-objective energy ratio, consistent with the perturbative analysis. This correspondence between the effective Hamiltonians extends to equal-weight fixed-magnetization constraints under the same perturbative conditions, providing a common mechanism for sampling bias in the two implementations.
One of the current major challenges surrounding the use of quantum annealers for solving practical optimization problems is their inability to encode even moderately sized problems, the main reason for this being the rigid layout of their quantum bits as well as their sparse connectivity. In particular, the implementation of constraints has become a major bottleneck in the embedding of practical problems, because the latter is typically achieved by adding harmful penalty terms to the problem Hamiltonian, a technique that often requires an all-to-all connectivity between the qubits. Recently, a novel technique designed to obviate the need for penalty terms was suggested; it is based on the construction of driver Hamiltonians that commute with the constraints of the problem, rendering the latter constants of motion. In this work we propose general guidelines for the construction of such driver Hamiltonians given an arbitrary set of constraints. We illustrate the broad applicability of our method by analyzing several diverse examples, namely, graph isomorphism, not-all-equal three-satisfiability, and the so-called Lechner-Hauke-Zoller constraints. We also discuss the significance of our approach in the context of current and future experimental quantum annealers.
The frustrated Ising ring is one of the simplest models exhibiting exponential closing spectral gaps, making it a paradigmatic and challenging benchmark for quantum annealing (QA). Ground-state preparation for this model has therefore been studied extensively in both continuous-time QA and digitized protocols such as the Quantum Approximate Optimization Algorithm (QAOA). Here, we use the frustrated Ising ring to investigate how the parity mapping affects the performance of both QA and QAOA. For QA, finite-size calculations show that the parity mapping increases the minimum spectral gap under the energy normalization used in this work, thereby enabling faster continuous-time ground state preparation protocols. An ideal implementation of Parity-QA, with a single global constraint, shows no evidence of exponential gap closing over the accessible system sizes, whereas a hardware-motivated decomposition into local constraints restores the exponential decrease, albeit with a smaller fitted exponent than conventional QA. For the digitized protocol, we find that the number of Parity-QAOA layers required to prepare the exact ground state remains constant over the simulated sizes, improving upon the quadratic scaling required by conventional QAOA. To investigate the role of constraints in Parity-QAOA, we further consider a modified Ising ring instance in which the constraint term is essential for preparing the target ground state. We then compare the corresponding resource requirements with those of conventional QAOA.
The potential quantum speedup in solving optimization problems via adiabatic quantum annealing is often hindered by the closing of the energy gap during the anneal, especially when this gap scales exponentially with system size. In this work, we alleviate this bottleneck by demonstrating that for the NP-complete Maximum Weighted Independent Set (MWIS) problem, an informed choice of n -local catalysts (operators involving n qubits) can reopen the gap during the annealing process. By analyzing first-order phase transitions in toy instances of the MWIS problem, we first identify direct-tunneling catalysts that effectively eliminate the transition and provide an analytical discussion on when the sign of the catalyst influences its impact. We then reveal that n -local catalysts exponentially improve gap scaling and in certain scenarios are as effective as direct-tunnel coupling between two minima. Utilizing this understanding, we show that they also increase the efficiency of ground-state preparation via adiabatic quantum annealing in random graphs and analytically demonstrate the necessity of their placement across unfrustrated loops in the graph for effective performance in MWIS problems. Additionally, using a circuit implementation of the n -local catalyst (requiring 2 n nearest-neighbor gates), we demonstrate that both the circuit depth and the total number of gates required to solve the problem are reduced by several orders of magnitude when compared to the discrete-time version of traditional quantum annealing using local drivers. Our analysis suggests that nonlocal quantum fluctuations entangling multiple qubits as a catalyst are key to achieving the desired quantum advantage.
Current quantum annealing (QA) hardware suffers from practical limitations such as finite temperature, sparse connectivity, small qubit numbers, and control error. We propose new algorithms for mapping boolean constraint satisfaction problems (CSPs) onto QA hardware mitigating these limitations. In particular we develop a new embedding algorithm for mapping a CSP onto a hardware Ising model with a fixed sparse set of interactions, and propose two new decomposition algorithms for solving problems too large to map directly into hardware. The mapping technique is locally-structured, as hardware compatible Ising models are generated for each problem constraint, and variables appearing in different constraints are chained together using ferromagnetic couplings. In contrast, global embedding techniques generate a hardware independent Ising model for all the constraints, and then use a minor-embedding algorithm to generate a hardware compatible Ising model. We give an example of a class of CSPs for which the scaling performance of the D-Wave hardware using the local mapping technique is significantly better than global embedding. We validate the approach by applying D-Wave's QA hardware to circuit-based fault-diagnosis. For circuits that embed directly, we find that the hardware is typically able to find \emph{all} solutions from a min-fault diagnosis set of size N using 1000N samples, using an annealing rate that is 25 times faster than a leading SAT-based sampling method. Further, we apply decomposition algorithms to find min-cardinality faults for circuits that are up to 5 times larger than can be solved directly on current hardware.
Quantum annealing is a promising algorithm for solving combinatorial optimization problems. It searches for the ground state of the Ising model, which corresponds to the optimal solution of a given combinatorial optimization problem. The guiding principle of quantum annealing is the adiabatic theorem in quantum mechanics, which guarantees that a system remains in the ground state of its Hamiltonian if the time evolution is sufficiently slow. According to the adiabatic theorem, the annealing time required for quantum annealing to satisfy the adiabaticity scales inversely proportional to the square of the minimum energy gap between the ground state and the first excited state during time evolution. As a result, finding the ground state becomes significantly more difficult when the energy gap is small, creating a major bottleneck in quantum annealing. Expanding the energy gap is one strategy for improving the performance of quantum annealing; however, its implementation in actual hardware remains difficult. This study proposes a method for efficiently solving instances with small energy gaps by introducing additional local terms to the Hamiltonian and exploiting the diabatic transition remaining in the small energy gap. The proposed method achieves an approximate quadratic speedup of the exponential scaling exponent in time to solution compared to the conventional quantum annealing. In addition, we investigate the transferability of the parameters obtained with the proposed method.