A vending machine's self-test function on input bits is promised to be either…
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 vending machine's self-test function on n=6 input bits is promised to be either constant or balanced.
((a)) State the worst-case number of queries D a deterministic classical algorithm needs to decide which.
((b)) Find the smallest number k of random queries (with replacement) that brings the probability of error below 5%.