メインコンテンツまでスキップ

# Bernstein-Vazirani Algorithm

The Bernstein-Vazirani algorithm is an algorithm that deterministically solves the following problem:

Suppose there is a secret bit string $s = s_{n-1}\cdots s_1 s_0$ and an oracle that implements the function

$$$f(x) = s_0 x_0 \oplus s_1 x_1 \oplus \cdots \oplus s_{n-1} x_{n-1}$$$

Find the secret bit string $s$.

We demonstrate how to use QURI Parts to implement the algorithm.

## Building the problem oracle​

Now, let's build the quantum circuit that implements the oracle.

from quri_parts.circuit import QuantumCircuitfrom quri_parts.circuit.utils.circuit_drawer import draw_circuitdef get_bv_oracle(s: int, bit_length: int) -> QuantumCircuit:    circuit = QuantumCircuit(bit_length + 1)    for i in range(bit_length):        this_s = (s >> i) & 1        if this_s:            circuit.add_CNOT_gate(i, bit_length)    return circuit

As an example, let's assume the secret bit string is $1101$ and see what the oracle circuit looks like:

draw_circuit(get_bv_oracle(0b1101, 4))
#output                                  0 ----●-------------------          |                             |                             |                       1 ----|-------------------          |                             |                             |                       2 ----|-------●-----------          |       |                     |       |                     |       |               3 ----|-------|-------●---          |       |       |            _|_     _|_     _|_          |CX |   |CX |   |CX |     4 --|0  |---|1  |---|2  |-        |___|   |___|   |___| 

We may confirm that the oracle we implemented is indeed correct. Let's assume that the secret string is $1101$

import numpy as npfrom functools import reduceimport pandas as pdfrom quri_parts.core.state import ComputationalBasisStatefrom quri_parts.qulacs.simulator import evaluate_state_to_vector n_bit_length = 4n_qubits = n_bit_length + 1s = 0b1101oracle = get_bv_oracle(s, 4)recorder = {}for i in range(2**n_bit_length):    out_vector = evaluate_state_to_vector(        ComputationalBasisState(n_qubits, bits=i).with_gates_applied(oracle)    ).vector    oracle_evaluted = np.where(out_vector)[0][0] >> n_bit_length    expected = reduce(lambda x, y: x^y, [((i & s) >> j) & 1 for j in range(n_bit_length)])    recorder[i] = {"oracle": oracle_evaluted, "expected": expected}print(pd.DataFrame.from_dict(recorder).to_markdown())
0123456789101112131415
oracle0101101010100101
expected0101101010100101

Given the table above, we have confirmed that the oracle implemention is indeed correct.

## Building the Bernstein-Vazirani algorithm circuit​

Now, let's build the circuit that implements the Bernstein-Vazirani algorithm. The circuit looks like:

import numpy as npdef get_bv_algorithm_circuit(oracle: QuantumCircuit) -> QuantumCircuit:    bit_length = oracle.qubit_count - 1    circuit = QuantumCircuit(oracle.qubit_count)        circuit.add_X_gate(bit_length)    for i in range(bit_length + 1):        circuit.add_H_gate(i)    circuit.extend(oracle)        for i in range(bit_length + 1):        circuit.add_H_gate(i)    return circuit

Now, let's look at the what the circuit implementing the algorithm looks like.

oracle = get_bv_oracle(0b110101, 6)draw_circuit(get_bv_algorithm_circuit(oracle))
#output         ___                     ___                                  | H |                   | H |                             0 --|1  |-------------●-----|12 |-------------------------        |___|             |     |___|                                  ___     ___      |                                           | H |   | H |     |                                       1 --|2  |---|13 |-----|-----------------------------------        |___|   |___|     |                                            ___              |              ___                          | H |             |             | H |                     2 --|3  |-------------|-------●-----|14 |-----------------        |___|             |       |     |___|                          ___     ___      |       |                                   | H |   | H |     |       |                               3 --|4  |---|15 |-----|-------|---------------------------        |___|   |___|     |       |                                    ___              |       |              ___                  | H |             |       |             | H |             4 --|5  |-------------|-------|-------●-----|16 |---------        |___|             |       |       |     |___|                  ___              |       |       |              ___          | H |             |       |       |             | H |     5 --|6  |-------------|-------|-------|-------●-----|17 |-        |___|             |       |       |       |     |___|          ___     ___     _|_     _|_     _|_     _|_     ___          | X |   | H |   |CX |   |CX |   |CX |   |CX |   | H |     6 --|0  |---|7  |---|8  |---|9  |---|10 |---|11 |---|18 |-        |___|   |___|   |___|   |___|   |___|   |___|   |___| 

Finally, let's construct a function that executes the algorithm. As the algorithm is deterministic, it can be executed using a sampler with only 1 shot.

from quri_parts.qulacs.sampler import create_qulacs_vector_samplerdef get_secret_string(oracle: QuantumCircuit, n_shot: int = 1) -> dict[str, int]:    algorithm = get_bv_algorithm_circuit(oracle)    n_qubits = algorithm.qubit_count        sampler = create_qulacs_vector_sampler()    sampling_cnt = sampler(algorithm, n_shot)    get_secret_string_from_int = lambda s: bin(s)[2:].zfill(n_qubits)[1:]    return {get_secret_string_from_int(s): v for s, v in sampling_cnt.items()}

Now, let's execute the algorithm with the secret string fed to the oracle being $s = 011101$.

bit_length = 6s = 0b011101oracle = get_bv_oracle(s, bit_length)next(iter(get_secret_string(oracle)))
#output    '011101'

The algorithm indeed gives us the desiresd result as expected.

### Showing that the algorithm is deterministic​

To ensure the algorithm is indeed deterministic, let's run the circuit 1000 times and see if it gives the exact same result every time.

import seaborn as snsimport matplotlib.pyplot as pltcounts = get_secret_string(oracle, n_shot=1000)sns.barplot(counts, x=counts.keys(), y=counts.values())plt.show()

Given that every execution gives the exact same result, we have confirmed that the algorithm is deterministic