Abstract

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, in theory, allows to find globally optimal solutions relying on a new computational paradigm. 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 α-expansion algorithm, which allows solving problems of an order of magnitude larger than current quantum methods. It works by implicitly enforcing the QAP constraints by updating the current estimates in a cyclic fashion. Further, Q-Match can be applied for shape matching problems 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.

Quantum Annealing

Quantum annealing is a metaheuristic method to solve discrete, combinatorial optimization problems. If the cost function contains high and narrow energy barriers it can search the energy landscape more efficiently than simulated annealing. We propose an iterative algorithm that uses a quantum annealer from D-Wave in each step. Our algorithm is used for quadratic assignment problems with permutation constraints, which appear frequently in shape matching problems.

Downloads


Citation

BibTeX, 1 KB

@misc{SeelbachBenkner2021, 
       author = {{Seelbach Benkner}, Marcel and {L\"{a}hner}, Zorah and {Golyanik}, Vladislav and {Wunderlich}, Christof and {Theobalt}, Christian and {Moeller}, Michael}, 
       title = {Q-Match: Iterative Shape Matching via Quantum Annealing}, 
       archivePrefix = {arXiv}, 
       year = {2021} 
}  				

Contact

For questions, clarifications, please get in touch with:
Marcel Seelbach Benkner Marcel.Seelbach@uni-siegen.de
Zorah Lähner zorah.laehner@uni-siegen.de
Vladislav Golyanik golyanik@mpi-inf.mpg.de

This page is Zotero translator friendly. Page last updated Imprint. Data Protection.