Quantum algorithm

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 find the prime factors of an integer. On a classical computer, this factorization process runs in NP (nondeterministic polynomial) time, meaning 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 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, large numbers are not factorable given the time and 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, NP, Quantum, Quantum computer, Qubit