A Quantum Computational Approach to Correspondence
Problems on Point Sets

Vladislav Golyanik   Christian Theobalt
Max Planck Institute for Informatics, Saarland Informatics Campus
(CVPR 2020)
(a): Schematic depiction of a qubit with a Bloch sphere. Spinup or |1〉 is located on the north pole, and spin down or |0〉 is located on the south pole. The state (|0〉+|1〉)/√2 with equal probability amplitudes to measure |1〉 and |0〉 values is geodetically equidistant to both poles. A point on the surface of the Bloch sphere corresponds to a valid pure state |φ〉 = α|0〉 + β|1〉.
(b): Schematic visualisation of adiabatic quantum annealing (AQA). At the beginning, all qubits are initialised in the state |+〉. After the annealing is finished, the qubit states are measured and returned. After the measurement, the states of variables are classical.
(c): Different 2D point sets aligned with our Quantum Approach (QA) for rigid point set registration.

Abstract

Modern adiabatic quantum computers (AQC) are already used to solve difficult combinatorial optimisation problems in various domains of science. Currently, only a few applications of AQC in computer vision have been demonstrated. We review AQC and derive a new algorithm for correspondence problems on point sets suitable for execution on AQC. Our algorithm has a subquadratic computational complexity of the state preparation. Examples of successful transformation estimation and point set alignment by simulated sampling are shown in the systematic experimental evaluation. Finally, we analyse the differences in the solutions and the corresponding energy values.

Downloads


Citation

BibTeX, 1 KB

@inProceedings{golyanik2020quantum, 
title={A Quantum Computational Approach to Correspondence Problems on Point Sets}, 
author={Vladislav Golyanik and Christian Theobalt}, 
booktitle={Computer Vision and Pattern Recognition (CVPR)}, 
year={2020} 
}
Experimental Evaluation on D-Wave 2000Q: 
 @inProceedings{golyanik2020quantum-supp, 
    title={A Quantum Computational Approach to Correspondence Problems on Point Sets  (Supplementary Material about the Experiments on D-Wave 2000Q)}, 
    author={Vladislav Golyanik and Christian Theobalt}, 
    booktitle={Computer Vision and Pattern  Recognition  (CVPR)}, 
    year={2020} 
}

Related Works on Quantum Computer Vision

[project page]   Adiabatic Quantum Graph Matching with Permutation Matrix Constraints (3DV 2020)
[project page]   Quantum Permutation Synchronization


Related Works on Gravitational Approaches for Point Set Alignment

Rigid Gravitational Approach with Second-Order ODE, CVPR 2016
Non-Rigid Gravitational Approach with Second-Order ODE, 3DV 2018
On Scale Resolution with Gravitational Approaches (Proof of Singularities), 3DV 2019
Accelerated Gravitational Point Set Alignment with Altered Physical Laws, ICCV 2019

Contact

For questions and clarifications please get in touch with:
Vladislav Golyanik golyanik@mpi-inf.mpg.de
This page is Zotero translator friendly. Page last updated Imprint. Data Protection.
  翻译：