The D-Wave quantum computer is designed to solve a specific class of problems - The Quadratic Unconstrained Binary Optimization (QUBO) problem. One of the key processes in this pathway to the solution consists in embedding the problem graph into a hardware graph. It is a nontrivial task to determine whether a problem graph is minor embeddable in a hardware graph. One method that singles out cases where minor embeddability fails requires calculation of the tree-width of both the problem and the hardware graphs. The latter computation is known to be NP-Complete. In this paper, we propose a novel, fast approximation to tree-width based on the differential geometric concept of Ollivier-Ricci curvature. This latter runs in linear time and thus could significantly reduce the overall complexity of determining whether a QUBO problem is solvable on the D-Wave architecture.
The D-Wave quantum computer is designed to solve a specific class of problems - The Quadratic Unconstrained Binary Optimization (QUBO) problem. One of the key processes in this pathway to the solution consists in embedding the problem graph into a hardware graph. It is a nontrivial task to determine whether a problem graph is minor embeddable in a hardware graph. One method that singles out cases where minor embeddability fails requires calculation of the tree-width of both the problem and the hardware graphs. The latter computation is known to be NP-Complete. In this paper, we propose a novel, fast approximation to tree-width based on the differential geometric concept of Ollivier-Ricci curvature. This latter runs in linear time and thus could significantly reduce the overall complexity of determining whether a QUBO problem is solvable on the D-Wave architecture.
We introduce a quantum algorithm for computing the Ollivier Ricci curvature, a discrete analogue of the Ricci curvature defined via optimal transport on graphs and general metric spaces. This curvature has seen applications ranging from signaling fragility in financial networks to serving as basic quantities in combinatorial quantum gravity. For inputs given as a point cloud with pairwise distances, we show that our algorithm can achieve an exponential speedup over the best-known classical methods for two particular classes of problem. Our work is another step toward quantum algorithms for geometrical problems that are capable of delivering practical value while also informing fundamental theory.
Quantum annealers such as the D-Wave 2X computer are designed to natively solve Quadratic Unconstrained Binary Optimization (QUBO) problems to optimality or near optimality. Most NP-hard problems, which are hard for classical computers, can be naturally described as quadratic binary problems that contain a quadratic binary objective function and one or more constraints. Since a QUBO cannot have constraints, each such constraint has to be added to the objective function as a penalty, in order to solve on D-Wave. For a minimization problem, for instance, such penalty can be a quadratic term that gets a value zero, if the constraint is satisfied, and a large value, if it is not. In many cases, however, the penalty can significantly increase the number of quadratic terms in the resulting QUBO and make it too large to embed into the D-Wave hardware. In this paper, we develop an alternative method for formulating and embedding constraints of the type Σi=1sxi=1, which is much more scalable than the existing ones, and analyze the properties of the resulting embeddings.
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.
Quantum annealing devices such as the ones produced by D-Wave systems are typically used for solving optimization and sampling tasks, and in both academia and industry the characterization of their usefulness is subject to active research. Any problem that can naturally be described as a weighted, undirected graph may be a particularly interesting candidate, since such a problem may be formulated a as quadratic unconstrained binary optimization (QUBO) instance, which is solvable on D-Wave's Chimera graph architecture. In this paper, we introduce a quantum-assisted finite-element method for design optimization. We show that we can minimize a shape-specific quantity, in our case a ray approximation of sound pressure at a specific position around an object, by manipulating the shape of this object. Our algorithm belongs to the class of quantum-assisted algorithms, as the optimization task runs iteratively on a D-Wave 2000Q quantum processing unit (QPU), whereby the evaluation and interpretation of the results happens classically. Our first and foremost aim is to explain how to represent and solve parts of these problems with the help of a QPU, and not to prove supremacy over existing classical finite-element algorithms for design optimization.
We propose a quadratic unconstrained binary optimization (QUBO) formulation for the Bounded-Depth Steiner Tree problem suitable for adiabatic quantum computers. The numbers of qubits (dimension of QUBO matrices) required by our formulation is O(|V|3), where |V| represents the number of vertices. A D-Wave 2X computer consisting of 1098 active qubits is evaluated for a selection of known common graphs. Experimental results are shown and discussed. Our results are applicable to the Bounded-Depth Minimum Spanning Tree problem, as a special case.
Today, hardware constraints are an important limitation on quantum adiabatic optimization algorithms. Firstly, computational problems must be formulated as quadratic unconstrained binary optimization (QUBO) in the presence of noisy coupling constants. Secondly, the interaction graph of the QUBO must have an effective minor embedding into a two-dimensional nonplanar lattice graph. We describe new strategies for constructing QUBOs for NP-complete/hard combinatorial problems that address both of these challenges. Our results include asymptotically improved embeddings for number partitioning, filling knapsacks, graph coloring, and finding Hamiltonian cycles. These embeddings can be also be found with reduced computational effort. Our new embedding for number partitioning may be more effective on next-generation hardware.