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:1009.5180 · Journal of the Physical Society of Japan

Necessity of Superposition of Macroscopically Distinct States for Quantum Computational Speedup

Akira Shimizu, Yuichiro Matsuzaki, Akihisa Ukena

Published Apr 15, 2013• 8 citations
arXivHTMLPDF

Abstract

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.

DOI
10.7566/jpsj.82.054801

Related papers

Macroscopic entanglement in Quantum Computation

Akihisa Ukena, Shimizu, Akira

We investigate macroscopic entanglement of quantum states in quantum computers, where we say a quantum state is entangled macroscopically if the state has superposition of macroscopically distinct states. The index $p$ of the macroscopic entanglement is calculated as a function of the step of the computation, for Grover's quantum search algorithm and Shor's factoring algorithm. It is found that whether macroscopically entangled states are used or not depends on the numbers and properties of the solutions to the problem to be solved. When the solutions are such that the problem becomes hard in the sense that classical algorithms take more than polynomial steps to find a solution, macroscopically entangled states are always used in Grover's algorithm and almost always used in Shor's algorithm. Since they are representative algorithms for unstructured and structured problems, respectively, our results support strongly the conjecture that quantum computers utilize macroscopically entangled states when they solve hard problems much faster than any classical algorithms.

arXiv:quant-ph/0505057•May 9, 2005•4 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

Superposition of Macroscopically Distinct States in Adiabatic Quantum Computation: A Necessary Condition for Quantum Speedup

Tatsuro Yuge

What are the conditions for adiabatic quantum computation (AQC) to outperform classical computation? Although there exist several quantum adiabatic algorithms achieving the strong quantum speedup, the essential keys to their speedups are still unclear. Here, we investigate the connection between superpositions of macroscopically distinct states and known examples of the speedup in AQC. To formalize this notion we consider an index $p$ that quantifies a superposition of macroscopically distinct states from the asymptotic behaviors of fluctuations of additive observables. We determine this index for five examples of adiabatic algorithms exhibiting various degrees of the speedup. The results suggest that the superposition of macroscopically distinct states is an appropriate indicator of entanglement crucial to the strong quantum speedup in AQC.

•May 23, 2017•0 citations

Generalized quantum search with parallelism

Robert M. Gingrich, Colin P. Williams, Nicolas J. Cerf

We generalize Grover's unstructured quantum search algorithm to enable it to work with arbitrary starting superpositions and arbitrary unitary operators. We show that the generalized quantum search algorithm, when cast in a special orthonormal basis, can be understood as performing an exact rotation of a starting superposition into a target superposition. We derive a formula for the success probability of the generalized quantum search algorithm after n rounds of amplitude amplification. We then use this formula to determine the optimal strategy for a punctuated quantum search algorithm, i.e., one in which the amplitude amplified state is observed before the point of maximum success probability. On average, the optimal strategy is about 12% better than the naive use of Grover's algorithm. The speedup obtained is not dramatic but it illustrates that a hybrid use of quantum computing and classical computing techniques can yield a performance that is better than either alone. In addition, we show that a punctuated quantum algorithm that takes the same average computation time as Grover's standard algorithm only requires half the coherence time. We then extend the analysis to the case of a society of k quantum searches acting in parallel. We derive an analytic formula that connects the degree of parallelism with the expected computation time for k-parallel quantum search. The resulting parallel speedup scales as $O(\sqrt{k}),$ while the minimum number of agents needed to ensure success, k, decreases as the inverse of the square of the achievable coherence time. This result has practical significance for the design of rudimentary quantum computers that are likely to have a limited coherence time.

arXiv:quant-ph/9904049•Physical Review A•Apr 19, 2000•41 citations

Evolution of Quantum Computing Based on Grover's Search Algorithm

Prakhar Shrivastava, Kapil Kumar Soni, Akhtar Rasool

Quantum computing introduces an efficient way for unfolding complex problems on computing systems. It uses concept of superposition and entanglement, & hence supports intrinsic parallelism for obtaining the speedup in context of time over classical computing. Quantum algorithms can be efficiently implemented over quantum computing system. Most popular quantum algorithms like Grover's and Shor's provide a great foundation to specifically design the algorithms. These algorithms work on improving the lower runtime bounds of classical algorithms. Grover's algorithm exhibits a quadratic polynomial speedup while searching an element among `N' elements unstructured database. The algorithmic strategy can be applied over various computer science related applications and some important are being considered in this article i.e. pattern matching, data mining and machine learning. This article explores quantum fundamentals; history based evolution followed by Grover's search algorithm in detail with cascading advantages, limitations & applications and also finally concludes with the significance of quantum computing & quantum algorithmic domains.

International Conference on Computing, Communication and Networking Technologies (ICCCNT)•Jul 1, 2019•18 citations

Superposition of Macroscopically Distinct States in Adiabatic Quantum Computation

Tatsuro Yuge

