Modern quantum annealers can find high-quality solutions to combinatorial optimisation objectives given as quadratic unconstrained binary optimisation (QUBO) problems. Unfortunately, obtaining suitable QUBO forms in computer vision remains challenging and currently requires problem-specific analytical derivations. Moreover, such explicit formulations impose tangible constraints on solution encodings. In stark contrast to prior work, this paper proposes to learn QUBO forms from data through gradient backpropagation instead of deriving them. As a result, the solution encodings can be chosen flexibly and compactly. Furthermore, our methodology is general and virtually independent of the specifics of the target problem type. We demonstrate the advantages of learnt QUBOs on the diverse problem types of graph matching, 2D point cloud alignment and 3D rotation estimation. Our results are competitive with the previous quantum state of the art while requiring much fewer logical and physical qubits, enabling our method to scale to larger problems.

Quantum Annealing

Quantum annealing is a metaheuristic method to solve discrete, combinatorial optimization problems. If the cost function contains high and narrow energy barriers it can search the energy landscape more efficiently than simulated annealing. We propose an iterative algorithm that uses a quantum annealer from D-Wave in each step. Our algorithm is used for quadratic assignment problems with permutation constraints, which appear frequently in shape matching problems.



BibTeX, 1 KB

@ARTICLE{Seelbach Benkner2023, 
       author = {{Seelbach Benkner}, Marcel and {Krahn}, Maximilian and {Tretschk}, Edith and {L{\"a}hner}, Zorah and {Moeller}, Michael and {Golyanik}, Vladislav}, 
        title = "{QuAnt: Quantum Annealing with Learnt Couplings}", 
      journal = "International Conference on Learning Representations (ICLR)", 
         year = 2023 


For questions, clarifications, please get in touch with:
Marcel Seelbach Benkner Marcel.Seelbach@uni-siegen.de
Maximilian Krahn mkrahn@mpi-inf.mpg.de
Edith Tretschk tretschk@mpi-inf.mpg.de
Zorah Lähner zorah.laehner@uni-siegen.de
Vladislav Golyanik golyanik@mpi-inf.mpg.de

This page is Zotero translator friendly. Page last updated Imprint. Data Protection.