A classical processor tests one item every against a linear (non-quantum) search of…

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 classical processor tests one item every tc=1 μst_c = 1\,\mu\mathrm{s} against a linear (non-quantum) search of an unstructured list with one marked item. A quantum processor performs one Grover iteration, including all overhead, every tq=100 μst_q = 100\,\mu\mathrm{s}. Both machines are run continuously for one day (86 400 s86\,400\,\mathrm{s}). ((a)) Estimate the largest list size NN the classical machine can search (on average) to completion in one day. ((b)) Estimate the largest NN the quantum machine can search, using π4N\frac{\pi}{4}\sqrt{N} iterations, in the same time. ((c)) By what factor does the quantum machine's reach in NN exceed the classical machine's?

Browse the problem library