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

DOI10.1007/S10773-009-0143-6MaRDI QIDQ2269555zbMATH OpenOpenAlexFDO

Authors Giuseppe Castagnoli

Publication date 17 March 2010

Published in International Journal of Theoretical Physics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0906.1811

zbMATH Keywords

quantum algorithmquantum computationquantum entanglementquantum measurementquantum speed up

Mathematics Subject Classification ID

Quantum measurement theory, state operations, state preparations (81P15) Quantum coherence, entanglement, quantum correlations (81P40) Quantum computation (81P68)

Abstract: 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.

Recommendations

• The 50\% advanced information rule of the quantum algorithms
• Completing the physical representation of quantum algorithms provides a quantitative explanation of their computational speedup
• Theory of the quantum speed-up
• The quantum speed up as advanced cognition of the solution
• Highlighting the mechanism of the quantum speedup by time-symmetric and relational quantum mechanics

Cites work

• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• Quantum phenomena within a new theory of time
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Rapid solution of problems by quantum computation
• The 50\% advanced information rule of the quantum algorithms
• The mechanism of quantum computation
• The quantum speed up as advanced cognition of the solution
• Theory of the quantum speed-up

Cited in

(9)

• Quantum effects in algorithms
• Completing the physical representation of quantum algorithms provides a quantitative explanation of their computational speedup
• Quantum one go computation and the physical computation level of biological information processing
• A relational time-symmetric framework for analyzing the quantum computational speedup
• Highlighting the mechanism of the quantum speedup by time-symmetric and relational quantum mechanics
• Theory of the quantum speed-up
• scientific article; zbMATH DE number 1406116 (Why is no real title available?)
• The quantum speed up as advanced cognition of the solution
• The 50\% advanced information rule of the quantum algorithms

This page was built for publication: Quantum algorithms know in advance 50\% of the Solution they will find in the future

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2269555)