RESEARCH PAPERS

The limited connectivity of current and next-generation quantum annealers motivates the need for efficient graph-minor embedding methods. These methods allow non-native problems to be adapted to the target annealer’s architecture. The overhead of the widely used heuristic techniques is quickly proving to be a significant bottleneck for solving real-world applications. To alleviate this difficulty, we propose a systematic and deterministic embedding method, exploiting the structures of both the input graph of the specific problem and the quantum annealer. We focus on the specific case of the Cartesian product of two complete graphs, a regular structure that occurs in many problems. We divide the embedding problem by first embedding one of the factors of the Cartesian product in a repeatable pattern. The resulting simplified problem consists of the placement and connecting together of these copies to reach a valid solution. Aside from the obvious advantage of a systematic and deterministic approach with respect to speed and efficiency, the embeddings produced are easily scaled for larger processors and show desirable properties for the number of qubits used and the chain length distribution. To conclude, we briefly address the problem of circumventing inoperable qubits by presenting possible extensions of the method.

In this paper, we tackle the problem of measuring similarity among graphs that represent real objects with noisy data. To account for noise, we relax the definition of similarity using the maximum weighted co-k-plex relaxation method, which allows dissimilarities among graphs up to a predetermined level. We then formulate the problem as a novel quadratic unconstrained binary optimization problem that can be solved by a quantum annealer. The context of our study is molecular similarity where the presence of noise might be due to regular errors in measuring molecular features. We develop a similarity measure and use it to predict the mutagenicity of a molecule. Our results indicate that the relaxed similarity measure, designed to accommodate the regular errors, yields a higher prediction accuracy than the measure that ignores the noise.

In this paper we present a quantum annealing algorithm for computation of homology of large point clouds. It is designed to work on resizable cloud computing platforms. The algorithm takes as input a witness complex K approximating the given point cloud. It uses quantum annealing to compute a clique cover of the 1-skeleton of K and then uses this cover to blow up K into a Mayer-Vietoris complex. Finally, it computes the homology of the Mayer-Vietoris complex in parallel. The novelty here is the use of clique covering which, compared to graph partitioning, substantially reduces the computational load assigned to each slave machine in the computing cluster. We describe two different clique covers and their quantum annealing formulation in the form of quadratic unconstrained binary optimization (QUBO).

Quantum adiabatic evolution is perceived as useful for binary quadratic programming problems that are a priori unconstrained. For constrained problems, it is a common practice to relax linear equality constraints as penalty terms in the objective function. However, there has not yet been proposed a method for efficiently dealing with inequality constraints using the quantum adiabatic approach. In this paper, we give a method for solving the Lagrangian dual of a binary quadratic programming (BQP) problem in the presence of inequality constraints and employ this procedure within a branch-and-bound framework for constrained BQP (CBQP) problems.

We solve a multi-period portfolio optimization problem using D-Wave Systems’ quantum annealer. We derive a formulation of the problem, discuss several possible integer encoding schemes, and present numerical examples that show high success rates. The formulation incorporates transaction costs (including permanent and temporary market impact), and, significantly, the solution does not require the inversion of a covariance matrix. The discrete multi-period portfolio optimization problem we solve is significantly harder than the continuous variable problem. We present insight into how results may be improved using suitable software enhancements, and why current quantum annealing technology limits the size of problem that can be successfully solved today. The formulation presented is specifically designed to be scalable, with the expectation that as quantum annealing technology improves, larger problems will be solvable using the same techniques.

A quantum annealer heuristically minimizes quadratic unconstrained binary optimization (QUBO) problems, but is limited by the physical hardware in the size and density of the problems it can handle. We have developed a meta-heuristic solver that utilizes D-Wave Systems’ quantum annealer (or any other QUBO problem optimizer) to solve larger or denser problems, by iteratively solving subproblems, while keeping the rest of the variables fixed. We present our algorithm, several variants, and the results for the optimization of standard QUBO problem instances from OR-Library of sizes 500 and 2500 as well as the Palubeckis instances of sizes 3000 to 7000. For practical use of the solver, we show the dependence of the time to best solution on the desired gap to the best known solution. In addition, we study the dependence of the gap and the time to best solution on the size of the problems solved by the underlying optimizer.

A quantum annealing solver for the renowned job-shop scheduling problem (JSP) is presented in detail. After formulating the problem as a time-indexed quadratic unconstrained binary optimization problem, several pre-processing and graph embedding strategies are employed to compile optimally parametrized families of the JSP for scheduling instances of up to six jobs and six machines on the D-Wave Systems Vesuvius processor. Problem simplifications and partitioning algorithms, including variable pruning and running strategies that consider tailored binary searches, are discussed and the results from the processor are compared against state-of-the-art global-optimum solvers.