Simulated Quantum Annealing (SQA) is a heuristic algorithm which can solve Quadratic Unconstrained Binary Optimization (QUBO) problems by emulating the exploration of the solution space done by a quantum annealer. It mimics the quantum superposition and tunnelling effects through a set of correlated replicas of the spins system representing the problem to be solved and performing Monte Carlo steps. However, the effectiveness of SQA over a classical algorithm strictly depends on the cost/energy profile of the target problem. In fact, quantum annealing only performs well in exploring functions with high and narrow peaks, while classical annealing is better in overcoming flat and wide energy-profile barriers. Unfortunately, real-world problems have a heterogeneous solution space and the probability of success of each solver depends on the size of the energy profile region compatible with its exploration mechanism. Therefore, significant advantages could be obtained by exploiting hybrid solvers, which combine SQA and classical algorithms. This work proposes four new quantum-classical algorithms: Simulated Quantum Parallel Tempering (SQPT), Simulated Quantum Population Annealing (SQPA), Simulated Quantum Parallel Tempering - Population Annealing v1 (SQPTPA1) and Simulated Quantum Parallel Tempering - Population Annealing v2 (SQPTPA2). They are obtained by combining SQA, Parallel Tempering (PT), and Population Annealing (PA). Their results are compared with those provided by SQA, considering benchmark QUBO problems, characterized by different profiles. Even though this work is preliminary, the obtained results are encouraging and prove hybrid solvers’ potential in solving a generic optimization problem.
Simulated Quantum Annealing (SQA) is a heuristic algorithm which can solve Quadratic Unconstrained Binary Optimization (QUBO) problems by emulating the exploration of the solution space done by a quantum annealer. It mimics the quantum superposition and tunnelling effects through a set of correlated replicas of the spins system representing the problem to be solved and performing Monte Carlo steps. However, the effectiveness of SQA over a classical algorithm strictly depends on the cost/energy profile of the target problem. In fact, quantum annealing only performs well in exploring functions with high and narrow peaks, while classical annealing is better in overcoming flat and wide energy-profile barriers. Unfortunately, real-world problems have a heterogeneous solution space and the probability of success of each solver depends on the size of the energy profile region compatible with its exploration mechanism. Therefore, significant advantages could be obtained by exploiting hybrid solvers, which combine SQA and classical algorithms. This work proposes four new quantum-classical algorithms: Simulated Quantum Parallel Tempering (SQPT), Simulated Quantum Population Annealing (SQPA), Simulated Quantum Parallel Tempering - Population Annealing v1 (SQPTPA1) and Simulated Quantum Parallel Tempering - Population Annealing v2 (SQPTPA2). They are obtained by combining SQA, Parallel Tempering (PT), and Population Annealing (PA). Their results are compared with those provided by SQA, considering benchmark QUBO problems, characterized by different profiles. Even though this work is preliminary, the obtained results are encouraging and prove hybrid solvers’ potential in solving a generic optimization problem.
Simulated quantum annealing (SQA) has been widely studied as a heuristic for solving hard optimization problems, including integer factorization formulated as a quadratic unconstrained binary optimization (QUBO) problem. In this work, we present a replication-oriented benchmark of annealing-based solvers applied to biprime factorization using the direct QUBO mapping. We perform a controlled comparison of SQA, implemented via path-integral Monte Carlo, simulated annealing (SA), and asynchronous parallel simulated annealing (A-PSA), evaluating their performance in terms of probability of success and time to solution. Here, A-PSA denotes a multistart strategy consisting of multiple independent SA trajectories with no inter-replica interactions. Solver and encoding parameters are systematically optimized using Bayesian optimization to ensure a fair and reproducible comparison. Our results reproduce previously reported performance trends: SQA outperforms conventional SA on the considered QUBO landscapes, while SQA and A-PSA can exhibit closely comparable performance in specific regimes, highlighting the importance of multistart baselines in annealing-based benchmarking. All simulations are performed on commodity multithreaded CPU hardware using open-source software, enabling straightforward reproducibility without reliance on specialized experimental platforms. As a reference benchmark, the largest semiprime successfully factorized in our study is 8 219 999 = 32 749 × 251 , matching results previously obtained using quantum annealing hardware.
It is well-known that quantum annealing (QA) is an excellent algorithm for solving combinatorial optimization problems (COPs). However, its hardware implementation poses challenges, requiring quantum devices. Therefore, a quantum Monte Carlo (QMC) method-based annealing approach called Simulated Quantum Annealing (SQA), which aims to emulate quantum annealing using classical computers, has been proposed. In the demo-night session, we will demonstrate a SQA based on stochastic computing (SC) on a standard FPGA board, called “PYNQ”. The use of SC-based data representation, along with the realization of SC-based spin-gate circuits, makes it possible to drastically reduce hardware costs compared to QA. This enhances the suitability for extending large-scale COPs.
Quantum annealing has emerged as an effective meta-heuristic for solving combinatorial optimization problems by leveraging quantum tunnelling to navigate complex energy landscapes. This paper examines both the theoretical foundations and the practical implementation of quantum annealing for project scheduling and resource-allocation problems formulated as Ising or Quadratic Unconstrained Binary Optimization (QUBO) models. A comprehensive explanation of the quantum annealing process is provided through a stage-by-stage process flowchart. In addition, the study discusses hybrid quantum classical frameworks in which quantum annealing is integrated with Monte Carlo simulations or digital twin environments, supported by illustrations of the optimization energy landscape and the hybrid system architecture. The adaptability of the proposed approach is further demonstrated through analogies with unit load device (ULD) configuration and other related combinatorial optimization problems across multiple application domains. Finally, the paper outlines key implementation considerations and evaluates the current level of technological maturity of quantum annealing for applications in construction planning and logistics optimization. Keywords: quantum annealing implementation; Ising model; QUBO; combinatorial optimization; project scheduling; hybrid quantum-classical; energy landscape; digital twin; Monte Carlo; supply-chain resilience; ULD configuration
In recent years, the diversification of problems that require computers to solve has attracted attention to the construction of meta-heuristics that can be applied to a wide range of problems, and to specialized computers that implement these meta-heuristics in their devices. The representative meta-heuristics are Simulated Annealing (SA) and its extension to quantum computation, Quantum Annealing (QA), and its path-integral Monte Carlo method for classical simulation Crosson and Harrow showed that for certain problems where QA outperformed SA, SQA achieved performance close to that of QA, and SQA sometimes outperformed SA by an exponential time factor. On the other hand, it remains unclear whether SQA can work efficiently on a wide range of other problems. In this study, we experimentally compared SA and SQA on instances of the restricted Boltzmann machine RBM, known as a fundamental building block in deep learning, and 3SAT, a fundamental combinatorial optimization problem. The results show that SQA gives slightly better solutions than SA as the problem size increases for RBM in terms of both accuracy and computation time in our setting, but the opposite trend is observed for 3SAT, indicating that there is no significant difference between the two methods. From the viewpoint of artificial intelligence research, it is necessary to further examine whether deep learning can be made more efficient by applying QA and SQA to RBM.
Quantum annealing has emerged as a promising approach for solving NP-hard optimization problems, leveraging quantum phenomena such as quantum tunneling to navigate complex energy landscapes. However, the extent to which quantum tunneling contributes to performance enhancements compared to classical methods remains unclear. In this work, we present a comprehensive investigation combining experimental analysis, theoretical modeling, and algorithmic development to characterize when and why quantum annealing provides computational advantages.
We introduce a novel methodology for generating synthetic Quadratic Unconstrained Binary Optimization (QUBO) problems with controlled gradient variance, enabling systematic investigation of landscape characteristics that favor quantum approaches. Our experimental evaluation encompasses four canonical NP-hard problems: Graph Partitioning, Max Cut, Number Partitioning, and Set Cover. Using D-Wave's Advantage2 quantum annealer with 4,400+ qubits, we compare quantum annealing against classical solvers including simulated annealing, stochastic gradient descent, and commercial optimization software.
Our results demonstrate that quantum annealing shows measurable advantages when energy landscapes exhibit high gradient variance (>0.3), suggesting that quantum tunneling effects are most beneficial for rugged optimization landscapes. We provide a theoretical justification for this empirical observation through a WKB-approximation-based model connecting gradient variance to barrier width and tunneling probability. This model achieves R2=0.90 correlation with experimental data and yields quantitative predictions for quantum advantage thresholds.
This study introduces an innovative application of Parallel Quantum Annealing (PQA) to concurrently solve multiple NP-hard problems on a quantum annealer, leveraging unused qubits on D-Wave's Pegasus architecture to enhance efficiency and accuracy. While parallel execution of different problems on the same quantum annealing device has been previously explored, our application extends the current PQA method, which typically solves a single problem multiple times or different problems with minor embedded combinatorial optimization. This study primarily focuses on three NP-hard problems relevant to integrated circuit design: the Graph Coloring Problem (GCP), the Minimum Vertex Cover Problem (MVCP), and the Graph Partitioning Problem (GPP). After formulating these problems as Quadratic Unconstrained Binary Optimization (QUBO), they were embedded into the D-Wave quantum annealing machine, and the annealing process was run on the combined QUBO. The results were subsequently decoded into individual problems. Our results, quantified via the Time-To-Target (TTT) metric, showcased enhanced efficiency and accuracy in reaching target solutions, indicating a substantial improvement over traditional Quantum Annealing (QA) and Simulated Annealing (SA) methods. The research illustrates the potential of quantum computing for solving complex real-world problems more efficiently and emphasizes the importance of leveraging all available qubits in quantum annealers. The findings can significantly contribute to the development and optimization of quantum computing methods and have broad application implications, particularly in areas where NP-hard problems are prevalent.