Bernstein-Vazirani Algorithm¶
The Bernstein-Vazirani (BV) algorithm demonstrates an exponential speedup over classical methods for the particular task:
Suppose we have an oracle that implements the function \(f: \{0,1\}^n \longrightarrow \{0,1\}\).
\(f(x)\) is promised to be the dot product between \(x\) and a secret \(n\)-bit binary string \(s\):
\(f(x) = x \cdot s (mod \space 2) = (x_1s_1 + x_2s_2 + ... + x_ns_n) (mod \space 2)\).
Our goal is to find the secret string \(s\).
Classical case¶
For the case of \(n=3\) consider \(s=101\), which is a secret string and hence we dont have access to it.
We have access to the function: \(f(x) = x\cdot s (mod \space 2) = (x_1s_1 + x_2s_2 + x_3s_3) (mod \space 2)\)
Let us strategically query the function to determine \(s\).
\(1^{st}\) query: \(f(001) = 001 \cdot s (mod \space 2) = (0 \cdot 1 + 0 \cdot 0 + 1 \cdot 1)(mod \space 2) = 1 (mod \space 2) = 1\)
\(2^{nd}\) query: \(f(010) = 010 \cdot s (mod \space 2) = (0 \cdot 1 + 1 \cdot 0 + 0 \cdot 1)(mod \space 2) = 0 (mod \space 2) = 0\)
\(3^{rd}\) query: \(f(100) = 100 \cdot s (mod \space 2) = (1 \cdot 1 + 0 \cdot 0 + 0 \cdot 1)(mod \space 2) = 1 (mod \space 2) = 1\)
Remember that from a user perspective, you only see \(f(001) = 1\) since the inner mechanisms of the oracle and the value of \(s\) is hidden from you.
Why did we query \(f(001)\) and not \(f(011)\)?
For \(f(001) = (x_1s_1 + x_2s_2 + x_3s_3) (mod \space 2) = (0 + 0 + x_3s_3) (mod \space 2) = (x_3s_3) (mod \space 2) = 1 \cdot s_3 (mod \space 2) = s_3 (mod \space 2) = 1\)
We have now isolated \(s_3\) and know that \(s_3 (mod \space 2) = 1\). \(s_3\) can only be 0 or 1 and in this case it has to be \(1\) since \(0 (mod \space 2) = 0\).
For \(f(011) = (x_2s_2 + x_3s_3) (mod \space 2)\), we will be left with \(s_2\) and \(s_3\) each of which will be more difficult to isolate via a combination of linear equations. Hence why we have to strategically query the function.
In the classical case, we see that the secret string \(s\) can be calculated in 3 queries. More generally speaking, it would take \(n\) queries to generate enough information to determine \(s\)
Quantum case¶
The BV quantum algorithm can take advantage of superposition and entanglement to encode the problem and produce an answer with a single oracle (black box function) query. The setup is a register of \(n\) qubits in the \(\ket{0}\) state and a single auxiliary qubit in the \(\ket{1}\) state. The auxiliary qubit enables the phase kickback. Consider the register of \(n\) qubits initialized here:
Application of a Hadamard gate to each qubit results in:
Next, the oracle, \(U_f\), performs maps \(\ket{x}\) to \((-1)^{f(x)}\ket{x}\) resulting in:
Applying Hadamard gates again returns the following state:
In the case of \(a \neq y\), the entire term becomes zero. In the case of \(a = y\), the state \(\ket{a}\) is returned with an amplitude of 1. This means there is a 100% chance of the measurement result being the hidden bitstring \(a\) with only one call to the oracle!
Implementing in CUDA-Q¶
The cell below generates a random bitstring of length \(n\). If you are running this on your CPU, keep the qubit count small and increase to around 30 if you are running on a GPU with the nvidia backend.
[1]:
import cudaq
from typing import List
cudaq.set_target('qpp-cpu')
#cudaq.set_target('nvidia') # GPU backend which enables scaling to large problem sizes
[2]:
qubit_count = 5 # Set to around 30 qubits if you have GPU access
secret_string = [1, 1, 0, 1,
0] # Change the secret string to whatever you prefer
assert qubit_count == len(secret_string)
Next, the oracle kernel is defined. This will be used inside of the primary BV kernel, so it needs to take both the main register and auxiliary qubit as inputs as well as the secret bitstring. The oracle loops through the bits and applies a CNOT on the auxiliary qubit if the register qubit is a 1.
[3]:
@cudaq.kernel
def oracle(register: cudaq.qview, auxiliary_qubit: cudaq.qubit,
secret_string: List[int]):
for index, bit in enumerate(secret_string):
if bit == 1:
x.ctrl(register[index], auxiliary_qubit)
The code below performs the steps described above for the BV algorithm, calling the oracle kernel as needed. You can see the circuit created below and verify that the procedure guessed the correct bitstring.
[4]:
@cudaq.kernel
def bernstein_vazirani(secret_string: List[int]):
qubits = cudaq.qvector(len(secret_string)) # register of size n
auxiliary_qubit = cudaq.qubit() # auxiliary qubit
# Prepare the auxillary qubit.
x(auxiliary_qubit)
h(auxiliary_qubit)
# Place the rest of the register in a superposition state.
h(qubits)
# Query the oracle.
oracle(qubits, auxiliary_qubit, secret_string)
# Apply another set of Hadamards to the register.
h(qubits)
mz(qubits) # measures only the main register
print(cudaq.draw(bernstein_vazirani, secret_string))
result = cudaq.sample(bernstein_vazirani, secret_string)
print(f"secret bitstring = {secret_string}")
print(f"measured state = {result.most_probable()}")
print(
f"Were we successful? {''.join([str(i) for i in secret_string]) == result.most_probable()}"
)
╭───╮ ╭───╮
q0 : ┤ h ├───────●──┤ h ├──────────
├───┤ │ ╰───╯╭───╮
q1 : ┤ h ├───────┼────●──┤ h ├─────
├───┤ │ │ ├───┤
q2 : ┤ h ├───────┼────┼──┤ h ├─────
├───┤ │ │ ╰───╯╭───╮
q3 : ┤ h ├───────┼────┼────●──┤ h ├
├───┤ │ │ │ ├───┤
q4 : ┤ h ├───────┼────┼────┼──┤ h ├
├───┤╭───╮╭─┴─╮╭─┴─╮╭─┴─╮╰───╯
q5 : ┤ x ├┤ h ├┤ x ├┤ x ├┤ x ├─────
╰───╯╰───╯╰───╯╰───╯╰───╯
secret bitstring = [1, 1, 0, 1, 0]
measured state = 11010
Were we successful? True
[5]:
print(cudaq.__version__)
CUDA-Q Version latest (https://github.com/NVIDIA/cuda-quantum 176f1e7df8a58c2dc3d6b1b47bf7f63b4b8d3b63)