A ground station must decide whether a diagnostic function on status bits from a…
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 Oracles, quantum parallelism and the first algorithms
Problem
A ground station must decide whether a diagnostic function on n=16 status bits from a satellite is constant or balanced, under the usual promise that it is one or the other. Each call to the diagnostic costs one query.
((a)) Estimate the worst-case number of queries a deterministic classical algorithm needs.
((b)) Estimate the smallest number of random queries (with replacement) that brings the error probability below 1%.