Please use this identifier to cite or link to this item:
|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||Citation:||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:
|SundaramA.pdf||1.72 MB||Adobe PDF|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.