A conference poster states: "Bernstein–Vazirani achieves an exponential quantum…
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 conference poster states: "Bernstein–Vazirani achieves an exponential quantum speed-up: for a hidden n-bit string s, one quantum query recovers s completely, whereas classically one needs 2n−1+1 queries in the worst case to be sure of s. For n=20 this is 1 query against 524289."
((a)) Name the error in this claim.
((b)) Give the correct classical query count for n=20 and state whether the separation is exponential or linear.