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\colon \{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 \pmod{2} = (x_1s_1 + x_2s_2 + \ldots + x_ns_n) \pmod{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\).
1st query: \(f(001) = 001 \cdot s \pmod2 = (0 \cdot 1 + 0 \cdot 0 + 1 \cdot 1)\pmod2 = 1 \pmod2 = 1\)
2nd query: \(f(010) = 010 \cdot s \pmod2 = (0 \cdot 1 + 1 \cdot 0 + 0 \cdot 1)\pmod2 = 0 \pmod2 = 0\)
3rd query: \(f(100) = 100 \cdot s \pmod2 = (1 \cdot 1 + 0 \cdot 0 + 0 \cdot 1)\pmod2 = 1 \pmod2 = 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) \pmod2 = (0 + 0 + x_3s_3) \pmod2 = (x_3s_3) \pmod2 = 1 \cdot s_3 \pmod2 = s_3 \pmod2 = 1\)
We have now isolated \(s_3\) and know that \(s_3 \pmod2 = 1\). \(s_3\) can only be 0 or 1 and in this case it has to be \(1\) since \(0 \pmod2 = 0\).
For \(f(011) = (x_2s_2 + x_3s_3) \pmod2\), 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 \(s \neq y\), the entire term becomes zero. In the case of \(s = y\), the state \(\ket{s}\) is returned with an amplitude of 1. This means there is a 100% chance of the measurement result being the hidden bitstring \(s\) 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
import numpy as np
cudaq.set_target("qpp-cpu") # CPU backend
# 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
random_generator = np.random.default_rng(seed=15)
secret_string = random_generator.integers(
2, size=qubit_count
) # Change the secret string to whatever you prefer
print("Your secret string is", secret_string)
assert qubit_count == len(secret_string)
Your secret string is [1 1 1 1 0]
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("Sample result:", result)
print(f"secret bitstring = {secret_string}")
print(f"measured state = {result.most_probable()}")
is_success = "".join(str(i) for i in secret_string) == result.most_probable()
print(f"Were we successful?", is_success)
╭───╮ ╭───╮
q0 : ┤ h ├───────●──┤ h ├───────────────
├───┤ │ ╰───╯╭───╮
q1 : ┤ h ├───────┼────●──┤ h ├──────────
├───┤ │ │ ╰───╯╭───╮
q2 : ┤ h ├───────┼────┼────●──┤ h ├─────
├───┤ │ │ │ ╰───╯╭───╮
q3 : ┤ h ├───────┼────┼────┼────●──┤ h ├
├───┤ │ │ │ │ ├───┤
q4 : ┤ h ├───────┼────┼────┼────┼──┤ h ├
├───┤╭───╮╭─┴─╮╭─┴─╮╭─┴─╮╭─┴─╮╰───╯
q5 : ┤ x ├┤ h ├┤ x ├┤ x ├┤ x ├┤ x ├─────
╰───╯╰───╯╰───╯╰───╯╰───╯╰───╯
Sample result: { 11110:1000 }
secret bitstring = [1 1 1 1 0]
measured state = 11110
Were we successful? True
[5]:
print(cudaq.__version__)
CUDA-Q Version amd64-cu13-0.13.0 (https://github.com/NVIDIA/cuda-quantum b66c5bb7fd8c08e5014e2f03e97e7b0e92691650)