Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-25T07:01:39.840Z Has data issue: false hasContentIssue false
  • English
  • Français

Quantum Hypercomputation—Hype or Computation?

Published online by Cambridge University Press:  01 January 2022

Amit Hagar  and
Alex Korolev
Get access Rights & Permissions [Opens in a new window]

Abstract

A recent attempt to compute a (recursion-theoretic) noncomputable function using the quantum adiabatic algorithm is criticized and found wanting. Quantum algorithms may outperform classical algorithms in some cases, but so far they retain the classical (recursion-theoretic) notion of computability. A speculation is then offered as to where the putative power of quantum computers may come from.

Type
Research Article
Information
Philosophy of Science , Volume 74 , Issue 3 , July 2007 , pp. 347 - 363
Copyright
Copyright © The Philosophy of Science Association

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

Footnotes

‡

We thank Itamar Pitowsky, Bill Unruh, Bill Demopoulos, Michael Dickson, and an anonymous referee for helpful comments. We also thank Andrew Hodges for an extensive discussion. Earlier versions of this paper were presented in the European Science Foundation Workshop on Quantum Information (Sardegna, September 2004), the Sigma Club Seminar (London School of Economics, March 2005), and the European Congress for Analytic Philosophy Workshop on Quantum Information (Lisbon, August 2005) and the Foundations of Physics Seminar at the University of Maryland (College Park, October 2005). Hagar is grateful for financial support from the Alexander von Humboldt Foundation, the Federal Ministry of Education and Research, and the Program for the Investment in the Future (ZIP) of the German Government through a Sofja Kovalevskaja Award. Korolev is grateful for financial support from the University of British Columbia Li Tze Fong Memorial Fellowship.

References

