Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1304.0208

On the Physical Explanation for Quantum Computational Speedup

Michael E. Cuffaro

Published Mar 31, 2013• 2 citations
arXivHTMLPDF

Abstract

The aim of this dissertation is to clarify the debate over the explanation of quantum speedup and to submit a tentative resolution to it. In particular, I argue 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 states. Chapter 2 begins with a discussion of the most popular of the candidate physical explanations for quantum speedup: the many worlds explanation. I argue that unlike the neo-Everettian interpretation of quantum mechanics it does not have the conceptual resources required to overcome the `preferred basis objection'. I further argue that the many worlds explanation, at best, can serve as a good description of the physical process which takes place in so-called network-based computation, but that it is incompatible with other models of computation such as cluster state quantum computing. I next consider, in Chapter 3, a common component of most other candidate explanations of quantum speedup: quantum entanglement. I investigate whether entanglement can be said to be a necessary component of any explanation for quantum speedup, and I consider two major purported counter-examples to this claim. I argue that neither of these, in fact, show that entanglement is unnecessary for speedup, and that, on the contrary, we should conclude that it is. In Chapters 4 and 5 I then ask whether entanglement can be said to be sufficient as well. In Chapter 4 I argue that despite a result that seems to indicate the contrary, entanglement, considered as a resource, can be seen as sufficient to enable quantum speedup. Finally, in Chapter 5 I argue that entanglement is sufficient to explain quantum speedup as well.

DOI
10.48550/arxiv.1304.0208

Related papers

Reflections on the Role of Entanglement in the Explanation of Quantum Computational Speedup

Michael E. Cuffaro

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 argue that entanglement is a necessary component for any explanation of quantum speedup and I address some purported counter-examples that some claim show that the contrary is true. In particular, I address Biham et al.'s mixed-state version of the Deutsch-Jozsa algorithm, and Knill \& Laflamme's deterministic quantum computation with one qubit (DQC1) model of quantum computation. I argue that these examples do not demonstrate that entanglement is unnecessary for the explanation of quantum speedup, but that they rather illuminate and clarify the role that entanglement does play.

•Dec 6, 2011•0 citations

On the Necessity of Entanglement for the Explanation of Quantum Speedup

Michael E. Cuffaro

In this paper I argue that entanglement is a necessary component for any explanation of quantum speedup and I address some purported counter-examples that some claim show that the contrary is true. In particular, I address Biham et al.'s mixed-state version of the Deutsch-Jozsa algorithm, and Knill & Laflamme's deterministic quantum computation with one qubit (DQC1) model of quantum computation. I argue that these examples do not demonstrate that entanglement is unnecessary for the explanation of quantum speedup, but that they rather illuminate and clarify the role that entanglement does play.

arXiv:1112.1347•Dec 6, 2011•2 citations

Exploring Quantum Speed-up Through Cluster-state Computers

Filippo Annovi

The aim of this thesis is to investigate the nature of quantum computation and the question of the quantum speed-up over classical computation by comparing two different quantum computational frameworks, the traditional quantum circuit model and the cluster-state quantum computer. After an introductory survey of the theoretical and epistemological questions concerning quantum computation, the first part of this thesis provides a presentation of cluster-state computation suitable for a philosophical audience. In spite of the computational equivalence between the two frameworks, their differences can be considered as structural. Entanglement is shown to play a fundamental role in both quantum circuits and cluster-state computers; this supports, from a new perspective, the argument that entanglement can reasonably explain the quantum speed-up over classical computation. However, quantum circuits and cluster-state computers diverge with regard to one of the explanations of quantum computation that actually accords a central role to entanglement, i.e. the Everett interpretation. It is argued that, while cluster-state quantum computation does not show an Everettian failure in accounting for the computational processes, it threatens that interpretation of being not-explanatory. This analysis presented here should be integrated in a more general work in order to include also further frameworks of quantum computation, e.g. topological quantum computation. However, what is revealed by this work is that the speed-up question does not capture all that is at stake: both quantum circuits and cluster-state computers achieve the speed-up, but the challenges that they posit go besides that specific question. Then, the existence of alternative equivalent quantum computational models suggests that the ultimate question should be moved from the speed-up to a sort of “representation theorem” for quantum computation, to be meant as the general goal of identifying the physical features underlying these alternative frameworks that allow for labelling those frameworks as “quantum computation”.

•Jan 1, 2015•0 citations

Is Entanglement Sufficient to Enable Quantum Speedup?

Michael E. Cuffaro

According to the Gottesman-Knill theorem, any quantum algorithm utilising operations chosen exclusively from a particular restricted set are efficiently simulable by a classical computer. Since some of these algorithms involve entangled states, it is commonly concluded that entanglement is insufficient to enable quantum speedup. As I explain, however, the operations belonging to this set are precisely those which will never yield a violation of the Bell inequalities. Thus it should be no surprise that entangled quantum states which only undergo operations in this set are efficiently simulable classically. What the Gottesman-Knill theorem shows us is that it is possible to use an entangled state to less than its full potential. Nevertheless, there is a meaningful sense in which entanglement is sufficient for quantum speedup: an entangled quantum state provides sufficient physical resources to enable quantum speedup, whether or not one elects to use these resources fully.

arXiv:1207.5236•Jul 22, 2012•0 citations

The Physical Impossibility of Quantum Computational Speedup

Daniel Burnstein

The Physical Impossibility of Quantum Computational Speedup: Two Independent Arguments from Quantum-Geometry Dynamics Quantum computing promises computational advantages that are, in the most celebrated cases, exponential. Shor's algorithm factors integers exponentially faster than the best known classical algorithm; Grover's algorithm searches an unstructured database with a quadratic speedup. These results are mathematically rigorous within their assumed framework. This paper asks not whether the mathematics is correct but whether the physical assumptions underlying it are. I argue that Quantum-Geometry Dynamics (QGD) — an axiomatic framework for physics derived from the discreteness of space and the kinetic nature of matter — establishes two independent foundational preclusions of quantum computational speedup. These are not engineering obstacles or decoherence problems that better technology can overcome. They are consequences of the physical structure of discrete space, and no improvement in qubit isolation, error correction, or fabrication technique can supply a physical resource that does not exist. The first preclusion concerns physical states. In QGD, matter is composed of preons⁺ that propagate through quantum-geometrical space by preonic leaps, each of which is a definite transition from one spatial unit to the next in the direction of the momentum vector. A preon(+) always occupies a definite position. There is no ontological superposition. What quantum mechanics represents as a superposed state is, in QGD, an epistemic description of our ignorance of the system's actual preonic microstate. Since ontological superposition is the physical resource on which quantum parallelism depends, its absence means that no physical system can instantiate the state required for exponential speedup. The second preclusion concerns physical processes. Causal succession in discrete space is categorically and structurally irreversible: every preonic leap has a definite direction, and no physical process can reverse the causal order of preonic states. This is not thermodynamic irreversibility arising from large numbers but a property of every individual preonic transition. Since the quantum circuit model is built on reversible unitary gates, and reversible computation has no physical instantiation in a discrete-space framework, the operational basis of quantum computing is equally precluded. I show how both arguments bite at specific steps in Shor's algorithm and Grover's algorithm. In Shor's algorithm, the first preclusion destroys the state preparation step and the second destroys the quantum Fourier transform. In Grover's algorithm, the first preclusion destroys the uniform superposition and the second destroys the diffusion operator and oracle. Either preclusion alone is sufficient; together they attack quantum speedup at both ends — what goes in and how it is processed. The black hole information paradox, correctly understood within QGD, provides independent confirmation: the paradox dissolves precisely because physical states are always definite and physical evolution is categorically irreversible — the same two features that preclude quantum speedup. The Uniqueness Theorem for QGD further strengthens the claim: if the two-axiom discrete-space structure is the unique viable foundational description of physical reality, these preclusions are not features of one possible framework among many but consequences of the physical structure of the universe. This paper supersedes the earlier paper Quantum Computing Under Quantum-Geometry Dynamics (Zenodo, DOI: 10.5281/zenodo.19522137) and should be read in its place. This paper is part of the Minimal Physically Derivable Theory (MPDT) programme.

•Apr 17, 2026•0 citations

The Many-Worlds Interpretation and Quantum Computation

Armond Duwell

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. As such, any other interpretation that treats the state vector as representing real ontological features of a system can explain quantum speedup too.

Philosophy of Science•Dec 1, 2007•14 citations
The aim of this dissertation is to clarify the debate over the explanation of quantum speedup and to submit a tentative resolution to it. In particular, I argue 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 states. Chapter 2 begins with a discussion of the most popular of the candidate physical explanations for quantum speedup: the many worlds explanation. I argue that unlike the neo-Everettian interpretation of quantum mechanics it does not have the conceptual resources required to overcome the `preferred basis objection'. I further argue that the many worlds explanation, at best, can serve as a good description of the physical process which takes place in so-called network-based computation, but that it is incompatible with other models of computation such as cluster state quantum computing. I next consider, in Chapter 3, a common component of most other candidate explanations of quantum speedup: quantum entanglement. I investigate whether entanglement can be said to be a necessary component of any explanation for quantum speedup, and I consider two major purported counter-examples to this claim. I argue that neither of these, in fact, show that entanglement is unnecessary for speedup, and that, on the contrary, we should conclude that it is. In Chapters 4 and 5 I then ask whether entanglement can be said to be sufficient as well. In Chapter 4 I argue that despite a result that seems to indicate the contrary, entanglement, considered as a resource, can be seen as sufficient to enable quantum speedup. Finally, in Chapter 5 I argue that entanglement is sufficient to explain quantum speedup as well.
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 argue that entanglement is a necessary component for any explanation of quantum speedup and I address some purported counter-examples that some claim show that the contrary is true. In particular, I address Biham et al.'s mixed-state version of the Deutsch-Jozsa algorithm, and Knill \& Laflamme's deterministic quantum computation with one qubit (DQC1) model of quantum computation. I argue that these examples do not demonstrate that entanglement is unnecessary for the explanation of quantum speedup, but that they rather illuminate and clarify the role that entanglement does play.
In this paper I argue that entanglement is a necessary component for any explanation of quantum speedup and I address some purported counter-examples that some claim show that the contrary is true. In particular, I address Biham et al.'s mixed-state version of the Deutsch-Jozsa algorithm, and Knill & Laflamme's deterministic quantum computation with one qubit (DQC1) model of quantum computation. I argue that these examples do not demonstrate that entanglement is unnecessary for the explanation of quantum speedup, but that they rather illuminate and clarify the role that entanglement does play.
The aim of this thesis is to investigate the nature of quantum computation and the question of the quantum speed-up over classical computation by comparing two different quantum computational frameworks, the traditional quantum circuit model and the cluster-state quantum computer. After an introductory survey of the theoretical and epistemological questions concerning quantum computation, the first part of this thesis provides a presentation of cluster-state computation suitable for a philosophical audience. In spite of the computational equivalence between the two frameworks, their differences can be considered as structural. Entanglement is shown to play a fundamental role in both quantum circuits and cluster-state computers; this supports, from a new perspective, the argument that entanglement can reasonably explain the quantum speed-up over classical computation. However, quantum circuits and cluster-state computers diverge with regard to one of the explanations of quantum computation that actually accords a central role to entanglement, i.e. the Everett interpretation. It is argued that, while cluster-state quantum computation does not show an Everettian failure in accounting for the computational processes, it threatens that interpretation of being not-explanatory. This analysis presented here should be integrated in a more general work in order to include also further frameworks of quantum computation, e.g. topological quantum computation. However, what is revealed by this work is that the speed-up question does not capture all that is at stake: both quantum circuits and cluster-state computers achieve the speed-up, but the challenges that they posit go besides that specific question. Then, the existence of alternative equivalent quantum computational models suggests that the ultimate question should be moved from the speed-up to a sort of “representation theorem” for quantum computation, to be meant as the general goal of identifying the physical features underlying these alternative frameworks that allow for labelling those frameworks as “quantum computation”.
According to the Gottesman-Knill theorem, any quantum algorithm utilising operations chosen exclusively from a particular restricted set are efficiently simulable by a classical computer. Since some of these algorithms involve entangled states, it is commonly concluded that entanglement is insufficient to enable quantum speedup. As I explain, however, the operations belonging to this set are precisely those which will never yield a violation of the Bell inequalities. Thus it should be no surprise that entangled quantum states which only undergo operations in this set are efficiently simulable classically. What the Gottesman-Knill theorem shows us is that it is possible to use an entangled state to less than its full potential. Nevertheless, there is a meaningful sense in which entanglement is sufficient for quantum speedup: an entangled quantum state provides sufficient physical resources to enable quantum speedup, whether or not one elects to use these resources fully.
The Physical Impossibility of Quantum Computational Speedup: Two Independent Arguments from Quantum-Geometry Dynamics Quantum computing promises computational advantages that are, in the most celebrated cases, exponential. Shor's algorithm factors integers exponentially faster than the best known classical algorithm; Grover's algorithm searches an unstructured database with a quadratic speedup. These results are mathematically rigorous within their assumed framework. This paper asks not whether the mathematics is correct but whether the physical assumptions underlying it are. I argue that Quantum-Geometry Dynamics (QGD) — an axiomatic framework for physics derived from the discreteness of space and the kinetic nature of matter — establishes two independent foundational preclusions of quantum computational speedup. These are not engineering obstacles or decoherence problems that better technology can overcome. They are consequences of the physical structure of discrete space, and no improvement in qubit isolation, error correction, or fabrication technique can supply a physical resource that does not exist. The first preclusion concerns physical states. In QGD, matter is composed of preons⁺ that propagate through quantum-geometrical space by preonic leaps, each of which is a definite transition from one spatial unit to the next in the direction of the momentum vector. A preon(+) always occupies a definite position. There is no ontological superposition. What quantum mechanics represents as a superposed state is, in QGD, an epistemic description of our ignorance of the system's actual preonic microstate. Since ontological superposition is the physical resource on which quantum parallelism depends, its absence means that no physical system can instantiate the state required for exponential speedup. The second preclusion concerns physical processes. Causal succession in discrete space is categorically and structurally irreversible: every preonic leap has a definite direction, and no physical process can reverse the causal order of preonic states. This is not thermodynamic irreversibility arising from large numbers but a property of every individual preonic transition. Since the quantum circuit model is built on reversible unitary gates, and reversible computation has no physical instantiation in a discrete-space framework, the operational basis of quantum computing is equally precluded. I show how both arguments bite at specific steps in Shor's algorithm and Grover's algorithm. In Shor's algorithm, the first preclusion destroys the state preparation step and the second destroys the quantum Fourier transform. In Grover's algorithm, the first preclusion destroys the uniform superposition and the second destroys the diffusion operator and oracle. Either preclusion alone is sufficient; together they attack quantum speedup at both ends — what goes in and how it is processed. The black hole information paradox, correctly understood within QGD, provides independent confirmation: the paradox dissolves precisely because physical states are always definite and physical evolution is categorically irreversible — the same two features that preclude quantum speedup. The Uniqueness Theorem for QGD further strengthens the claim: if the two-axiom discrete-space structure is the unique viable foundational description of physical reality, these preclusions are not features of one possible framework among many but consequences of the physical structure of the universe. This paper supersedes the earlier paper Quantum Computing Under Quantum-Geometry Dynamics (Zenodo, DOI: 10.5281/zenodo.19522137) and should be read in its place. This paper is part of the Minimal Physically Derivable Theory (MPDT) programme.
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. As such, any other interpretation that treats the state vector as representing real ontological features of a system can explain quantum speedup too.