Q-Match: Iterative Shape Matching via Quantum Annealing
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
CCuantuMM: Cycle-Consistent Quantum-Hybrid Matching of Multiple Shapes
Jointly matching multiple, non-rigidly deformed 3D shapes is a challenging, $\mathcal{NP}$-hard problem. A perfect matching is necessarily cycle-consistent: Following the pairwise point correspondences along several shap…
Matching Point Sets with Quantum Circuit Learning
In this work, we propose a parameterised quantum circuit learning approach to point set matching problem. In contrast to previous annealing-based methods, we propose a quantum circuit-based framework whose parameters are…
set matchingQuantum-Hybrid Stereo Matching With Nonlinear Regularization and Spatial Pyramids
Quantum visual computing is advancing rapidly. This paper presents a new formulation for stereo matching with nonlinear regularizers and spatial pyramids on quantum annealers as a maximum a posteriori inference problem t…
Combinatorial OptimizationStereo MatchingQuantum adiabatic machine learning with zooming
Recent work has shown that quantum annealing for machine learning, referred to as QAML, can perform comparably to state-of-the-art machine learning methods with a specific application to Higgs boson classification. We pr…
BIG-bench Machine LearningQuantum Machine LearningEnhancing Multiple Object Tracking Accuracy via Quantum Annealing
Multiple object tracking (MOT), a key task in image recognition, presents a persistent challenge in balancing processing speed and tracking accuracy. This study introduces a novel approach that leverages quantum annealin…
ManagementMultiple Object TrackingObjectObject Tracking