A database of items has exactly marked items

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

N=2^{20}

items has exactly

M=4

marked items, found by Grover's algorithm (amplitude amplification with a fixed number of marked items). ((a)) Compute the optimal number of Grover iterations

k^\ast = \left\lfloor \dfrac{\pi}{4}\sqrt{N/M}\right\rfloor

and the success probability

\sin^2\!\big((2k^\ast+1)\theta\big)

at that count, where

\theta = \arcsin\sqrt{M/N}

. ((b)) A technician mistakenly runs the number of iterations optimal for a single marked item,

k=804

, instead of

k^\ast

. Estimate the resulting success probability.

Browse the problem library