Quantum Computer Vision


Imperial College London        Max Planck Institute for Informatics, SIC


Quantum computers (QCs) differ from classical computers in that they leverage quantum mechanical effects to perform computations. Their primary advantage is that they can find (probabilistically optimal) solutions to some computational problems (including combinatorial ones) orders of magnitude faster than what is possible on classical machines. Most of the problems QCs excel on frequently occur in multitude of computer vision applications. Thus, QCs have a large, perhaps unprecedented potential in computer vision to challenge scenarios where existing methods would provide only approximate solutions or would not be able to solve problems in reasonable time at all. After being a prerogative of physics laboratories for decades, functioning circuit-based quantum computers and quantum annealers that can be used to solve real-world problems can be nowadays accessed remotely for research purposes. To fully leverage such great potential, specialised algorithms have to be designed for QCs, and these algorithms have to be formulated in representations/forms consumable by modern QCs. We therefore introduce quantum computer vision as a computer vision paradigm enhanced by quantum compute power and focus on methods that can run and be evaluated on real quantum hardware.

We present a hybrid classical-quantum framework based on the Frank-Wolfe algorithm, Q-FW, for solving quadratic, linearly-constrained, binary optimization problems on quantum annealers (QA). The computational premise of quantum computers has cultivated the re-design of various existing vision problems into quantum-friendly forms. Experimental QA realizations can solve a particular non-convex problem known as the quadratic unconstrained binary optimization (QUBO). Yet a naive-QUBO cannot take into account the restrictions on the parameters. To introduce additional structure in the parameter space, researchers have crafted ad-hoc solutions incorporating (linear) constraints in the form of regularizers. However, this comes at the expense of a hyper-parameter, balancing the impact of regularization. To date, a true constrained solver of quadratic binary optimization (QBO) problems has lacked. Q-FW first reformulates constrained-QBO as a copositive program (CP), then employs Frank-Wolfe iterations to solve CP while satisfying linear (in)equality constraints. This procedure unrolls the original constrained-QBO into a set of unconstrained QUBOs all of which are solved, in a sequel, on a QA. We use D-Wave Advantage QA to conduct synthetic and real experiments on two important computer vision problems, graph matching and permutation synchronization, which demonstrate that our approach is effective in alleviating the need for an explicit regularization coefficient.




Citation

@inproceedings{yurtsever2022ECCV,
title={Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary Optimization},
author={Yurtsever, Alp and Birdal, Tolga and Golyanik, Vladislav},
journal={Proceedings of the European Conference on Computer Vision (ECCV),},
year={2022}
}


We present QuantumSync, the first quantum algorithm for solving a synchronization problem in the context of computer vision. In particular, we focus on permutation synchronization which involves solving a non-convex optimization problem in discrete variables. We start by formulating synchronization into a quadratic unconstrained binary optimization problem (QUBO). While such formulation respects the binary nature of the problem, ensuring that the result is a set of permutations requires extra care. Hence, we: (i) show how to insert permutation constraints into a QUBO problem and (ii) solve the constrained QUBO problem on the current generation of the adiabatic quantum computers D-Wave. Thanks to the quantum annealing, we guarantee global optimality with high probability while sampling the energy landscape to yield confidence estimates. Our proof-of-concepts realization on the adiabatic D-Wave computer demonstrates that quantum machines offer a promising way to solve the prevalent yet difficult synchronization problems.


Citation

@inproceedings{birdal2021cvpr,
title={Quantum Permutation Synchronization},
author={Birdal, Tolga and Golyanik, Vladislav and Theobalt, Christian and Guibas, Leonidas},
journal={Proceedings of IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)},
year={2021}
}

Funding

The work was supported by the ERC Grant 4DReply (770784), a Vannevar Bush Faculty fellowship, a grant from the Stanford-Ford Alliance and gifts from Amazon AWS and Snap, Inc.

Interested in Collaborating with Us?

We would like this project to evolve towards a repository of methods for handling challenging (3D) computer vision problems using Quantum computers. Therefore, we look for contributors and collaborators with great coding and mathematical skills as well as good knowledge in 3D vision, machine learning and quantum computation. If you are interested please send an e-mail to Tolga.