A search register has qubits

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 Grover search, amplitude amplification and counting

Problem

A search register has

n = 6

qubits, so

N = 2^6 = 64

. ((a)) The diffusion operator

2|s\rangle\langle s| - I

is built as

H^{\otimes n}(2|0\rangle\langle0|-I)H^{\otimes n}

, and

2|0\rangle\langle0|-I

is built, up to a global sign, by conjugating

C^{n-1}(Z)

Z

on the last qubit controlled by the other

n-1

) with

X^{\otimes n}

. Using the multiply-controlled-gate construction from the circuit model (with

m-1

ancilla qubits and

2(m-1)

Toffoli gates plus one controlled-

Z

for an

m

-control gate), state the number of ancilla qubits and Toffoli gates this diffusion step needs for

n = 6

. ((b)) Phase estimation on the Grover operator

G

(as used for quantum counting) needs a control register of

t

qubits such that

2^t \ge 4\pi\sqrt{MN}

in order to distinguish

M = 8

marked items from

M = 9

. Find the smallest such

t

and the corresponding number of oracle queries,

2^t - 1

Browse the problem library