Bernstein-Vazirani Algorithm¶
Overview¶
This module emulates the Bernstein-Vazirani Algorithm.
The problem is summarized as follows. Given a function \(f\) such that
$$f:\{0,1\}^n \rightarrow \{0,1\} \ \mathbf{x} \rightarrow \mathbf{a}\cdot\mathbf{x} + b\pmod{2} \ (\mathbf{a}\in\{0,1\}^n, b\in\{0,1\})$$
determine \(\mathbf{a}\) and \(b\) with as few queries to \(f\) as possible.
Classically, \(n+1\) queries are required: \(n\) for \(\mathbf{a}\) and one for \(b\). However, using a quantum algorithm, only \(2\) queries are required: just one each both \(\mathbf{a}\) and \(b\).
This module is able to generate and run a program to determine \(\mathbf{a}\) and \(b\), given an oracle. It also has the ability to prescribe a way to generate an oracle out of quantum circuit components, given \(\mathbf{a}\) and \(b\).
More details about the Bernstein-Vazirani Algorithm can be found in reference [1].
Source Code Docs¶
Here you can find documentation for the different submodules in bernstein_vazirani.
grove.bernstein_vazirani.bernstein_vazirani¶
Module for the Bernstein-Vazirani Algorithm. For more information, see [Loceff2015]
[Loceff2015] | Loceff, M. (2015), “A Course in Quantum Computing for the Community College”, Volume 1, Chapter 18, p 484-541. |
-
class
grove.bernstein_vazirani.bernstein_vazirani.
BernsteinVazirani
¶ Bases:
object
This class contains an implementation of the Bernstein-Vazirani algorithm using pyQuil. For more references see the documentation
-
check_solution
()¶ Checks if the the found solution correctly reproduces the input.
Returns: True if solution correctly reproduces input bitstring map Return type: Bool
-
get_solution
()¶ Returns the solution of the BV algorithm
Returns: a tuple of string corresponding to the dot-product partner vector and the bias term Return type: Tuple[String, String]
-
run
(cxn, bitstring_map)¶ Runs the Bernstein-Vazirani algorithm.
Given a connection to a QVM or QPU, find the \(\mathbf{a}\) and \(b\) corresponding to the function represented by the oracle function that will be constructed from the bitstring map.
Parameters: - cxn (Connection) – connection to the QPU or QVM
- String] bitstring_map (Dict[String,) – a truth table describing the boolean function, whose dot-product vector and bias is to be found
Return type:
-
-
grove.bernstein_vazirani.bernstein_vazirani.
create_bv_bitmap
(dot_product_vector, dot_product_bias)¶ This function creates a map from bitstring to function value for a boolean formula \(f\) with a dot product vector \(a\) and a dot product bias \(b\)
\[ \begin{align}\begin{aligned}f:\{0,1\}^n\rightarrow \{0,1\}\\\mathbf{x}\rightarrow \mathbf{a}\cdot\mathbf{x}+b\pmod{2}\\(\mathbf{a}\in\{0,1\}^n, b\in\{0,1\})\end{aligned}\end{align} \]Parameters: - dot_product_vector (String) – a string of 0’s and 1’s that represents the dot-product partner in \(f\)
- dot_product_bias (String) – 0 or 1 as a string representing the bias term in \(f\)
Returns: A dictionary containing all possible bitstring of length equal to \(a\) and the function value \(f\)
Return type: Dict[String, String]
References
[1] | http://pages.cs.wisc.edu/~dieter/Courses/2010f-CS880/Scribes/04/lecture04.pdf |