A Quantum Computational Approach to Correspondence
Problems on Point Sets

(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} 
}  		   

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.