Optimizing Database Searching with Grover’s Algorithm
Suppose that there are four doors in front of you, and you’ve been told to find the room with the ‘winning’ object.
You might choose to go through each door individually to determine whether it belongs to the winning room. Even though it’s possible that door #1 is the desired solution and you’ll only need to make one attempt to locate it, it’s not definite. The worst-case scenario is that it’s the final door, in which you’ll need to make multiple efforts instead.
But what if there were 16 doors instead of 4, and the winning room was door 16? You would go through every single door before it to find your winning solution.
That entire process can get extremely time-consuming as the number of options increases exponentially.
The same thing applies to data sets — where the number of potential options can be much higher than 16.
Considering that we are currently living in this era of big data, the ability to quickly and efficiently search through enormous amounts of data is essential.
A Classical Approach 📜
What sucks is that our traditional computers use the same approach of evaluating each potential option sequentially until they identify the desired answer.
The code for a conventional computer’s technique resembles something like this:
# creating a random list
my_list=[1,3,5,2,4,9,5,8,0,7,6]
# define an oracle and tell it the winner
def the_oracle(my_input):
winner=7
if my_input is winner:
response = True
else:
response = False
return response
# figure out how many queries were made to find the winner
for index, trial_number in enumerate(my_list):
if the_oracle(trial_number) is True:
print ('Winner found at index %i' %index)
print ('%i calls to the Oracle used'%(index+1))
breakIf this looks like a bunch of letters and you’re unable to make out what’s happening, don’t worry.
The process goes as follows:
- The computer is given the list of numbers (in this case, these are our potential options)
- The oracle (an unexposed operation that feeds data to another algorithm) is informed of what number is the winner and is told to output the ‘True’ response when the input is the desired option
- When the winning number is discovered, the computer can also tell you how queries (a more technical term to describe the act of requesting for information) were made to find the answer
As seen above, the amount of queries made by the classical computer was the number of options… in this case, it was only 10, But, whether the number of options was 256, or 50,000 — it would take that many queries to find the solution, and so on.
Due to the complexity of this problem and the ineffectiveness of this approach, O(N) refers to the amount of time that it’ll take to determine the answer — where O refers to ‘on the order of’ and N refers to the length of the list.
The longer the list, the more time it’ll take — and given that companies typically have millions of data sets to sift through, I’m sure the thought of this doesn’t sound too appealing.
Lov Grover’s Quantum Approach 🔑
In 1996, Lov Grover — a computer scientist — showed us that there is a quantum algorithm that solves this problem with O(√N) queries.
This algorithm is now referred to as Grover’s Algorithm — the key to optimizing unstructured search problems.
Grover’s search algorithm is one of the first and most prominent examples that demonstrates quantum advantage.
The difference in the number of queries may not seem significant — but as the value for N increases, it becomes more visible.
Anyways, he proposed leveraging this trick known as amplitude amplification. Amplitude amplification is a procedure that raises the probability amplitude of the value being searched while simultaneously lowering the other probability amplitudes. This is the key to helping quantum computers quadratically accelerate the process of solving the problem.
Time to Code 👩🏻💻
Note: When I was diving deeper into understanding the fundamentals of Grover’s Algorithm, this was too much to take in at once. So stay with me and let’s take it step-by-step as we learn more about the quantum mechanics, math and code behind enhancing our searching abilities. If you’d prefer to listen to an explanation of the code, I’ve also created a YouTube video that acts as a walkthrough of the code… if not, continue reading!
The process of Grover’s algorithm can be broken done into 3 steps:
- Initializing the quantum circuit, where it starts off in uniform superposition (represented by a vector; |s⟩)
- Applying an oracle reflection, where the phase of the state |w⟩ is reflected
- Reversing the reflection, so that |w⟩ has the greatest amplitude and largest probability of getting chosen as the ‘winning’ answer
Step 1: Initialize the Circuit
In this particular example, we’ll be figuring out the correct answer between 2 qubits — as defined in the code below.
Since there’s 2 qubits, there’s 4 potential states (which means that N = 4):
The winning state we’ll be searching for today is |11⟩.
Once that’s determined, we’ll start off by coding the initialization of the quantum circuit in uniform superposition — a special state that we’ll consider.
# prepare a quantum circuit with two qubits
num_qubits = 2
grover_circuit = QuantumCircuit(num_qubits)
# initialize the state
def initialize_s(qc,qubits):
for q in qubits:
qc.h(q)
return qc
grover_circuit = initialize_s(grover_circuit,[0,1])
grover_circuit.draw()
If we were to look at this on a graph, it would look like this:
Step 2: Oracle Reflection
Now, let’s take a step back and remember the process from the classical approach. We told the oracle what our winning number was, so the same rule applies here — we need a way to ‘mark’ the winning state.
# apply controlled-Z gates as an oracle
grover_circuit.cz(0,1)
grover_circuit.draw()
We do so by applying a Controlled-Z gate (as the oracle reflection) after initialization, which applies a negative phase to the winning state. It’s important to note that this oracle is specific to this example of 2 qubits.
But, how does this work…?
Basically, the way that the CZ gate works is that oracle will flip the sign of the winning state so that it is differentiated from the rest.
To make this easier, think of the oracle like a black box. The option that is being evaluated goes through this black box to be ‘tested’ if it is the winning option.
Mathematically, we can represent the way this works through functions; if the input is equal to the winning number, f(x) = 1, otherwise, f(x) = 0.
The equation that represents the oracle’s transformations on the input is:
So, if |x⟩ = |w⟩, the output from the black box will be the negative value of winning state, which means the amplitude in front of |w⟩ is negative as well. All other states remain the same.
After the negative phase is applied, the graph looks like this:
Although, as a result of applying the Controlled-Z gate to winning state, the average amplitude has been lowered — as indicated by the dashed line in the graph above.
Step 3: Diffusion Operator
The final step is to reverse the previous transformation on |w⟩ (after it’s been marked) so we can increase its amplitude.
We can do this by applying a combination of Hadamard, Pauli-Z, and Controlled-Z gates on the qubits, as seen in the code below:
# apply diffusion operator and measure the qubits
grover_circuit.h([0,1])
grover_circuit.z([0,1])
grover_circuit.cz(0,1)
grover_circuit.h([0,1])
grover_circuit.measure_all()
grover_circuit.draw()
The mathematical expression that represents this reflection is as follows:
Essentially, all this operation does is reduce the probabilities of the non-winning states and increases the probability for the winning state.
It’ll make more sense when you see it graphically — the transformation looks like:
Here, you can see that this transformation allows for the winning state’s amplitude to boost itself to roughly 3 times its original value, all while the average amplitude remains significantly lower.
To maximize the accuracy, the quantum computer will repeat steps 2 and 3 several times — but don’t worry, it’s still much faster than a classical computer as it’ll perform these operations around √N times.
Let’s Run the Algorithm on a Real Quantum Computer…👾
Now comes the best part — being able to run the Grover’s algorithm we built on an actual quantum computer. IBM’s Qiskit will go ahead and find the least busy backend device where it’ll let us know whether or not the job status has been successful or not…
# run the circuit on a real quantum computer
provider = IBMQ.load_account()
provider = IBMQ.get_provider("ibm-q")
device = least_busy(provider.backends(filters=lambda x: int(x.configuration().n_qubits) >= 3 and
not x.configuration().simulator and x.status().operational==True))
print(device)
transpiled_grover_circuit = transpile(grover_circuit, device, optimization_level=3)
job = device.run(transpiled_grover_circuit)
job_monitor(job, interval=2)…this one was a success! But, to wrap things off, we have to get the results from our computation to really determine how successful we were.
# get results from the computation
results = job.result()
answer = results.get_counts(grover_circuit)
plot_histogram(answer)
We can see that 91% of the time of running this algorithm on a real quantum computer results in the correct output, the state of |11⟩.
Even though 9% of outputs are computation errors, the results above prove a high degree of effectiveness and ultimately prove the concept of quantum advantage for this particular problem.
Closing Thoughts 💭
When looking into practical applications of Grover’s search algorithm, I came across its use in the Travelling Salesman Problem — I’ve written an article about Quantum Computing’s role in improving the supply chain & route logistics, check it out here.
Overall, in the quantum computing world, this algorithm is extremely valuable and holds great significance as it proves one of the most talked-about QC applications, searching through unstructured data. Its use of quantum properties speed up the execution time. When fully developed, at an even higher accuracy rate, the impact it’ll have on various industries will be outstanding to see.
Hey, I’m Priyal, a 16-year-old driven to impact the world using emerging technologies. If you enjoyed my article or learned something new, feel free to subscribe to my monthly newsletter to keep up with my progress in quantum computing exploration and an insight into everything I’ve been up to. You can also connect with me on LinkedIn and follow my Medium for more content! Thank you so much for reading.
