Abstract
Bob hides a ball in one of four drawers. Alice is to locate it. Classically she has to open up to three drawers, quantally just one. The fundamental reason for this quantum speedup is not known. The usual representation of the quantum algorithm is limited to the process of solving the problem. We extend it to the process of setting the problem. The number of the drawer with the ball becomes a unitary transformation of the random outcome of the preparation measurement. This extended, time-symmetric, representation brings in relational quantum mechanics. It is with respect to Bob and any external observer and cannot be with respect to Alice. It would tell her the number of the drawer with the ball before she opens any drawer. To Alice, the projection of the quantum state due to the preparation measurement should be retarded at the end of her search; in the input state of the search, the drawer number is determined to Bob and undetermined to Alice. We show that, mathematically, one can ascribe any part of the selection of the random outcome of the preparation measurement to the final Alice’s measurement. Ascribing half of it explains the speedup of the present algorithm. This leaves the input state to Bob unaltered and projects that to Alice on a state of lower entropy where she knows half of the number of the drawer with the ball in advance. The quantum algorithm turns out to be a sum over histories in each of which Alice knows in advance that the ball is in a pair of drawers and locates it by opening one of the two. In the sample of quantum algorithms examined, the part of the random outcome of the initial measurement selected by the final measurement is one half or slightly above it. Conversely, given an oracle problem, the assumption it is one half always corresponds to an existing quantum algorithm and gives the order of magnitude of the number of oracle queries required by the optimal one.
Similar content being viewed by others
Notes
In Newton’s formulation, it states We are to admit no more causes of natural things than such that are both true and sufficient to explain their appearances [14].
This means that the content of register B affects the output of \(U_{f}\) while remaining unaltered through it.
References
Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proc. of the 28th Annual ACM Symposium on the Theory of Computing, pp. 212–219. ACM Press, New York (1996)
Leggett, A.J., Garg, A.: Quantum mechanics versus macroscopic realism: is the flux there when nobody looks? Phys. Rev. Lett. 54, 857–860 (1985)
Braunstein, S.L., Caves, C.M.: Information theoretic Bell inequalities. Phys. Rev. Lett. 61, 662–665 (1988)
Morikoshi, F.: Information-theoretic temporal Bell inequality and quantum computation. Phys. Rev. A 73, 052308–052312 (2006)
Finkelstein, D.R.: Space-time structure in high energy interaction. In: Gudehus, T., Kaiser, G., Perlmutter, A. (eds.) Fundamental Interactions at High Energy, pp. 324–338. Gordon & Breach, New York (1969)
Bennett, C.H.: The thermodynamics of computation—a review. Int. J. Theor. Phys. 21, 905–940 (1982)
Fredkin, E., Toffoli, T.: Conservative logic. Int. J. Theor. Phys. 21, 219–253 (1982)
Feynman, R.: Simulating physics with computers. Int. J. Theor. Phys. 21(6–7), 467–488 (1982)
Deutsch, D.: Quantum theory, the church turing principle and the universal quantum computer. Proc. R. Soc. Lond. A 400, 97–117 (1985)
Aharonov, Y., Bergman, P.G., Lebowitz, J.L.: Time symmetry in the quantum process of measurement. Phys. Rev. B 134, 1410–1416 (1964)
Aharonov, Y., Albert, D., Vaidman, L.: How the result of a measurement of a component of the spin of a spin-1/2 particle can turn out to be 100”. Phys. Rev. Lett. 60(14), 1351–1354 (1988)
Aharonov, Y., Popescu, S., Tollaksen, J.: A time-symmetric formulation of quantum mechanics. Phys. Today 63, 27–32 (2010)
Rovelli, C.: Relational quantum mechanics. Int. J. Theor. Phys. 35, 637–658 (1996)
Hawking, S.: On the Shoulders of Giants. Running Press, Philadelphia (2003)
Long, G.L.: Grover algorithm with zero theoretical failure rate. Phys. Rev. A 64, 022307 (2001)
Toyama, F.M., van Dijk, W., Nogami, Y.: Quantum search with certainty based on modified Grover algorithms: optimum choice of parameters. Quantum Inf Process 12, 1897–1914 (2013)
Bennett, C.H., Bernstein, E., Brassard, G., Vazirani, U.: Strengths and weaknesses of quantum computing. SIAM J. Comput. 26(5), 1510–1523 (1997)
Castagnoli, G., Finkelstein, D.R.: Theory of the quantum speedup. Proc. Roy. Soc. Lond. A 457, 1799–1807 (2001)
Castagnoli, G.: The quantum correlation between the selection of the problem and that of the solution sheds light on the mechanism of the quantum speed up. Phys. Rev. A 82, 052334–052342 (2010)
Castagnoli, G.: Probing the mechanism of the quantum speed-up by time-symmetric quantum mechanics. In: Proc. of the 92nd Annual Meeting of the AAAS Pacific Division, Quantum Retrocausation: Theory and Experiment (2011)
Morikoshi, F.: Problem-solution symmetry in Grover’s quantum search algorithm. Int. J. Theor. Phys. 50, 1858–1867 (2011)
Dolev S., Elitzur, A.C.: Non-sequential behavior of the wave function. arXiv:quant-ph/0102109v1 (2001)
Bohm, D., Pines, D.A.: Collective description of electron interactions: III. Coulomb interactions in a degenerate electron gas. Phys. Rev. 92, 626–636 (1953)
Finkelstein, D.R.: Private communication
Feynman, R., Hibbs, A.R.: Quantum Mechanics and Path Integrals. McGraw-Hill, New York (1965)
Deutsch, D., Jozsa, R.: Rapid solution of problems by quantum computation. Proc. R. Soc. Lond. A 439, 553–558 (1992)
Simon, D.: On the power of quantum computation. In: Proc. 35th Annual IEEE Symposium on the Foundations of Computer Science, pp. 116–123 (1994)
Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: Proc. 35th Annual IEEE Symposium on the Foundations of Computer Science, pp. 124–134 (1994)
Mosca, M., Ekert, A.: The hidden subgroup problem and eigenvalue estimation on a quantum computer. In: Proc. QCQC ’98, selected papers from the First NASA International Conference on Quantum Computing and Quantum Communications, Springer-Verlag London, pp. 174–188 (1998)
Kaye, P., Laflamme, R., Mosca, M.: An Introduction To Quantum Computing, pp. 146–147. Oxford University Press, Oxford (2007)
Acknowledgments
Thanks are due to David Finkelstein for useful discussions.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Castagnoli, G. Highlighting the Mechanism of the Quantum Speedup by Time-Symmetric and Relational Quantum Mechanics. Found Phys 46, 360–381 (2016). https://doi.org/10.1007/s10701-015-9968-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10701-015-9968-4