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:1810.00194 · Communications in Computational Physics

Quantum Annealing with Anneal Path Control: Application to 2-SAT Problems with Known Energy Landscapes

Ting-Jui Hsu, Fengping Jin, Christian Seidel, Florian Neukart, Hans A. De Raedt, Kristel F. L. Michielsen

Published Apr 28, 2019• 10 citations
arXivHTMLPDF

Abstract

We study the effect of the anneal path control per qubit, a new user control feature offered on the D-Wave 2000Q quantum annealer, on the performance of quantum annealing for solving optimization problems by numerically solving the time-dependent Schrödinger equation for the time-dependent Hamiltonian modeling the annealing problems. The anneal path control is thereby modeled as a modified linear annealing scheme, resulting in an advanced and retarded scheme. The considered optimization problems are 2-SAT problems with 12 Boolean variables, a known unique ground state and a highly degenerate first excited state. We show that adjustment of the anneal path control can result in a widening of the minimal spectral gap by one or two orders of magnitude and an enhancement of the success probability of finding the solution of the optimization problem. We scrutinize various iterative methods based on the spin floppiness, the average spin value, and on the average energy and describe their performance in boosting the quantum annealing process.

DOI
10.4208/cicp.oa-2018-0257

Related papers

Quantum annealing for hard 2-satisfiability problems: Distribution and scaling of minimum energy gap and success probability

Vrinda Mehta, Fengping Jin, Hans A. De Raedt +1 more

In recent years, quantum annealing has gained the status of being a promising candidate for solving various optimization problems. Using a set of hard 2-satisfiability (2-SAT) problems, consisting of problems of up to 18 variables, we analyze the scaling complexity of the quantum annealing algorithm and study the distributions of the minimum energy gap and the success probability. We extend the analysis of the standard quantum annealing Hamiltonian by introducing an additional term, the trigger Hamiltonian, which can be of two types: ferromagnetic and antiferromagnetic. We use these trigger Hamiltonians to study their influence on the success probability for solving the selected 2-SAT problems. We find that although the scaling of the runtime is exponential for the standard and modified quantum annealing Hamiltonians, the scaling constant in the case of adding the trigger Hamiltonians can be significantly smaller. Furthermore, certain choices for the trigger Hamiltonian and annealing times can result in a better scaling than that for simulated annealing. Finally, we also use the quantum annealers of D-Wave Systems Inc. to study their performance in solving the 2-SAT problems and compare it with the simulation results.

arXiv:2202.00118•Physical Review A•Jun 3, 2022•11 citations

Towards Quantum Computing: Solving Satisfiability Problem by Quantum Annealing

Juexiao Su

To date, conventional computers have never been able to efficiently handle certain tasks, where the number of computation steps is likely to blow up as the problem size increases. As an emerging technology and new computing paradigm, quantum computing has a great potential to tackle those hard tasks efficiently. Among all the existing quantum computation models, quantum annealing has drawn significant attention in recent years due to the realization of the commercialized quantum annealer, sparking research interests in developing applications to solve problems that are intractable for classical computers.However, designing and implementing algorithms that manage to harness the enormous computation power from quantum annealer remains a challenging task. Generally, it requires mapping of the given optimization problem into quadratic unconstrained binary optimization(QUBO) problem and embedding the subsequent QUBO onto the physical architecture of quantum annealer. Additionally, practical quantum annealers are susceptible to errors leading to low probability of the correct solution.In this study, we focus on solving Boolean satisfiability (SAT) problem using quantum annealer while addressing practical limitations. We have proposed a mapping technique that maps SAT problem to QUBO, and we have further devised a tool flow that embeds the QUBO onto the architecture of a quantum annealing device. Additionally, We have optimized the proposed embedding flow to reduce run-time in addition to shortening the qubit chain length, leading to robust quantum annealing. To further improve the reliability of quantum annealing, we have also developed a post processing embedding technique that enlarges the energy gap between ground state and the first excited state. To demonstrate the effectiveness of proposed methods, we have conducted experiments on real quantum annealing devices manufactured by D-Wave Systems, showing compelling result of using quantum annealer to solve SAT problem.

