Skip to main content
SpringerLink
Log in

Highlighting the Mechanism of the Quantum Speedup by Time-Symmetric and Relational Quantum Mechanics

  • Published:
Foundations of Physics Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 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].

  2. Reference [17] showed that Grover algorithm is optimal in the order of magnitude. Reference [16], posterior of 16 years, shows that Grover/Long algorithm is exactly optimal.

  3. This means that the content of register B affects the output of \(U_{f}\) while remaining unaltered through it.

References

  1. 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)

  2. Leggett, A.J., Garg, A.: Quantum mechanics versus macroscopic realism: is the flux there when nobody looks? Phys. Rev. Lett. 54, 857–860 (1985)

    Article  ADS  MathSciNet  Google Scholar 

  3. Braunstein, S.L., Caves, C.M.: Information theoretic Bell inequalities. Phys. Rev. Lett. 61, 662–665 (1988)

    Article  ADS  MathSciNet  Google Scholar 

  4. Morikoshi, F.: Information-theoretic temporal Bell inequality and quantum computation. Phys. Rev. A 73, 052308–052312 (2006)

    Article  ADS  Google Scholar 

  5. 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)

    Google Scholar 

  6. Bennett, C.H.: The thermodynamics of computation—a review. Int. J. Theor. Phys. 21, 905–940 (1982)

    Article  Google Scholar 

  7. Fredkin, E., Toffoli, T.: Conservative logic. Int. J. Theor. Phys. 21, 219–253 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  8. Feynman, R.: Simulating physics with computers. Int. J. Theor. Phys. 21(6–7), 467–488 (1982)

    Article  MathSciNet  Google Scholar 

  9. Deutsch, D.: Quantum theory, the church turing principle and the universal quantum computer. Proc. R. Soc. Lond. A 400, 97–117 (1985)

    Article  ADS  MathSciNet  MATH  Google Scholar 

  10. Aharonov, Y., Bergman, P.G., Lebowitz, J.L.: Time symmetry in the quantum process of measurement. Phys. Rev. B 134, 1410–1416 (1964)

    Article  ADS  Google Scholar 

  11. 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)

    Article  ADS  MathSciNet  Google Scholar 

  12. Aharonov, Y., Popescu, S., Tollaksen, J.: A time-symmetric formulation of quantum mechanics. Phys. Today 63, 27–32 (2010)

    Article  Google Scholar 

  13. Rovelli, C.: Relational quantum mechanics. Int. J. Theor. Phys. 35, 637–658 (1996)

    Article  MathSciNet  Google Scholar 

  14. Hawking, S.: On the Shoulders of Giants. Running Press, Philadelphia (2003)

    Google Scholar 

  15. Long, G.L.: Grover algorithm with zero theoretical failure rate. Phys. Rev. A 64, 022307 (2001)

    Article  ADS  Google Scholar 

  16. 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)

    Article  ADS  MathSciNet  MATH  Google Scholar 

  17. Bennett, C.H., Bernstein, E., Brassard, G., Vazirani, U.: Strengths and weaknesses of quantum computing. SIAM J. Comput. 26(5), 1510–1523 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  18. Castagnoli, G., Finkelstein, D.R.: Theory of the quantum speedup. Proc. Roy. Soc. Lond. A 457, 1799–1807 (2001)

    Article  ADS  MathSciNet  MATH  Google Scholar 

  19. 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)

    Article  ADS  Google Scholar 

  20. 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)

  21. Morikoshi, F.: Problem-solution symmetry in Grover’s quantum search algorithm. Int. J. Theor. Phys. 50, 1858–1867 (2011)

    Article  Google Scholar 

  22. Dolev S., Elitzur, A.C.: Non-sequential behavior of the wave function. arXiv:quant-ph/0102109v1 (2001)

  23. Bohm, D., Pines, D.A.: Collective description of electron interactions: III. Coulomb interactions in a degenerate electron gas. Phys. Rev. 92, 626–636 (1953)

    Article  ADS  MathSciNet  Google Scholar 

  24. Finkelstein, D.R.: Private communication

  25. Feynman, R., Hibbs, A.R.: Quantum Mechanics and Path Integrals. McGraw-Hill, New York (1965)

    MATH  Google Scholar 

  26. Deutsch, D., Jozsa, R.: Rapid solution of problems by quantum computation. Proc. R. Soc. Lond. A 439, 553–558 (1992)

    Article  ADS  MathSciNet  MATH  Google Scholar 

  27. Simon, D.: On the power of quantum computation. In: Proc. 35th Annual IEEE Symposium on the Foundations of Computer Science, pp. 116–123 (1994)

  28. 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)

  29. 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)

  30. Kaye, P., Laflamme, R., Mosca, M.: An Introduction To Quantum Computing, pp. 146–147. Oxford University Press, Oxford (2007)

    MATH  Google Scholar 

Download references

Acknowledgments

Thanks are due to David Finkelstein for useful discussions.

Author information

Authors and Affiliations

  1. Elsag Bailey ICT Division and Quantum Information Laboratory, Genova, Italy

    Giuseppe Castagnoli

Authors
  1. Giuseppe Castagnoli
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Giuseppe Castagnoli.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10701-015-9968-4

Keywords

Search

Navigation