Introduction to the Bernstein–Vazirani Algorithm
The Bernstein–Vazirani Algorithm is just another one of the many quantum algorithms in which quantum computers outperform classical computers.
What’s the problem?
So, let’s just say that we are given a box. Hidden in the box is a secret number. This “secret number” is represented by six bits made up of 0’s and 1’s. We need to figure out what the “secret number” is.
In more mathematical terms…
The problem is to find s.
Classically, a computer would find it most efficient to calculate the “secret number” by evaluating the function n times, where x = 2^i and i is the summation of 0, 1, … n-1.
Each of these queries reveals the ith bit of s which is why with x = 1 we can obtain the least significant bit of s and so on. This is why in the classical solution you need at least n queries to find s, and would thus have to call on the function n amount of times.
Let’s go back to the secret six-bit number in our box. This means that classically it would take us six tries to find out what the number is. If our secret number was 50-bits, it would take us 50 tries, since n bits mean it will take you n tries. As the secret number (and the bits) increases, so will the number of tries and the amount of time to solve the problem.!
Now imagine if you could find out what the secret number is in one try, no matter its size. That’s exactly what running the Bernstein-Vazirani algorithm on a quantum computer allows you to do.
What is the algorithm?
Invented by Ethan Bernstein and Umesh Vazirani in 1992, the Bernstein-Vazirani algorithm is a restricted version of the Deutsch–Jozsa algorithm. There are only a few steps in the algorithm.
- Set the register for the qubits to 0
- Apply the Hadamard gates
- Query the oracle and perform a controlled negation of every state in the superposition generated by the previous Hadamard transformation for which it returns 1
- Apply the Hadamard gates, for when the qubit is s of i = 1 its — state is converted to 1 and for when the qubit is s of i = 0 its + state is converted to 0
- Then to get s, measure the qubits
So, only for |s⟩ are all contributions to the amplitude of a measurement outcome pointing the same way. For all the other outcomes, the contributions interfere destructively, with equally many positive and negative terms (all of the same magnitude), so the total amplitude for each of those outcomes is 0.
Coding it using Qiskit
By using IBM Quantum’s Qiskit platform, I was able to see the Bernstein-Vazirani algorithm in action.
I set n = 2 (the number of qubits in the register) and s = 3 (the secret number).
Here are the above-mentioned steps of the algorithm coded in Qiskit.
Here are the results after I ran the code on one of IBM’s quantum computers.
As you can see, the quantum computer was able to calculate the secret number (3, or 11 in binary) 86.1% of the time, on the first try.
Key Takeaways
- Bernstein and Vazirani designed their problem and algorithm around what a quantum computer would be able to do.
- In almost every quantum algorithm, the amplitude reinforces each other only for the outcomes that we want.
- The Bernstein-Vazirani algorithm solves the problem quantumly using only one query, whereas it would take n queries classically.
- The algorithm is important in showing the advantages of using a quantum computer to solve complex problems, even though the black box problem isn’t very hard.
Hi! I’m Nidhi Jadhav. I am 16 years old and incredibly passionate about AI and Quantum Computing. Thank you so much for reading my article! If you want to learn more about new emerging technologies, follow me, connect with me on Linkedin, or email me at nidhivjadhav@gmail.com for any inquiries. Thanks again!
