Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-12-05T03:18:36.678Z Has data issue: false hasContentIssue false
  • English
  • Français

Quantum Computation and Pseudotelepathic Games

Published online by Cambridge University Press:  01 January 2022

Jeffrey Bub
Get access Rights & Permissions [Opens in a new window]

Abstract

A quantum algorithm succeeds not because the superposition principle allows ‘the computation of all values of a function at once’ via ‘quantum parallelism’, but rather because the structure of a quantum state space allows new sorts of correlations associated with entanglement, with new possibilities for information-processing transformations between correlations, that are not possible in a classical state space. I illustrate this with an elementary example of a problem for which a quantum algorithm is more efficient than any classical algorithm. I also introduce the notion of ‘pseudotelepathic’ games and show how the difference between classical and quantum correlations plays a similar role here for games that can be won by quantum players exploiting entanglement, but not by classical players whose only allowed common resource consists of shared strings of random numbers (common causes of the players’ correlated responses in a game).

Type
Research Article
Information
Philosophy of Science , Volume 75 , Issue 4 , October 2008 , pp. 458 - 472
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.)

References

Bengtsson, Ingemar, and Życzkowski, Karol (2006), Geometry of Quantum States: An Introduction to Quantum Entanglement. Cambridge: Cambridge University Press.CrossRefGoogle Scholar
Brassard, Gilles, Broadbent, Anne, and Tapp, Alain (2004), “Quantum Pseudo-Telepathy”, arXiv: quant-ph/0407221v3.Google Scholar
Brassard, Gilles, Cleve, Richard, and Tapp, Alain (1999), “Cost of Exactly Simulating Quantum Entanglement with Classical Communication”, Cost of Exactly Simulating Quantum Entanglement with Classical Communication 83:1874–1877.Google Scholar
Bub, Jeffrey (2007), “Quantum Computation from a Quantum Logical Perspective”, Quantum Computation from a Quantum Logical Perspective 7:281–296.Google Scholar
Buhrman, H., Cleve, R., and Widgerson, A. (1998), “Quantum vs. Classical Communication and Computation”, in Jeffrey Vitter (chairman), Proceedings of the 30th Annual ACM Symposium on Theory of Computing, 63–68.CrossRefGoogle Scholar
Clauser, John F., Horne, Michael A., Shimony, Abner, and Holt, Richard A. (1969), “Proposed Experiment to Test Local Hidden Variable Theories”, Proposed Experiment to Test Local Hidden Variable Theories 23:880–883.Google Scholar
Cleve, Richard, Ekert, Artur, Machiavello, Chiara, and Mosca, Michele (1997),“Quantum Algorithms Revisited”, Quantum Algorithms Revisited 454:339–354.Google Scholar
Deutsch, David (1985), “Quantum Theory, the Church-Turing Principle, and the Universal Quantum Computer”, Quantum Theory, the Church-Turing Principle, and the Universal Quantum Computer 400: 497.Google Scholar
Deutsch, David (1997), The Fabric of Reality. London: Penguin.Google Scholar
Deutsch, David, and Jozsa, Richard (1992), “Rapid Solution of Problems by Quantum Computation”, Rapid Solution of Problems by Quantum Computation 439:553–558.Google Scholar
Galliard, V., and Wolf, S. (2002), “Pseudo-Telepathy, Entanglement, and Graph Colorings”, in Proceedings of the 2002 IEEE International Symposium on Information Theory, 101.Google Scholar
Galliard, V., Wolf, S., and Tapp, A. (2003), “The Impossibility of Pseudo-Telepathy without Entanglement”, in Proceedings of the IEEE International Symposium on Information Theory, 457.CrossRefGoogle Scholar
Greenberger, D. M., Horne, M. A., and Zeilinger, A. (1989), “Going beyond Bell's Theorem”, in Kafatos, M. (ed.), Bell's Theorem, Quantum Theory, and Conceptions of the Universe. Dordrecht: Kluwer Academic, 69–72.Google Scholar
Heywood, P., and Redhead, Michael (1983), “Nonlocality and the Kochen-Specker Paradox”, Nonlocality and the Kochen-Specker Paradox 13:481–499.Google Scholar
Mermin, N. David (1990), “Quantum Mysteries Revisited”, Quantum Mysteries Revisited 58:731–743.Google Scholar
Nielsen, Michael A., and Chuang, Isaac (2000), Quantum Computation and Quantum Information. Cambridge: Cambridge University Press.Google Scholar
Pitowsky, Itamar (1989), Quantum Probability, Quantum Logic. Berlin: Springer.Google Scholar
Shor, Peter W. (1994), “Algorithms for Quantum Computation: Discrete Logarithms and Factoring”, in Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 124–134.CrossRefGoogle Scholar
Shor, Peter W. (1997), “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer 26:1484–1509.Google Scholar
Stairs, Allen (1978), Quantum Mechanics, Logic, and Reality. PhD dissertation. London: University of Western Ontario.Google Scholar
Steane, Andrew (2003), “A Quantum Computer Only Needs One Universe”, A Quantum Computer Only Needs One Universe 34:469–478.Google Scholar
Tsirelson, B. S. (1980), “Quantum Generalizations of Bell's Inequality”, Quantum Generalizations of Bell's Inequality 4:93–100.Google Scholar