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

Theory of the Quantum Speed Up

Castagnoli, G C, Finkelstein, D R

Published Oct 23, 2000• 14 citations
OpenAlex

Abstract

Insofar as quantum computation is faster than classical, it appears to be irreversible. In all quantum algorithms found so far the speed-up depends on the extra-dynamical irreversible projection representing quantum measurement. Quantum measurement performs a computation that dynamical computation cannot accomplish as efficiently.

Related papers

Theory of the Quantum Speed Up

Giuseppe Castagnoli, David Finkelstein

Insofar as quantum computation is faster than classical, it appears to be irreversible. In all quantum algorithms found so far the speed-up depends onthe extra-dynamical irreversible projection representing quantum measurement. Quantum measurement performs a computation that dynamical computation cannot accomplish as efficiently. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Kluwer Academic Publishers eBooks•Feb 24, 2006•2 citations

Theory of the quantum speed-up

Giuseppe Castagnoli, David Ritz Finkelstein

We analyse the quantum speed-up: the fact that some quantum algorithms are faster than their classical counterparts. The classical formulation of problem solving must be modified. In general a problem statement defines the solution only implicitly, giving a property that a solution must possess, and does not represent a process that constructs the solution explicitly. A solution algorithm must then specify explicitly a finite step-by-step procedure that constructs the solution through a dynamical development. In the quantum speed-up, however, an implicit definition directly determines the solution through an extra-dynamical irreversible non-algorithmic quantum measurement. While in an algorithmic solution, the initial conditions determine the solution in a one-way manner, in a solution by measurement, the initial conditions and a final condition influence the solution jointly. The quantum computation is as implicit as the problem statement. Implicit determination with joint influence is richer than explicit one-way dynamical determination, as it yields the speed-up. Quantum problem solving with speed-up is essentially extra-dynamical and irreversible. Other forms of implicit quantum problem solving may exploit extra-dynamical projections for speed-up.

arXiv:quant-ph/0010081•Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences•Jul 8, 2001•16 citations

Introduction to Quantum Algorithms

Peter W. Shor

These notes discuss the quantum algorithms we know of that can solve problems significantly faster than the corresponding classical algorithms. So far, we have only discovered a few techniques which can produce speed up versus classical algorithms. It is not clear yet whether the reason for this is that we do not have enough intuition to discover more techniques, or that there are only a few problems for which quantum computers can significantly speed up the solution.

arXiv:quant-ph/0005003•Apr 29, 2000•78 citations

A Quantum Computer Is Not a Faster Computer

Emilio Billi

A Quantum Computer Is Not a Faster Computer examines one of the most persistent misconceptions surrounding quantum computing: the idea that a quantum computer is simply a faster version of a classical computer. The paper explains why quantum computation represents a fundamentally different computational paradigm, based on superposition, interference, entanglement, measurement, and problem-specific quantum algorithms rather than on a generalized increase in processing speed. It distinguishes computational speed from computational complexity and shows why quantum advantage applies only to particular classes of problems for which quantum algorithms can exploit mathematical structures inaccessible, or prohibitively expensive, to classical approaches. The work also discusses the practical limitations of current quantum systems, including decoherence, error correction, qubit quality, scalability, and the continuing role of classical computing. It argues that the future of computing is therefore more accurately understood as a heterogeneous ecosystem in which classical, accelerated, and quantum architectures coexist and complement one another. The paper is intended to provide a technically rigorous yet accessible conceptual framework for understanding what quantum computers actually are, where their potential advantage originates, and why describing them merely as “faster computers” fundamentally misrepresents their nature.

•Aug 17, 2026•0 citations

Quantum computation: Where does the speed-up come from?

Jeffrey Bub

Introduction Discussions of quantum-computational algorithms in the literature refer to various features of quantum mechanics as the source of the exponential speed-up relative to classical algorithms: superposition and entanglement, the fact that the state space of n bits is a space of 2 n states while the state space of n qubits is a space of 2 n dimensions, the possibility of computing all values of a function in a single computational step by “quantum parallelism,” or the possibility of an efficient implementation of the discrete quantum Fourier transform. Here I propose a different answer to the question posed in the title, in terms of the difference between classical logic and quantum logic, i.e., the difference between the Boolean classical event structure and the non-Boolean quantum event structure. In a nutshell, the ultimate source of the speed-up is the difference between a classical disjunction, which is true (or false) in virtue of the truth values of the disjuncts, and a quantum disjunction, which can be true (or false) even if none of the disjuncts is either true or false. In the following, I will discuss the information-processing in Deutsch's XOR algorithm (the first genuinely quantum algorithm) and related period-finding quantum algorithms (Simon's algorithm and Shor's factorization algorithm). It is well known that these algorithms can be formulated as solutions to a hidden-subgroup problem. Here the salient features of the information-processing are presented from the perspective of the way in which the algorithms exploit the non-Boolean logic represented by the projective geometry (the subspace structure) of Hilbert space.

