A register of inventory records is to be searched by quantum counting to decide…

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 register of

N=2^{14}=16384

inventory records is to be searched by quantum counting to decide whether

M=5

M=6

records are flagged, using the rule

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

for the number of counting qubits

t

needed to resolve

M

from

M\pm1

. ((a)) Find the minimum

t

satisfying the rule, using

M=5

. ((b)) Give the number of oracle queries used by the phase-estimation counting circuit,

2^t - 1

, and compare it with the

N

queries needed to count the flagged records by testing every one classically.

Browse the problem library