PIRSA:17030046

Video URL

https://pirsa.org/17030046

Quantum Computation and the Foundations of Computational Complexity Theory

Cuffaro, M. (2017). Quantum Computation and the Foundations of Computational Complexity Theory. Perimeter Institute for Theoretical Physics. https://pirsa.org/17030046

Cuffaro, Michael. Quantum Computation and the Foundations of Computational Complexity Theory. Perimeter Institute for Theoretical Physics, Mar. 28, 2017, https://pirsa.org/17030046 

          @misc{ scivideos_PIRSA:17030046,
            doi = {10.48660/17030046},
            url = {https://pirsa.org/17030046},
            author = {Cuffaro, Michael},
            keywords = {Quantum Foundations},
            language = {en},
            title = {Quantum Computation and the Foundations of Computational Complexity Theory},
            publisher = {Perimeter Institute for Theoretical Physics},
            year = {2017},
            month = {mar},
            note = {PIRSA:17030046 see, \url{https://scivideos.org/index.php/pirsa/17030046}}
          }

Michael Cuffaro Western University

Talk numberPIRSA:17030046
DOI10.48660/17030046
Source RepositoryPIRSA
Collection
Talk Type Scientific Series
Subject

Abstract

Computational complexity theory is a branch of computer science dedicated to classifying computational problems in terms of their difficulty. While computability theory tells us what we can compute in principle, complexity theory informs us regarding what is feasible. In this chapter I argue that the science of quantum computing illuminates the foundations of complexity theory by emphasising that its fundamental concepts are not model-independent. However this does not, as some have suggested, force us to radically revise the foundations of the theory. For model-independence never has been essential to those foundations. The fundamental aim of complexity theory is to describe what is achievable in practice under various models of computation for our various practical purposes. Reflecting on quantum computing illuminates complexity theory by reminding us of this, too often under-emphasised, fact.