Cambridge University Press eBooks•Jun 10, 2010•20 citations

QUANTUM ALGORITHMS FOR PROBLEMS IN NUMBER THEORY, ALGEBRAIC GEOMETRY, AND GROUP THEORY

Wim van Dam, Yoshitaka Sasaki

Quantum computers can execute algorithms that sometimes dramatically outperform classical computation. Undoubtedly the best-known example of this is Shor's discovery of an efficient quantum algorithm for factoring integers, whereas the same problem appears to be intractable on classical computers. Understanding what other computational problems can be solved significantly faster using quantum algorithms is one of the major challenges in the theory of quantum computation, and such algorithms motivate the formidable task of building a large-scale quantum computer. This article will review the current state of quantum algorithms, focusing on algorithms for problems with an algebraic flavor that achieve an apparent superpolynomial speedup over classical computation.

arXiv:1206.6126•Dec 1, 2012•5 citations
We analyse the quantum speed-up: the fact that some quantum algorithms are faster than their classical counterparts. The classical formulation of problem solving must be modified. In general a problem statement defines the solution only implicitly, giving a property that a solution must possess, and does not represent a process that constructs the solution explicitly. A solution algorithm must then specify explicitly a finite step-by-step procedure that constructs the solution through a dynamical development. In the quantum speed-up, however, an implicit definition directly determines the solution through an extra-dynamical irreversible non-algorithmic quantum measurement. While in an algorithmic solution, the initial conditions determine the solution in a one-way manner, in a solution by measurement, the initial conditions and a final condition influence the solution jointly. The quantum computation is as implicit as the problem statement. Implicit determination with joint influence is richer than explicit one-way dynamical determination, as it yields the speed-up. Quantum problem solving with speed-up is essentially extra-dynamical and irreversible. Other forms of implicit quantum problem solving may exploit extra-dynamical projections for speed-up.
A Quantum Computer Is Not a Faster Computer examines one of the most persistent misconceptions surrounding quantum computing: the idea that a quantum computer is simply a faster version of a classical computer. The paper explains why quantum computation represents a fundamentally different computational paradigm, based on superposition, interference, entanglement, measurement, and problem-specific quantum algorithms rather than on a generalized increase in processing speed. It distinguishes computational speed from computational complexity and shows why quantum advantage applies only to particular classes of problems for which quantum algorithms can exploit mathematical structures inaccessible, or prohibitively expensive, to classical approaches. The work also discusses the practical limitations of current quantum systems, including decoherence, error correction, qubit quality, scalability, and the continuing role of classical computing. It argues that the future of computing is therefore more accurately understood as a heterogeneous ecosystem in which classical, accelerated, and quantum architectures coexist and complement one another. The paper is intended to provide a technically rigorous yet accessible conceptual framework for understanding what quantum computers actually are, where their potential advantage originates, and why describing them merely as “faster computers” fundamentally misrepresents their nature.
Introduction Discussions of quantum-computational algorithms in the literature refer to various features of quantum mechanics as the source of the exponential speed-up relative to classical algorithms: superposition and entanglement, the fact that the state space of n bits is a space of 2 n states while the state space of n qubits is a space of 2 n dimensions, the possibility of computing all values of a function in a single computational step by “quantum parallelism,” or the possibility of an efficient implementation of the discrete quantum Fourier transform. Here I propose a different answer to the question posed in the title, in terms of the difference between classical logic and quantum logic, i.e., the difference between the Boolean classical event structure and the non-Boolean quantum event structure. In a nutshell, the ultimate source of the speed-up is the difference between a classical disjunction, which is true (or false) in virtue of the truth values of the disjuncts, and a quantum disjunction, which can be true (or false) even if none of the disjuncts is either true or false. In the following, I will discuss the information-processing in Deutsch's XOR algorithm (the first genuinely quantum algorithm) and related period-finding quantum algorithms (Simon's algorithm and Shor's factorization algorithm). It is well known that these algorithms can be formulated as solutions to a hidden-subgroup problem. Here the salient features of the information-processing are presented from the perspective of the way in which the algorithms exploit the non-Boolean logic represented by the projective geometry (the subspace structure) of Hilbert space.
Quantum computers can execute algorithms that sometimes dramatically outperform classical computation. Undoubtedly the best-known example of this is Shor's discovery of an efficient quantum algorithm for factoring integers, whereas the same problem appears to be intractable on classical computers. Understanding what other computational problems can be solved significantly faster using quantum algorithms is one of the major challenges in the theory of quantum computation, and such algorithms motivate the formidable task of building a large-scale quantum computer. This article will review the current state of quantum algorithms, focusing on algorithms for problems with an algebraic flavor that achieve an apparent superpolynomial speedup over classical computation.