Search button


Date Range:

From: To:

View all

  • Graduate Student Center Graduate Student Center
  • General Public Presentations General Public Presentations
  • Thesis/Dissertation Seminars Thesis/Dissertation Seminars
  • Arts and Humanities Seminars Arts and Humanities Seminars
  • Education Seminars Education Seminars
  • Health Professions Seminars Health Professions Seminars
  • Professional/Business Seminars Professional/Business Seminars
  • Social Sciences Seminars Social Sciences Seminars
  • STEM* Seminars STEM* Seminars
  • Social Events Social Events
  • Student and Professional Development Student and Professional Development
  • Informational Events Informational Events
  • Important Dates Important Dates

*STEM: Science, Technology, Engineering, and Mathematics

International Community

Events Calendar   

Back to Summary

Thesis/Dissertation Seminars

Dissertation Defense: Solving Constraint Satisfaction Problems with Matrix Product States

PSB 160
August 17, 2017 @ 10:00 AM - 12:00 PM

Announcing the Final Examination of Sabine Pelton for the Degree of Doctor of Philosophy in Physics

In the past decade, Matrix Product State (MPS) algorithms have emerged as an e_cient 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, we 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 modi_ed MPS algorithm to classical Boolean satis_ability problems, speci_cally k-SAT and max k-SAT. By construction, the algorithm also counts solutions to a given Boolean formula (#-SAT). For easy satis_able instances, the method is more expensive than other existing algorithms; however, for hard and unsatis_able instances, the method succeeds with subexponential scaling where other algorithms fail to converge.

Committee in Charge: Eduardo Mucciolo (Chair), Aniket Bhattacharya, Richard Klemm, Pawel Wocjan


The University of Central Florida is accredited by the Southern Association of Colleges and Schools Commission on Colleges (SACSCOC) to award degrees at the associate, baccalaureate, master’s, specialist, and doctoral levels. Contact the Commission on Colleges at 1866 Southern Lane, Decatur, Georgia 30033-4097 or call (404) 679-4500 for questions about the accreditation of the University of Central Florida.

Please note the commission's expectation that contact occur only if there is evidence to support significant non-compliance with a requirement or standard. For other information about UCF’s SACSCOC accreditation, please contact the university's SACSCOC liaison in UCF's Office of Academic Affairs.

| © 2015 University of Central Florida - College of Graduate Studies