Skip to main content Accessibility help
×
Hostname: page-component-78c5997874-m6dg7 Total loading time: 0 Render date: 2024-11-09T05:35:38.595Z Has data issue: false hasContentIssue false

Turing in Quantumland

Published online by Cambridge University Press:  05 June 2014

Harry Buhrman
Affiliation:
University of Amsterdam
Rod Downey
Affiliation:
Victoria University of Wellington
Get access

Summary

Abstract. We revisit the notion of a quantum Turing-machine, whose design is based on the laws of quantum mechanics. It turns out that such a machine is not more powerful, in the sense of computability, than the machine originally constructed by Turing. Quantum Turing-machines do not violate the Church–Turing thesis. The benefit of quantum computing lies in efficiency. Quantum computers appear to be more efficient, in time, than classical Turing-machines, however its exact additional computational power is unclear, as this question ties in with deep open problems in complexity theory. We will sketch where BQP, the quantum analogue of the complexity class P, resides in the realm of complexity classes.

§1. Introduction. A decade before Turing developed his theory of computing, physicists struggled with the advent of quantum mechanics. During the famous 5th Solvay Conference in 1927 it was clear that a new era of physics had surfaced. Its strange features like superposition and entanglement still lead to heated discussions and much confusion. However strange and counter-intuitive, the theory has never been refuted by experiments that are performed daily and in great numbers throughout laboratories around the world. Time after time the predictions of quantum mechanics are in full agreement with experiment.

Shortly after the advent of quantum mechanics, Church, Turing and Post developed the notion of computability [Chu36, Tur36, Pos36]. Less than 10 years later these formal ideas would be put to practice resulting in the ENIAC, the first general purpose machine.

