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:quant-ph/0010081 · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences

Theory of the quantum speed-up

Giuseppe Castagnoli, David Ritz Finkelstein

Published Jul 8, 2001• 20 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1098/rspa.2001.0797

Related papers

Theory of the Quantum Speed Up

Castagnoli, G C, Finkelstein, D R

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.

•Oct 23, 2000•16 citations

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•3 citations

On the Relation Between Quantum Computational Speedup and Retrocausality

Giuseppe Castagnoli

We investigate the reason for the quantum speedup (quantum algorithms require fewer computation steps than their classical counterparts). We extend the representation of the quantum algorithm to the process of setting the problem, namely choosing the function computed by the black box. The initial measurement selects a setting at random, Bob (the problem setter) unitarily changes it into the desired one. With reference to the observer dependent quantum states of relational quantum mechanics, this representation is with respect to Bob and any external observer, it cannot be with respect to Alice (the problem solver). It would tell her the function computed by the black box, which to her should be hidden. To Alice, the projection of the quantum state due to the initial measurement is retarded at the end of her problem solving action, so that the algorithm input state remains one of complete ignorance of the setting. By black box computations, she unitarily sends it into the output state that, for each possible setting, encodes the corresponding solution, acquired by the final measurement. Mathematically, we can ascribe to the final measurement the selection of any fraction R of the random outcome of the initial measurement. This projects the input state to Alice on one of lower entropy where she knows the corresponding fraction of the problem setting. Given the appropriate value of R, the quantum algorithm is a sum over classical histories in each of which Alice, knowing in advance one of the R-th parts of the setting, performs the black box computations still required to identify the solution. Given a quantum algorithm, this retrocausality model provides the value of R that explains its speed up; in the major quantum algorithms, R is 1/2 or slightly above it. Conversely, given the problem, R=1/2 always yields the order of magnitude of the number of black box computations required to solve it in an optimal quantum way. Quanta 2016; 5: 34–52.

Quanta•Jan 10, 2016•8 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.In the first section of these notes, I try to explain why the recent results about quantum computing have been so surprising.This section comes from a talk I have been giving for several years now, and discusses the history of quantum computing and its relation to the mathematical foundations of computer science.In Sections 2 and 3, I talk about the quantum computing model and its relationship to physics.These sections rely heavily on two of my papers [SIAM J. Comp.26 (1997), 1484-1509; Doc.Math.Extra Vol.ICM I (1998), 467-486].Sections 4 and 5 illustrate the general technique of using quantum Fourier transforms to find periodicity.Section 4 contains an algorithm of Dan Simon showing that quantum computers are likely to be exponentially faster than classical computers for some problems.Section 5 discusses my factoring algorithm, which was inspired in part by Dan Simon's paper.In the final section, I discuss Lov Grover's search algorithm, which illustrates a different technique for speeding up classical algorithms.These techniques for constructing faster algorithms for classical problems on quantum computers are the only two significant ones which have been discovered so far.

Proceedings of symposia in applied mathematics•Jan 1, 2002•56 citations

Completing the physical representation of quantum algorithms explains their computational speedup

Giuseppe Castagnoli

The usual representation of quantum algorithms, limited to the problem solving process, is incomplete as it lacks the initial measurement. Completing it involves three steps: (i) representing the problem setting process, (ii) relativizing this representation to Alice, the problem solver, to whom the problem setting must be concealed, (iii) representing the reversibility of the computation process by symmetrizing it for time reversal. The latter step shows that all is as if Alice, before beginning her problem solving action, knew half of the information that specifies the solution of the problem she will read in the future. An optimal quantum algorithm is a sum over classical histories in each of which Alice knows in advance one of the possible halves of the solution and performs the computation steps (oracle queries) necessary to identify the missing half. This explains the quantum computational speedup and allows to predict the speedup offered by the optimal quantum solution of any oracle problem.

•May 7, 2017•0 citations

Mechanism Of The Quantum Speed-up

Giuseppe Castagnoli, Daniel P. Sheehan

We explain the mechanism of the quantum speed-up -quantum algorithms requiring fewer computation steps than their classical equivalentfor a family of algorithms.Bob chooses a function and gives to Alice the black box that computes it.Alice, without knowing Bob's choice, should find a character of the function (e. g. its period) by computing its value for different arguments.There is naturally correlation between Bob's choice and the solution found by Alice.We show that, in quantum algorithms, this correlation becomes quantum.This highlights an overlooked measurement problem: sharing between two measurements the determination of correlated (thus redundant) measurement outcomes.All is like Alice, by reading the solution at the end of the algorithm, contributed to the initial choice of Bob, for half of it in quantum superposition for all the possible ways of taking this half.This contribution, back evolved to before running the algorithm, where Bob's choice is located, becomes Alice knowing in advance half of this choice.The quantum algorithm is the quantum superposition of all the possible ways of taking half of Bob's choice and, given the advanced knowledge of it, classically computing the missing half.This yields a speed-up with respect to the classical case where, initially, Bob's choice is completely unknown to Alice.

