bernstein_vazirani

bernstein_vazirani#

Functionality#

The Bernstein-Vazirani algorithm, first introduced in Reference [3], can be seen as an extension of the Deutsch-Jozsa algorithm we covered in the last section. It showed that there can be advantages in using a quantum computer as a computational tool for more complex problems than the Deutsch-Jozsa problem.

The Bernstein-Vazirani problem is defined as follows: given a hidden binary string \(s\) of length \(n\), we have access to an oracle that computes the function

\[ f(x) = s \cdot x \mod 2, \]

where \( x \) is an \(n\)-bit input string and \(s \cdot x\) denotes the bitwise inner product. The goal is to determine the hidden string \(s\) using as few queries to the oracle as possible.

As a classical reversible circuit, the Bernstein-Vazirani oracle looks like this:

Bernstein-Vazirani oracle

Bernstein-Vazirani oracle (Source: Qiskit/textbook)

bv.py#

Callee: BernsteinVazirani

Using a quantum computer, we can solve the Bernstein-Vazirani problem with 100% confidence after only one call to the function \(f(x)\). The quantum Bernstein-Vazirani algorithm to find the hidden bit string is very simple:

  • Initialize the inputs qubits to the \(\ket{0}^{\otimes n}\) state, and output qubit to \(\ket{-}\).

  • Apply Hadamard gates to the input register

  • Query the oracle

  • Apply Hadamard gates to the input register

  • Measure the input register

where the quantum circuit for the Bernstein-Vazirani algorithm is shown below:

Bernstein-Vazirani circuit

Bernstein-Vazirani circuit (Source: Qiskit/textbook)

More details about the mathematical derivation of the Bernstein-Vazirani algorithm can be found in Reference [4]. Here, we just summarize the final result of the entire algorithm:

\[ U_{\text{BV}}: \ket{0}_1 \ket{0}_n \mapsto \ket{-}_1 \ket{s}_n. \]

where the algorithm includes the preparation of the output qubit in the \(\ket{-}\) state.

Test expectations:

The hidden binary string is encoded in the first \(n\) qubits and can be directly obtained by measurement.

Doc references: [4]

API#

qolumbina.programs.bernstein_vazirani.bv#

class BernsteinVazirani(secret, insert_barriers=False, name=None)[source]#

Bases: QuantumCircuit

Bernstein-Vazirani algorithm circuit.

Acts on \(n\) input qubits and 1 auxiliary qubit

Parameters:

  • secret (str) – The hidden binary string \(s\).

  • insert_barriers (bool) – Whether to insert barriers in the circuit.

  • name (str | None) – Optional name for the circuit.

Raises:

ValueError – If secret is empty or contains characters other than '0' and '1'.

Contents