Quantum Annealing for Constrained Optimization

Recent advances in quantum technology have led to the development and manufacturing of experimental programmable quantum annealers that promise to solve certain combinatorial optimization problems of practical relevance faster than their classical analogues. The applicability of such devices for many theoretical and real-world optimization problems, which are often constrained, is severely limited by the sparse, rigid layout of the devices’ quantum bits. Traditionally, constraints are addressed by the addition of penalty terms to the Hamiltonian of the problem, which, in turn, requires prohibitively increasing physical resources while also restricting the dynamical range of the interactions. Here, we propose a method for encoding constrained optimization problems on quantum annealers that eliminates the need for penalty terms and thereby reduces the number of required couplers and removes the need for minor embedding, greatly reducing the number of required physical qubits. We argue the advantages of the proposed technique and illustrate its effectiveness. We conclude by discussing the experimental feasibility of the suggested method as well as its potential to appreciably reduce the resource requirements for implementing optimization problems on quantum annealers and its significance in the field of quantum computing.

Figure 1

Connectivity of a random 12-bit degree-6 graph partitioning instance. The black edges are those of the random instance, whereas the thicker green edges are the additional edges required to satisfy the constraint in the standard approach (left) and in the CQA approach (right). While “traditional” penalty-based embedding requires a fully connected graph, in the CQA approach, only six additional edges are required (so as to close a cycle).

Figure 2

First excitation gap for a random 14-bit degree-6 graph partitioning instance as a function of the adiabatic parameter $s$. The blue curve corresponds to the conservation-law-based (CQA) embedding approach, whereas the penalty-based technique is the dashed red curve. Inset: Initial ($H_d$) gap scaling inversely with problem size.

Figure 3

Exponential scaling of the typical minimum relevant gap with problem size for random GP instances (log-linear scale). The resource-efficient CQA minimum gap (blue circles) scales similarly to that of the penalty-based method (red squares) and is typically about 3 times larger.