Logical aspects of the quantum satisfiability problem

• Grant number: 11/07781-2
• Support Opportunities: Scholarships in Brazil - Post-Doctoral
• Start date: August 01, 2011
• End date: June 30, 2012
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Marcelo Finger
• Grantee: Anderson Beraldo de Araújo
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
• Associated research grant: 08/03995-5 - Logprob: probabilistic logic --- foundations and computational applications, AP.TEM

Abstract

In these days one of the main themes of research in theoretical computer science is quantum computing. In that context, the quantum satisfiability problem (QSAT) shows important elements of the quantum computational complexity, which are related to the probabilistic satisfiability problem (PSAT). The general aim of the present project is to investigate the logical aspects of QSAT, contrasting them with the logical characteristics of PSAT. More concretely, this research has two specific aims: (1) to provide a version of QSAT through a logical system adequate to the peculiarities of quantum computing and (2) to evaluate the differences between 2-QSAT and 2-PSAT, analyzing their respective logical-probabilistic properties. (AU)

Scientific publications

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

DE ARAUJO, ANDERSON; FINGER, MARCELO. Classical and quantum satisfiability. ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE, v. N/A, n. 81, p. 6-pg., 2012-01-01. (10/51038-0, 08/03995-5, 11/07781-2)