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:quant-ph/0107081 · New Journal of Physics

Quantum optimization for combinatorial searches

Carlo A. Trugenberger

Published Apr 19, 2002• 13 citations
arXivHTMLPDF

Abstract

I propose a `quantum annealing' heuristic for the problem of a combinatorial search among a frustrated set of states characterized by a cost function to be minimized. The algorithm is probabilistic, with post-selection of the measurement result. A unique parameter playing the role of an effective temperature governs the computational load and the overall quality of the optimization. Any level of accuracy can be reached with a computational load independent of the dimension N of the search set by choosing the effective temperature correspondingly low. This is much better than classical search heuristics, which typically involve computation times growing as powers of log( N ).

DOI
10.1088/1367-2630/4/1/326

Related papers

Quantum Annealing-Based Combinatorial Optimization Algorithm

Jincheng Zhang

This paper investigates the application of quantum annealing for solving complex combinatorial optimization problems. The core claim is that quantum annealing leverages its global search capabilities to efficiently address such problems. The proposed mechanism involves formulating the combinatorial optimization problem as a quantum annealing problem and utilizing the simulated annealing process within quantum annealing to conduct a search for the optimal solution. This research explores the potential of quantum annealing in practical applications, acknowledging that its application in combinatorial optimization is still in its exploratory phase. The algorithm is designed to minimize the energy of a system described by a Hamiltonian, which evolves over time according to the time-dependent Schrödinger equation. The core of the algorithm lies in mapping the problem's constraints and objective function into this Hamiltonian. The search process is governed by quantum fluctuations, represented by the operator $\hat{H}$, which encourages transitions to lower energy states, effectively navigating the solution space. The effectiveness of the algorithm is evaluated based on the quality of the solution found and the computational resources required. This work provides a foundational exploration of quantum annealing's potential within the field of combinatorial optimization.

•Sep 3, 2026•0 citations

Quantum Annealing Algorithm Optimization and Application

Jincheng Zhang

Quantum annealing (QA) is a promising quantum computing paradigm for solving optimization problems. However, the performance of QA is often limited by issues such as slow convergence rates and sensitivity to parameter settings. This paper presents a novel optimization method designed to address these limitations. The approach introduces refined parameters and an adaptive strategy to enhance the algorithm's convergence speed and solution accuracy. We explore the application of this optimized QA method to complex problems, demonstrating its potential for improved performance. The core of the optimization lies in modifying the annealing schedule and incorporating a dynamic adjustment of the magnetic field strength, denoted as $H(t)$, where $t$ represents time. The objective function to be minimized is typically represented as $E[s]$, where $s$ is the state vector of the quantum annealer. We introduce a variance reduction technique, denoted as $\sigma(t)$, which is dynamically adjusted based on the error estimates of the current state. The overall optimization process can be summarized as: $\min_{s} E[s] \quad \text{subject to} \quad \frac{dS}{dt} = - \beta(t) E[s] - \gamma(t) H(t)s$ where $\beta(t)$ is the annealing rate and $\gamma(t)$ is the magnetic field strength. The adaptive strategy involves updating $\beta(t)$ and $\gamma(t)$ based on the error in the current solution, aiming to reduce the variance $\sigma(t)$ and improve the convergence. The theoretical analysis suggests that this approach can significantly reduce the computational cost and improve the solution quality compared to traditional QA methods. Furthermore, we investigate the impact of different parameter settings on the algorithm's performance, highlighting the importance of careful tuning for optimal results. The results demonstrate a notable improvement in solution quality and convergence speed across various benchmark problems.

•Sep 3, 2026•0 citations

Quantum Annealing Algorithm for Probabilistic Topological Optimization

Jincheng Zhang

This paper investigates the application of quantum annealing algorithms to the field of topological optimization, specifically focusing on a probabilistic approach. Traditional topological optimization relies on iterative refinement of a mesh, often computationally expensive. We propose a novel method leveraging the quantum annealing algorithm's inherent probabilistic search capabilities, combined with topological structural information, to achieve more efficient solutions for complex optimization problems. The core concept involves translating the optimization problem into a search problem within the space of possible topological structures. The quantum annealing algorithm then explores this space probabilistically, guided by the topological constraints, with the goal of identifying the optimal topology. This approach aims to reduce the computational burden associated with conventional iterative methods and potentially unlock solutions that are inaccessible through classical optimization techniques. The presented framework is theoretically grounded and offers a promising avenue for future research in hybrid quantum-classical optimization. The key performance indicator for this approach is the convergence rate and the quality of the solutions obtained compared to traditional methods. The algorithm's success depends heavily on the effective encoding of the problem's constraints into the topology search space.

•Sep 5, 2026•0 citations

Stochastic Simulated Quantum Annealing for Fast Solution of Combinatorial Optimization Problems

Naoya Onizawa, Ryoma Sasaki, Duckgyu Shin +2 more

Combinatorial optimization problems are frequently classified as NP-hard, which means that the time needed to find the optimal solution generally increases exponentially with the problem size. However, the existing research gap highlights the necessity to develop combinatorial optimization methods capable of scaling to large problems while maintaining low solution latency. In this paper, we introduce stochastic simulated quantum annealing (SSQA) for fast solution of combinatorial optimization problems. SSQA is designed based on stochastic computing, which can simulate quantum annealing (QA) by using multiple replicas of spins (probabilistic bits) in classical computing. The use of stochastic computing leads to an efficient parallel spin-state update algorithm, enabling quick search for a solution around the global minimum energy. Therefore, SSQA realizes quantum-like annealing for large-scale problems and can handle fully connected models in combinatorial optimization, unlike QA. The proposed method is evaluated in MATLAB on graph isomorphism problems, which are typical combinatorial optimization problems. It can handle a 100-times larger problem size compared to QA and a 25-times larger problem size compared to a traditional SA method, respectively, for similar convergence probabilities. The time to solution of SSQA is 11.5 times and 423 times smaller than that of the conventional stochastic simulated annealing method and traditional SA, respectively, when solving a 2,025-node combinatorial optimization problem.

arXiv:2302.12454•IEEE Access•Jan 1, 2024•10 citations

Quantum-Inspired Stochastic Search for Combinatorial Optimization

Jincheng Zhang

This paper introduces a novel stochastic search algorithm, Quantum-Inspired Stochastic Search (QISS), designed to tackle complex combinatorial optimization problems. QISS draws inspiration from the principles of quantum superposition and entanglement, adapting them into a classical probabilistic framework. Unlike traditional stochastic search methods that rely solely on classical probability distributions, QISS represents potential solutions as a superposition of states, exhibiting entanglement-like correlations to guide exploration. This approach aims to dramatically accelerate the search process by effectively exploring a wider range of the solution space. The core mechanism involves iteratively updating the probabilities associated with each state in the superposition, influenced by both random fluctuations and the observed correlations between states. The algorithm is formulated as a Markov chain Monte Carlo method, where the state transition probabilities are governed by a probability distribution derived from the problem's cost function. The effectiveness of QISS is evaluated through theoretical analysis and, importantly, through a conceptual framework that highlights its potential advantages over existing stochastic optimization techniques. The ultimate goal is to demonstrate that incorporating quantum-inspired concepts, even within a purely classical setting, can lead to significant improvements in the efficiency and robustness of combinatorial optimization algorithms.

•Sep 6, 2026•0 citations

Analyzing performance of commercial quantum annealing solvers for the capacitated vehicle routing problem

Salvatore Sinno, Thomas Groß, Alan Mott +4 more

Quantum Annealing (QA) is a heuristic search algorithm that can run on adiabatic quantum computation processors to solve combinatorial optimization problems. Although theoretical studies and simulations on classical hardware have shown encouraging results, these analyses often assume that the computation occurs in adiabatically closed systems without environmental interference. This is not a realistic assumption for real systems; therefore, without extensive empirical measurements on real quantum platforms, theory-based predictions, simulations on classical hardware, or limited tests do not accurately assess the current commercial capabilities. This study has assessed the quality of the solution provided by a commercial quantum annealing platform compared to known solutions for the capacitated vehicle routing problem. This study has conducted an extensive analysis on more than 30 hours of access to QA commercial platforms to investigate how the size of the problem and its complexity impact the accuracy of the solution and the time used to find a solution. Our results have found that the absolute error is between 0.12 and 0.55, and the time of the quantum processor unit is between 30 and 46 μs. Our results show that as the constraint density increases, the quality of the solution degrades. Therefore, more than the size of the problem, the complexity of the model plays a critical role, and practical applications should select formulations that minimize the constraint density.

arXiv:2309.05564•AIP Advances•Dec 1, 2025•20 citations
I propose a `quantum annealing' heuristic for the problem of a combinatorial search among a frustrated set of states characterized by a cost function to be minimized. The algorithm is probabilistic, with post-selection of the measurement result. A unique parameter playing the role of an effective temperature governs the computational load and the overall quality of the optimization. Any level of accuracy can be reached with a computational load independent of the dimension N of the search set by choosing the effective temperature correspondingly low. This is much better than classical search heuristics, which typically involve computation times growing as powers of log( N ).
This paper investigates the application of quantum annealing for solving complex combinatorial optimization problems. The core claim is that quantum annealing leverages its global search capabilities to efficiently address such problems. The proposed mechanism involves formulating the combinatorial optimization problem as a quantum annealing problem and utilizing the simulated annealing process within quantum annealing to conduct a search for the optimal solution. This research explores the potential of quantum annealing in practical applications, acknowledging that its application in combinatorial optimization is still in its exploratory phase. The algorithm is designed to minimize the energy of a system described by a Hamiltonian, which evolves over time according to the time-dependent Schrödinger equation. The core of the algorithm lies in mapping the problem's constraints and objective function into this Hamiltonian. The search process is governed by quantum fluctuations, represented by the operator H^\hat{H}H^, which encourages transitions to lower energy states, effectively navigating the solution space. The effectiveness of the algorithm is evaluated based on the quality of the solution found and the computational resources required. This work provides a foundational exploration of quantum annealing's potential within the field of combinatorial optimization.
Quantum annealing (QA) is a promising quantum computing paradigm for solving optimization problems. However, the performance of QA is often limited by issues such as slow convergence rates and sensitivity to parameter settings. This paper presents a novel optimization method designed to address these limitations. The approach introduces refined parameters and an adaptive strategy to enhance the algorithm's convergence speed and solution accuracy. We explore the application of this optimized QA method to complex problems, demonstrating its potential for improved performance. The core of the optimization lies in modifying the annealing schedule and incorporating a dynamic adjustment of the magnetic field strength, denoted as H(t)H(t)H(t), where ttt represents time. The objective function to be minimized is typically represented as E[s]E[s]E[s], where sss is the state vector of the quantum annealer. We introduce a variance reduction technique, denoted as σ(t)\sigma(t)σ(t), which is dynamically adjusted based on the error estimates of the current state. The overall optimization process can be summarized as: min⁡sE[s]subject todSdt=−β(t)E[s]−γ(t)H(t)s\min_{s} E[s] \quad \text{subject to} \quad \frac{dS}{dt} = - \beta(t) E[s] - \gamma(t) H(t)smins​E[s]subject todtdS​=−β(t)E[s]−γ(t)H(t)s where β(t)\beta(t)β(t) is the annealing rate and γ(t)\gamma(t)γ(t) is the magnetic field strength. The adaptive strategy involves updating β(t)\beta(t)β(t) and γ(t)\gamma(t)γ(t) based on the error in the current solution, aiming to reduce the variance σ(t)\sigma(t)σ(t) and improve the convergence. The theoretical analysis suggests that this approach can significantly reduce the computational cost and improve the solution quality compared to traditional QA methods. Furthermore, we investigate the impact of different parameter settings on the algorithm's performance, highlighting the importance of careful tuning for optimal results. The results demonstrate a notable improvement in solution quality and convergence speed across various benchmark problems.
This paper investigates the application of quantum annealing algorithms to the field of topological optimization, specifically focusing on a probabilistic approach. Traditional topological optimization relies on iterative refinement of a mesh, often computationally expensive. We propose a novel method leveraging the quantum annealing algorithm's inherent probabilistic search capabilities, combined with topological structural information, to achieve more efficient solutions for complex optimization problems. The core concept involves translating the optimization problem into a search problem within the space of possible topological structures. The quantum annealing algorithm then explores this space probabilistically, guided by the topological constraints, with the goal of identifying the optimal topology. This approach aims to reduce the computational burden associated with conventional iterative methods and potentially unlock solutions that are inaccessible through classical optimization techniques. The presented framework is theoretically grounded and offers a promising avenue for future research in hybrid quantum-classical optimization. The key performance indicator for this approach is the convergence rate and the quality of the solutions obtained compared to traditional methods. The algorithm's success depends heavily on the effective encoding of the problem's constraints into the topology search space.
Combinatorial optimization problems are frequently classified as NP-hard, which means that the time needed to find the optimal solution generally increases exponentially with the problem size. However, the existing research gap highlights the necessity to develop combinatorial optimization methods capable of scaling to large problems while maintaining low solution latency. In this paper, we introduce stochastic simulated quantum annealing (SSQA) for fast solution of combinatorial optimization problems. SSQA is designed based on stochastic computing, which can simulate quantum annealing (QA) by using multiple replicas of spins (probabilistic bits) in classical computing. The use of stochastic computing leads to an efficient parallel spin-state update algorithm, enabling quick search for a solution around the global minimum energy. Therefore, SSQA realizes quantum-like annealing for large-scale problems and can handle fully connected models in combinatorial optimization, unlike QA. The proposed method is evaluated in MATLAB on graph isomorphism problems, which are typical combinatorial optimization problems. It can handle a 100-times larger problem size compared to QA and a 25-times larger problem size compared to a traditional SA method, respectively, for similar convergence probabilities. The time to solution of SSQA is 11.5 times and 423 times smaller than that of the conventional stochastic simulated annealing method and traditional SA, respectively, when solving a 2,025-node combinatorial optimization problem.
This paper introduces a novel stochastic search algorithm, Quantum-Inspired Stochastic Search (QISS), designed to tackle complex combinatorial optimization problems. QISS draws inspiration from the principles of quantum superposition and entanglement, adapting them into a classical probabilistic framework. Unlike traditional stochastic search methods that rely solely on classical probability distributions, QISS represents potential solutions as a superposition of states, exhibiting entanglement-like correlations to guide exploration. This approach aims to dramatically accelerate the search process by effectively exploring a wider range of the solution space. The core mechanism involves iteratively updating the probabilities associated with each state in the superposition, influenced by both random fluctuations and the observed correlations between states. The algorithm is formulated as a Markov chain Monte Carlo method, where the state transition probabilities are governed by a probability distribution derived from the problem's cost function. The effectiveness of QISS is evaluated through theoretical analysis and, importantly, through a conceptual framework that highlights its potential advantages over existing stochastic optimization techniques. The ultimate goal is to demonstrate that incorporating quantum-inspired concepts, even within a purely classical setting, can lead to significant improvements in the efficiency and robustness of combinatorial optimization algorithms.
Quantum Annealing (QA) is a heuristic search algorithm that can run on adiabatic quantum computation processors to solve combinatorial optimization problems. Although theoretical studies and simulations on classical hardware have shown encouraging results, these analyses often assume that the computation occurs in adiabatically closed systems without environmental interference. This is not a realistic assumption for real systems; therefore, without extensive empirical measurements on real quantum platforms, theory-based predictions, simulations on classical hardware, or limited tests do not accurately assess the current commercial capabilities. This study has assessed the quality of the solution provided by a commercial quantum annealing platform compared to known solutions for the capacitated vehicle routing problem. This study has conducted an extensive analysis on more than 30 hours of access to QA commercial platforms to investigate how the size of the problem and its complexity impact the accuracy of the solution and the time used to find a solution. Our results have found that the absolute error is between 0.12 and 0.55, and the time of the quantum processor unit is between 30 and 46 μs. Our results show that as the constraint density increases, the quality of the solution degrades. Therefore, more than the size of the problem, the complexity of the model plays a critical role, and practical applications should select formulations that minimize the constraint density.