Quantum Optimization
(2020) FYSK02 20201Mathematical Physics
Department of Physics
- Abstract
- This thesis concerns the implementation of quantum algorithms on a computer vision problem called bundle adjustment.
Bundle adjustment can be simplified for illustration purposes by the following example. Two different cameras take a picture of the same object in different angles. Features of the pictures on the different cameras can be seen as points and, in a space sense, they are desired to be as close as possible to each other in a 3D space, because this minimizes the error on the 3D model in space. The bundle adjustment optimizes a cost function so that, distance between the points of the individual pictures can be minimized. The different quantum algorithms may be used to minimize the error between the points in the 3D space.
In... (More) - This thesis concerns the implementation of quantum algorithms on a computer vision problem called bundle adjustment.
Bundle adjustment can be simplified for illustration purposes by the following example. Two different cameras take a picture of the same object in different angles. Features of the pictures on the different cameras can be seen as points and, in a space sense, they are desired to be as close as possible to each other in a 3D space, because this minimizes the error on the 3D model in space. The bundle adjustment optimizes a cost function so that, distance between the points of the individual pictures can be minimized. The different quantum algorithms may be used to minimize the error between the points in the 3D space.
In order to understand the quantum algorithms one needs to understand the foundations of quantum computing. Quantum computers are fundamentally different compared to classical computers. Whereas a classical computer works with bits, which can be 0 or 1, a quantum computer is based on qubits, which are vectors $\ket{+}$ and $\ket{-}$ of a Hilbert space. The computations on qubits and between different qubits are performed via quantum gates.
A more precise picture of how bundle adjustment works and how gates are applied to form different quantum algorithms as well as different algorithms used in this thesis are given and explained in detail in section \ref{method1}.
The three quantum algorithms used in this paper are HHL, VQE and QAOA. The HHL algorithm is a quantum linear problem solver and is used to update the cost function. VQE and QAOA are quantum algorithms, which find the minimum eigenvalue and its corresponding eigenvector.
In the result section, we apply the VQE algorithm onto a linear problem with four points. Then we attempt to introduce VQE and HHL to the bundle adjustment, where computational difficulties and strategy problems arise. (Less) - Popular Abstract
- New technology is constantly developed. One of the most significant technologies, which changed the whole society, is the classical computers. Recently, a new type of computer has arisen. This type of computer is fundamentally different and is called "quantum computer". We try to simulate implementations of quantum algorithms on quantum computers to solve classical problems, such as the linear regression and the bundle adjustment problem. A comparison of the algorithms regarding the problems is also provided. Finally, the bundle adjustment problem could not be solved with quantum algorithms, due to lack of computational power and choice of algorithm.
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/student-papers/record/9024725
- author
- Bernecker, Luca LU
- supervisor
-
- Andrea Idini LU
- organization
- course
- FYSK02 20201
- year
- 2020
- type
- M2 - Bachelor Degree
- subject
- keywords
- Quantum, Optimization, HHL, VQE, Optimisation, Physics
- language
- English
- id
- 9024725
- date added to LUP
- 2020-07-13 15:25:43
- date last changed
- 2020-07-13 15:25:43
@misc{9024725,
abstract = {{This thesis concerns the implementation of quantum algorithms on a computer vision problem called bundle adjustment.
Bundle adjustment can be simplified for illustration purposes by the following example. Two different cameras take a picture of the same object in different angles. Features of the pictures on the different cameras can be seen as points and, in a space sense, they are desired to be as close as possible to each other in a 3D space, because this minimizes the error on the 3D model in space. The bundle adjustment optimizes a cost function so that, distance between the points of the individual pictures can be minimized. The different quantum algorithms may be used to minimize the error between the points in the 3D space.
In order to understand the quantum algorithms one needs to understand the foundations of quantum computing. Quantum computers are fundamentally different compared to classical computers. Whereas a classical computer works with bits, which can be 0 or 1, a quantum computer is based on qubits, which are vectors $\ket{+}$ and $\ket{-}$ of a Hilbert space. The computations on qubits and between different qubits are performed via quantum gates.
A more precise picture of how bundle adjustment works and how gates are applied to form different quantum algorithms as well as different algorithms used in this thesis are given and explained in detail in section \ref{method1}.
The three quantum algorithms used in this paper are HHL, VQE and QAOA. The HHL algorithm is a quantum linear problem solver and is used to update the cost function. VQE and QAOA are quantum algorithms, which find the minimum eigenvalue and its corresponding eigenvector.
In the result section, we apply the VQE algorithm onto a linear problem with four points. Then we attempt to introduce VQE and HHL to the bundle adjustment, where computational difficulties and strategy problems arise.}},
author = {{Bernecker, Luca}},
language = {{eng}},
note = {{Student Paper}},
title = {{Quantum Optimization}},
year = {{2020}},
}