Introduction
It is the algorithm which runs on the realistic model of quantum computation. Similar to the classical(non-quantum) computer algorithm, a quantum algorithm is also a step-by-step procedure for solving a problem where each steps can be performed on the quantum computer. All the classical computers algorithm can be performed on a quantum computer.
The problems that are undecided or unpredictable by a classical computer are still undecidable by the quantum computers but quantum algorithms makes problem solving faster. Best known quantum algorithms are Shor's algorithm for integer factoring and Grover's algorithm for searching an unstructured database or an unordered list.
Shor's Algorithm
It was invented in 1994 by the American mathematician Peter Shor.
It is used for discrete logarithm problem and integer factorization problem in polynomail time, whereas classical computers algorithm takes super-polynomail time. Shors algorithm helps to achieve polymail time with efficiency by Quantum Fourier transform. It makes use of reduction of factorization problem to order finding problem. Shor’s algorithm is very important for cryptography, as it can factor large numbers much faster than classical algorithms.
Algorithm
- Determine if 'n' is even, prime or a prime power. If so, exit.
- Pick a random integer x<n and calculate gcd(x,n). If this is not 1, then we have obtained a factor of n.
- Quantum algorithm
pick 'q' as the smallest power of 2 within n 2 ≤ q < 2n 2 .
Find period r of xa mod n.
Measurements gives us a variable 'c' which has the property c/q ≈ d/r where d ∈ N.
- Determine d, r via continued fraction expansion algorithm. d, r only determined if gcd(d, r) = 1 (reduced fraction).
- If r is odd, go back to 2. If "x r/2 ≡ −1 mod n" go back to 2. Otherwise the factors p,q = gcd(x r/2 ± 1, n).
Grover's Algorithm
Grover's algorithm is a quantum algorithm for searching an unstructured database or an unordered list. It finds with high probability the unique input to a black box function that produces a particular output value. It was invented by Lov Grover in 1996.
Algorithm
