Quantum Annealing (QA) is a metaheuristic designed to enhance Simulated Annealing by leveraging concepts from quantum mechanics, improving parallelization on classical computers. Studies have shown promising results for this technique in the field of NP-hard problems and constrained optimization. In this article, we examine Path Integral Quantum Annealing (PIQA), a well-known technique for simulating QA on conventional computers. We then propose optimizations to the algorithm, offering hardware software developers a suite of parallelization techniques evaluated for their effectiveness in enhancing quality and speed. The proposed approach encompasses four distinct degrees of optimization, leveraging techniques based on multiple-trial parallelism and a novel pre-optimization method. The article further proposes a methodology for handling multiple instances within the search space, whereby problem data is replicated into slices and allocated to concurrent processes during the simulation. Through empirical trials, we evaluate the impact of our optimization techniques on the convergence speed of the algorithm compared to unoptimized PIQA, using the Multidimensional Knapsack Problem as a benchmark. Our findings show that these optimizations, applied individually or collectively, enable the algorithm to achieve equal or superior results with fewer simulation steps. Overall, the results highlight the potential for future implementations of optimized PIQA on dedicated hardware.
Quantum Annealing (QA) is a metaheuristic designed to enhance Simulated Annealing by leveraging concepts from quantum mechanics, improving parallelization on classical computers. Studies have shown promising results for this technique in the field of NP-hard problems and constrained optimization. In this article, we examine Path Integral Quantum Annealing (PIQA), a well-known technique for simulating QA on conventional computers. We then propose optimizations to the algorithm, offering hardware software developers a suite of parallelization techniques evaluated for their effectiveness in enhancing quality and speed. The proposed approach encompasses four distinct degrees of optimization, leveraging techniques based on multiple-trial parallelism and a novel pre-optimization method. The article further proposes a methodology for handling multiple instances within the search space, whereby problem data is replicated into slices and allocated to concurrent processes during the simulation. Through empirical trials, we evaluate the impact of our optimization techniques on the convergence speed of the algorithm compared to unoptimized PIQA, using the Multidimensional Knapsack Problem as a benchmark. Our findings show that these optimizations, applied individually or collectively, enable the algorithm to achieve equal or superior results with fewer simulation steps. Overall, the results highlight the potential for future implementations of optimized PIQA on dedicated hardware.
Quantum Annealing (QA) is an emerging technique, derived from Simulated Annealing, providing metaheuristics for multivariable optimisation problems. Studies have shown that it can be applied to solve NP-hard problems with faster convergence and better quality of result than other traditional heuristics, with potential applications in a variety of fields, from transport logistics to circuit synthesis and optimisation. In this paper, we present a hardware architecture implementing a QA-based solver for the Multidimensional Knapsack Problem, designed to improve the performance of the algorithm by exploiting parallelised computation. We synthesised the architecture using as a target an Altera FPGA board and simulated the execution for solving a set of benchmarks available in the literature. Simulation results show that the proposed implementation is about 100 times faster than a single-thread general-purpose CPU without impact on the accuracy of the solution.
Quantum annealing approximately solves combinatorial optimization problems by leveraging the principles of adiabatic quantum systems. In this approach, the system's Hamiltonian evolves from an initial general state to a problem-specific state. This study introduces multi-tasking quantum annealing (MTQA), a method that enables the parallel processing of multiple optimization problems by embedding them into spatially distinct regions on quantum hardware. MTQA is evaluated using two NP-hard problems: the minimum vertex cover problem (MVCP) and the graph partitioning problem (GPP). This parallel approach optimizes quantum resource utilization by concurrently utilizing idle qubits. The findings demonstrate that MTQA achieves a solution quality comparable to single-problem quantum annealing and classical simulated annealing (SA), while notably reducing the time-to-solution (TTS) metrics. Eigenspectrum analysis further theoretically supports the hypothesis that parallel embedding preserves quantum coherence and does not increase computational complexity by efficiently utilizing available quantum hardware (e.g., qubits and couplers). MTQA enables efficient multitasking in quantum annealing, optimizing hardware utilization and improving throughput for concurrent tasks and demonstrating performance for problems up to 100 nodes in real-world applications.
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.
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.
We are interested in Quantum Annealing (QA), an algorithm inspired by quantum theory and Simulated Annealing (SA). It is based on quantum replicas, which explore an energy surface, and are less prone to be trapped in local minima. Moreover, kinetic energy helps replicas to find a global minimum. This method has proved its efficiency for several optimization problems. We start this study by presenting the application of QA to a new problem: the Multidimensional Knapsack Problem (MKP). We then present a new idea to speed up the quantum annealing process by detecting the resemblance between replicas. If many of the replicas exhibit the same properties, our assumption is that these properties will also be present with a high probability in a global solution. Consequently, the QA may restrict certain mutations in order to preserve those similarities. We call this algorithm Restrictive Quantum Annealing (RQA). We establish that RQA has better performances than QA and SA by carrying out an adequate analysis of the RQA performance, taking the Traveling Salesman Problem (TSP) and the above-mentioned MKP as references. We also advance guidelines indicating types of NP-hard problems for which our algorithm is particularly well adapted.
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 σ(t), which is dynamically adjusted based on the error estimates of the current state. The overall optimization process can be summarized as: minsE[s]subject todtdS=−β(t)E[s]−γ(t)H(t)s where β(t) is the annealing rate and γ(t) is the magnetic field strength. The adaptive strategy involves updating β(t) and γ(t) based on the error in the current solution, aiming to reduce the variance σ(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.