Quantum annealing (QA) is a different technology from gate-model quantum computing. This research proposes a novel technique for solving the Minimum Spanning Tree (MST) (or, the minimum weight spanning tree) problem on a quantum annealer. The problem is of interest due to its applications in clustering, unsupervised learning, network design, and image processing to name a few. The advent of quantum cloud computing has provided access to quantum computing tools, previously unavailable to the general community. D-Wave systems recently released cloud access to their quantum annealer type hardware, which this project leverages to provide a novel solution method to the MST problem.
Quantum annealing (QA) is a different technology from gate-model quantum computing. This research proposes a novel technique for solving the Minimum Spanning Tree (MST) (or, the minimum weight spanning tree) problem on a quantum annealer. The problem is of interest due to its applications in clustering, unsupervised learning, network design, and image processing to name a few. The advent of quantum cloud computing has provided access to quantum computing tools, previously unavailable to the general community. D-Wave systems recently released cloud access to their quantum annealer type hardware, which this project leverages to provide a novel solution method to the MST problem.
One of the most common and well-known problems in combinatorial optimization is the minimum spanning tree. With the emergence of complex data structures, new, more complex, but asymptotically efficient algorithms have been proposed. In this research, we present a new evolutionary algorithm influenced by quantum mechanics, known as quantum-inspired evolutionary algorithm (QIEA) to find the minimum spanning tree of a complete weighted undirected graph as input and computational results to demonstrate the effectiveness of proposed algorithm. The proposed algorithm is named QIEA-MST and is based on concept and principle such as qubits and the superposition, coherence and the entanglement of different qubits of quantum state. The algorithm is simple and easy to understand and easy to implement. Some types of scientific and engineering problems will benefit from the proposed method.
Finding the minimum spanning tree (MST) of a graph is an important task in computer vision, as it enables a sparse and low-cost representation of connectivity among elements (such as superpixels, points, or regions), which is useful for tasks such as segmentation, reconstruction, and clustering. In this work, we propose and evaluate a fully quantum pipeline for computing MSTs using the FALQON algorithm, a feedback-based quantum optimization method that does not require classical optimizers. We construct a Hamiltonian formulation whose ground-state energy encodes the MST of a graph and compare different FALQON strategies: (i) time rescaling (TR-FALQON) and (ii) multi-driver configurations. To avoid domain-specific biases, we adopt graphs with random weights and show that the FALQON variants exhibit significant differences in ground-state fidelity. We discuss the relevance of this approach for computer vision problems that naturally yield graph representations, and experimental results on synthetic instances together with a small demonstrative study on image segmentation illustrate both the potential and the current limitations of the method. Our numerical simulations on randomly weighted graphs show that standard one drive FALQON, although it reduces the expected energy, fails to concentrate amplitude in the MST solution. The multi drive variant succeeds in redistributing probability mass toward the ground state so that the MST appears among the most probable outcomes, and TR FALQON applied over multi drive produces the best results with faster convergence, lower final energy, and the highest solution state probability or fidelity in our tested instances. These improvements were observed on small synthetic graphs, underscoring both the promise of multi drive controls with temporal rescaling and the need for further scaling and hardware validation.
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.
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.
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.
With the emergence of D-wave’s quantum annealing machine, the power of quantum computing has become tangible, and the development of quantum computers is accelerating rapidly. Unfortunately, at present, the minimum value search that D-wave’s quantum annealing machine can handle is limited to quadratic functions of binary integer variables. This constraint is due to both hardware and software limitations. If this constraint was to be lifted, it would undoubtedly bring about a revolution in the world. Therefore, in this study, we obtained the basic mathematics of using quantum annealing, which enables hyper-parallel computing using qubits, to find the global minimum of any minimum value problem. Furthermore, we conducted simple simulations using classical computers to demonstrate the effectiveness of the ideas and algorithms. Furthermore, we conducted simple simulations using classical computers to demonstrate the effectiveness of the ideas and algorithms. We obtained also the mathematical method of using quantum annealing in learning neural networks and solving linear equations.