Parallel Quantum Annealing is a technique to solve multiple optimization problems simultaneously. Parallel quantum annealing aims to optimize the utilization of available qubits on a quantum topology by addressing multiple independent problems in a single annealing cycle. This study provides insights into the potential and the limitations of this parallelization method. The experiments consisting of two different problems are integrated, and various problem dimensions are explored including normalization techniques using specific methods such as DWaveSampler with Default Embedding, DWaveSampler with Custom Embedding and LeapHybridSampler. This method minimizes idle qubits and holds promise for substantial speed-up, as indicated by the Time-to-Solution (TTS) metric, compared to traditional quantum annealing, which solves problems sequentially and may leave qubits unutilized.
Parallel Quantum Annealing is a technique to solve multiple optimization problems simultaneously. Parallel quantum annealing aims to optimize the utilization of available qubits on a quantum topology by addressing multiple independent problems in a single annealing cycle. This study provides insights into the potential and the limitations of this parallelization method. The experiments consisting of two different problems are integrated, and various problem dimensions are explored including normalization techniques using specific methods such as DWaveSampler with Default Embedding, DWaveSampler with Custom Embedding and LeapHybridSampler. This method minimizes idle qubits and holds promise for substantial speed-up, as indicated by the Time-to-Solution (TTS) metric, compared to traditional quantum annealing, which solves problems sequentially and may leave qubits unutilized.
Quantum annealers of D-Wave Systems, Inc., offer an efficient way to compute high quality solutions of NP-hard problems. This is done by mapping a problem onto the physical qubits of the quantum chip, from which a solution is obtained after quantum annealing. However, since the connectivity of the physical qubits on the chip is limited, a minor embedding of the problem structure onto the chip is required. In this process, and especially for smaller problems, many qubits will stay unused. We propose a novel method, called parallel quantum annealing, to make better use of available qubits, wherein either the same or several independent problems are solved in the same annealing cycle of a quantum annealer, assuming enough physical qubits are available to embed more than one problem. Although the individual solution quality may be slightly decreased when solving several problems in parallel (as opposed to solving each problem separately), we demonstrate that our method may give dramatic speed-ups in terms of the Time-To-Solution (TTS) metric for solving instances of the Maximum Clique problem when compared to solving each problem sequentially on the quantum annealer. Additionally, we show that solving a single Maximum Clique problem using parallel quantum annealing reduces the TTS significantly.
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.
This study presents a comprehensive analysis of optimization methodologies in quantum annealing (QA), investigating both theoretical frameworks and practical implementations. We examine various techniques for enhancing quantum annealing performance, including embedding strategies, parameter optimization, and hybrid quantum-classical approaches. Our research identifies critical challenges: qubit connectivity constraints, noise susceptibility, and problem representation difficulties. Through quantitative comparisons of optimization strategies across various problem classes, we establish a systematic framework for evaluating quantum annealing solutions. Results indicate that while significant challenges persist, strategic optimization approaches can substantially improve quantum annealing performance for specific problem domains, suggesting potential quantum advantage for certain complex optimization tasks.
Quantum annealing (QA) has the potential to significantly improve solution quality and reduce time complexity in solving combinatorial optimization problems compared to classical optimization methods. However, due to the limited number of qubits and their connectivity, the QA hardware did not show such an advantage over classical methods in past benchmarking studies. Recent advancements in QA with more than 5000 qubits, enhanced qubit connectivity, and the hybrid architecture promise to realize the quantum advantage. Here, we use a quantum annealer with state-of-the-art techniques and benchmark its performance against classical solvers. To compare their performance, we solve over 50 optimization problem instances represented by large and dense Hamiltonian matrices using quantum and classical solvers. The results demonstrate that a state-of-the-art quantum solver has higher accuracy (~0.013%) and a significantly faster problem-solving time (~6561×) than the best classical solver. Our results highlight the advantages of leveraging QA over classical counterparts, particularly in hybrid configurations, for achieving high accuracy and substantially reduced problem solving time in large-scale real-world optimization problems.
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.