2009/06/30 by Giuseppe Castagnoli
Computer Science · Physics and Astronomy · #Algorithm #Artificial intelligence #Computability, Logic, AI Algorithms #Computer science #Encoding (memory) #Oracle #Physics #Quantum #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum algorithm #Quantum computer #Quantum error correction #Quantum mechanics #Quantum sort #Theoretical computer science #quant-ph
paper · pdf · doi:10.1007/s10773-009-0143-6
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
arxiv created 2009/07/29 · openalex publication_date 2009/09/21 · arxiv updated 2015/05/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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.