Quantum computational complexity and entanglement

• Grant number: 14/06467-0
• Support Opportunities: Scholarships abroad - Research Internship - Master's degree
• Start date: June 01, 2014
• End date: November 30, 2014
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Arnaldo Vieira Moura
• Grantee: Fernando Granha Jeronimo
• Supervisor: Thomas Vidick
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
• Institution abroad: California Institute of Technology, United States
• Associated to the scholarship: 13/20661-1 - Quantum Computing: Automaton, Games and Complexity, BP.MS

Abstract

Quantum Computing offers a new theoretical computational model to the study of Computational Complexity. Properties of quantum systems such as superposi-tion, interference, and entanglement have the potential to make quantum computers faster than any classical one. Shor algorithm solves integer factorization in poly-nomial time while it is only known exponential time classical algorithms. In this context, it is important to have a deeper understanding of the unique quantum properties and the role it plays in the computational complexity. This knowledge would help to explain which properties are behind the quantum improvements. One property that deserves special attention is entanglement: it can be a desired feature, as well as, a bug according to the circumstances. Therefore, it is very important to have deeper understating this property to elucidate when and how it can be exploited or suppressed. (AU)