Quantum algorithm: Difference between revisions

Revision as of 14:56, 10 December 2015

Revision as of 14:57, 10 December 2015

Line 14:

| class = quant-ph

| eprint = 0808.0369

}}</ref> A classical (or non-quantum) algorithm is a finite sequence of instructions, or a step-by-step procedure for solving a problem, where each step or instruction can be performed on a classical [[computer]]. Similarly, a quantum algorithm is a step-by-step procedure, where each of the steps can be performed on a [[quantum computer]]. Although all classical algorithms can also be performed on a quantum computer, {{Citation needed}}, the term quantum algorithm is usually used for those algorithms which seem inherently quantum, or use some essential feature of quantum computation such as [[quantum superposition]] or [[quantum entanglement]].

All problems which can be solved on a quantum computer can be solved on a classical computer. In particular, problemsProblems which are [[Undecidable problem|undecidable]] using classical computers remain undecidable using quantum computers. What makes quantum algorithms interesting is that they might be able to solve some problems faster than classical algorithms.

The most well known algorithms are [[Shor's algorithm]] for factoring, and [[Grover's algorithm]] for searching an unstructured database or an unordered list. Shor's algorithms runs exponentially faster than the best known classical algorithm for factoring, the [[general number field sieve]]. Grover's algorithm runs quadratically faster than the best possible classical algorithm for the same task.