Quantum computing requires qubits, which obey the laws of quantum mechanics and therefore behave very dierently from classical bits. This dierence can allow quantum computers to achieve massive levels of parallelism impossible on a classical computer. As a result, certain problems that are in NP but highly parallelizable can be solved by quantum computers in polynomial time. Quantum computers have the capacity to drastically change the computing world, but they are complex and dicult to implement; to study them, we often look to simulators that can bypass many of the roadblocks inhibiting our path to a true quantum computer. A simulated quantum annealer takes advantage of the adiabatic theorem to solve problems by transitioning from a simple to complex quantum state while maintaining minimal energy. We simulate these quantum states, energies, and transitions on classical machines by mathematical abstractions for proof of concept and to circumvent the complications of physical implementation. To do this, we solve 3SAT on a classical machine simulating how it would be solved by quantum annealing.
Quantum computing requires qubits, which obey the laws of quantum mechanics and therefore behave very dierently from classical bits. This dierence can allow quantum computers to achieve massive levels of parallelism impossible on a classical computer. As a result, certain problems that are in NP but highly parallelizable can be solved by quantum computers in polynomial time. Quantum computers have the capacity to drastically change the computing world, but they are complex and dicult to implement; to study them, we often look to simulators that can bypass many of the roadblocks inhibiting our path to a true quantum computer. A simulated quantum annealer takes advantage of the adiabatic theorem to solve problems by transitioning from a simple to complex quantum state while maintaining minimal energy. We simulate these quantum states, energies, and transitions on classical machines by mathematical abstractions for proof of concept and to circumvent the complications of physical implementation. To do this, we solve 3SAT on a classical machine simulating how it would be solved by quantum annealing.
Quantum physics has the potential to revolutionize computer science by building what is called a quantum computer. Quantum computers can perform tasks that are impossible with Turing-machine based classical computers (e.g., generating random sequences of bits) and can outperform classical computers (to different degrees) in a variety of classical computation problems. Several different models of quantum computing exist. Based on the Adiabatic Theorem in physics, Adiabatic Quantum Computing is a novel computing framework that is drastically different from the more traditional quantum logic gate model. Traditionally, quantum computing has only been tested on devices with a very small number of qubits, severely limiting their uses in practice. In recent years however, advances in engineering and physics have allowed the construction for (relatively) large machines called quantum annealers that do what is known as a specific type of adiabatic quantum computation called quantum annealing. Solving classical computation problems with the quantum annealing framework is not an easy task and there are many obstacles to overcome if we want to achieve any kind of speedups over classical algorithms. In this thesis, we present quantum annealing solutions to several classical problems including the Hamiltonian Cycle Problem, Mixed Dominating Set Problem, Graph Isomorphism Problem, Densest k-Subgraph Problem and the Maximum Weighted Independent Set Problem. Experimental results of these quantum solutions on DWave quantum annealers are also reported. We also look at some of the bottlenecks in the quantum annealing framework and propose several novel approach to mitigate their effects on the efficiency of the quantum solutions.
Quantum computers use quantum resources to carry out computational tasks and may outperform classical computers in solving certain computational problems. Special-purpose quantum computers such as quantum annealers employ quantum adiabatic theorem to solve combinatorial optimization problems. In this paper, we compare classical annealings such as simulated annealing and quantum annealings that are done by the D-Wave machines both theoretically and numerically. We show that if the classical and quantum annealing are characterized by equivalent Ising models, then solving an optimization problem, i.e., finding the minimal energy of each Ising model, by the two annealing procedures, are mathematically identical. For quantum annealing, we also derive the probability lower-bound on successfully solving an optimization problem by measuring the system at the end of the annealing procedure. Moreover, we present the Markov chain Monte Carlo (MCMC) method to realize quantum annealing by classical computers and investigate its statistical properties. In the numerical section, we discuss the discrepancies between the MCMC based annealing approaches and the quantum annealing approach in solving optimization problems.
Many problems of industrial interest are NP-complete, and quickly exhaust resources of computational devices with increasing input sizes. Quantum annealers (QA) are physical devices that aim at this class of problems by exploiting quantum mechanical properties of nature. However, they compete with efficient heuristics and probabilistic or randomised algorithms on classical machines that allow for finding approximate solutions to large NP-complete problems. While first implementations of QA have become commercially available, their practical benefits are far from fully explored. To the best of our knowledge, approximation techniques have not yet received substantial attention. In this paper, we explore how problems' approximate versions of varying degree can be systematically constructed for quantum annealer programs, and how this influences result quality or the handling of larger problem instances on given set of qubits. We illustrate various approximation techniques on both, simulations and real QA hardware, on different seminal problems, and interpret the results to contribute towards a better understanding of the real-world power and limitations of current-state and future quantum computing.
Quantum annealing is a computational paradigm in which optimisation problems are mapped onto the energy landscape of an interacting quantum system and explored through its dynamical evolution. By continuously transforming a simple initial Hamiltonian into one whose ground state encodes the solution, the system traverses a complex landscape via a combination of quantum fluctuations, tunnelling processes, and dissipative dynamics. Unlike gate-based quantum computing, quantum annealing is a specialised and near-term approach aimed primarily at discrete optimisation and sampling tasks. While it is not expected to provide polynomial-time solutions to NP-hard problems in the worst case, it offers a physically motivated heuristic for navigating rugged energy landscapes that arise across science and engineering. Modern quantum annealers realise programmable spin systems with thousands of qubits, placing them among the largest controllable quantum devices currently available. As a result, their significance extends beyond optimisation: they also function as experimental platforms for studying non-equilibrium many-body quantum dynamics in regimes that are difficult to access using classical simulation. In this review we present an accessible introduction to the principles of quantum annealing, describe the main hardware platforms and algorithmic techniques, and analyse how tunnelling, spectral gaps, and open-system effects shape computational performance. We survey applications ranging from optimisation and machine learning to quantum simulation and many-body physics, and discuss the central challenges in benchmarking, scaling, and control. These perspectives position quantum annealing as a distinctive framework at the interface of optimisation, stochastic sampling, and programmable quantum dynamics, with a role that is complementary to both classical algorithms and gate-based quantum computing.
I describe how real quantum annealers may be used to perform local (in state space) searches around specified states, rather than the global searches traditionally implemented in the quantum annealing algorithm (QAA). Such protocols will have numerous advantages over simple quantum annealing. By using such searches the effect of problem mis-specification can be reduced, as only energy differences between the searched states will be relevant. The QAA is an analogue of simulated annealing, a classical numerical technique which has now been superseded. Hence, I explore two strategies to use an annealer in a way which takes advantage of modern classical optimization algorithms. Specifically, I show how sequential calls to quantum annealers can be used to construct analogues of population annealing and parallel tempering which use quantum searches as subroutines. The techniques given here can be applied not only to optimization, but also to sampling. I examine the feasibility of these protocols on real devices and note that implementing such protocols should require minimal if any change to the current design of the flux qubit-based annealers by D-Wave Systems Inc. I further provide proof-of-principle numerical experiments based on quantum Monte Carlo that demonstrate simple examples of the discussed techniques.
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.