arXiv Analytics

Sign in

arXiv:0906.1811 [quant-ph]AbstractReferencesReviewsResources

Quantum algorithms know in advance 50% of the solution they will find in the future

Giuseppe Castagnoli

Published 2009-06-09, updated 2009-07-29Version 4

Quantum algorithms require less operations than classical algorithms. The exact reason of this has not been pinpointed until now. Our explanation is that quantum algorithms know in advance 50% of the solution of the problem they will find in the future. In fact they can be represented as the sum of all the possible histories of a respective "advanced information classical algorithm". This algorithm, given the advanced information (50% of the bits encoding the problem solution), performs the operations (oracle's queries) still required to identify the solution. Each history corresponds to a possible way of getting the advanced information and a possible result of computing the missing information. This explanation of the quantum speed up has an immediate practical consequence: the speed up comes from comparing two classical algorithms, with and without advanced information, with no physics involved. This simplification could open the way to a systematic exploration of the possibilities of speed up.

Comments: The example of new quantum speed up that was just outlined in the previous version (finding the character of a permutation) is fully deployed in the present version. There are minor distributed changes to the writing
Categories: quant-ph
Related articles: Most relevant | Search more
arXiv:quant-ph/9811073 (Published 1998-11-25, updated 1998-12-30)
Tools for Quantum Algorithms
arXiv:quant-ph/0311038 (Published 2003-11-06, updated 2003-12-01)
Quantum algorithms for subset finding
arXiv:quant-ph/0005003 (Published 2000-04-29, updated 2001-07-06)
Introduction to Quantum Algorithms