Back to search

Central Florida

Solving Constraint Satisfaction Problems with Matrix Product States

Abstract

dc:description.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.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Pelton, Sabine
Contributors dc:contributor
  • Mucciolo, Eduardo

Subjects

dc:subject × 1

Rights

Language dc:language
English

Identifiers

dc:identifier.*
Identifier
CFE0006902

Chain of custody

source
Harvested from
Central Florida
Base URL
stars.library.ucf.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Pelton, Sabine. Solving Constraint Satisfaction Problems with Matrix Product States. https://stars.library.ucf.edu/etd/5712