Bernstein-Vazirani is run for with hidden string

PHYSICS · Multi-part · Fermi University Physics · Quantum Information & Technology · The quantum circuit model and quantum algorithms · The quantum circuit model and quantum algorithms

Quantum Information and Technology, Ch Oracles, quantum parallelism and the first algorithms

Problem

Bernstein-Vazirani is run for

n=3

with hidden string

a=101

. The oracle

O_f=Z^{a_1}\otimes Z^{a_2}\otimes Z^{a_3}

Z

gate on qubit

i

exactly where

a_i=1

, otherwise the identity) is built from three independent single-qubit phase gates. Suppose each of these three gates, independently, applies the wrong one of

\{I,Z\}

(identity where

Z

was needed, or

Z

where identity was needed) with probability

\epsilon

, and the correct one with probability

1-\epsilon

. ((a)) Show that

O_f=Z^{a_1}\otimes Z^{a_2}\otimes Z^{a_3}

correctly reproduces

(-1)^{a\cdot x}

on every basis state

|x\rangle

. ((b)) Explain why, whichever three gates actually fire, the Bernstein-Vazirani circuit still returns, with certainty, whatever string those three gates happen to encode. ((c)) Find the probability that a run of the circuit returns the true string

a=101

Browse the problem library