arXiv:1101.4359•AIP conference proceedings•Jan 1, 2011•3 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.
We investigate the reason for the quantum speedup (quantum algorithms require fewer computation steps than their classical counterparts). We extend the representation of the quantum algorithm to the process of setting the problem, namely choosing the function computed by the black box. The initial measurement selects a setting at random, Bob (the problem setter) unitarily changes it into the desired one. With reference to the observer dependent quantum states of relational quantum mechanics, this representation is with respect to Bob and any external observer, it cannot be with respect to Alice (the problem solver). It would tell her the function computed by the black box, which to her should be hidden. To Alice, the projection of the quantum state due to the initial measurement is retarded at the end of her problem solving action, so that the algorithm input state remains one of complete ignorance of the setting. By black box computations, she unitarily sends it into the output state that, for each possible setting, encodes the corresponding solution, acquired by the final measurement. Mathematically, we can ascribe to the final measurement the selection of any fraction R of the random outcome of the initial measurement. This projects the input state to Alice on one of lower entropy where she knows the corresponding fraction of the problem setting. Given the appropriate value of R, the quantum algorithm is a sum over classical histories in each of which Alice, knowing in advance one of the R-th parts of the setting, performs the black box computations still required to identify the solution. Given a quantum algorithm, this retrocausality model provides the value of R that explains its speed up; in the major quantum algorithms, R is 1/2 or slightly above it. Conversely, given the problem, R=1/2 always yields the order of magnitude of the number of black box computations required to solve it in an optimal quantum way. Quanta 2016; 5: 34–52.
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.In the first section of these notes, I try to explain why the recent results about quantum computing have been so surprising.This section comes from a talk I have been giving for several years now, and discusses the history of quantum computing and its relation to the mathematical foundations of computer science.In Sections 2 and 3, I talk about the quantum computing model and its relationship to physics.These sections rely heavily on two of my papers [SIAM J. Comp.26 (1997), 1484-1509; Doc.Math.Extra Vol.ICM I (1998), 467-486].Sections 4 and 5 illustrate the general technique of using quantum Fourier transforms to find periodicity.Section 4 contains an algorithm of Dan Simon showing that quantum computers are likely to be exponentially faster than classical computers for some problems.Section 5 discusses my factoring algorithm, which was inspired in part by Dan Simon's paper.In the final section, I discuss Lov Grover's search algorithm, which illustrates a different technique for speeding up classical algorithms.These techniques for constructing faster algorithms for classical problems on quantum computers are the only two significant ones which have been discovered so far.
The usual representation of quantum algorithms, limited to the problem solving process, is incomplete as it lacks the initial measurement. Completing it involves three steps: (i) representing the problem setting process, (ii) relativizing this representation to Alice, the problem solver, to whom the problem setting must be concealed, (iii) representing the reversibility of the computation process by symmetrizing it for time reversal. The latter step shows that all is as if Alice, before beginning her problem solving action, knew half of the information that specifies the solution of the problem she will read in the future. An optimal quantum algorithm is a sum over classical histories in each of which Alice knows in advance one of the possible halves of the solution and performs the computation steps (oracle queries) necessary to identify the missing half. This explains the quantum computational speedup and allows to predict the speedup offered by the optimal quantum solution of any oracle problem.
We explain the mechanism of the quantum speed-up -quantum algorithms requiring fewer computation steps than their classical equivalentfor a family of algorithms.Bob chooses a function and gives to Alice the black box that computes it.Alice, without knowing Bob's choice, should find a character of the function (e. g. its period) by computing its value for different arguments.There is naturally correlation between Bob's choice and the solution found by Alice.We show that, in quantum algorithms, this correlation becomes quantum.This highlights an overlooked measurement problem: sharing between two measurements the determination of correlated (thus redundant) measurement outcomes.All is like Alice, by reading the solution at the end of the algorithm, contributed to the initial choice of Bob, for half of it in quantum superposition for all the possible ways of taking this half.This contribution, back evolved to before running the algorithm, where Bob's choice is located, becomes Alice knowing in advance half of this choice.The quantum algorithm is the quantum superposition of all the possible ways of taking half of Bob's choice and, given the advanced knowledge of it, classically computing the missing half.This yields a speed-up with respect to the classical case where, initially, Bob's choice is completely unknown to Alice.