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.
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.
Quantum computing's most consequential claim — that quantum computers provide exponential computational speedup over classical computation — rests on a specific physical assumption: that superposition is ontologically real, that a qubit genuinely and simultaneously occupies multiple states, and that quantum algorithms exploit this simultaneity as a physical resource. A quantum computer with n qubits is claimed to process 2ⁿ computational paths in parallel by virtue of this simultaneous occupation. This paper argues that all three foundational assumptions are precluded by Quantum-Geometry Dynamics (QGD), the physical theory derived from the Minimal Physically Derivable Theories (MPDT) framework established by the Uniqueness Theorem. In QGD, physical reality is strictly and absolutely deterministic. Every fundamental constituent — every preon(+) — has a definite position and definite intrinsic momentum at every moment. There are no indeterminate states, no superpositions, and no wave function collapse at the fundamental level. What quantum mechanics describes as superposition is not a physical state of simultaneous occupation but an epistemic description of ignorance of the deterministic microstate of a preonic configuration. The wave function is a probabilistic description of deterministic preonic dynamics — a calculational tool that correctly predicts statistical outcomes — not a description of a physical state in which a system genuinely occupies multiple configurations simultaneously. This distinction has a direct and specific consequence for quantum computing. Quantum computing devices are genuine physical systems that exploit real quantum mechanical phenomena — phenomena that QGD derives from the deterministic dynamics of preons(+) and preons(−) in the finite discrete preon(−) lattice. The MPDT framework does not forbid the construction or operation of quantum computing devices. What QGD precludes is the ontological foundation on which the exponential speedup argument rests. A quantum computing device is a deterministic preonic configuration occupying one microstate at each moment. The 2ⁿ simultaneous amplitude states of the quantum formalism are elements of a probabilistic description of that microstate — not physical states simultaneously instantiated in the device. Quantum parallelism is a feature of the formalism, not of the underlying physics. The paper develops this argument systematically across eight sections. Section 2 establishes QGD's account of quantum phenomena as emergent from deterministic preonic dynamics, including the derivation of wave-like interference patterns and Bell correlations without superposition. Section 3 examines precisely what superposition is and is not in QGD, culminating in the formal statement that a qubit in the state α|0⟩ + β|1⟩ is not a system simultaneously occupying both states but a deterministic preonic configuration whose microstate determines measurement outcomes but is not individually accessible at the observational level. Section 4 identifies the exact point at which the exponential speedup argument fails: the physical resource it invokes — simultaneous occupation of 2ⁿ states — does not exist in the physical universe that QGD describes. Sections 5 examines three specific quantum algorithms: Shor's factoring algorithm, whose polynomial-time complexity is demonstrated within the quantum formalism but whose underlying preonic complexity remains an open question; Grover's search algorithm, whose quadratic speedup rests on the same ontological assumption; and quantum simulation, which survives the critique more robustly because it does not require exponential parallelism as a resource. Section 6 addresses decoherence, reinterpreting it not as an engineering challenge to be solved by better isolation but as a fundamental feature of reality — the inevitable influence of the instantaneous gravitational field of the entire preon(−) lattice on every qubit configuration, which cannot be shielded against in principle. Sections 7 and 8 develop the implications for the quantum computing programme and conclude. The argument connects directly to the P vs NP analysis in the companion Physicality of Logic paper. Shor's algorithm is the canonical example of a quantum algorithm claimed to solve a classically hard problem — integer factoring — in polynomial time, with significant implications for the security of RSA encryption. If QGD is correct and the exponential speedup argument fails, the classical hardness of factoring is preserved and the cryptographic implications attributed to quantum computing do not follow. The paper does not claim that quantum computing devices are useless — it claims that the specific resource driving the most dramatic projections for quantum computing does not physically exist, and that whatever computational advantages quantum devices possess must be explained within the deterministic preonic framework rather than by appeal to quantum parallelism. The paper is intended for physicists working on quantum computing and quantum foundations, philosophers of physics, and computer scientists working on computational complexity. It is submitted to Foundations of Physics. It is a companion to the author's papers on the Uniqueness Theorem and the Physicality of Logic, and to the book Quantum-Geometry Dynamics: An Axiomatic Approach to Physics.
For quantum computation, we investigate the conjecture that the superposition of macroscopically distinct states is necessary for a large quantum speedup. Although this conjecture was supported for a circuit-based quantum computer performing Shor's factoring algorithm [A. Ukena and A. Shimizu, Phys. Rev. A69 (2004) 022301], it needs to be generalized for it to be applicable to a large class of algorithms and/or other models such as measurement-based quantum computers. To treat such general cases, we first generalize the indices for the superposition of macroscopically distinct states. We then generalize the conjecture, using the generalized indices, in such a way that it is unambiguously applicable to general models if a quantum algorithm achieves exponential speedup. On the basis of this generalized conjecture, we further extend the conjecture to Grover's quantum search algorithm, whose speedup is large but quadratic. It is shown that this extended conjecture is also correct. Since Grover's algorithm is a representative algorithm for unstructured problems, the present result further supports the conjecture.
The fundamental laws of classical mechanics, quantum mechanics, and general relativity are time-symmetric, yet macroscopic experience is irreversible without exception. Standard physics bridges this gap with statistical argument: reversal is treated as merely improbable, not physically inadmissible. This paper argues that the gap is an artifact of treating space as a continuum, and that it closes once space is treated as discrete, as in Quantum-Geometry Dynamics (QGD). Two independent grounds are identified for the categorical, non-statistical irreversibility of every elementary interaction in discrete space: a local ground, the loss of individual addressability when one particle's constituent preon(+)s merge into another upon absorption; and a global ground, the irreducible universal gravitational trace left by any positional change, given that gravity in QGD is instantaneous and universal in scope. Applied across four domains, this single result dissolves the arrow-of-time problem, grounds the second law of thermodynamics in dynamics rather than probability, dissolves the apparent asymmetry between unitary evolution and measurement collapse, and shows the reversible/irreversible distinction in quantum gate theory to be a feature of the abstract computational model rather than of physical mechanism. The result is shown to be compatible with, and silent on, whether a finite deterministic system's forward dynamics eventually revisit an earlier configuration by a non-retracing causal path. No new axiom or free parameter is introduced: the result follows from elements of QGD already established for independent reasons.
Grover’s algorithm is one of the primary algorithms offered as evidence that quantum computers can provide an advantage over classical computers. It involves an “oracle” (external quantum subroutine), which must be specified for a given application and whose internal structure is not part of the formal scaling of the quadratic quantum speedup guaranteed by the algorithm. Grover’s algorithm also requires exponentially many calls to the quantum oracle (approximately 2 n calls where n is the number of qubits) to succeed, raising the question of its implementation on both noisy and error-corrected quantum computers. In this work, we construct a quantum-inspired algorithm executable on a classical computer that performs Grover’s task in a linear number of calls to (simulations of) the oracle—an exponentially smaller number than Grover’s algorithm—and demonstrate this algorithm explicitly for Boolean satisfiability problems. The complexity of our algorithm depends on the cost to simulate the oracle once, which may or may not be exponential, depending on its internal structure. Indeed, Grover’s algorithm does not have an quantum speedup as soon as one is given access to the “source code” of the oracle, which may reveal an internal structure of the problem. Our findings illustrate this point explicitly, as our algorithm exploits the structure of the quantum circuit used to program the quantum computer to speed up the search. There are still problems where Grover’s algorithm would provide an asymptotic speedup if it could be run accurately for large enough sizes. Our quantum-inspired algorithm provides lower bounds, in terms of the quantum-circuit complexity, for the quantum hardware to beat classical approaches for these problems. These estimates, combined with the unfavorable scaling of the success probability of Grover’s algorithm, which in the presence of noise decays as the exponential of the exponential of the number of qubits, makes a practical speedup unrealistic even under extremely optimistic assumptions of the evolution of both hardware quality and availability. Published by the American Physical Society 2024
Quantum computing represents a revolutionary leap in computational power, leveraging the principles of quantum mechanics to process information in fundamentally new ways. Unlike classical computers, which use bits to represent data as 0s or 1s, quantum computers use quantum bits or qubits, enabling the phenomena of superposition and entanglement to perform complex calculations more efficiently (Nielsen & Chuang, 2010). This article explores the basic principles of quantum computing, the different models and algorithms that have been developed, and the current state of quantum hardware. The power of quantum computing lies in its ability to solve certain types of problems exponentially faster than classical computers. For instance, Shor's algorithm can factorize large integers in polynomial time, posing a significant threat to classical encryption methods (Shor, 1997). Similarly, Grover's algorithm provides a quadratic speedup for unstructured search problems, showcasing the potential for dramatic improvements in database search capabilities (Grover, 1996). These algorithms exemplify how quantum computing can revolutionize fields that rely on complex computations. Quantum hardware, however, is still in its nascent stage, with significant challenges to be overcome. Current quantum computers, such as those developed by IBM and Google, have demonstrated quantum supremacy but are limited by issues of qubit coherence and error rates (Arute et al., 2019). Quantum error correction and the development of more stable qubit technologies are critical areas of ongoing research (Preskill, 2018). Despite these challenges, recent advancements in quantum hardware and algorithms continue to drive the field forward, promising transformative impacts on industries such as cryptography, drug discovery, and artificial intelligence. As quantum computing continues to advance, it holds the promise of solving problems that are currently intractable for classical computers, paving the way for unprecedented technological and scientific advancements (Shor, 1997; Grover, 1996). This article provides a comprehensive overview of the current landscape of quantum computing, discussing its foundational principles, key algorithms, hardware challenges, and potential applications. By understanding these aspects, we can better appreciate the profound implications of quantum computing for the future of technology and science.
A quantum computer applies the axioms of quantum mechanics to efficiently run quantum algorithms, thereby performing calculations which, we speculate, would demand exponential time or memory on a classical computer. This thesis focuses on deriving better explanations of, and in the process improving upon, quantum algorithms and models of (a sub-theory of) the quantum mechanical foundations that dictate how quantum computers operate. Our contributions consist of three parts. First, we construct an efficient Einstein-Podolsky-Rosen(EPR)-complete hidden-variable model of the sub-theory of quantum mechanics given by the stabilizer formalism. Being EPR-complete means every element of physical reality is contained in the model. Next, we create a single-qubit rotation algorithm using the universal Toffoli gate. Our circuit requires only a logarithmic gate depth (and so a loga-rithmic number of Toffolis), substantially improving on previous algorithms. The circuit admits an efficient construction, that uses a comparison with a constant obtained through a trigonometric expression, and so the gate array can be constructed in polynomial time. We perform quantum state and process tomography on our algorithm when run on both a simulated and a real quantum computer, and analyze the results, attaining good estimates of our algorithm’s performance under various (both simulated and real) noise levels. Finally, we study Recursive Fourier Sampling (RFS): The quantum algorithm solving RFS is one of the first such appearing to give an advantage over any classical algorithm. By reformulating RFS in terms of which information its oracles write into the phase of the qubits, we show that the quantum algorithm solving RFS relies on the quantum computational resource of phase kickback, strengthening similar arguments made in related work. We show that this algorithm cannot be improved as the calculations carried out by the oracles must be uncomputed, lest random information gets written into the phase.