About this topic
Summary Quantum computing is contrasted with classical computing. The foundation of classical computing starts with a bit, a unit of information that can be in one of two states, 0 or 1. In quantum computing, the analogue of a bit is a qubit. For a qubit, 0 and 1 are just two possible states that a qubit could be in among others. The other possible physical states are motivated by possibilities of quantum systems such as superpositions. The idea behind a qubit as a means for computing has historically been speculative, but recent technological advances are bringing us closer to the realization of quantum computing. One of the main challenges in this area is to construct quantum systems that avoid decoherence as long as possible while manipulating the system. Another issue has to do with algorithms that serve as a foundation for security. If quantum computing systems are eventually constructed, they have the potential to undermine current encryption practices because many known intractable factoring problems would be turned into tractable ones.   Of more philosophical interest, the technological development of quantum computing has the potential to help us better understand the foundations of quantum physics.
Key works Much research was triggered by Shor 1994, who demonstrated how quantum algorithms could significantly speed up the factoring of large numbers into primes, and more generally exponentially speed up classical computation. Not everyone is so optimistic about the prospects of quantum speed ups, include Levin 2003
Introductions An introduction to the technical aspects of quantum computing and some of the philosophical issues can be found in Hagar & Cuffaro 2015.
Related categories

120 found
1 — 50 / 120
  1. Quantum Computing Since Democritus.Scott Aaronson - 2013 - Cambridge University Press.
    Takes students and researchers on a tour through some of the deepest ideas of maths, computer science and physics.
  2. Quantum Algorithms.D. Abrams & C. Williams - forthcoming - Complexity.
  3. Quantum Theory: Reconsideration of Foundations-3: Växjö, Sweden, 6-11 June 2005.Guillaume Adenier, A. I͡U Khrennikov & Theo M. Nieuwenhuizen (eds.) - 2006 - American Institute of Physics.
    This Växjö conference was devoted to the reconsideration of quantum foundations. Due to increasing research in quantum information theory, especially on quantum computing and cryptography, many questions regarding the foundations of quantum mechanics, which have long been considered to be exclusively of philosophical interest, nowadays play an important role in theoretical and experimental quantum physics.
  4. Processen, veranderingen en interacties in computerwetenschappen en quantumfysica: Verslag van de SLI-2003 workshop, gehouden te Brussel, op 31 maart 2003. [REVIEW]Patrick Allo - 2003 - Algemeen Nederlands Tijdschrift voor Wijsbegeerte 3.
  5. The Theoretical Foundations for Engineering a Conscious Quantum Computer.Richard L. Amoroso - 1997 - In M. Gams, M. Paprzycki & X. Wu (eds.), Mind Versus Computer: Were Dreyfus and Winograd Right? Amsterdam: IOS Press.
  6. Verschränkte Welt. Faszination der Quanten.Jürgen Audretsch (ed.) - 2002 - Wiley.
  7. Info-Computational Constructivism and Quantum Field Theory.G. Basti - 2014 - Constructivist Foundations 9 (2):242-244.
    Open peer commentary on the article “Info-computational Constructivism and Cognition” by Gordana Dodig-Crnkovic. Upshot: Dodig-Crnkovic’s “info-computational constructivism” (IC), as an essential part of a constructivist approach, needs integration with the logical, mathematical and physical evidence coming from quantum field theory (QFT) as the fundamental physics of the emergence of “complex systems” in all realms of natural sciences.
  8. Entangled Fields in Multiple Cavities as a Testing Ground for Quantum Mechanics.János A. Bergou - 1999 - Foundations of Physics 29 (4):503-519.
    Entangled states provide the necessary tools for conceptual tests of quantum mechanics and other alternative theories. These tests include local hidden variables theories, pre- and postselective quantum mechanics, QND measurements, complementarity, and tests of quantum mechanics itself against, e.g., the so-called causal communication constraint. We show how to produce various nonlocal entangled states of multiple cavity fields that are useful for these tests, using cavity QED techniques. First, we discuss the generation of the Bell basis states in two entangled cavities, (...)
  9. A Simple Example of “Quantum Darwinism”: Redundant Information Storage in Many-Spin Environments.Robin Blume-Kohout & Wojciech H. Zurek - 2005 - Foundations of Physics 35 (11):1857-1876.
  10. Perfect State Distinguishability and Computational Speedups with Postselected Closed Timelike Curves.Todd A. Brun & Mark M. Wilde - 2012 - Foundations of Physics 42 (3):341-361.
    Bennett and Schumacher’s postselected quantum teleportation is a model of closed timelike curves (CTCs) that leads to results physically different from Deutsch’s model. We show that even a single qubit passing through a postselected CTC (P-CTC) is sufficient to do any postselected quantum measurement with certainty, and we discuss an important difference between “Deutschian” CTCs (D-CTCs) and P-CTCs in which the future existence of a P-CTC might affect the present outcome of an experiment. Then, based on a suggestion of Bennett (...)
  11. Quantum Africa 2010: Theoretical and Experimental Foundations of Recent Quantum Technology, Umhlanga, South Africa, 20-23 September 2010. [REVIEW]Erwin Brüning, Thomas Konrad & F. Petruccione (eds.) - 2012 - American Institute of Physics.
    The conference Quantum Africa 2010 addressed recent advances, both theoretical and experimental, in the rapidly progressing field of quantum technologies. In particular progress in the foundations of quantum cryptography, quantum computing as well as quantum metrology was reported.
  12. Quantum Computation From a Quantum Logical Perspective.Jeffrey Bub - forthcoming - Philosophical Explorations.
  13. Quantum Computation: Where Does the Speed-Up Come From?Jeffrey Bub - 2010 - In Alisa Bokulich & Gregg Jaeger (eds.), Philosophy of Quantum Information and Entanglement. Cambridge University Press. pp. 231--246.
  14. Quantum Computation and Pseudotelepathic Games.Jeffrey Bub - 2008 - Philosophy of Science 75 (4):458-472.
    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 (...)
  15. Quantum Entanglement and Information.Jeffrey Bub - 2008 - Stanford Encyclopedia of Philosophy.
  16. On the Possibility of Quantum Informational Structural Realism.Terrell Ward Bynum - 2014 - Minds and Machines 24 (1):123-139.
    In The Philosophy of Information, Luciano Floridi presents an ontological theory of Being qua Being, which he calls “Informational Structural Realism”, a theory which applies, he says, to every possible world. He identifies primordial information (“dedomena”) as the foundation of any structure in any possible world. The present essay examines Floridi’s defense of that theory, as well as his refutation of “Digital Ontology” (which some people might confuse with his own). Then, using Floridi’s ontology as a starting point, the present (...)
  17. Is the Mind a Quantum Computer?Claudio Calosi - 2013 - Epistemologia 36 (2):194-206.
  18. Reflections on Quantum Computing.Christian S. Calude, Michael J. Dinneen & Karl Svozil - 2000 - Complexity 6 (1):35-37.
  19. Quantum Learning.Ronald Chrisley - 1995 - In P. Pyllkkänen & P. Pyllkkö (eds.), New Directions in Cognitive Science. Finnish Society for Artificial Intelligence.
  20. Learning in Non-Superpositional Quantum Neurocomputers.Ronald L. Chrisley - 1996 - In Paavo Pylkkänen & Pauli Pylkkö (eds.), Brain, Mind & Physics.
    A distinction is made between superpositional and non-superpositional quantum computers. The notion of quantum learning systems - quantum computers that modify themselves in order to improve their performance - is introduced. A particular non-superpositional quantum learning system, a quantum neurocomputer, is described: a conventional neural network implemented in a system which is a variation on the familiar two-slit apparatus from quantum physics. This is followed by a discussion of the advantages that quantum computers in general, and quantum neurocomputers in particular, (...)
  21. On Quantum Algorithms.Richard Cleve, Artur Ekert, Leah Henderson, Chiara Macchiavello & Michele Mosca - 1998 - Complexity 4 (1):33-42.
  22. Information Theoretic Representations of Qubit Channels.Tanner Crowder & Keye Martin - 2012 - Foundations of Physics 42 (7):976-983.
    A set of qubit channels has a classical representation when it is isomorphic to the convex closure of a group of classical channels. From Crowder and Martin (Proceedings of Quantum Physics and Logic, Electronic Notes in Theoretical Computer Science, 2009), we know that up to isomorphism there are five such sets, each corresponding to either a subgroup of the alternating group on four letters, or a subgroup of the symmetric group on three letters. In this paper, we show that the (...)
  23. On the Necessity of Entanglement for the Explanation of Quantum Speedup.Michael Cuffaro - manuscript
    Of the many and varied applications of quantum information theory, perhaps the most fascinating is the sub-field of quantum computation. In this sub-field, computational algorithms are designed which utilise the resources available in quantum systems in order to compute solutions to computational problems with, in some cases, exponentially fewer resources than any known classical algorithm. While the fact of quantum computational speedup is almost beyond doubt, the source of quantum speedup is still a matter of debate. In this paper I (...)
  24. Reconsidering No-Go Theorems From a Practical Perspective.Michael E. Cuffaro - 2018 - British Journal for the Philosophy of Science 69 (3):633-655.
    I argue that our judgements regarding the locally causal models that are compatible with a given constraint implicitly depend, in part, on the context of inquiry. It follows from this that certain quantum no-go theorems, which are particularly striking in the traditional foundational context, have no force when the context switches to a discussion of the physical systems we are capable of building with the aim of classically reproducing quantum statistics. I close with a general discussion of the possible implications (...)
  25. Universality, Invariance, and the Foundations of Computational Complexity in the Light of the Quantum Computer.Michael E. Cuffaro - 2018 - In Sven Ove Hansson (ed.), Technology and Mathematics: Philosophical and Historical Investigations. Springer. pp. 253-282.
    Computational complexity theory is a branch of computer science dedicated to classifying computational problems in terms of their difficulty. While computability theory tells us what we can compute in principle, complexity theory informs us regarding our practical limits. In this chapter I argue that the science of \emph{quantum computing} illuminates complexity theory by emphasising that its fundamental concepts are not model-independent, but that this does not, as some suggest, force us to radically revise the foundations of the theory. For model-independence (...)
  26. On the Significance of the Gottesman–Knill Theorem.Michael E. Cuffaro - 2017 - British Journal for the Philosophy of Science 68 (1):91-121.
    According to the Gottesman–Knill theorem, quantum algorithms that utilize only the operations belonging to a certain restricted set are efficiently simulable classically. Since some of the operations in this set generate entangled states, it is commonly concluded that entanglement is insufficient to enable quantum computers to outperform classical computers. I argue in this article that this conclusion is misleading. First, the statement of the theorem is, on reflection, already evident when we consider Bell’s and related inequalities in the context of (...)
  27. How-Possibly Explanations in (Quantum) Computer Science.Michael E. Cuffaro - 2015 - Philosophy of Science 82 (5):737-748.
    A primary goal of quantum computer science is to find an explanation for the fact that quantum computers are more powerful than classical computers. In this paper I argue that to answer this question is to compare algorithmic processes of various kinds and to describe the possibility spaces associated with these processes. By doing this, we explain how it is possible for one process to outperform its rival. Further, in this and similar examples little is gained in subsequently asking a (...)
  28. Review Of: Christopher G. Timpson, Quantum Information Theory and the Foundations of Quantum Mechanics. [REVIEW]Michael E. Cuffaro - 2014 - Philosophy of Science 81 (4):681-684,.
  29. On the Physical Explanation for Quantum Computational Speedup.Michael E. Cuffaro - 2013 - Dissertation, The University of Western Ontario
    The aim of this dissertation is to clarify the debate over the explanation of quantum speedup and to submit, for the reader's consideration, a tentative resolution to it. In particular, I argue, in this dissertation, that the physical explanation for quantum speedup is precisely the fact that the phenomenon of quantum entanglement enables a quantum computer to fully exploit the representational capacity of Hilbert space. This is impossible for classical systems, joint states of which must always be representable as product (...)
  30. Many Worlds, the Cluster-State Quantum Computer, and the Problem of the Preferred Basis.Michael E. Cuffaro - 2012 - Studies in History and Philosophy of Science Part B: Studies in History and Philosophy of Modern Physics 43 (1):35-42.
    I argue that the many worlds explanation of quantum computation is not licensed by, and in fact is conceptually inferior to, the many worlds interpretation of quantum mechanics from which it is derived. I argue that the many worlds explanation of quantum computation is incompatible with the recently developed cluster state model of quantum computation. Based on these considerations I conclude that we should reject the many worlds explanation of quantum computation.
  31. Physical Perspectives on Computation, Computational Perspectives on Physics.Michael E. Cuffaro & Samuel C. Fletcher (eds.) - 2018 - Cambridge University Press.
    Although computation and the science of physical systems would appear to be unrelated, there are a number of ways in which computational and physical concepts can be brought together in ways that illuminate both. This volume examines fundamental questions which connect scholars from both disciplines: is the universe a computer? Can a universal computing machine simulate every physical process? What is the source of the computational power of quantum computers? Are computational approaches to solving physical problems and paradoxes always fruitful? (...)
  32. The Algebraic Structure of an Approximately Universal System of Quantum Computational Gates.Maria Luisa Dalla Chiara, Roberto Giuntini, Hector Freytes, Antonio Ledda & Giuseppe Sergioli - 2009 - Foundations of Physics 39 (6):559-572.
  33. The Toffoli-Hadamard Gate System: An Algebraic Approach.Maria Luisa Dalla Chiara, Antonio Ledda, Giuseppe Sergioli & Roberto Giuntini - 2013 - Journal of Philosophical Logic 42 (3):467-481.
    Shi and Aharonov have shown that the Toffoli gate and the Hadamard gate give rise to an approximately universal set of quantum computational gates. The basic algebraic properties of this system have been studied in Dalla Chiara et al. (Foundations of Physics 39(6):559–572, 2009), where we have introduced the notion of Shi-Aharonov quantum computational structure. In this paper we propose an algebraic abstraction from the Hilbert-space quantum computational structures, by introducing the notion of Toffoli-Hadamard algebra. From an intuitive point of (...)
  34. On Bits and Quanta.Jean-Michel Delhôtel - 2001 - Studies in History and Philosophy of Science Part B: Studies in History and Philosophy of Modern Physics 32 (1):143-150.
  35. It From Qubit.David Deutsch - unknown
    Of John Wheeler’s ‘Really Big Questions’, the one on which the most progress has been made is It From Bit? – does information play a significant role at the foundations of physics? It is perhaps less ambitious than some of the other Questions, such as How Come Existence?, because it does not necessarily require a metaphysical answer. And unlike, say, Why The Quantum?, it does not require the discovery of new laws of nature: there was room for hope that it (...)
  36. Is Measurement a Black Box? On the Importance of Understanding Measurement Even in Quantum Information and Computation.Michael Dickson - 2007 - Philosophy of Science 74 (5):1019–1032.
    It has been argued, partly from the lack of any widely accepted solution to the measurement problem, and partly from recent results from quantum information theory, that measurement in quantum theory is best treated as a black box. However, there is a crucial difference between ‘having no account of measurement' and ‘having no solution to the measurement problem'. We know a lot about measurements. Taking into account this knowledge sheds light on quantum theory as a theory of information and computation. (...)
  37. Preface Special Issue Foundations of Physics.Dennis Dieks, Décio Krause & Christian de Ronde - 2014 - Foundations of Physics 44 (12):1245-1245.
    The foundations of quantum mechanics are attracting new and significant interest in the scientific community due to the recent striking experimental and technical progress in the fields of quantum computation, quantum teleportation and quantum information processing. However, at a more fundamental level the understanding and manipulation of these novel phenomena require not only new laboratory techniques but also new understanding, development and interpretation of the formalism of quantum mechanics itself, a mathematical structure whose connection to what happens in physical reality (...)
  38. Fermionic Linear Optics Revisited.David P. DiVincenzo & Barbara M. Terhal - 2005 - Foundations of Physics 35 (12):1967-1984.
    We provide an alternative view of the efficient classical simulatibility of fermionic linear optics in terms of Slater determinants. We investigate the generic effects of two-mode measurements on the Slater number of fermionic states. We argue that most such measurements are not capable (in conjunction with fermion linear optics) of an efficient exact implementation of universal quantum computation. Our arguments do not apply to the two-mode parity measurement, for which exact quantum computation becomes possible.
  39. Would the Existence of CTCs Allow for Nonlocal Signaling?Lucas Dunlap - 2017 - Erkenntnis:1-20.
    A recent paper from Brun et al. has argued that access to a closed timelike curve would allow for the possibility of perfectly distinguishing nonorthogonal quantum states. I show how this result can be used to develop a protocol for instantaneous nonlocal signaling, and detail the debate surround- ing these results. Several commenters have argued that nonlocal signaling must fail in this and in similar cases, for various reasons. I argue that each of these objections fails to rule out nonlocal (...)
  40. Editors' Introduction: The Third Life of Quantum Logic: Quantum Logic Inspired by Quantum Computing. [REVIEW]J. Michael Dunn, Lawrence S. Moss & Zhenghan Wang - 2013 - Journal of Philosophical Logic 42 (3):443-459.
  41. The Physics of Quantum Information: Quantum Cryptography, Quantum Teleportation, Quantum Computation - D. Bouwmeester, A. Ekert and A. Zeilinger (Eds.); Germany, 2000, 314pp, US$ 54, ISBN 3-540-66778-. [REVIEW]A. Duwell - 2003 - Studies in History and Philosophy of Science Part B: Studies in History and Philosophy of Modern Physics 34 (2):331-334.
  42. The Many‐Worlds Interpretation and Quantum Computation.Armond Duwell - 2007 - Philosophy of Science 74 (5):1007-1018.
    David Deutsch and others have suggested that the Many-Worlds Interpretation of quantum mechanics is the only interpretation capable of explaining the special efficiency quantum computers seem to enjoy over classical ones. I argue that this view is not tenable. Using a toy algorithm I show that the Many-Worlds Interpretation must crucially use the ontological status of the universal state vector to explain quantum computational efficiency, as opposed to the particular ontology of the MWI, that is, the computational histories of worlds. (...)
  43. Quantum Mechanics and Computation.Bart D’Hooghe & Jaroslaw Pykacz - 2004 - Foundations of Science 9 (4):387-404.
    In quantum computation non classical features such as superposition states and entanglement are used to solve problems in new ways, impossible on classical digital computers.We illustrate by Deutsch algorithm how a quantum computer can use superposition states to outperform any classical computer. We comment on the view of a quantum computer as a massive parallel computer and recall Amdahls law for a classical parallel computer. We argue that the view on quantum computation as a massive parallel computation disregards the presence (...)
  44. Structural Explanation From Special Relativity to Quantum Information Theory.Laura Felline - 2010 - In M. D'Agostino, G. Giorello & F. Laudisa (eds.), SILFS New Essays in Logic and Philosophy of Science. College Pubblications.
  45. A Triadic Theory of Elementary Particle Interactions and Quantum Computation (Review).Eliseo Fernández - 2008 - Transactions of the Charles S. Peirce Society 44 (2):pp. 384-389.
  46. Quantum Mechanical Computers.Richard P. Feynman - 1986 - Foundations of Physics 16 (6):507-531.
    The physical limitations, due to quantum mechanics, on the functioning of computers are analyzed.
  47. Quantum Probability and Cognitive Modeling: Some Cautions and a Promising Direction in Modeling Physics Learning.Donald R. Franceschetti & Elizabeth Gire - 2013 - Behavioral and Brain Sciences 36 (3):284-285.
    Quantum probability theory offers a viable alternative to classical probability, although there are some ambiguities inherent in transferring the quantum formalism to a less determined realm. A number of physicists are now looking at the applicability of quantum ideas to the assessment of physics learning, an area particularly suited to quantum probability ideas.
  48. Quantum Computational Structures: Categorical Equivalence for Square Root qMV -Algebras.Hector Freytes - 2010 - Studia Logica 95 (1-2):63 - 80.
    In this paper we investigate a categorical equivalence between square root qMV-algehras (a variety of algebras arising from quantum computation) and a category of preordered semigroups.
  49. The Theoretical Foundations for Engineering a Conscious Quantum Computer.M. Gams - 1997 - In Matjaz Gams (ed.), Mind Versus Computer: Were Dreyfus and Winograd Right? Amsterdam: Ios Press. pp. 43--141.
  50. Mind Versus Computer: Were Dreyfus and Winograd Right?Matjaz Gams (ed.) - 1997 - Amsterdam: IOS Press.
1 — 50 / 120