Quadratic constrained mixed discrete optimization with an adiabatic quantum optimizer

We extend the family of problems that may be implemented on an adiabatic quantum optimizer (AQO). When a quadratic optimization problem has at least one set of discrete controls and the constraints are linear, we call this a quadratic constrained mixed discrete optimization (QCMDO) problem. QCMDO problems are NP-hard, and no efficient classical algorithm for their solution is known. Included in the class of QCMDO problems are combinatorial optimization problems constrained by a linear partial differential equation (PDE) or system of linear PDEs. An essential complication commonly encountered in solving this type of problem is that the linear constraint may introduce many intermediate continuous variables into the optimization while the computational cost grows exponentially with problem size. We resolve this difficulty by developing a constructive mapping from QCMDO to quadratic unconstrained binary optimization (QUBO) such that the size of the QUBO problem depends only on the number of discrete control variables. With a suitable embedding, taking into account the physical constraints of the realizable coupling graph, the resulting QUBO problem can be implemented on an existing AQO. The mapping itself is efficient, scaling cubically with the number of continuous variables in the general case and linearly in the PDE case if an efficient preconditioner is available.

Figure 1

Charges (black and gray dots denote the presence and absence of a charge) and equipotential contours of the measured potential for the optimal (left) and best suboptimal (right) solutions of a charge reconstruction example.

Figure 2

Distribution and correlation of the minimum and final gaps of the electrostatics example in Sec. 3 as implemented in the AQO Hamiltonian in Eq. (7) for (a) all instances of $p=5$, (b) all instances of $p=13$, and (c) 1000 random samples of $p=25$. Nonblack data points indicate cases when the Hamming distance between the ground- and first excited-state charge distributions is greater than 1.