Q-Match: Iterative Shape Matching via Quantum Annealing
This addresses shape correspondence challenges in computer vision and graphics, offering a scalable quantum solution for real-world problems, though it is incremental in improving quantum annealing efficiency.
The paper tackles the NP-hard quadratic assignment problem for shape matching by proposing Q-Match, an iterative quantum method that scales to problems an order of magnitude larger than current quantum methods, achieving results on QAPLIB and FAUST datasets.
Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) that becomes infeasible for shapes with high sampling density. A promising research direction is to tackle such quadratic optimization problems over binary variables with quantum annealing, which allows for some problems a more efficient search in the solution space. Unfortunately, enforcing the linear equality constraints in QAPs via a penalty significantly limits the success probability of such methods on currently available quantum hardware. To address this limitation, this paper proposes Q-Match, i.e., a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm, which allows solving problems of an order of magnitude larger than current quantum methods. It implicitly enforces the QAP constraints by updating the current estimates in a cyclic fashion. Further, Q-Match can be applied iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems. Using the latest quantum annealer, the D-Wave Advantage, we evaluate the proposed method on a subset of QAPLIB as well as on isometric shape matching problems from the FAUST dataset.