You are here

UCF Digital Collections ยป ETD Collection

Solving Constraint Satisfaction Problems with Matrix Product States

Download pdf | Full Screen View

Date Issued:
2017
Abstract/Description:
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.
Title: Solving Constraint Satisfaction Problems with Matrix Product States.
27 views
12 downloads
Name(s): Pelton, Sabine, Author
Mucciolo, Eduardo, Committee Chair
Ishigami, Masa, Committee Member
Leuenberger, Michael, Committee Member
University of Central Florida, Degree Grantor
Type of Resource: text
Date Issued: 2017
Publisher: University of Central Florida
Language(s): English
Abstract/Description: 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.
Identifier: CFE0006902 (IID), ucf:51713 (fedora)
Note(s): 2017-12-01
Ph.D.
Sciences, Physics
Doctoral
This record was generated from author submitted information.
Subject(s): tensor network states -- matrix product states -- quantum adiabatic annealing -- adiabatic quantum computation -- combinatorial optimization -- many-body algorithms -- computational physics
Persistent Link to This Record: http://purl.flvc.org/ucf/fd/CFE0006902
Restrictions on Access: public 2017-12-15
Host Institution: UCF

In Collections