Quantum annealing (QA) uses the principles of quantum mechanics for solving unconstrained optimization problems. Since its initial proposal, there has been much interest in the search for practical problems for which QA has advantage over classical algorithms. Although it is believed that quantum computers cannot in general solve NP-complete problems efficiently, there has been evidence suggesting that effects such as quantum tunneling can bring quantum speedup over classical computation for some problems in NP. In this dissertation, we consider two problems that have both theoretical and practical importance. One is the Set Cover with Pairs problem. The other is the Factorization problem. The Set Cover with Pairs (SCP) problem is a generalization of the Set Cover problem. It requires each element in a set to be covered by at least two objects instead of one as in the Set Cover problem. The SCP problem is believed to be not only NP-hard, but also hard to approximate. In this dissertation, we explicitly construct the Ising Hamiltonians whose ground states encode the solutions of SCP instances. The resulting Ising Hamiltonian has the appealing property that the control precision required for encoding an SCP instance scales only linearly with the number of objects in the covering set. The Integer Factorization problem is of great interest in the quantum community because it is difficult to solve using classical methods and its importance in cryptography. In this dissertation, we propose a general framework for solving factorization problems using quantum annealing, by mapping the framework to an Ising Hamiltonian. We develop several methods to consider the specific requirements such as control precision, spin-spin connection in the current Ising machines. We test the methods on the latest D-Wave 2000Q machine.
Quantum annealing (QA) uses the principles of quantum mechanics for solving unconstrained optimization problems. Since its initial proposal, there has been much interest in the search for practical problems for which QA has advantage over classical algorithms. Although it is believed that quantum computers cannot in general solve NP-complete problems efficiently, there has been evidence suggesting that effects such as quantum tunneling can bring quantum speedup over classical computation for some problems in NP. In this dissertation, we consider two problems that have both theoretical and practical importance. One is the Set Cover with Pairs problem. The other is the Factorization problem. The Set Cover with Pairs (SCP) problem is a generalization of the Set Cover problem. It requires each element in a set to be covered by at least two objects instead of one as in the Set Cover problem. The SCP problem is believed to be not only NP-hard, but also hard to approximate. In this dissertation, we explicitly construct the Ising Hamiltonians whose ground states encode the solutions of SCP instances. The resulting Ising Hamiltonian has the appealing property that the control precision required for encoding an SCP instance scales only linearly with the number of objects in the covering set. The Integer Factorization problem is of great interest in the quantum community because it is difficult to solve using classical methods and its importance in cryptography. In this dissertation, we propose a general framework for solving factorization problems using quantum annealing, by mapping the framework to an Ising Hamiltonian. We develop several methods to consider the specific requirements such as control precision, spin-spin connection in the current Ising machines. We test the methods on the latest D-Wave 2000Q machine.
Quantum annealing (QA) uses the principles of quantum mechanics for solving unconstrained optimization problems. Since its initial proposal, there has been much interest in the search for practical problems for which QA has advantage over classical algorithms. Although it is believed that quantum computers cannot in general solve NP-complete problems effciently, there has been evidence suggesting that effects such as quantum tunneling can bring quantum speedup over classical computation for some problems in NP. In this dissertation, we consider two problems that have both theoretical and practical importance. One is the Set Cover with Pairs problem. The other is the Factorization problem. The Set Cover with Pairs (SCP) problem is a generalization of the Set Cover problem. It requires each element in a set to be covered by at least two objects instead of one as in the Set Cover problem. The SCP problem is believed to be not only NP-hard, but also hard to approximate. In this dissertation, we explicitly construct the Ising Hamiltonians whose ground states encode the solutions of SCP instances. The resulting Ising Hamiltonian has the appealing property that the control precision required for encoding an SCP instance scales only linearly with the number of objects in the covering set. The Integer Factorization problem is of great interest in the quantum community because it is diffcult to solve using classical methods and its importance in cryptography. In this dissertation, we propose a general framework for solving factorization problems using quantum annealing, by mapping the framework to an Ising Hamiltonian. We develop several methods to consider the specifc requirements such as control precision, spin-spin connection in the current Ising machines. We test the methods on the latest D-Wave 2000Q machine.
Here we consider using quantum annealing to solve Set Cover with Pairs (SCP), an NP-hard combinatorial optimization problem that plays an important role in networking, computational biology, and biochemistry. We show an explicit construction of Ising Hamiltonians whose ground states encode the solution of SCP instances. We numerically simulate the time-dependent Schrödinger equation in order to test the performance of quantum annealing for random instances and compare with that of simulated annealing. We also discuss explicit embedding strategies for realizing our Hamiltonian construction on the D-wave type restricted Ising Hamiltonian based on Chimera graphs. Our embedding on the Chimera graph preserves the structure of the original SCP instance and in particular, the embedding for general complete bipartite graphs and logical disjunctions may be of broader use than that the specific problem we deal with.
The recent availability of the first commercial quantum computers has provided a promising tool to tackle NP hard problems which can only be solved heuristically with present techniques. However, it is unclear if the current state of quantum computing already provides a quantum advantage over the current state of the art in classical computing. This article assesses the performance of the D-Wave 2X quantum annealer on two NP hard graph problems, in particular clique finding and graph partitioning. For this, we provide formulations as Qubo and Ising Hamiltonians suitable for the quantum annealer and compare a variety of quantum solvers (Sapi, QBSolv, QSage provided by D-Wave Sys, Inc.) to current classical algorithms (METIS, Simulated Annealing, third-party clique finding and graph splitting heuristics) on certain test sets of graphs. We demonstrate that for small graph instances, classical methods still outperform the quantum annealer in terms of computing time, even though the quality of the best solutions obtained is comparable. Nevertheless, due to the limited problem size which can be embedded on the D-Wave 2X chip, the aforementioned finding applies to most of problems of general nature solvable on the quantum annealer. For instances specifically designed to fit the D-Wave 2X architecture, we observe substantial speed-ups in computing time over classical approaches.
Quantum annealing is a form of quantum computing that exploits quantum effects to probabilistically solve a specific, NP-hard problem: finding the ground state of a classical, Ising-model Hamiltonian. Because physical quantum annealers are already available, there exists the pressing question of how to program such systems. That is, how can one map a computational problem into the coefficients of an Ising-model Hamiltonian for solution by quantum-annealing hardware? In this article, we address that question primarily from a practical standpoint. We survey extant software tools intended for programming D-wave annealing-based quantum processors and examine the programming model and solution technique promoted by each tool in an attempt to showcase the variety of contemporary approaches to solving computationally challenging problems on an existing annealing-based quantum computer.
Critical decision-making issues in science, engineering, and industry are based on combinatorial optimization; however, its application is inherently limited by the NP-hard nature of the problem. A specialized paradigm of analogue quantum computing, quantum annealing (QA), has been proposed to solve these problems by encoding optimization problems into physical energy landscapes and solving them by quantum tunnelling systematically through exploration of solution space. This is a critical review that summarizes the current applications of quantum annealing to combinatorial optimization and includes a theoretical background, hardware designs, algorithm implementation strategies, encoding and embedding schemes, protocols to benchmark quantum annealing, areas of implementation, and links with the quantum algorithms implementation with gate-based hardware and classical solvers. We develop a unified framework, relating adiabatic quantum dynamics, Ising and QUBO models, stoquastic and non-stoquastic Hamiltonians, and diabatic transitions to modern flux-qubit annealers (Chimera, Pegasus, Zephyr topologies), and emergent architectures (Lechner-Hauke-Zoller systems, Rydberg atom platforms), and hybrids of quantum and classical computation. Through our analysis, we find that overhead in embedding and encoding is the largest determinant of the scalability and performance (this is not just the number of qubits). Minor embeddings also usually have a physical qubit count per logical variable of between 5 and 12 qubits, which limits effective problem capacity by 80-92% and, due to chain-breaking errors, compromises the quality of solutions.
With the slow progress of universal quantum computers, studies on the feasibility of optimization by a dedicated and quantum-annealing-based annealer are important. The quantum principle is expected to utilize the quantum tunneling effects to find the optimal solutions for the exponential-level problems while classical annealing may be affected by the initializations. This study constructs a new Quantum-Inspired Annealing (QIA) framework to explore the potentials of quantum annealing for solving Ising model with comparisons to the classical one. Through various configurations of the 1D Ising model, the new framework can achieve ground state, corresponding to the optimum of classical problems, with higher probability up to 28% versus classical counterpart (22% in case). This condition not only reveals the potential of quantum annealing for solving the Ising-like Hamiltonian, but also contributes to an improved understanding and use of the quantum annealer for various applications in the future.