Two Boolean formulas on two bits are given: and

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 What quantum computers can compute efficiently

Problem

Two Boolean formulas on two bits are given:

f(x_1,x_2) = x_1 \wedge x_2

and

g(x_1,x_2) = x_1 \oplus x_2

. A randomised classical circuit tests whether

f

and

g

are identically equal by flipping two independent fair coins to obtain a uniformly random pair

(b_1,b_2)\in\{0,1\}^2

, evaluating

f(b_1,b_2)

and

g(b_1,b_2)

, and outputting

1

("equivalent") if the two values agree,

0

("not equivalent") otherwise. ((a)) Tabulate the circuit's output for the four coin outcomes and give its acceptance probability (probability of outputting

1

). Confirm that, since

f\not\equiv g

, this is a valid randomised test with error at most

1/3

(the definition used for

\mathrm{BPP}

). ((b)) Following the proof that

\mathrm{BPP}\subseteq\mathrm{BQP}

, build an explicit quantum circuit that reproduces this test: replace each coin by a qubit prepared in

H|0\rangle

, compute the agreement bit reversibly with

\mathrm{CNOT}

/Toffoli-type gates into an output qubit initialised to

|0\rangle

, and defer measurement of the coin qubits to the end. Write the state of the circuit, as a path sum over the two coins, immediately before any measurement. ((c)) Measure the output qubit. Using the path sum, compute the probability of the outcome

1

and confirm it matches part (a).

Browse the problem library