Editing Quantum computing (section)

=== Computability<span class="anchor" id="Computability theory"></span> ===
{{Further|Computability theory}}

Any [[computational problem]] solvable by a classical computer is also solvable by a quantum computer.{{sfn|Nielsen|Chuang|2010|p=29}} Intuitively, this is because it is believed that all physical phenomena, including the operation of classical computers, can be described using [[quantum mechanics]], which underlies the operation of quantum computers.

Conversely, any problem solvable by a quantum computer is also solvable by a classical computer. It is possible to simulate both quantum and classical computers manually with just some paper and a pen, if given enough time. More formally, any quantum computer can be simulated by a [[Turing machine]]. In other words, quantum computers provide no additional power over classical computers in terms of [[computability]]. This means that quantum computers cannot solve [[undecidable problem]]s like the [[halting problem]], and the existence of quantum computers does not disprove the [[Church–Turing thesis]].{{sfn|Nielsen|Chuang|2010|p=126}}