The main issue in these, and most other computational problems, is combinatorial explosion: the exponential number of potential solutions that the algorithm must choose between. Indeed, algorithms for factoring large numbers have been studied over the centuries by mathematicians and very intensely over the last few decades by computer scientists. 2 These quantum algorithms generated serious concern in the security community, since the classical hardness of these two problems lie at the core of the public key “cryptosystems” that protect the vast majority of society’s digital data. The extended Church-Turing thesis is sometimes referred to as “the feasibility thesis” or the “computational complexity-theoretic Church-Turing thesis.”Īny developed for a classical computer. Deutsch, 1985, Quantum theory, the Church-Turing Principle and the universal quantum computer, Proceedings of the Royal Society of London A 400(1818):97-117. 1 The practical potential of quantum computers was illustrated soon thereafter when Peter Shor created quantum algorithms for factoring large numbers and computing discrete logarithms that were exponentially faster thanġ Note that quantum computers do not violate the original Church-Turing thesis, which defines the limits of what it is possible to compute at all (independent of time required to perform the computation). The discovery that quantum computers violate the extended Church-Turing thesis -by solving certain computational tasks with exponentially fewer steps than the best classical algorithm for the same task-shook up the foundations of computer science, and opened the possibility of an entirely new way of solving computational problems quickly.

This basic principle, called the extended Church-Turing thesis, implies that to solve a computational problem faster, one may (1) reduce the time to implement a single step, (2) perform many steps in parallel, or (3) reduce the total number of steps to completion via the design of a clever algorithm. A bedrock of the field of algorithms lies in the principle that the total number of computational steps required to solve a problem is (roughly) independent of the underlying design of the computer-remarkably, to a first approximation what is designated a single step of computation is a matter of convenience and does not change the total time to solution.

Tree quantum error correction