Benchmark study of simulated quantum annealing and asynchronous parallel simulated annealing for quadratic unconstrained binary optimization-based semiprime factorization
Gianbiagio Curato, Manuel Ponzi, Edoardo Chiatello, R Giorgetti
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.
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.
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.
We benchmark current annealing-based optimization workflows on a greenhouse-inspired quadratic unconstrained binary optimization problem for binary heater scheduling, where the horizon H denotes the number of hourly control decisions. For the main one-day instance (H=24), all solver outputs are decoded back into heater schedules and evaluated in the original greenhouse simulator using the same physical objective and feasibility criterion. Classical simulated annealing and path-integral simulated quantum annealing produce feasible near-optimal solutions in all repetitions, with best objectives close to the exact optimum. In contrast, the tested D-Wave Leap Hybrid BQM workflow is less reliable and does not outperform the classical baselines under 15--60~s requested time limits. Direct D-Wave QPU execution on reduced instances remains feasible in all runs and recovers the exact optimum for H=10 and H=12, but the exact-hit rate drops from 5/10 to 2/10 and then to 0/10 at H=14, with substantially higher variance than the classical baselines. The results do not indicate quantum advantage, but provide a reproducible, physically decoded benchmark that exposes the current strengths and limitations of classical, hybrid, and direct quantum annealing workflows on structured control QUBOs.
Abstract We benchmark classical, simulated-quantum, hybrid, and direct quantum-annealing workflows on a structured binary control problem formulated as a quadratic unconstrained binary optimization (QUBO) model. The benchmark is motivated by greenhouse heater scheduling, where the horizon (H) denotes the number of hourly binary control decisions, but the focus is on solver behavior for a physically decoded control-QUBO formulation. For the main one-day instance ((H=24)), all solver outputs are decoded back into heater schedules and evaluated using the same simulator-side objective and feasibility criterion. Classical simulated annealing and path-integral simulated quantum annealing produce feasible near-optimal solutions in all repetitions, with best objectives close to the exact optimum. In contrast, the tested D-Wave Leap Hybrid binary quadratic model workflow is less reliable and does not outperform the classical baselines under 15--60 s requested time limits. Direct D-Wave quantum processing unit execution on reduced instances remains feasible in all runs and recovers the exact optimum for (H=10) and (H=12), but the exact-hit rate decreases with increasing horizon. The results do not indicate quantum advantage, but provide a reproducible benchmark for evaluating annealing-based natural and quantum computing workflows on structured control QUBOs. MSC Classification: 90C27 , 90C59 , 81P68 , 93C55
Recent advances in quantum computing have shown great potential for solving combinatorial optimization problems. A notable example is the quadratic knapsack problem, a constrained binary optimization problem. However, current quantum-inspired algorithms require Quadratic Unconstrained Binary Optimization (QUBO) formulations. Transforming constrained optimization into QUBO impacts the algorithms' speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess them by using Simulated Annealing (SA), and find that three of our approaches outperform existing methods in terms of execution time as well as quality and quantity of feasible solutions found. Also, we tested these transformations on a quantum annealer, which was unable to solve even small instances, due to limitations in connectivity and error rates. In general, our results highlight the advantages of the new approaches, which reduce the number of variables in the QUBO representation.
Simulated annealing (SA) is a key algorithm for solving combinatorial optimization problems, which model numerous real-world systems. While SA is commonly used to solve quadratic unconstrained binary optimization (QUBO) problems, many practical problems are more naturally formulated using integer variables. We therefore study quadratic and higher-order unconstrained integer optimization (QUIO and HUIO) problems, which generalize QUBO by allowing integer-valued variables and higher-order interactions. Conventional approaches often convert these problems into QUBO formulations through binary encoding and the reduction of higher-order terms. Such conversions, however, greatly increase the number of variables and interactions, resulting in long computation times and, for large-scale problems, even making the conversion itself a dominant computational bottleneck. To overcome this limitation, we propose an efficient framework that directly applies SA to QUIO and HUIO problems without converting them into QUBO. Within this framework, we introduce an optimal-transition Metropolis method, designed to improve efficiency when the variable range is wide, and evaluate its performance alongside the conventional Metropolis and heat bath methods. Numerical experiments demonstrate that the proposed direct approach achieves higher efficiency and better solution quality than the conventional QUBO-based formulation and reveal the practical advantages of the optimal-transition Metropolis method. The algorithm developed in this study is available as part of the open-source library OpenJij, which provides a Python front end with a C++ backend.
This paper investigates several Quadratic Unconstrained Binary optimisation (QUBO) formulations for the parallel machine scheduling problem P m | | C max with the goal of assessing their suitability for quantum annealing and related heuristic optimisation methods. Three QUBO models are constructed, ranging from formulations derived from classical integer and one-hot encodings to a more compact load-balancing based representation. Extensive computational experiments using Simulated Annealing (SA) and Quantum Annealing (QA) reveal substantial differences in scalability and solution quality among the formulations. The alternative load-balanced model consistently yields near-optimal makespans, typically within 1%–3% of the theoretical lower bound, highlighting its stability and effectiveness compared to the more penalty sensitive formulations, whose performance deteriorates for larger instances. Sensitivity analyses further reveal that the appropriate selection of penalty weights and problem-specific parameter tuning significantly influences both solution accuracy and computational effort in QUBO formulations. While current quantum hardware limitations restrict experimentation to small problem sizes, the findings illustrate how compact QUBO designs can better exploit quantum optimisation frameworks. The insights gained in this study provide practical modelling guidelines for future quantum scheduling research and lay the groundwork for extending QUBO-based approaches to more complex scheduling environments. • Three QUBO formulations are compared for identical parallel machine scheduling. • A compact load-balancing QUBO avoids auxiliary variables. • Load balancing yields makespans on average within 1–3%. • Both simulated and quantum annealing produce near-optimal schedules. • Penalty selection and encoding strongly affect scalability and solution quality.