Aharonov, Dorit (1998), “Quantum Computing”, Annual Review of Computational Physics VI; quant-ph/9812037.CrossRefGoogle Scholar
Aharonov, Dorit, et al. (2004), “Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation”, quant-ph/0405098.Google Scholar
Biham, Eli, et al. (2004), “Quantum Computing without Entanglement”, Quantum Computing without Entanglement 320:15–33.Google Scholar
Born, Max, and Fock, Vladimir (1928), “Beweis des Adiabatensatzes,” Zeitschrift für Physik 51: 165.CrossRefGoogle Scholar
Copeland, Jack B. (1998), “Super Turing Machines”, Super Turing Machines 4:30–32.Google Scholar
Copeland, Jack B. (2002), “Hypercomputation”, Hypercomputation 12:461–502.Google Scholar
Davis, Martin (2003), “The Myth of Hypercomputation”, in Teuscher, C. (ed.), Alan Turing: Life and Legacy of a Great Thinker. New York: Springer, 195–210.Google Scholar
Farhi, E., et al. (2000), “Quantum Computation by Adiabatic Evolution”, quant-ph/0001106.Google Scholar
Feynman, Richard (1982), “Simulating Physics with Computers”, Simulating Physics with Computers 21:467–488.Google Scholar
Fortnow, Lance (2003), “One Complexity Theorist’s View of Quantum Computing”, One Complexity Theorist’s View of Quantum Computing 292:597–610.Google Scholar
Garey, Michael, and Johnson, David (1979), Computers and Intractability. New York: Freeman.Google Scholar
Grover, Lov (1996), “A Fast Quantum Mechanical Algorithm for Database Search”, Proceedings of the 28th ACM Symposium on Theory of Computing, 212–219.CrossRefGoogle Scholar
Haroche, Serge, and Raimond, J. M. (1996), “Quantum Computing: Dream or Nightmare?”, Quantum Computing: Dream or Nightmare? 8:51–52.Google Scholar
Hodges, Andrew (2005), “Can Quantum Computing Solve Classically Unsolvable Problems?”, quant-ph/0512248.Google Scholar
Hogarth, Mark (1994), “Non-Turing Computers and Non-Turing Computability”, in Hull, David, Forbes, Micky, and Burian, Richard M. (eds.), PSA 1994: Proceedings of the 1994 Biennial Meeting of the Philosophy of Science Association, Vol. 1. East Lansing, MI: Philosophy of Science Association, 126–138.Google Scholar
Jozsa, Richar (1997), “Entanglement and Quantum Computation”, in Hugget, S. et al. (eds.), Geometric Issues in the Foundations of Science. Oxford: Oxford University Press; quant-ph/9707034.Google Scholar
Kieu, Tien D. (2002), “Quantum Hypercomputability”, Quantum Hypercomputability 12:541–561.Google Scholar
Kieu, Tien D. (2003), “Computing the Noncomputable”, Computing the Noncomputable 44:51–71.Google Scholar
Kieu, Tien D. (2004), “A Reformulation of Hilbert’s Tenth Problem through Quantum Mechanics”, A Reformulation of Hilbert’s Tenth Problem through Quantum Mechanics A 460:1535–1545.Google Scholar
Kieu, Tien D. (2005), “An Anatomy of a Quantum Adiabatic Algorithm That Transcends the Turing Computability”, An Anatomy of a Quantum Adiabatic Algorithm That Transcends the Turing Computability 3:177–183.Google Scholar
Linden, Noah, and Popescu, Sandu (1999), “Good Dynamics versus Bad Kinematics: Is Entanglement Needed for Quantum Computation?”, Good Dynamics versus Bad Kinematics: Is Entanglement Needed for Quantum Computation? 87: 047901.Google Scholar
Messiah, A. (1961), Quantum Mechanics, Vol. 1. New York: Interscience.Google Scholar
Moore, Christopher (1990), “Unpredictability and Undecidability in Dynamical Systems”, Unpredictability and Undecidability in Dynamical Systems 64:2354–2357.Google ScholarPubMed
Nielsen, Michael A., and Chuang, Isaac L. (2000), Quantum Computation and Quantum Information. Cambridge: Cambridge University Press.Google Scholar
Pitowsky, Itamar (1990), “The Physical Church Thesis and Physical Computational Complexity”, The Physical Church Thesis and Physical Computational Complexity 39:81–99.Google Scholar
Pitowsky, Itamar (2002), “Quantum Speed–up of Computations”, Quantum Speed–up of Computations 69 (Symposium): S168–S177.Google Scholar
Pour-el, M., and Richards, I. (1981), “The Wave Equation with Computable Initial Data Such That Its Unique Solution Is Not Computable”, The Wave Equation with Computable Initial Data Such That Its Unique Solution Is Not Computable 39:215–239.Google Scholar
Reichardt, Ben W. (2004), “The Quantum Adiabatic Optimization Algorithm and Local Minima”, Proceedings of the 36th Symposium on Theory of Computing (STOC), 502–510.CrossRefGoogle Scholar
Shagrir, Oron, and Pitowsky, Itamar (2003), “Physical Hypercomputation and the Church-Turing Thesis”, Physical Hypercomputation and the Church-Turing Thesis 13:87–101.Google Scholar
Shor, Peter (1994), “Algorithms for Quantum Computation: Discrete Logarithms and Factoring”, Proceedings of 35th Annual Symposium on Foundations of Computer Science, 124–134.CrossRefGoogle Scholar
Smith, Warren D. (2005a), “Some Uncomputable Quantum Mechanical Tasks”, preprint.Google Scholar
Smith, Warren D. (2005b), “Three Counterexamples Refuting Kieu’s Plan for Quantum Adiabatic Hypercomputation”, preprint.CrossRefGoogle Scholar
Unruh, William G. (1995), “Maintaining Coherence in Quantum Computers”, Maintaining Coherence in Quantum Computers 51:992–997.Google ScholarPubMed
Van Dam, Wim, Mosca, Michele, and Vazirani, Umash (2002), “How Powerful Is Adiabatic Quantum Computation?”, quant-ph/0206003.CrossRefGoogle Scholar