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
Given oracle access to f:{0,1}4→{0,1}, someone prepares the uniform superposition over the four input qubits, applies the bit oracle once to obtain 2−2∑x∈{0,1}4∣x⟩∣f(x)⟩, and argues: "this state contains f(x) for all sixteen values of x at once, so measuring it lets me read off the entire truth table of f in a single shot, beating any classical method, which needs sixteen queries to learn the whole table."
((a)) Compute the probability that a measurement of this state yields the specific outcome x=0110 together with the value f(0110).
((b)) Use this probability to state exactly how much information about f a single query and measurement actually yields, and explain why the claim is false.