Just as were classical computers in the beginning of development large and cumbersome devices, in which errors in calculation could occur, somehow in this phase of development are now quantum computers. In this thesis, I will present three leading companies in quantum computing, which are D-Wave, Google and IBM. These quantum computers are not intended for general use, they specialize in three things, solving optimization problems, simulating molecules and generating discrete distributions. In the thesis, I will focus on solving optimization problem called maximum cut problem with a quantum computer. This problem belongs to the class of NP-complete problems and is practically unsolvable for larger instances with a classical computer. Here comes in handy quantum mechanics, which says that a qubit can be in multiple states at once, we can exploit this property for computing optimization problems that we can express in a quantum computer. If we can express the problem in the form of the energy of the Hamiltonian function, then we can also write it in a quantum computer, and it can provides us with a meaningful solution. One of the optimization problems that we can express with the energy of the Hamiltonian function is the problem of quadratic unconstrained binary optimization, and this can be shown as an equivalent problem of the maximum cut problem. In the thesis, I will show that we can express any maximum cut problem as an quadratic unconstrained binary optimization problem, then, by translating the maximum cut problem into an quadratic unconstrained binary optimization problem, I will try to solve the maximum cut problem for larger instances of graphs ($250 \le n$) with the help of D-Wave's quantum computer. Then, I will also look at the efficiency of solving maximum cut problem of the other two quantum computers (Google and IBM), which do not allow inputs as large as D-Wave, and make a comparison of cuts between all computers with the aim of seeing which one is most suitable for finding the maximum cut.
|
