Abstract

In the past decade, Matrix Product State (MPS) algorithms have emerged as an efficient method of modeling some many-body quantum spin systems. Since spin system Hamiltonians can be considered constraint satisfaction problems (CSPs), it follows that MPS should provide a versatile framework for studying a variety of general CSPs. In this thesis, we apply MPS to two types of CSP. First, use MPS to simulate adiabatic quantum computation (AQC), where the target Hamiltonians are instances of a fully connected, random Ising spin glass. Results of the simulations help shed light on why AQC fails for some optimization problems. We then present the novel application of a modified MPS algorithm to classical Boolean satisfiability problems, specifically k-SAT and max k-SAT. By construction, the algorithm also counts solutions to a given Boolean formula (\#-SAT). For easy satisfiable instances, the method is more expensive than other existing algorithms; however, for hard and unsatisfiable instances, the method succeeds in finding satisfying assignments where other algorithms fail to converge.

Notes

If this is your thesis or dissertation, and want to learn how to access it or for more information about readership statistics, contact us at STARS@ucf.edu

Graduation Date

2017

Semester

Fall

Advisor

Mucciolo, Eduardo

Degree

Doctor of Philosophy (Ph.D.)

College

College of Sciences

Department

Physics

Degree Program

Physics

Format

application/pdf

Identifier

CFE0006902

URL

http://purl.fcla.edu/fcla/etd/CFE0006902

Language

English

Release Date

December 2017

Length of Campus-only Access

None

Access Status

Doctoral Dissertation (Open Access)

Download

Included in

Physics Commons

Share

COinS