•Jan 1, 2018•4 citations

Performance of quantum annealing for 2-satisfiability problems with multiple satisfying assignments

Vrinda Mehta, Hans A. De Raedt, Kristel F. L. Michielsen +1 more

Using a specially constructed set of hard 2-satisfiability problems with four satisfying assignments, we study the scaling and sampling performance of numerical simulation of quantum annealing as well as that of the physical quantum annealers offered by D-Wave. To this end, we use both the standard quantum annealing and reverse annealing protocols in both our simulations and on the D-Wave quantum annealer. In the case of ideal quantum annealing the sampling behavior can be explained by perturbation theory and the scaling behavior of the time to solution depends on the scaling behavior of the minimum energy gap between the ground state and the first-excited state of the annealing Hamiltonian. The corresponding results from the D-Wave quantum annealers do not fit to this ideal picture, but suggest that the scaling of the time to solution from the quantum annealers matches those calculated from the equilibrium probability distribution.

arXiv:2502.01423•Physical Review A•Jun 11, 2025•5 citations

Spin-1 quantum annealing with anisotropy-controlled intermediate-state pathways

M. Haider Akbar, Özgür E. Müstecaplıoğlu

Quantum annealing offers a promising strategy for solving complex optimization problems by encoding the solution into the ground state of a problem Hamiltonian. While most implementations rely on spin-$1/2$ systems, we explore the performance of quantum annealing on a spin-$1$ system where the problem Hamiltonian includes a single ion anisotropy term of the form $D\sum (S^z)^2$. Our results reveal that for a suitable range of the anisotropy strength $D$, the spin-$1$ annealer reaches the ground state with higher fidelity. We attribute this performance to the presence of the intermediate spin level and the tunable anisotropy, which together enable the algorithm to traverse the energy landscape through smaller, incremental steps instead of a single large spin flip. This mechanism effectively lowers barriers in the configuration space and stabilizes the evolution. These findings suggest that higher spin annealers offer intrinsic advantages for robust and flexible quantum optimization, especially for problems naturally formulated with ternary decision variables.

quant-pharXiv:2512.23469•Dec 30, 2025•0 citations

Performance of quantum annealing for 2-satisfiability problems with multiple satisfying assignments

Vrinda Mehta, Hans A. De Raedt, Kristel F. L. Michielsen +1 more

Using a specially constructed set of hard 2-satisfiability problems with four satisfying assignments, we study the scaling and sampling performance of numerical simulation of quantum annealing as well as that of the physical quantum annealers offered by D-Wave. To this end, we use both the standard quantum annealing and reverse annealing protocols in both our simulations and on the D-Wave quantum annealer. In the case of ideal quantum annealing the sampling behavior can be explained by perturbation theory and the scaling behavior of the time to solution depends on the scaling behavior of the minimum energy gap between the ground state and the first-excited state of the annealing Hamiltonian. The corresponding results from the D-Wave quantum annealers do not fit to this ideal picture, but suggest that the scaling of the time to solution from the quantum annealers matches those calculated from the equilibrium probability distribution.

Physical Review A•Jan 1, 2025•0 citations

Advanced anneal paths for improved quantum annealing

Elijah Pelofske, Georg Hahn, Hristo N. Djidjev

