Date of Award

8-2018

Degree Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Economics

Committee Chair

Kevin Mumford

Committee Co-Chair

Miguel Sarzosa

Committee Member 1

Jillian Carr

Committee Member 2

Victoria Prowse

Abstract

Quantum annealing (QA) uses the principles of quantum mechanics for solving unconstrained optimization problems. Since its initial proposal, there has been much interest in the search for practical problems for which QA has advantage over classical algorithms. Although it is believed that quantum computers cannot in general solve NP-complete problems effciently, there has been evidence suggesting that effects such as quantum tunneling can bring quantum speedup over classical computation for some problems in NP.

In this dissertation, we consider two problems that have both theoretical and practical importance. One is the Set Cover with Pairs problem. The other is the Factorization problem.

The Set Cover with Pairs (SCP) problem is a generalization of the Set Cover problem. It requires each element in a set to be covered by at least two objects instead of one as in the Set Cover problem. The SCP problem is believed to be not only NP-hard, but also hard to approximate. In this dissertation, we explicitly construct the Ising Hamiltonians whose ground states encode the solutions of SCP instances. The resulting Ising Hamiltonian has the appealing property that the control precision required for encoding an SCP instance scales only linearly with the number of objects in the covering set.

The Integer Factorization problem is of great interest in the quantum community because it is diffcult to solve using classical methods and its importance in cryptography. In this dissertation, we propose a general framework for solving factorization problems using quantum annealing, by mapping the framework to an Ising Hamiltonian. We develop several methods to consider the specifc requirements such as control precision, spin-spin connection in the current Ising machines. We test the methods on the latest D-Wave 2000Q machine.

Download

Share

COinS