Data Convergence — Quantum Computing — GROVER’S ALGORITHM

GROVER’S ALGORITHM : The Quantum Search Algorithm

The year 1996 lead to the emergence of one of the major algorithm proposed for quantum computing by a prominent researcher, Lov K Grover ,which was initially published in ACM STOC (1996).

Grover’s algorithm is a combinatorial search algorithm to find a solution to an arbitrary predicate. It is an efficient search algorithm for a huge database even when the search items are unstructured ie. an unstructured search. Grover’s algorithm uses qubits in superposition in parallel universes to make it’s computation.

What do we mean by an unstructured search? Let’s say we have a list 1 to N. It contains number of items and we are looking for particular item in list , be it V. A classical computing search algorithm would solve this in O(N) time , reason being it would search each element at a time to and move to next .The worst case being the item is the last item in the list. Whereas a Grover’s algorithm would solve the search in O(⎷N)time , which is a huge advantage when N would be very large .

For , N = 1 Million

Classical algorithm à 1 million steps

Grover’s algorithm à 1 thousand steps

We have an oracle function , a method to encode the list of items of function f , such that :

f(x)=0 à not required items x

f(v)=1 à required item v

The items are placed in superposition to this function ,and this function is encoded into a unitary matrix x , called oracle . We choose binary encoding of items , so that N=2n , to represent it in terms of qubits on quantum computer.

If x is an unrequired item, oracle does nothing to state .

However , when oracle is applied to basis state |v> , it maps the unitary matrix Uv|v> = -|v> ,

ie . Uv|x>=(-1)f(x)|x>

for , |x> à does nothing

for , |v> à Flips the state

Say for N= 2n states labelled by S1,S2,S3,………………SN represented as n bit strings. A unique state Sv ,that satisfy the condition C(SV) =1 , whereas for all other states S, C(S)=0. The next step is to initialize the states and repeat the operation of rotating the phase by radian for C(S)=1 and leave system unaltered for C(s)=0 ( a phase rotation transformation) . Each iteration increases the amplitude in desired state by (1/⎷N) , as a result of O(⎷N) repetition .

Hence , probability and amplitude of desired state reach O(1).

Implementation:

Step 1 : |S> = 1/(⎷N) ,This puts qubit in every possible input ie. in superposition state.

Step 2: Uf|x> =(-1)f(x) |x> , If oracle function equates to 1 then eigen value becomes -1, else 1.

This flips the amplitude of the item we are searching for .

Step 3: US =2 |S><S| -1 , This applies state change to qubits .

Increasing the expectation value and when we measure it , we have high chance of finding it.

Step 2 and 3 is repeated till amplitude reach close to 1.

Example for state |00>

Similarly, for state |10>

for state |01>

for state |11>

Like all quantum computer algorithms, Grover’s algorithm is probabilistic, in the sense that it gives the correct answer with high probability . The probability of failure can be decreased by repeating the algorithm.

Applications of Grover’s algorithms for NP complete problems provides quadratic speedup. Apart from being an efficient database search algorithm it’s used in various NP complete problems like graph colouring, maximum clique, satisfiability, travelling salesman, DNA sequencing , scheduling and many more. For further understanding of the applications link has been shared in the reference section.

Reference :

1) Grover, L. K. (1996). A fast quantum mechanical algorithm for database search. Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing — STOC ’96. doi:10.1145/237814.237866

2) Quantum Algorithm for Finding a Maximum Clique in an Undirected Graph https://jios.foi.hr/index.php/jios/article/view/624

3) https://qiskit.org/textbook/ch-applications/satisfiability-grover.html

4) A quantum heuristic algorithm for traveling salesman problem
arXiv:1004.4124 [quant-ph] https://arxiv.org/pdf/1004.4124.pdf

5) An algorithm for DNA read alignment on quantum accelerators arXiv:1909.05563v1 [quant-ph] 12 Sep 2019 https://arxiv.org/pdf/1909.05563.pdf