Advances in quantum annealing technology make it possible to obtain high quality approximate solutions of important NP-hard problems. With the newer generations of the D-Wave annealer, more advanced features are available which allow the user to have greater control of the anneal process. In this contribution, we study how such features can help in improving the quality of the solutions returned by the annealer. Specifically, we focus on two of these features: reverse annealing and h-gain. Reverse annealing (RA) was designed to allow refining a known solution by backward annealing from a classical state representing the solution to a mid-anneal point where a transverse field is present, followed by an ordinary forward anneal, which is hoped to improve on the previous solution. The h-gain (HG) feature stands for time-dependent gain in Hamiltonian linear (h) biases and was originally developed to help study freezeout times and phase transitions in spin glasses. Here we apply HG to bias the quantum state in the beginning of the annealing process towards the known solution as in the RA case, but using a different apparatus. We also investigate a hybrid reverse annealing/h-gain schedule, which has a backward phase resembling an RA step and whose forward phase uses the HG idea. To optimize the parameters of the schedules, we employ a Bayesian optimization framework. We test all techniques on a variety of input problems including the weighted Maximum Cut problem and the weighted Maximum Clique problem. Our results show that each technique may dominate the others depending on the input instance, and that the HG technique is a viable alternative to RA for some problems.

arXiv:2009.05008•IEEE International Conference on Quantum Computing and Engineering (QCE)•Oct 1, 2020•21 citations
We study the effect of the anneal path control per qubit, a new user control feature offered on the D-Wave 2000Q quantum annealer, on the performance of quantum annealing for solving optimization problems by numerically solving the time-dependent Schrödinger equation for the time-dependent Hamiltonian modeling the annealing problems. The anneal path control is thereby modeled as a modified linear annealing scheme, resulting in an advanced and retarded scheme. The considered optimization problems are 2-SAT problems with 12 Boolean variables, a known unique ground state and a highly degenerate first excited state. We show that adjustment of the anneal path control can result in a widening of the minimal spectral gap by one or two orders of magnitude and an enhancement of the success probability of finding the solution of the optimization problem. We scrutinize various iterative methods based on the spin floppiness, the average spin value, and on the average energy and describe their performance in boosting the quantum annealing process.
In recent years, quantum annealing has gained the status of being a promising candidate for solving various optimization problems. Using a set of hard 2-satisfiability (2-SAT) problems, consisting of problems of up to 18 variables, we analyze the scaling complexity of the quantum annealing algorithm and study the distributions of the minimum energy gap and the success probability. We extend the analysis of the standard quantum annealing Hamiltonian by introducing an additional term, the trigger Hamiltonian, which can be of two types: ferromagnetic and antiferromagnetic. We use these trigger Hamiltonians to study their influence on the success probability for solving the selected 2-SAT problems. We find that although the scaling of the runtime is exponential for the standard and modified quantum annealing Hamiltonians, the scaling constant in the case of adding the trigger Hamiltonians can be significantly smaller. Furthermore, certain choices for the trigger Hamiltonian and annealing times can result in a better scaling than that for simulated annealing. Finally, we also use the quantum annealers of D-Wave Systems Inc. to study their performance in solving the 2-SAT problems and compare it with the simulation results.
To date, conventional computers have never been able to efficiently handle certain tasks, where the number of computation steps is likely to blow up as the problem size increases. As an emerging technology and new computing paradigm, quantum computing has a great potential to tackle those hard tasks efficiently. Among all the existing quantum computation models, quantum annealing has drawn significant attention in recent years due to the realization of the commercialized quantum annealer, sparking research interests in developing applications to solve problems that are intractable for classical computers.However, designing and implementing algorithms that manage to harness the enormous computation power from quantum annealer remains a challenging task. Generally, it requires mapping of the given optimization problem into quadratic unconstrained binary optimization(QUBO) problem and embedding the subsequent QUBO onto the physical architecture of quantum annealer. Additionally, practical quantum annealers are susceptible to errors leading to low probability of the correct solution.In this study, we focus on solving Boolean satisfiability (SAT) problem using quantum annealer while addressing practical limitations. We have proposed a mapping technique that maps SAT problem to QUBO, and we have further devised a tool flow that embeds the QUBO onto the architecture of a quantum annealing device. Additionally, We have optimized the proposed embedding flow to reduce run-time in addition to shortening the qubit chain length, leading to robust quantum annealing. To further improve the reliability of quantum annealing, we have also developed a post processing embedding technique that enlarges the energy gap between ground state and the first excited state. To demonstrate the effectiveness of proposed methods, we have conducted experiments on real quantum annealing devices manufactured by D-Wave Systems, showing compelling result of using quantum annealer to solve SAT problem.
Using a specially constructed set of hard 2-satisfiability problems with four satisfying assignments, we study the scaling and sampling performance of numerical simulation of quantum annealing as well as that of the physical quantum annealers offered by D-Wave. To this end, we use both the standard quantum annealing and reverse annealing protocols in both our simulations and on the D-Wave quantum annealer. In the case of ideal quantum annealing the sampling behavior can be explained by perturbation theory and the scaling behavior of the time to solution depends on the scaling behavior of the minimum energy gap between the ground state and the first-excited state of the annealing Hamiltonian. The corresponding results from the D-Wave quantum annealers do not fit to this ideal picture, but suggest that the scaling of the time to solution from the quantum annealers matches those calculated from the equilibrium probability distribution.
Quantum annealing offers a promising strategy for solving complex optimization problems by encoding the solution into the ground state of a problem Hamiltonian. While most implementations rely on spin-1/21/21/2 systems, we explore the performance of quantum annealing on a spin-111 system where the problem Hamiltonian includes a single ion anisotropy term of the form D∑(Sz)2D\sum (S^z)^2D∑(Sz)2. Our results reveal that for a suitable range of the anisotropy strength DDD, the spin-111 annealer reaches the ground state with higher fidelity. We attribute this performance to the presence of the intermediate spin level and the tunable anisotropy, which together enable the algorithm to traverse the energy landscape through smaller, incremental steps instead of a single large spin flip. This mechanism effectively lowers barriers in the configuration space and stabilizes the evolution. These findings suggest that higher spin annealers offer intrinsic advantages for robust and flexible quantum optimization, especially for problems naturally formulated with ternary decision variables.
Using a specially constructed set of hard 2-satisfiability problems with four satisfying assignments, we study the scaling and sampling performance of numerical simulation of quantum annealing as well as that of the physical quantum annealers offered by D-Wave. To this end, we use both the standard quantum annealing and reverse annealing protocols in both our simulations and on the D-Wave quantum annealer. In the case of ideal quantum annealing the sampling behavior can be explained by perturbation theory and the scaling behavior of the time to solution depends on the scaling behavior of the minimum energy gap between the ground state and the first-excited state of the annealing Hamiltonian. The corresponding results from the D-Wave quantum annealers do not fit to this ideal picture, but suggest that the scaling of the time to solution from the quantum annealers matches those calculated from the equilibrium probability distribution.
Advances in quantum annealing technology make it possible to obtain high quality approximate solutions of important NP-hard problems. With the newer generations of the D-Wave annealer, more advanced features are available which allow the user to have greater control of the anneal process. In this contribution, we study how such features can help in improving the quality of the solutions returned by the annealer. Specifically, we focus on two of these features: reverse annealing and h-gain. Reverse annealing (RA) was designed to allow refining a known solution by backward annealing from a classical state representing the solution to a mid-anneal point where a transverse field is present, followed by an ordinary forward anneal, which is hoped to improve on the previous solution. The h-gain (HG) feature stands for time-dependent gain in Hamiltonian linear (h) biases and was originally developed to help study freezeout times and phase transitions in spin glasses. Here we apply HG to bias the quantum state in the beginning of the annealing process towards the known solution as in the RA case, but using a different apparatus. We also investigate a hybrid reverse annealing/h-gain schedule, which has a backward phase resembling an RA step and whose forward phase uses the HG idea. To optimize the parameters of the schedules, we employ a Bayesian optimization framework. We test all techniques on a variety of input problems including the weighted Maximum Cut problem and the weighted Maximum Clique problem. Our results show that each technique may dominate the others depending on the input instance, and that the HG technique is a viable alternative to RA for some problems.