Computational complexity and quantum computing

• Grant number: 12/22478-7
• Support Opportunities: Scholarships abroad - Research Internship - Master's degree
• Start date: April 13, 2013
• End date: October 12, 2013
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Arnaldo Vieira Moura
• Grantee: Alex Bredariol Grilo
• Supervisor: Iordanis Kerenidis
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
• Institution abroad: Université Paris Diderot - Paris 7, France
• Associated to the scholarship: 12/06648-0 - Quantum Computing and Theoretical Computer Science, BP.MS

Abstract

Quantum Computation became a prominent area when it was proposed a quantum algorithm that factors integer number in polynomial time, problem for which we only know exponential algorithms in the classical model. Since then, the topic has developed and it has presented important results in different areas of Computer Science. In the study of Computational Complexity, it is not different, and the quantum computational model has also contributed to numerous advances. The objective of this research project is to study the recent results of the influence of Quantum Computation in Computational Complexity, complementing the work in progress during the Master's regular project. We intend to address topics related to complexity classes introduced by the new model, comparing them with the classical ones. It is also planned to study results in classical Theory of Complexity using techniques inspired in the quantum computational model. (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)

GRILO, A. B.; MOURA, A., V. ON FINITE AUTOMATA WITH QUANTUM AND CLASSICAL STATES. SIBERIAN ELECTRONIC MATHEMATICAL REPORTS-SIBIRSKIE ELEKTRONNYE MATEMATICHESKIE IZVESTIYA, v. 10, p. 13-pg., 2013-01-01. (12/22478-7, 12/06648-0)