Computational complexity: Difference between revisions

Revision as of 03:25, 6 April 2020

Revision as of 02:33, 14 April 2020

Line 59:

===Quantum computing===

A [[quantum computer]] is a computer whose model of computation is based on [[quantum mechanics]]. The [[Church–Turing thesis (complexity theory)|Church–Turing thesis]] applies to quantum computers; that is, every problem that can be solved by a quantum computer maycan also be also solved by a Turing machine. However, some problems may theoretically be solved with a much lower [[time complexity]] using a quantum computer rather than using a classical computer. This is, for the moment, purely theoretical, as no one knows how to build an efficient quantum computer.

[[Quantum complexity theory]] has been developed to study the [[complexity class]]es of problems solved using quantum computers. It is used in [[post-quantum cryptography]], which consists of designing [[cryptographic protocol]]s that are resistant to attacks by quantum computers.