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 studyof Computational Complexity. Properties of quantum systems such as superposi-tion, interference, and entanglement have the potential to make quantum computersfaster than any classical one. Shor algorithm solves integer factorization in poly-nomial time while it is only known exponential time classical algorithms. In thiscontext, it is important to have a deeper understanding of the unique quantumproperties and the role it plays in the computational complexity. This knowledgewould help to explain which properties are behind the quantum improvements. Oneproperty 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 importantto have deeper understating this property to elucidate when and how it can beexploited or suppressed.