Quantum algorithm

Updated: 04/26/2017 by Computer Hope

A quantum algorithm is a step-by-step procedure performed by a quantum computer. Although any algorithm can run on a quantum computer, a quantum algorithm benefits from the unique characteristics of qubits, such as quantum entanglement and quantum superposition.

An example of a quantum algorithm is Shor's algorithm, which can be used to find the prime factors of an integer. On a classical computer, this factorization process runs in NP (nondeterministic polynomial) time, which means that the harder the problem becomes, the exponentially longer it takes. However, on a quantum computer it is performed in polynomial time making the problem scale linearly rather than exponentially, so factoring a very large number does not become unfeasible. Most modern cryptographic ciphers are based on the assumption that factoring large polynomials is an NP time problem. Thus, very large numbers are not factorable given a reasonable amount of time and a reasonable number of resources. However, Shor's algorithm, performed on a quantum computer, could theoretically break any such encryption because the large numbers could be factored in polynomial time.

Algorithm, Encryption, Hardware terms, Quantum, Quantum computer, Qubit