In summers of 2012, I got the opportunity to do a research project in Quantum Computing under the supervision of Prof. Anil Kumar. Quantum Computing has gained a lot of attention lately because certain quantum algorithms like Grover’s search algorithm and Shor’s factorization algorithm can be performed faster than their classical counterpart.
Luv K. Grover found an elegant way to search data from an unstructured database. So what do we mean by the term unstructured? Basically a database can be stored in a certain way which can perform the searching operation faster. This “certain way” is called structured.
For example consider a simple database consisting of numbers 8, 1, 4, 7, 3 and 6 (stored in hard disk cells). Now I want to know if number 7 is there or not. So lets start search for number 7. The search algorithm to perform the operation is simple
- Get the input address of the cell (passed as argument by user at beginning of execution).
- Obtain the number residing in cell.
- Compare the obtained number with the given number.
- If comparison results to true then exit and return true, else check if next cell exist (check if we are at the end).
- If next cell exists, then goto step 1 and pass the address of next cell, else exit and return false.
Now 7 could have been at first place or at the last place in the database. In worst case scenario, the total number of iterations required will be 6. Also, if the required number is not in database, one would require 6 iteration to confirm that it is not. We say that the complexity of this algorithm is (number of elements in database) with respect to time. More iterations will certainly need more time.
Now let us arrange this database in “certain way”, say ascending order. Then I will be having 1, 3, 4, 6, 7 and 8. Let’s put the information “ascending order” to use and consider the following algorithm
- Obtain the range (first and last number (of database) for beginning of algorithm).
- Find mid number. (in case of even number of numbers, take a convention, say take greater number)
- Compare the mid number with the number to be found.
- If mid value is greater then number, then define range as first number of database and the number just before mid number and if it doesn’t exist return false. If mid value is smaller then number, then define range as last number of database and the number just after mid number and if it doesn’t exist return false. If mid value is equal to the number then return true.
- Goto step 1 and pass the range.
Here, in worst case scenario, the total number of iterations will be after which the algorithm will come out returning false. This is called binary search algorithm. Of course it is faster, but here the database was already ordered (which adds some complexity in greater picture). There are some data structures in computer science like binary trees, which cut down the complexity and perform faster search.
The Grover’s algorithm has complexity of the order and on unstructured database. This is the reason why there is so much excitement in this field. The basic difference (which I am able to recognize) is that unlike classical mechanics, quantum mechanics allows the existence of superposition of qubits and their simultaneous manipulation which speed up the computation.
In my project I designed quantum circuit and NMR pulse sequence to implement Grover’s search algorithm on 3 qubit unstructured database.
Now let me describe my experience and what I actually learnt these summers. I opted for this particular research activity because I wanted to have an exposure to quantum mechanics and it’s intimidating notions like superposition, probabilistic outcomes and, of course, the uncertainty principle.
The dynamics of nuclear spin qubits, their evolution in time by suitable hamiltonians, the precession of spins and the system of more than one spin with couplings, were good examples to get acquainted with quantum mechanical phenomenons. Notions like linear superposition and uncertainty principle were no longer intimidating. Then NMR readouts in agreement with theoretical calculations provided the required confidence in Quantum
Further I studied the way of doing computation from excitation/de-excitation of spin, the implementation of quantum algorithms through sequence of hamiltonian and art of designing NMR pulse sequence to realize quantum circuits. Not only I started feeling comfortable with quantum mechanics, I started experiencing the impact of it in our length scale: how Pauli’s exclusion principle keeps matter from collapsing, the appearance of magnetism due to the collective effort of spins.
Fun with quantum computers.