Quantum Algorithms for Binary Problems with Applications to Image Processing

In this thesis, we investigate multiple approaches for constructing quantum algo-
rithms with applications to image processing: Hybrid, fully universal, annealing-
based, and based on quantum time evolution.
First, we develop a variational quantum algorithm for the Ising Hamiltonian
ground-state problem which block-encodes the Ising Hamiltonian in a unitary
operator acting on a parameterized quantum state, the parameters of which are
optimized in a way to solve the problem using an outer classical optimization
routine. Experimentally, the algorithm outperforms the quantum approximate
optimization algorithm (QAOA) and challenges dedicated D-Wave annealers in
returning approximate solutions.
Second, we propose an iterative, fully universal quantum algorithm which uses
quantum amplitude amplification and does not require the classical outer loop.
This fully universal method guarantees that, after an optimal number of itera-
tions, a ground state of the Ising Hamiltonian is measured with the highest prob-
ability compared to other states.
Turning to a specific application in image processing, we formulate the rigid
point set registration problem as a quadratic unconstrained binary optimization
(QUBO) problem suitable for quantum annealers. Here, we consider a contin-
uous yet constrained objective function, optimizing over rotation matrices from
the special orthogonal group – a Lie group. Moreover, we solve the orthogonality
constraint and propose instead to optimize over the Lie algebra. In an iterative
process, we construct and solve QUBO problems to adjust the rotation param-
eters. We successfully deploy our method on D-Wave quantum annealers and
demonstrate its viability on several 2D and 3D point sets, improving the state-of-
the-art quantum approach for this problem.
Finally, we investigate quantum time evolution for solving parametric non-convex
image registration problems. We consider the existing quantum Hamiltonian
descent (QHD) algorithm, which is derived from the quantum path integral of
dynamical systems and its relation to the continuous time limit of classical gra-
dient descent methods. We classically simulate the time evolution of the QHD
Hamiltonian for a non-convex rigid image registration problem and find that the
method can effectively find globally optimal solutions.