The exploitation of quantum mechanical principles seems to provide a decisive advantage over classical computation technologies. In the recent years there has been big progress in realizing different quantum computer architectures, especially by the Canadian company D-Wave Systems, which developed the first commercially available adiabatic quantum annealer. By adiabatic evolution of quantum mechanical systems it can solve NP-hard discrete optimization problems probabilistically. Due to the restrictions of the hardware architecture the directly mappable problems are limited to quadratic unconstrained binary optimization (QUBO) problems over a so called Chimera interaction graph. After briefly introducing the physical and quantum computational background including the diffculties in determining the run time and success probability of the D-Wave machine, the presentation will focus on the mapping of more general problems onto their specific problem structure. In addition to the reductions to QUBOs the main part here is the minor embedding with the distribution of the weight of the original node onto several hardware nodes.
The exploitation of quantum mechanical principles seems to provide a decisive advantage over classical computation technologies. In the recent years there has been big progress in realizing different quantum computer architectures, especially by the Canadian company D-Wave Systems, which developed the first commercially available adiabatic quantum annealer. By adiabatic evolution of quantum mechanical systems it can solve NP-hard discrete optimization problems probabilistically. Due to the restrictions of the hardware architecture the directly mappable problems are limited to quadratic unconstrained binary optimization (QUBO) problems over a so called Chimera interaction graph. After briefly introducing the physical and quantum computational background including the diffculties in determining the run time and success probability of the D-Wave machine, the presentation will focus on the mapping of more general problems onto their specific problem structure. In addition to the reductions to QUBOs the main part here is the minor embedding with the distribution of the weight of the original node onto several hardware nodes.
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.
Commercial adiabatic quantum annealers have the potential to solve important NP-hard optimization problems efficiently. The newest generation of those machines additionally allows the user to customize the anneal schedule, that is, the schedule with which the anneal fraction is changed from the start to the end of the annealing. In this work we use the aforementioned feature of the D-Wave 2000Q to attempt to monitor how the anneal solution evolves during the anneal process. This process we call slicing: at each time slice during the anneal, we are able to obtain an approximate distribution of anneal solutions. We use our technique to obtain a variety of insights into the D-Wave 2000Q. For example, we observe when individual bits flip during the anneal process and when they stabilize, which allows us to determine the freeze-out point for each qubit individually. We highlight our results using both random QUBO (quadratic unconstrained binary optimization) instances and, for better visualization, instances which we specifically optimize (using our own genetic algorithm) to exhibit a pronounced evolution of its solution during the anneal.
In the recent years the field of adiabatic quantum computing has gained importance due to the advances in the realisation of such machines, especially by the company D-Wave Systems. In contrast to a quantum computer in the conventional sense, an adiabatic quantum computer can solve a discrete optimisation problem by encoding the objective function into a quantum mechanical system. By carefully evolving the system in time from an initial state into the lowest energy state, the optimisation problem is solved. Due to the quantum nature of the device it is assumed that there is a substantial speedup compared to classical HPC facilities. The D-Wave machines are capable of finding the minimum of a subclass of the Ising model, a quadratic unconstrained binary optimisation problem. In this paper, we present a way of mapping more general problems to the subclass of Ising problems in order to make them solvable on an adiabatic quantum computer. As an example, we choose the maximum clique problem where one needs to find the maximal complete subgraph in an undirected graph. The corresponding decision problem is NP-complete. It has applications in social media or computational chemistry. Moreover, the solution of the maximum clique problem can be used to increase the number of logical variables which can be realised on a D-Wave machine. In addition, we investigate the applicability of adiabatic quantum computing to the scheduling optimisation of satellite missions performed by the German Aerospace Center.
Abstract Quantum annealing is a type of analog computation that aims to use quantum mechanical fluctuations in search of optimal solutions of QUBO (quadratic unconstrained binary optimization) or, equivalently, Ising problems. Since NP-hard problems can in general be mapped to Ising and QUBO formulations, the quantum annealing paradigm has the potential to help solve various NP-hard problems. Current quantum annealers, such as those manufactured by D-Wave Systems, Inc. have various practical limitations including the size (number of qubits) of the problem that can be solved, the qubit connectivity, and error due to the environment or system calibration, which can reduce the quality of the solutions. Typically, for an arbitrary problem instance, the corresponding QUBO (or Ising) structure will not natively embed onto the available qubit architecture on the quantum chip. Thus, in these cases, a minor embedding of the problem structure onto the device is necessary. However, minor embeddings on these devices do not always make use of the full sparse chip hardware graph, and a large portion of the available qubits stay unused during quantum annealing. In this work, we embed a disjoint random QUBO on the unused parts of the chip alongside the QUBO to be solved, which acts as an indicator of the solution quality of the device over time. Using experiments on three different D-Wave quantum annealers, we demonstrate that (i) long term trends in solution quality exist on the D-Wave device, and (ii) the unused qubits can be used to measure the current level of noise of the quantum system.
Vehicle Routing Problem is a well-known optimization issue, which has many extensions resulting from practical appliances. The problem is NP-hard, therefore it may be impossible to find an optimal solution for big instances, with traditional computation methods. Recent development of quantum technology, may be a response for this challenge, which however requires a different formulation of the model. The problem is then modeled using Quadratic Unconstrained Binary Optimization (QUBO) equations. Such model can be run using quantum annealers (QA), designed specifically for optimization purposes. This paper is a systematic survey of Vehicle Routing Problem models that are formulated using QUBO, to be solved on quantum computers. The main goal of the paper is to check research gaps in this subject, compare and explain different approaches of modeling various problem extensions with QUBO. The results obtained in reviewed papers will be presented and analyzed. Moreover, the theoretical basis for quantum computation will be presented, with focus on D-Wave company solutions.
Quantum annealing (QA) can be used to quickly obtain near-optimal solutions for quadratic unconstrained binary optimization (QUBO) problems. In QA hardware, each decision variable of a QUBO should be mapped to one or more adjacent qubits in such a way that pairs of variables defining a quadratic term in the objective function are mapped to some pair of adjacent qubits. However, qubits have limited connectivity in existing QA hardware. This has spurred work on preprocessing algorithms for embedding the graph representing problem variables with quadratic terms into the hardware graph representing qubits adjacencies, such as the Chimera graph in hardware produced by D-Wave Systems. In this paper, we use integer linear programming to search for an embedding of the problem graph into certain classes of minors of the Chimera graph, which we call template embeddings. One of these classes corresponds to complete bipartite graphs, for which we show the limitation of the existing approach based on minimum odd cycle transversals (OCTs). One of the formulations presented is exact and thus can be used to certify the absence of a minor embedding using that template. On an extensive test set consisting of random graphs from five different classes of varying size and sparsity, we can embed more graphs than a state-of-the-art OCT-based approach, our approach scales better with the hardware size, and the runtime is generally orders of magnitude smaller. Summary of Contribution: Our work combines classical and quantum computing for operations research by showing that integer linear programming can be successfully used as a preprocessing step for adiabatic quantum optimization. We use it to determine how a quadratic unconstrained binary optimization problem can be solved by a quantum annealer in which the qubits are coupled as in a Chimera graph, such as in the quantum annealers currently produced by D-Wave Systems. The paper also provides a timely introduction to adiabatic quantum computing and related work on minor embeddings.