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("===========================================================")
|