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

Kluwer Academic Publishers eBooks

Theory of the Quantum Speed Up

Giuseppe Castagnoli, David Finkelstein

Published Feb 24, 2006• 2 citations
Publisher

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 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.

DOI
10.1007/0-306-47114-0_34

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•14 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

A New Approach to Quantum Computation

Horace P. Yuen

A general quantum machine is characterized to capture all the possible physical structures that may be employed for effective or efficient computation. As an illustration, a specific machine is described for the permanent evaluation problem. The contrast between quantum and classical parallelism is also discussed, as is the effect of quantum error correction against decoherence and loss. 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•Dec 19, 2005•3 citations

Quantum Information Processing with Quantum Optics

J. I. Cirac, L.-M. Duan, Dieter Jaksch +1 more

We review theoretical proposals for implementation of quantum computing and quantum communication with quantum optical methods. 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.

Birkhäuser Basel eBooks•Jan 1, 2003•3 citations

Quantum Algorithms

A. O. Pittenger

We are now ready to assemble quantum subroutines into quantum algorithms. A reasonable first question is: Are there problems which can be solved efficiently on a quantum computer? In his analysis of a universal quantum computer [25], Deutsch illustrated quantum parallelism by constructing a procedure to compute the parity f (0) ⊕ f (1) of a function on one bit. In a generalization of this context, Deutsch and Jozsa [27] defined a quantum algorithm that could solve a problem more efficiently than is possible on a classical computer. This problem helped motivate the search for algorithms that could solve “real” problems, and Simon [67] provided an example that inspired Shor’s subsequent work on the factoring problem and on the discrete logarithm problem. 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.

Birkhäuser Boston eBooks•Jan 1, 2001•0 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
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.
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 general quantum machine is characterized to capture all the possible physical structures that may be employed for effective or efficient computation. As an illustration, a specific machine is described for the permanent evaluation problem. The contrast between quantum and classical parallelism is also discussed, as is the effect of quantum error correction against decoherence and loss. 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.
We are now ready to assemble quantum subroutines into quantum algorithms. A reasonable first question is: Are there problems which can be solved efficiently on a quantum computer? In his analysis of a universal quantum computer [25], Deutsch illustrated quantum parallelism by constructing a procedure to compute the parity f (0) ⊕ f (1) of a function on one bit. In a generalization of this context, Deutsch and Jozsa [27] defined a quantum algorithm that could solve a problem more efficiently than is possible on a classical computer. This problem helped motivate the search for algorithms that could solve “real” problems, and Simon [67] provided an example that inspired Shor’s subsequent work on the factoring problem and on the discrete logarithm problem. 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.