A randomised classical circuit is meant to copy its single input bit to its output

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

A randomised classical circuit is meant to copy its single input bit

x\in\{0,1\}

to its output, but is corrupted by two independent fair coin flips

c_1,c_2\in\{0,1\}

: it outputs

y = x \oplus (c_1 \wedge c_2)

, where

\oplus

is addition modulo

2

and

c_1\wedge c_2

1

only when both coins show the outcome labelled

1

. ((a)) Find

P(y=x)

and confirm it is consistent with using this circuit as a bounded-error subroutine with error at most

1/3

on every input

x

. ((b)) Following the proof that

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

, replace each coin by a qubit prepared in

H|0\rangle

and build the reversible circuit (a Toffoli gate computing

c_1\wedge c_2

into a fresh ancilla, then a

\mathrm{CNOT}

from that ancilla onto a qubit initialised to

|x\rangle

) that computes

y

, deferring measurement of the coin qubits to the end. Write the resulting state, before any measurement, as a path sum over the two coins. ((c)) Measure the qubit that holds

y

. Using the path sum, compute

P(y=x)

and confirm it matches part (a).

Browse the problem library