With the current progress of quantum computing, quantum annealing is being introduced as a powerful method to solve hard computational problems. In this paper, we study the potential capability of quantum annealing in solving the phase unwrapping problem, an instance of hard computational problems. To solve the phase unwrapping problem using quantum annealing, we deploy the D-Wave Advantage machine which is currently the largest available quantum annealer. The structure of this machine, however, is not compatible with our problem graph structure. Consequently, the problem graph needs to be mapped onto the target (Pegasus) graph, and this embedding significantly affects the quality of the results. Based on our experiment and also D-Wave's reports, the lower chain lengths can result in a better performance of quantum annealing. In this paper, we propose a new embedding algorithm that has the lowest possible chain length for embedding the graph of the phase unwrapping problem onto the Pegasus graph. The obtained results using this embedding strongly outperform the results of Auto-embedding provided by D-Wave. Besides the phase unwrapping problem, this embedding can be used to embed any subset of our problem graph to the Pegasus graph.
With the current progress of quantum computing, quantum annealing is being introduced as a powerful method to solve hard computational problems. In this paper, we study the potential capability of quantum annealing in solving the phase unwrapping problem, an instance of hard computational problems. To solve the phase unwrapping problem using quantum annealing, we deploy the D-Wave Advantage machine which is currently the largest available quantum annealer. The structure of this machine, however, is not compatible with our problem graph structure. Consequently, the problem graph needs to be mapped onto the target (Pegasus) graph, and this embedding significantly affects the quality of the results. Based on our experiment and also D-Wave's reports, the lower chain lengths can result in a better performance of quantum annealing. In this paper, we propose a new embedding algorithm that has the lowest possible chain length for embedding the graph of the phase unwrapping problem onto the Pegasus graph. The obtained results using this embedding strongly outperform the results of Auto-embedding provided by D-Wave. Besides the phase unwrapping problem, this embedding can be used to embed any subset of our problem graph to the Pegasus graph.
In this paper, we study the potential capability of quantum annealing in solving the phase unwrapping problem, an instance of hard computational problems. To solve the phase unwrapping problem using quantum annealing, we deploy the D-Wave Advantage machine which is currently the largest available quantum annealer. The structure of this machine, however, is not compatible with our problem graph structure. Consequently, the problem graph needs to be mapped into the target (Pegasus) graph, and this minor embedding significantly affects the quality of the results. Based on our experiment and also D-Wave's reports, the lower chain lengths can result in a better performance of quantum annealing. In this paper, we propose a new minor embedding algorithm that has the lowest possible chain length for minor embedding the graph of the phase unwrapping problem onto the Pegasus graph. The obtained results using this embedding strongly outperform the results of Auto-embedding provided by the D- Wave's minorminer tool both in the quality of the solution obtained and in the length of the chain.
Quantum computers and algorithms are undergoing rapid development, offering promising solutions to complex computational problems. This study focuses on harnessing the potential of quantum annealing to address the challenging phase unwrapping problem. Specifically, we employed D-Wave’s quantum annealers, currently among the most powerful in existence. To effectively utilize these systems, it is crucial to embed the problem onto their underlying structure, the Pegasus graph in the case of the D-Wave Advantage system. A shorter chain-length in the embedding process generally correlates with improved results. In the course of this thesis, we devised an algorithm for efficiently embedding the phase unwrapping problem onto the D-Wave Advantage system. Our approach yielded promising results when compared to D-Wave’s automatic embeddings. Notably, our introduced embedding boasts the minimum chain-length and utilizes the native structure of the target graph. Additionally, we leveraged D-Wave’s hybrid workflow, combining classical and quantum computing capabilities, to tackle larger image problems. Refinements to the hybrid method were implemented, resulting in enhanced performance. Experimental evaluations were conducted on actual quantum annealers, demonstrating that our refined algorithms outperform those provided by D-Wave.
Quantum annealing is a quantum algorithm for computing solutions to combinatorial optimization problems. This study proposes a method for minor embedding optimization problems onto sparse quantum annealing hardware graphs called 4-clique network minor embedding. This method is in contrast to the standard minor embedding technique of using a path of linearly connected qubits in order to represent a logical variable state. The 4-clique minor embedding is possible on Pegasus graph connectivity, which is the native hardware graph for some of the current D-Wave quantum annealers. The Pegasus hardware graph contains many cliques of size 4, making it possible to form a graph composed entirely of paths of connected 4-cliques on which a problem can be minor-embedded. The 4-clique chains come at the cost of additional qubit usage on the hardware graph, but they allow for stronger coupling within each chain, thereby increasing chain integrity, reducing chain breaks, and allow for greater usage of the available energy scale for programming logical problem coefficients on current quantum annealers. The 4-clique minor embedding technique is compared with the standard linear path minor embedding with experiments on two D-Wave quantum annealing processors with Pegasus hardware graphs. We show proof-of-concept experiments where the 4-clique minor embeddings can use weak chain strengths while successfully carrying out the computation of minimizing random all-to-all spin glass problem instances. Published by the American Physical Society 2024
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.
The qubits in a D-wave quantum annealer (D-wave QA) are designed on a Pegasus graph that is different from the structure of a combinatorial optimization problem. This situation requires embedding with the chains connected by ferromagnetic coupling Jc between the qubits. Weak and strong Jc values induce chain breaking and enforcement of chain energy, which reduce the accuracy of quantum annealing (QA) measurements, respectively. In addition, we confirmed that even though the D-wave Ocean package provides a default coupling Jcdefault, it is not an optimal coupling Jcoptimal that maximizes the possible correct rate of QA measurements. In this paper, we present an algorithm how Jcoptimal with the maximum probability p for observing the possible lowest energy is determined. Finally, we confirm that the extracted Jcoptimal shows much better p than Jcdefault in QA measurements of various parameters of frustrated and fully connected combinatorial optimization problems. The open code is available in https://github.com/HunpyoLee/OptimizeChainStrength.
To date, conventional computers have never been able to efficiently handle certain tasks, where the number of computation steps is likely to blow up as the problem size increases. As an emerging technology and new computing paradigm, quantum computing has a great potential to tackle those hard tasks efficiently. Among all the existing quantum computation models, quantum annealing has drawn significant attention in recent years due to the realization of the commercialized quantum annealer, sparking research interests in developing applications to solve problems that are intractable for classical computers.However, designing and implementing algorithms that manage to harness the enormous computation power from quantum annealer remains a challenging task. Generally, it requires mapping of the given optimization problem into quadratic unconstrained binary optimization(QUBO) problem and embedding the subsequent QUBO onto the physical architecture of quantum annealer. Additionally, practical quantum annealers are susceptible to errors leading to low probability of the correct solution.In this study, we focus on solving Boolean satisfiability (SAT) problem using quantum annealer while addressing practical limitations. We have proposed a mapping technique that maps SAT problem to QUBO, and we have further devised a tool flow that embeds the QUBO onto the architecture of a quantum annealing device. Additionally, We have optimized the proposed embedding flow to reduce run-time in addition to shortening the qubit chain length, leading to robust quantum annealing. To further improve the reliability of quantum annealing, we have also developed a post processing embedding technique that enlarges the energy gap between ground state and the first excited state. To demonstrate the effectiveness of proposed methods, we have conducted experiments on real quantum annealing devices manufactured by D-Wave Systems, showing compelling result of using quantum annealer to solve SAT problem.