Type
Chapter
Information
Turing's Legacy
Developments from Turing's Ideas in Logic
, pp. 70 - 89
Publisher: Cambridge University Press
Print publication year: 2014

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[AarlO] Scott, Aaronson, BQP and the polynomial hierarchy, STOC, 2010, pp. 141-150.
[Aarll] Scott, Aaronson, A counterexample to the generalized linial-nisan conjecture, CoRR abs/1110.6126,2011.
[Adl78] Leonard M., Adleman, Two theorems on random polynomial time, FOCS, 1978, pp. 75-83.
[ADH97] Leonard M., Adleman, Jonathan, De Marrais, and Ming-Deh A., Huang, Quantum computability, SIAM Journal on Computing, vol. 26 (1997), no. 5, pp. 1524-1540.Google Scholar
[AKS04] Manindra, Agrawal, Neeraj, Kayal, and Nitin, Saxena, PRIMES Is in P, Annals of Mathematics. Second Series, vol. 160 (2004), no. 2, pp. 781-793.Google Scholar
[AB09] Sanjeev, Arora and Boaz, Barak, Computational complexity—a modern approach, Cambridge University Press, 2009.
[BBC+01] Robert, Beals, Harry, Buhrman, Richard, Cleve, Michele, Mosca, and Ronald, de Wolf, Quantum lower bounds by polynomials, Journal of the ACM, vol. 48 (2001), no. 4, pp. 778-797.Google Scholar
[BB84] C. H., Bennett and G., Brassard, Quantum cryptography: Public key distribution and coin tossing, Proceedings of IEEE international conference on Computers, Systems, and Signal Processing, IEEE, 1984, pp. 175-179.
[Ben89] Charles H., Bennett, Time/space trade-offs for reversible computation, SIAM Journal on Computing, vol. 18 (1989), no. 4, pp. 766-776.Google Scholar
[BS98] Charles H., Bennett and Peter W., Shor, Quantum information theory, IEEE Transactions on Information Theory, vol. 44 (1998), no. 6, pp. 2724-2742.Google Scholar
[BV97] Ethan, Bernstein and Umesh V., Vazirani, Quantum complexity theory, SIAM Journal on Computing, vol. 26 (1997), no. 5, pp. 1411-1473.Google Scholar
[BCMdW10] Harry, Buhrman, Richard, Cleve, Serge, Massar, and Ronald, de Wolf, Nonlocality and communication complexity, Reviews of Modern Physics, vol. 82 (2010), no. 1, pp. 665-698.Google Scholar
[BdW02] Harry, Buhrman and Ronald, de Wolf, Complexity measures and decision tree complexity: a survey, Theoretical Computer Science, vol. 288 (2002), no. 1, pp. 21-43.Google Scholar
[Chu36] Alonzo, Church, An unsolvable problem of elementary number theory, American Journal of Mathematics, (1936).Google Scholar
[Coo71] Stephen A., Cook, The complexity of theorem-proving procedures, STOC, 1971, pp. 151-158.
[Deu85] David, Deutsch, Quantum theory, the Church–Turing principle and the universal quantum computer, Proceedings of the Royal Society of London. Series A, (1985).
[DJ92] David, Deutsch and Richard, Jozsa, Rapid solution ofproblems by quantum computation, Proceedings of the Royal Society of London. Series A, vol. 493 (1992), no. 1907, pp. 553-558.Google Scholar
[DdW11] Andrew, Drucker and Ronald, de Wolf, Quantum proofs for classical theorems, Theory of Computing, vol. 2 (2011), pp. 1-54.Google Scholar
[EFMP11] M. D., Eisaman, J., Fan, A., Migdall, and S. V., Polyakov, Invited review article: Single-photon sources and detectors, Review of Scientific Instruments, vol. 82 (2011), no. 7, p. 25.Google Scholar
[FU10] Bill, Fefferman and Chris, Umans, Pseudorandom generators and the BQP vs. PH problem, manuscript, 2010.
[Fey82] Richard, Feynman, Simulating physics with computers, International Journal of Theoretical Physics, vol. 21 (1982), no. 6–7, pp. 467-488.Google Scholar
[GJ79] M. R., Garey and D. S., Johnson, Computers and intractability: A guide to the theory of NP-completeness, W. H. Freeman, New York, 1979.
[Gro96] L. K., Grover, A fast quantum mechanical algorithm for database search, Proceedings of 28th ACM STOC, 1996, quant-ph/9605043, pp. 212-219.
[KL80] Richard M., Karp and Richard J., Lipton, Some connections between nonuniform and uniform complexity classes, STOC, 1980, pp. 302-309.
[Lan61] Rolf, Landauer, Irreversibility and heat generation in the computing process, IBM Journal of Research and Development, vol. 5 (1961), pp. 183-191.Google Scholar
[Lev73] Leonid, Levin, Universal search problems, Problems of Information Transmission, vol. 9 (1973), no. 3, pp. 265-266.Google Scholar
[Moo65] Gordon, Moore, Cramming more components onto integrated circuits, Electronics, vol. 38 (1965), no. 8.Google Scholar
[NC00] Michael A., Nielsen and Isaac L., Chuang, Quantum computation and quantum information, Cambridge University Press, 2000.
[NW94] Noam, Nisan and Avi, Wigderson, Hardness vs randomness, Journal of Computer and System Sciences, vol. 49 (1994), no. 2, pp. 149-167.Google Scholar
[Pos36] Emil, Post, Finite combinatory processes-formulation 1, The Journal of Symbolic Logic, vol. 1 (1936), no. 3, pp. 103-105.Google Scholar
[RSA78] R. L., Rivest, A., Shamir, and L., Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, vol. 21 (1978), no. 2, pp. 120-126.Google Scholar
[RGF+12] Guy, Ropars, Gabriel, Gorre, Albert, le Floch, Jay, Enoch, and Vasudevan, Lakshminarayanan, A depolarizer as a possible precise sunstone for viking navigation by polarized skylight, Proceedings of the Royal Society A, vol. 468 (2012), no. 2139, pp. 671-684.Google Scholar
[Sch35] E., Schrödinger, Die gegenwärtige Situation in der Quantenmechanik, Naturwissenschaften, vol. 23 (1935), no. 48, pp. 807-812.Google Scholar
[Sho94] P. W., Shor, Algorithms for quantum computation: Discrete logarithms and factoring, Proceedings of the 35th annual symposium on the Foundations of Computer Science (Los Alamitos, CA), IEEE, 1994, pp. 124-134.
[Sim97] Daniel R., Simon, On the power of quantum computation, SIAM Journal on Computing, vol. 26 (1997), no. 5, pp. 1474-1483.Google Scholar
[Sin00] Simon, Singh, The code book. The science of secrecy from ancient Egypt to quantum cryptography, Harper Collins Publishers, 2000.
[Sip83] Michael, Sipser, A complexity theoretic approach to randomness, STOC, 1983, pp. 330-335.
[Tur36] Alan, Turing, On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, vol. 2 (1936), no. 42, pp. 230-265, addendum 1937.Google Scholar
[vEB90] Peter Van Emde, Boas, Machine models and simulation, Handbook of theoretical computer science, Volume A: Algorithms and complexity (A), 1990, pp. 1-66.
[Zac86] Stathis, Zachos, Probabilistic quantifiers, adversaries, and complexity classes: An overview, Structure in complexity theory conference, 1986, pp. 383-400.Google Scholar

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

  • Turing in Quantumland
  • Edited by Rod Downey, Victoria University of Wellington
  • Book: Turing's Legacy
  • Online publication: 05 June 2014
  • Chapter DOI: https://doi.org/10.1017/CBO9781107338579.004
Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

  • Turing in Quantumland
  • Edited by Rod Downey, Victoria University of Wellington
  • Book: Turing's Legacy
  • Online publication: 05 June 2014
  • Chapter DOI: https://doi.org/10.1017/CBO9781107338579.004
Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

  • Turing in Quantumland
  • Edited by Rod Downey, Victoria University of Wellington
  • Book: Turing's Legacy
  • Online publication: 05 June 2014
  • Chapter DOI: https://doi.org/10.1017/CBO9781107338579.004
Available formats
×