Quantum Algorithms Know in Advance 50% of the Solution They Will Find in the Future
Tóm tắt
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.
Tài liệu tham khảo
Bernstein, E., Vazirani, U.: In: Proceedings of the 25th Annual ACM Symposium on the Theory of Computing, p. 11, 1993
Castagnoli, G., Finkelstein, D.: Theory of the quantum speed up. Proc. R. Soc. Lond. A 457, 1799 (2001). arXiv:quant-ph/0010081v1
Castagnoli, G.: The mechanism of quantum computation. Int. J. Theor. Phys. 47(8), 2181 (2008)
Castagnoli, G.: The quantum speed up as advanced cognition of the solution. Int. J. Theor. Phys. 48(3), 857 (2009)
Castagnoli, G.: The 50% advanced information rule of the quantum algorithms. Int. J. Theor. Phys. (2009, to be published)
Deutsch, D.: Quantum theory, the Church-Turing principle, and the universal quantum computer. Proc. R. Soc. (Lond.) A 400, 97 (1985)
Deutsch, D., Jozsa, R.: Rapid solution of problems by quantum computation. Proc. R. Soc. (Lond.) A 439, 553 (1992)
Dolev, S., Elitzur, A.C.: Non-Sequential Behavior of the Wave Function. (2005). arXiv:quant-ph/0102109v1
Gross, D., Flammia, S.T., Eisert, X.: J. Phys. Rev. Lett. 102(19) (2009)
Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proc. 28th Ann. ACM Symp. Theory of Computing, 1996
Grover, L.K.: From Schrödinger equation to quantum search algorithm. (2001). arXiv:quant-ph/0109116
Simon, D.: On the power of quantum computation. In: Proc. 35th Ann. Symp. on Foundations of Comp. Sci., p. 116, 1994