Research map / Point clouds / Registration and matching
QuCOOP: A Versatile Framework for Solving Composite and Binary-Parametrised Problems on Quantum Annealers
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes QuCOOP, which iteratively linearises the inner function of a composite objective and solves the resulting QUBO subproblems on simulated or real quantum annealers, applied to QAP, shape matching and point set registration.
Problem
Quantum annealers (D-Wave) only accept QUBO problems, which limits AQC use for computer vision problems with non-quadratic or composite objectives over binary parameters, such as permutation matching and point set registration without correspondences.
Approach
Iteratively linearise the smooth inner parametrisation g around the current binary iterate, so the objective becomes quadratic in binary variables and each sub-step is a QUBO solvable by annealing; a quadratic penalty enforces feasibility, and a binary parametrisation of permutations (2-cycles) and rotations enables the framework.
Key results
- On QAPLIB instances with n<=50 (72 total), the method achieved the lowest mean percentage energy error (5.53 vs 10.01 for Q-Match, 12.64 for 2-OPT, 19.95 for FAQ) using simulated annealing.
- On FAUST shape matching, mean geodesic error was reduced slightly versus Q-Match (about 0.01, e.g. 0.1649 vs 0.1728 in one category).
- On D-Wave Advantage hardware, valid permutation matrices were found up to about n=12 for QAP and point set registration succeeded up to n=5 without known correspondences.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use QuCOOP instead of Q-Match | QAPLIB instances with n ≤ 50 · QAPLIB | % Energy Error: 5% | Helped |
| Use QuCOOP instead of Q-Match | FAUST shape matching · FAUST inter and intra poses | mean geodesic error: 0.01 | Helped |
| Use QuCOOP instead of CPD | rigid point set registration · 2D and 3D point sets | registration accuracy | Mixed |
| Run QuCOOP on D-Wave rather than with simulated annealing | QuCOOP for QAP · Random QAP instances, n = 3, 5, 7, 9, 12, 15 | objective function value | Hurt |
Surprising findings
- On D-Wave hardware, returned matrices become invalid as n grows, so the quantum-annealer results are limited to small problem sizes.
- The classical CPD baseline performs worse on non-isomorphic point sets, while the method remains correct on some non-isomorphic cases.
Limitations
- Linearisation of the inner function may be inaccurate for highly nonlinear g, leading to suboptimal solutions.
- Quadratic growth of binary parameters with n makes D-Wave embeddings hard; hardware experiments limited to n around 12-15.
- Penalty factors are set by grid search and the method does not guarantee global convergence.
Experimental setup
Datasets: QAPLIB FAUST
Benchmarks: QAPLIB FAUST
Metrics: percentage energy error runtime (s) cumulative geodesic error mean geodesic error energy validness of permutation matrices rotation error ||R||_F
Baselines: FAQ 2-OPT Q-Match CPD IQT
Builds on: Q-Match IQT (iterative quantum transformation) prox-linear composite optimisation quadratisation of pseudo-Boolean functions
Closest papers by meaning
- Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling (ICLR 2025 · similarity 0.83)
- Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum Computing (CVPR 2024 · similarity 0.83)
- A Sub-Problem Quantum Alternating Operator Ansatz for Correlation Clustering (ICML 2025 · similarity 0.83)
- QCircuitBench: A Large-Scale Dataset for Benchmarking Quantum Algorithm Design (NeurIPS 2025 · similarity 0.82)
- Hybrid Quantum-Classical Multi-Agent Pathfinding (ICML 2025 · similarity 0.82)
- Q-MAML: Quantum Model-Agnostic Meta-Learning for Variational Quantum Algorithms (AAAI 2025 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.