Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/136507
Title: ON CLASSICAL AND QUANTUM CONSTRAINT SATISFACTION PROBLEMS IN THE TRIAL AND ERROR MODEL
Authors: AARTHI MEENAKSHI SUNDARAM
Keywords: trial and error, quantum satisfiability, constraint satisfaction problems, monotone graph properties, Boolean satisfiability, computational complexity
Issue Date: 15-May-2017
Source: AARTHI MEENAKSHI SUNDARAM (2017-05-15). ON CLASSICAL AND QUANTUM CONSTRAINT SATISFACTION PROBLEMS IN THE TRIAL AND ERROR MODEL. ScholarBank@NUS Repository.
Abstract: This thesis studies quantum satisfiability (QSAT) and classical constraint satisfaction problems (CSP) in the trial and error model recently formalized by Bei, Chen and Zhang (STOC13). The principal component in this setting involves an oracle which accepts assignments from the domain of the CSP as trials and reveals either that the trial is a valid solution or some information about the error that caused the assignment to fail. We provide a systematic framework to analyze how the complexity of a CSP with unknown inputs changes with respect to the information revealed by the oracle. Additionally, two different modifications to this oracle are considered with the aim of determining the minimum amount of information required to solve 2SAT and find if a graph possesses some property. Finally, a new linear time algorithm for Quantum 2SAT is presented which improves on Bravyi’s algorithm (2006) with its quartic time dependence on input size.
URI: http://scholarbank.nus.edu.sg/handle/10635/136507
Appears in Collections:Ph.D Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
SundaramA.pdf1.72 MBAdobe PDF

OPEN

NoneView/Download

Page view(s)

30
checked on Jan 13, 2018

Download(s)

18
checked on Jan 13, 2018

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.