The area of quantum computing is a relatively new and promising branch of computation that hopes to provide help especially in the field of non-deterministic polynomial hard problems. Due to the fact that quantum computers are a heuristically non-binary approach to computation, based on the effects of quantum mechanics, a bunch of advantages and disadvantages come with it. The following work focuses especially on so-called quantum annealers, a special architecture of quantum computers that one can see as an application-specific unit that is using certain quantum mechanical effects to target binary quadratic optimization problems of the class of non-deterministic polynomial-time problems and tries to solve them faster than classical computers can do. Because this is a whole new area, it lacks extensive software support which is addressed in this work. Hence the majority of the thesis aims to develop and extend software that enables users to solve problem instances on a quantum annealer fast and reliable. Furthermore, the necessary steps to solve combinatorial optimization problems are explained and the necessary background of quantum physics theory is given. In conclusion, the main question of this work can be described as follows: 'Is it possible to create an automated pipeline to solve problems on a D-Wave Systems n.d. quantum annealer?'.
The area of quantum computing is a relatively new and promising branch of computation that hopes to provide help especially in the field of non-deterministic polynomial hard problems. Due to the fact that quantum computers are a heuristically non-binary approach to computation, based on the effects of quantum mechanics, a bunch of advantages and disadvantages come with it. The following work focuses especially on so-called quantum annealers, a special architecture of quantum computers that one can see as an application-specific unit that is using certain quantum mechanical effects to target binary quadratic optimization problems of the class of non-deterministic polynomial-time problems and tries to solve them faster than classical computers can do. Because this is a whole new area, it lacks extensive software support which is addressed in this work. Hence the majority of the thesis aims to develop and extend software that enables users to solve problem instances on a quantum annealer fast and reliable. Furthermore, the necessary steps to solve combinatorial optimization problems are explained and the necessary background of quantum physics theory is given. In conclusion, the main question of this work can be described as follows: 'Is it possible to create an automated pipeline to solve problems on a D-Wave Systems n.d. quantum annealer?'.
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.
Since the ability of quantum computing to speed up certain, specific computations has a solid theoretical underpinning, it is a natural question to ask if problems in computer vision also benefit from it. This doctoral thesis is in particular concerned with the question if the recently emerging optimization method of quantum annealing is useful for solving combinatorial optimization problems that arise in computer vision. The computer vision problem that is mainly investigated here is the problem of shape matching. The task of shape matching is to obtain the correspondences of two objects in a scene that are described with point clouds. Most often, one is concerned with finding the correspondences for a person who is recorded in 3D two times but with a different pose. The reason why this computer vision problem was picked as an interesting candidate for an application of quantum annealing is because it can be formulated as a difficult combinatorial optimization problem with a quadratic objective. This is close to the type of optimization problem that recent quantum annealing devices try to solve. The biggest difference is that in quantum annealing one a priori has unconstrained problems so that one cannot include equality constraints in the optimization. In the first work of this thesis, multiple methods are presented to overcome this difference and for really small shape matching problems experiments with simulated quantum annealing and with quantum annealing on D-Wave quantum computers were presented. In the second work of this thesis an iterative method was developed so that it was even possible to solve shape matching problems with over 500 vertices. Finally, a third publication looked at problems where one needs to find the correspondences between multiple shapes. Besides applications of quantum annealing for shape matching, this thesis also contains work on solving the motion segmentation problem with quantum annealing and work about integrating a quantum annealer in a neural network to solve computer vision problems. The integration of the quantum annealer in a neural network can also be viewed as the task to learn an appropriate formulation of a computer vision problem in a way that is solvable with a current quantum annealer. Finally, we also present work about an iterative method for compensating limited connectivity in quantum annealing devices. This work has no particular computer vision application in mind, but investigates the performance of the different approaches on Max-Cut problems. The thesis is structured in a cumulative way, so that the individual publications are presented separately. On a broader picture, the works are motivated by the following questions: What could be the impact of quantum annealing on computer vision and how could computer vision algorithms that use quantum annealing look like? And from another perspective: How would the field of computer vision be changed if there were massive advances in building quadratic, unconstrained, binary optimization problem solvers with or even without utilizing quantum computing?
Quantum computers can be much faster than any classical computers in solving a certain class of problems. One of the interesting problems is the combinatorial optimization problem, which is a challenge for classical computer systems. We encode these problems into the Quadratic Unconstrained Binary Optimization (QUBO) format and then solve them with quantum solvers. In this study, we compare the performance of D-Wave’s quantum annealing system with classical solvers, namely, Gurobi and Fixstars. We demonstrate the current capabilities of the D-Wave system.
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.
Abstract Quantum computers have strict requirements for the problems that they can efficiently solve. One of the principal limiting factor for the performances of noisy intermediate-scale quantum (NISQ) devices is the number of qubits required by the running algorithm. Several combinatorial optimization problems can be solved with NISQ devices once that a corresponding quadratic unconstrained binary optimization (QUBO) form is derived. Numerous techniques have been proposed to achieve such reformulations and, depending on the method chosen, the number of binary variables required, and therefore of qubits, can vary considerably. The aim of this work is to drastically reduce the variables needed for these QUBO reformulations in order to unlock the possibility to efficiently obtain optimal solutions for a class of optimization problems with NISQ devices. This goal is achieved by introducing novel tools that allow an efficient use of slack variables, even for problems with non-linear constraints, without the need to approximate the starting problem. We divide our new techniques in two independent parts, called the iterative quadratic polynomial and the master-satellite methods. Hence, we show how to apply our techniques in case of an NP-hard optimization problem inspired by a real-world financial scenario called Max-Profit Balance Settlement . We follow by submitting several instances of this problem to two D-wave quantum annealers, comparing the performances of our novel approach with the standard methods used in these scenarios. Moreover, this study allows to appreciate several performance differences between the D-wave Advantage and next-generation Advantage2 quantum annealers. We show that the adoption of our techniques in this context allows to obtain QUBO formulations with significantly fewer slack variables, i.e. around 90% less, and D-wave annealers provide considerably higher correct solution rates, which moreover do not decrease with the input size as fast as when adopting standard techniques.
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.