Completing the physical representation of quantum algorithms explains their computational speedup
Giuseppe Castagnoli · arXiv (Cornell University) · 2017
The usual representation of quantum algorithms, limited to the problem solving process, is incomplete as it lacks the initial measurement. Completing it involves three steps: (i) representing the problem setting process, (ii) relativizing this representation to Alice, the problem solver, to whom the problem setting must be concealed, (iii) representing the reversibility of the computation process by symmetrizing it for time reversal. The latter step shows that all is as if Alice, before beginning her problem solving action, knew half of the information that specifies the solution of the problem she will read in the future. An optimal quantum algorithm is a sum over classical histories in each of which Alice knows in advance one of the possible halves of the solution and performs the computation steps (oracle queries) necessary to identify the missing half. This explains the quantum computational speedup and allows to predict the speedup offered by the optimal quantum solution of any oracle problem.