Computational complexity: Difference between revisions

Revision as of 22:32, 25 March 2020

Revision as of 01:19, 26 March 2020

Line 61:

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 may be also solved by a Turing machine. However, some problems may theoretically be solved with a much lower complexity using a quantum computer 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 forto studyingstudy computationalthe [[complexity class]]es of problems solved using quantum computingcomputers. It is used in [[post-quantum cryptography]], which consists of designing [[cryptographic protocol]]s that willare resistresistant to attacks withby quantum computers, when such computers will really exist.

==Problem complexity (lower bounds)==