Solving problems with quantum annealing

Elizabeth Behrman, James E. Steck

Sovanmonynuth Heng, Dongmin Kim, Tae-Kyung Kim +1 more

A combinatorial optimization problem (COP) is the problem of finding the optimal solution in a finite set. When the size of the feasible solution set is large, the complexity of the problem increases, and it is not easy to solve in a reasonable time with the current classical computer technology. Quantum annealing (QA) is a method that replaces classical simulated annealing (SA) methods that do not solve these cases. Therefore, several attempts have been made to solve this problem using a special-purpose quantum annealer to which the QA method is applied. In this survey, we analyze recent studies that solve real-scale COPs using quantum annealers. Through this, we discuss how to reduce the size of the COP to be input to overcome the hardware limitations of the existing quantum annealer. Additionally, we demonstrated the applicability of quantum annealer to COP on a practical scale by comparing and analyzing the results of the classical simulated annealing (SA) and QA method from each study.

Mayar Mohamed

This thesis studies several aspects of the quantum annealing (QA) computing approach. Quantum annealers' primary objective is to solve hard computational optimization problems. Because these optimization problems are in the NP-Hard complexity class, they are of great interest in several fields. One of the leading open questions concerning quantum annealers asks whether they will outperform other classical methods for solving these problems; Some aspects of this question are addressed in this thesis. The first part of the thesis investigates whether quantum annealing provides improved performance for solving a particular family of NP problems, called the Quadratic Knapsack Problem (QKP), using the D-Wave Quantum Annealer. The performance metrics used to assess QKP solving are the solution quality and the total runtime, and are benchmarked against other classical solvers. \n \nFurthermore, we extend our research on quantum annealers to propose two use cases for such systems. One is for Blockchain technology, and the second is in the area of quantum chaos. For the first use case of QA, an application for Blockchain's Proof of Work (PoW) is proposed, based on having hard optimization problems as an alternative to PoW hashing challenge, and using quantum annealers as solvers. For the second use case of QA, we propose simulating quantum chaos on the D-Wave Quantum Annealer to study the transition between the deep quantum realm and the classical limit in a chaotic system, and obtain insights into the “quantumness" of quantum annealers.

G. Aeppli, T. F. Rosenbaum

Jargalsaikhan Artag, Moe Shimada, Jun‐ichi Shirakashi

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.

Eliahu Cohen, Boaz Tamir