A start-up claims its 'quantum database appliance' beats any classical disk-based…

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 start-up claims its 'quantum database appliance' beats any classical disk-based search once the database is large enough. A classical lookup (read one item and test it) takes

t_c = 20\,\mathrm{ns}

. One Grover iteration on the quantum device, including every control overhead, takes

t_q = 5\,\mathrm{ms}

. Assume one marked item among

N

, classical search by testing items one at a time (average

N/2

tests) and quantum search using

\frac{\pi}{4}\sqrt{N}

Grover iterations. ((a)) Estimate the crossover value of

N

above which the quantum device is faster. ((b)) Estimate how long a search takes, on either machine, right at that crossover.

Browse the problem library