What I learned in my quantum computing experiment

You’ve heard the buzz about quantum computers outdoing their classical counterparts in computational speed. For example, Lov Grover, a computer scientist at Bell Labs, designed a quantum search algorithm called Grover’s Algorithm that achieves a quadratic increase in speed in database search. In other words, a process that would take 31 years to complete on a classical computer can be completed by a quantum computer in approximately 9 hours.

“Wow! How is that possible?” you may ask. I had the same question and was excited to explore this topic.

Searching a billion

Let’s say you are given a huge list of phone numbers that are not in order but listed in some haphazard way.  Your task is to find out whether a particular number is in the list.

Isn’t the solution simple?  You start with the first number and check if it matches the one you need. If it matches, voilà — you are done! If it doesn’t match, you move on to the next number, and the next, until a match is found or you reach the end of the list.

The problem with this straightforward search algorithm is that it is highly expensive (both in time and computing power) when the phone number list is huge. Try searching a list of one billion phone numbers!  For N entries in the list (here N=1,000,000,000), the complexity of this linear search algorithm is theta times N or O(N).

Simultaneous testing

Grover’s algorithm, on the other hand, makes use of quantum superposition. Imagine checking all the list entries at the same time. It can be mathematically proved that after searching just a fraction of the entries, if the number is found, then we have our desired result. If the number is not found, we can conclude that it is not in the list (i.e., we will get some other random value as the output).  This is much better, as the complexity now becomes theta times the square root of N or O(√N). We have been able to reduce the number of searches significantly.

Remember our hypothetical search of one billion entries? The square root of 1,000,000,000 is a mere 31,623.  As such, there is a quadratic speed-up in finding the result. That’s a lot!

How it works

What Grover’s Algorithm proposes is that you simultaneously test every input value to see which one is possibly correct (i.e, present in the list). Using quantum superposition, you get qubits in a state that represents all possible inputs. Then run that superposition of states through some function (called an “Oracle” function) to get each input together with its associated output. Using quantum transformations, you can make the state with the desired output value more likely than the others. Apply that transformation a calculated number of times, and you can get to a state where it’s very likely that a measurement will give you the final output.

I am hooked on quantum computing and continuing my experiments with it!

Check out my implementation of Grover’s Algorithm here: quant-algos

I used IBM’s QISKIT APIs for implementing quantum programs, located here: https://github.com/QISKit/qiskit-tutorial.git



Vimarsh Sathia is a summer intern working on quantum computing at DXC Labs in DXC Technology’s Bangalore location. Vimarsh is an upcoming freshman at IIT Madras, majoring in computer science and engineering. @vimarsh_sathia

Trackbacks

  1. […] my final report, I decided to present my viewpoint of quantum computing, and a demonstration of Grover’s Algorithm. Initially, I was nervous, but as time went by, I grew more confident due to the support meted out […]

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: