There is growing interest in solving computer vision problems such as mesh or point set alignment using Adiabatic Quantum Computing (AQC). Unfortunately, modern experimental AQC devices such as D-Wave only support Quadratic Unconstrained Binary Optimisation (QUBO) problems, which severely limits their applicability. This paper proposes a new way to overcome this limitation and introduces QuCOOP, an optimisation framework extending the scope of AQC to composite and binary-parametrised, possibly non-quadratic problems. The key idea of QuCOOP is to iteratively approximate the original objective function by a sequel of local (intermediate) QUBO forms, whose binary parameters can be sampled on AQC devices. We experiment with quadratic assignment problems, shape matching, and point set registration without knowing the correspondences in advance. Our approach achieves state-of-the-art results across multiple instances of tested problems.
QuCOOP aims to solve the binary problem \[ \arg \min_{x\in\{0, 1\}^k} \ g(x)^\top \mathbf Q g(x) + \mathbf{c}^\top g(x), \quad \text{s.t.} \quad g(x) \in \mathcal S \tag{1} \label{eq:originalpb} \] where \(g\) is a possibly non-linear function in \(x\), \(\mathbf Q\) and \(\mathbf c\) are provided coupling matrix and bias vector, and \(\mathcal S \subset \mathbb R^n \) the modelisation of some constraints. QuCOOP leverages quantum annealing (QA) as a solver to sample the binary variables \(x\). To deal with the restriction of QA devices to Quadratic Unconstrained Binary Optimisation (QUBO) problems, QuCOOP reduces the original problem \((1)\), that may be non-quadratic for a non-linear \(g\) in \(x\), to a sequel of QUBO solvable on QA devices.
Initialise \(x^0\) and repeat for \(t = 0, 1, 2, \ldots\)
\[ g^t (x) := g(x^t) + \langle \nabla g(x^t), x - x^t \rangle \tag{2} \label{eq:linearisation} \]
\[ x^{t+1} \gets \arg\min_{x \in \{0, 1\}^k} \ \left\{f^t(x) := f(g^t(x))\right\} \\ \quad \text{s.t.} \quad g^t(x) \in \mathcal{S} \tag{3} \label{eq:minimisation_step} \]
We propose a binary-parametrised function to model permutation matrices. Any permutation matrix \(\mathbf P \) of \(n\) elements can be written as the product of binary parametrised transpositions: \[ \mathbf P(x) := \prod_i \mathbf T_i^{x_i}, \quad \mathbf T_i^{x_i} = \begin{cases} \mathbf T_i &\quad \text{if} \ x_i = 1,\\ \mathbf I &\quad \text{otherwise}, \end{cases} \] where \(\mathbf T_i\) is the \(i\)th element of the tuple \( ((a, b), \ a, b = 1, \ldots, n, \ a \lt b) \), with cardinality \(k = n(n-1)/2\), of all transpositions, i.e. \(2\)-cycles permuting \(a\) and \(b\). This encoding allows tackling a range of permutation-related problems with QuCOOP.
QuCOOP can approximately solve graph matching and QAP; it is versatile, as it is compatible with continuous problems such as point set registration without correspondences. We experiment on the QAPLIB and FAUST datasets, and register \(2\)D and \(3\)D point sets.
Registration results on 2D and 3D point sets with different \(n\). Grey lines show correspondences between reference (olive) and template (blue) points. With up to a few correspondence errors, our method performs well on both isomorphic (left to vertical line) and non-isomorphic shapes (right to vertical line). CPD performs better on isomorphic shapes than on non-isomorphic shapes.
Our general QuCOOP framework clearly matches the accuracy of the previous specialised Q-Match method. It reduces the mean geodesic error by about 0.01, as it can achieve better results on the sub-problems.
We plot the percentage energy error for all considered problem instances (note the means over all instances reported in the legend) and provide their runtimes. Our QuCOOP solver clearly outperforms its competitors.
We now execute QuCOOP on a real quantum device, D-Wave Advantage 6.4 accessed through the Leap API.
QuCOOP QA finds valid permutation matrices, but returns higher objective values compared to QuCOOP SA and Q-Match QA. As \(n\) becomes large, QuCOOP QA tends to compute non-valid matrices. QuCOOP QA took about \(5\times\) less runtime than Q-Match QA on the same problem instance, including overheads such as minor embedding and access.
We see that QuCOOP can register the points without correspondences up to \(n = 5\), improving previous works in which correspondences are known beforehand.
@inproceedings{meli2025qucoop,
title={QuCOOP: A Versatile Framework for Solving Composite and Binary-Parametrised Problems on Quantum Annealers},
author={Natacha Kuete Meli and Vladislav Golyanik and Marcel Seelbach Benkner and Michael Moeller},
booktitle={Computer Vision and Pattern Recognition (CVPR)},
year={2025}
}