A conference abstract states: "The Deutsch-Jozsa algorithm decides whether a Boolean…
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 abstract states: "The Deutsch-Jozsa algorithm decides whether a Boolean function on n=20 bits is constant or balanced using a single quantum query, whereas any classical algorithm needs 219+1=524289 queries. Quantum computers are therefore exponentially faster than classical computers at this task, full stop."
((a)) Name the specific classical algorithm this comparison is measured against.
((b)) Calculate the number of random classical queries needed to decide the same n=20 promise with error probability at most 1%, and use it to say what the fair, honest statement of the separation is.