The 50 % advanced information rule of the quantum algorithms
2009
The oracle chooses a function out of a known set of functions and gives to the player a black box that, given an argument, evaluates the function. The player should find out a certain character of the function (e. g. its period) through function evaluation. This is the typical problem addressed by the quantum algorithms. In former theoretical work, we showed that a quantum algorithm requires the number of function evaluations of a classical algorithm that knows in advance 50 % of the information that specifies the solution of the problem. This requires representing physically, besides the solution algorithm, the oracle’s choice. Here we check that this 50 % rule holds for the main quantum algorithms. In the structured problems, a classical algorithm with the advanced information, to identify the missing information should perform one function evaluation. The speed up is exponential since a classical algorithm without advanced information should perform an exponential