What are the conditions for adiabatic quantum computation (AQC) to outperform classical computation? Although there exist several quantum adiabatic algorithms achieving the strong quantum speedup, the essential keys to their speedups are still unclear. Here, we investigate the connection between superpositions of macroscopically distinct states and known examples of the speedup in AQC. To formalize this notion we consider an index $p$ that quantifies a superposition of macroscopically distinct states from the asymptotic behaviors of fluctuations of additive observables. We determine this index for five examples of adiabatic algorithms exhibiting various degrees of the speedup. The results suggest that the superposition of macroscopically distinct states is an appropriate indicator of entanglement crucial to the strong quantum speedup in AQC.

arXiv:1705.08117•Journal of the Physical Society of Japan•Nov 13, 2018•2 citations
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.
We investigate macroscopic entanglement of quantum states in quantum computers, where we say a quantum state is entangled macroscopically if the state has superposition of macroscopically distinct states. The index ppp of the macroscopic entanglement is calculated as a function of the step of the computation, for Grover's quantum search algorithm and Shor's factoring algorithm. It is found that whether macroscopically entangled states are used or not depends on the numbers and properties of the solutions to the problem to be solved. When the solutions are such that the problem becomes hard in the sense that classical algorithms take more than polynomial steps to find a solution, macroscopically entangled states are always used in Grover's algorithm and almost always used in Shor's algorithm. Since they are representative algorithms for unstructured and structured problems, respectively, our results support strongly the conjecture that quantum computers utilize macroscopically entangled states when they solve hard problems much faster than any classical algorithms.
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.
What are the conditions for adiabatic quantum computation (AQC) to outperform classical computation? Although there exist several quantum adiabatic algorithms achieving the strong quantum speedup, the essential keys to their speedups are still unclear. Here, we investigate the connection between superpositions of macroscopically distinct states and known examples of the speedup in AQC. To formalize this notion we consider an index ppp that quantifies a superposition of macroscopically distinct states from the asymptotic behaviors of fluctuations of additive observables. We determine this index for five examples of adiabatic algorithms exhibiting various degrees of the speedup. The results suggest that the superposition of macroscopically distinct states is an appropriate indicator of entanglement crucial to the strong quantum speedup in AQC.
We generalize Grover's unstructured quantum search algorithm to enable it to work with arbitrary starting superpositions and arbitrary unitary operators. We show that the generalized quantum search algorithm, when cast in a special orthonormal basis, can be understood as performing an exact rotation of a starting superposition into a target superposition. We derive a formula for the success probability of the generalized quantum search algorithm after n rounds of amplitude amplification. We then use this formula to determine the optimal strategy for a punctuated quantum search algorithm, i.e., one in which the amplitude amplified state is observed before the point of maximum success probability. On average, the optimal strategy is about 12% better than the naive use of Grover's algorithm. The speedup obtained is not dramatic but it illustrates that a hybrid use of quantum computing and classical computing techniques can yield a performance that is better than either alone. In addition, we show that a punctuated quantum algorithm that takes the same average computation time as Grover's standard algorithm only requires half the coherence time. We then extend the analysis to the case of a society of k quantum searches acting in parallel. We derive an analytic formula that connects the degree of parallelism with the expected computation time for k-parallel quantum search. The resulting parallel speedup scales as O(k),O(\sqrt{k}),O(k​), while the minimum number of agents needed to ensure success, k, decreases as the inverse of the square of the achievable coherence time. This result has practical significance for the design of rudimentary quantum computers that are likely to have a limited coherence time.
Quantum computing introduces an efficient way for unfolding complex problems on computing systems. It uses concept of superposition and entanglement, & hence supports intrinsic parallelism for obtaining the speedup in context of time over classical computing. Quantum algorithms can be efficiently implemented over quantum computing system. Most popular quantum algorithms like Grover's and Shor's provide a great foundation to specifically design the algorithms. These algorithms work on improving the lower runtime bounds of classical algorithms. Grover's algorithm exhibits a quadratic polynomial speedup while searching an element among `N' elements unstructured database. The algorithmic strategy can be applied over various computer science related applications and some important are being considered in this article i.e. pattern matching, data mining and machine learning. This article explores quantum fundamentals; history based evolution followed by Grover's search algorithm in detail with cascading advantages, limitations & applications and also finally concludes with the significance of quantum computing & quantum algorithmic domains.
What are the conditions for adiabatic quantum computation (AQC) to outperform classical computation? Although there exist several quantum adiabatic algorithms achieving the strong quantum speedup, the essential keys to their speedups are still unclear. Here, we investigate the connection between superpositions of macroscopically distinct states and known examples of the speedup in AQC. To formalize this notion we consider an index ppp that quantifies a superposition of macroscopically distinct states from the asymptotic behaviors of fluctuations of additive observables. We determine this index for five examples of adiabatic algorithms exhibiting various degrees of the speedup. The results suggest that the superposition of macroscopically distinct states is an appropriate indicator of entanglement crucial to the strong quantum speedup in AQC.