Breaking secrets with quantum computers!
Artificial Intelligence, molecular modelling, cryptography, weather forecasting, and particle physics- all of these different fields have on thing in common: Quantum computers can incredibly enhance all of them and impact everything we know.
I have heard so much about Quantum computers solving problems that we never could have even with the world’s fastest supercomputer. With so much talk about quantum supremacy, I’ve been super curious of how exactly quantum computers might make a difference, because of which I thought I could replicate an algorithm to check it out by myself.
The Bernstein Vazirani algorithm is one of many examples where a quantum computer has outperformed a classical computer. So I decided to use that algorithm to satisfy my curiosity as it was a fairly simple yet efficient code.
Bernstein-Vazirani algorithm
Problems with the classical algorithm
The Bernstein-Vazirani algorithm demonstrates the advantage of using quantum computers over classical computers by solving a specific problem.
This specific problem is where we can break secrets😜 A user will enter a secret number in binary values(0s and 1s) and our aim is to find an entered string of bits in the exact order. To do so, we use a black box which gives us simply one function: tell us if our guess is right or wrong.
So, let us say I set the secret number to 11001 in the box. One way to do it is to manually ask the box if the number is 00000. If not, we keep doing this method of trial and error with every possible combination until we randomly come across the number.
Luckily we don’t have to do that if we use a classical computer with the black box. Here’s how the black box works: it implements an AND operation to our guess and the secret number. It would place our secret number and the guess next to each other. With the AND operation, it would give a “1" wherever the two numbers in the same place is “1”.
The first guess by the computer would be 00001 to find out if the first digit is 1. Then the computer would move on to the second guess which would be 00010. In this guess, the computer tries to find out if the second digit is “1.” So the classical computer takes as many guesses as the number of digits to find the secret number.
If there were 600,000 digits, that’s exactly how many tries a classical computer would need. However, the problem is that this can be very slow in spite of being the most efficient solution today in a classical computer. But… a quantum computer could do it all in just one try no matter how many digits!
Quantum computer’s advantage
A quantum computer can do this in just one try because of some of its special abilities that I will explain below.
We start by building a circuit made from the number of qubits as the length of the secret number plus one (n+1) all in the states of |0> and n bits as well to store results we get.
Then we apply a Hadamard gate to n qubits.
The Hadamard gate always converts |0> to |+> and |1> to |->. This puts all of the n qubits in a superposition of |+> since they all were |0>. For the extra qubit we have, we apply an x gate before applying a Hadamard on it. The x gate is a quantum-NOT gate so it converts the |0> to |1> so when the Hadamard gate is applied it will be in a superposition of |- >.
Now we build the box that contains the secret number. The box has to have a CX (or) Controlled-X gate from every “1” in the secret code to the extra qubit. In our case where the secret number is 11001, our CX gates would be from the first, second and last qubit.
A CX gate operates using two qubits; the first one which is the control and another qubit which will be the target. In this operation, the value of the target is put into the control qubit only if the value of the control qubit is |1>. So basically it is a NOT gate but with a control that only happens if the condition is true.
This whole process is called phase kickback, during which the control qubit changes from |+> to |->(because our target qubit had the value of |->) letting us distinguish the 1s from the zero. This ability to change states is what makes our quantum algorithm unique from the classical algorithm
In the end, we need to apply another set of Hadamard gates for all the qubits except the last one. At this point, all the qubits that had a 1 are in a state of |->, so we add a Hadamard gate to reverse their states. That means the qubit with |-> turns to 1 and qubits in a state of |+> turns to 0.
We still need some way to measure the values. So we use the circuit.measure() function to put the values of the qubits into the corresponding classical bits. The result made from the classical bits will give you the secret number!
When I tried this out by coding in Qiskit, the program was able to find out the secret number every single time in just one try. Imagine having a program that could find out any number you have even if it is 30,000 digits long! This is MIND-BLOWING!!
But at the same time, I thought a lot of demonstrations about Quantum computer’s “supremacy” is based only on math problems like this that can’t be done as fast in a classical computer. Just like the Bernstein-Vazirani algorithm, although most are amazing programs they don’t give us practical implementations in the real world. However, what this does give us is a promise of what quantum computers can achieve once we can harness their full potential.
If you’re wondering what makes doing this on a quantum computer so powerful, it is because of the qubits. These qubits are so small and exist within their own quantum realm that they have completely different abilities like existing in two different places at the same time or being able to do “spooky action at a distance.” If you want to learn more about these properties read my article on Introduction to Quantum Computers!
Key Takeaways:
- Even though the Bernstein Vazirani algorithm may not have a practical use case right now, it’s one of the most simplest ways to prove the power of quantum computers.
- A quick summary of how the algorithm works is that the qubits are put in superposition, queried through the black box and then measured to find the secret number.
- Once we comprehend the potential of this power, the rest is up to us and as far as our curiosity can take us until we solve some of humanity’s biggest problems.
Hi 👋 Thank you so much for reading my article!
I’m a sixteen-year-old high school student super passionate about quantum computers and if you enjoyed this article, I would be super excited if you left claps or shared it with your friends!
If you had any questions or feedback don’t hesitate to send me an email at shivesrini2013@gmail.com or message me on LinkedIn:)
