Bernstein-Vazirani Algorithm

An Introduction to Bernstein-Vazirani Algorithm

Bernstein-Vazirani algorithm was proposed by Bernstein Ethan and Vazitani Umesh in 1993. This algorithm can solve the Bernstein-Vazirani problem, which can be described as follows.

Give a Boolean function

\[f_s:\{0,1\}^n\rightarrow \{0,1\}: f_s(x)=s\cdot x, x,s\in\{0,1\}^n.\]

Here, \(s\) is an unknown bit string and

\[s\cdot x=(\sum_{i=1}^n s_ix_i) mod~2,\]

where \(x_i​\) and \(s_i​\) are \(i​\)-th bit of \(x​\) and \(s​\), respectively.

Our goal is to determine the bit string \(s​\). The classical algorithms of this problem need at least \(\Omega(n)​\) black boxes of \(f_s​\), but Bernstein-Vazirani algorithm only needs \(O(1)​\) black boxes of \(f_s​\).

Realization of Bernstein-Vazirani Algorithm on HiQ

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
 def run_BV_algorithm(eng, n, oracle):
     """
     Args:
         eng (MainEngine): the Main engine on which we run the BV algorithm
         n (int): number of qubits
         oracle (function): oracle used by the BV algorithm
     """
     x = eng.allocate_qureg(n)

     # start in uniform superposition
     All(H) | x

     oracle_out = eng.allocate_qubit()
     X | oracle_out
     H | oracle_out

     oracle(eng, x, oracle_out)

     All(H) | x

     All(Measure) | x
     Measure | oracle_out

     eng.flush()

     return [int(qubit) for qubit in x]

 def BV_oracle(eng, qubits, output):
     """
     This is an oracle for linear function f(x) = s cdot x, where s=[1,0,0,0,...].
     This oracle mark the basis x for which f(x)=1.

     Args:
         eng (MainEngine): Main compiler engine the algorithm is being run on.
         qubits (Qureg): n-qubit quantum register BV_algorithm is run on.
         output (Qubit): Output qubit to flip in order to mark the solution.
     """
     CNOT | (qubits[0], output)

 if __name__ == "__main__":
     # create a main compiler engine with a simulator backend:
     backend = SimulatorMPI(gate_fusion=True, num_local_qubits=20)

     cache_depth = 10
     rule_set = DecompositionRuleSet(modules=[projectq.setups.decompositions])
     engines = [TagRemover(),
             LocalOptimizer(cache_depth),
             AutoReplacer(rule_set),
             TagRemover(),
             LocalOptimizer(cache_depth)
             #,CommandPrinter()
         , GreedyScheduler()
             ]

     eng = HiQMainEngine(backend, engines)

     n = 10 # number of qubits

     print("===========================================================")
     print("= This is the Bernstein-Vazirani algorithm demo")
     print("= you can change the unknown string by modifying the oracle")

     s = run_BV_algorithm(eng, n, BV_oracle)
     s_str = "".join([str(ch) for ch in s])
     print("= Length of the bit string: {}".format(n))
     print("= The unknown bit string is: {}".format(s_str))
     print("===========================================================")