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

On the Speed of Quantum Computation

Tino Gramß

Published Apr 1, 1994• 3 citations
OpenAlex

Abstract

Feynman and Margolus have shown that a closed, locally interacting quantum system is capable of performing deterministic computation. Feynman's system computes in a serial way. Margolus was able to extend Feynman's ideas to get quantum description of a cellular automaton, i.e. a model which calculates in parallel. In this article, a new kind of speed limit for quantum computation is established. An upper bound on the average velocity ("instructions per second ") for both computers is derived. One would expect a cellular automaton to have a computational velocity which scales with the number k of its cells. However, the upper bound on the average velocity is only proportional to p k in this case. This does not reflect the parallelism of the cellular automaton. Whether it is possible to construct a locally interacting quantum computer that really works in parallel remains an open problem. Introduction There is a growing interest in devices computing on a scale where quantum mechanic...

Related papers

On the Speed of Quantum Computers with Finite Size Clocks

Tino Gramß

In previous work, the speed of locally coupled quantum computers with infinite size clocks has been investigated in detail. One of the results is that the Feynman quantum computer and the Margolus cellular automaton compute at a constant rate. We show that this is no longer true for computers with finite size clocks and we will argue that finite size clocks are more appropriate for the computers under consideration. Furthermore, we give alternative definitions for computational speed that seem to be appropriate for finite size computers. 1 Introduction In 1985, Feynman introduced a model for a serial computer that is able to model the computation of a deterministic computation in a closed, locally interacting quantum system [Fe85]. Margolus was able to generalize Feynman's ideas to a quantum model of a cellular automaton [Ma86, Ma90]. The result of a Feynman or Margolus computer is obtained by performing a quantum measurement. The outcome of such a measurement is not certain. A fina...

•Oct 1, 1995•2 citations

Quantum cellular automaton for universal quantum computation

Robert Raussendorf

This paper describes a quantum cellular automaton capable of performing universal quantum computation. The automaton has an elementary transition function that acts on Margolus cells of $2\ifmmode\times\else\texttimes\fi{}2$ qubits, and both the ``quantum input'' and the program are encoded in the initial state of the system.

arXiv:quant-ph/0412048•Physical Review A•Aug 1, 2005•54 citations

On one-dimensional quantum cellular automata

John Watrous

Since Richard Feynman introduced the notion of quantum computation in 1982, various models of "quantum computers" have been proposed (R. Feynman, 1992). These models include quantum Turing machines and quantum circuits. We define another quantum computational model, one dimensional quantum cellular automata, and demonstrate that any quantum Turing machine can be efficiently simulated by a one dimensional quantum cellular automaton with constant slowdown. This can be accomplished by consideration of a restricted class of one dimensional quantum cellular automata called one dimensional partitioned quantum cellular automata. We also show that any one dimensional partitioned quantum cellular automaton can be simulated by a quantum Turing machine with linear slowdown, but the problem of efficiently simulating an arbitrary one dimensional quantum cellular automaton with a quantum Turing machine is left open. From this discussion, some interesting facts concerning these models are easily deduced.

Annual Symposium on Foundations of Computer Science•Nov 19, 2002•156 citations

Physics of Computation

Wojciech H. Zurek

Results of Feynman and others have shown that the quantum formalism permits a closed, microscopic, and locally interacting system to perform deterministic serial computation. In this paper we show that this formalism can also describe deterministic parallel computation. Achieving full parallelism in more than one dimension remains an open problem.

CRC Press eBooks•Mar 8, 2018•0 citations

Fast quantum computation at arbitrarily low energy

Stephen P. Jordan

One version of the energy-time uncertainty principle states that the minimum time ${T}_{\ensuremath{\perp}}$ for a quantum system to evolve from a given state to any orthogonal state is $h/(4\mathrm{\ensuremath{\Delta}}E)$, where $\mathrm{\ensuremath{\Delta}}E$ is the energy uncertainty. A related bound called the Margolus-Levitin theorem states that ${T}_{\ensuremath{\perp}}\ensuremath{\ge}h/(2\ensuremath{\langle}E\ensuremath{\rangle})$, where $\ensuremath{\langle}E\ensuremath{\rangle}$ is the expectation value of energy and the ground energy is taken to be zero. Many subsequent works have interpreted ${T}_{\ensuremath{\perp}}$ as defining a minimal time for an elementary computational operation and correspondingly a fundamental limit on clock speed determined by a system's energy. Here we present local time-independent Hamiltonians in which computational clock speed becomes arbitrarily large relative to $\ensuremath{\langle}E\ensuremath{\rangle}$ and $\mathrm{\ensuremath{\Delta}}E$ as the number of computational steps goes to infinity. We argue that energy considerations alone are not sufficient to obtain an upper bound on computational speed, and that additional physical assumptions such as limits to information density and information transmission speed are necessary to obtain such a bound.

arXiv:1701.01175•Physical Review A•Mar 6, 2017•40 citations

Feynman and Computation

J. J. Hopfield

There were few basic aspects of computers and computation which intrigued Richard P. Feynman, and made the subject sufficiently interesting that he would spend time teaching it. Feynman himself did the lecture on quantum computation. Charles Bennett has already prepared the way by talking about reversible computation, and Norman Margolus on the billiard ball computer, so Feynman developed quantum computation in ways which made its connection to classical reversible computers obvious. His lecture was chiefly developing the idea that an entirely reversible quantum system, without damping processes, could perform universal computation. The insight that quantum computers were really different came only later, and to others, not to Feynman. Feynman only emphasized that the physical scale and speed of computers were not limited by the classical world, since conceptually they could be built of reversible components at the atomic level.

CRC Press eBooks•Nov 16, 2018•64 citations
Feynman and Margolus have shown that a closed, locally interacting quantum system is capable of performing deterministic computation. Feynman's system computes in a serial way. Margolus was able to extend Feynman's ideas to get quantum description of a cellular automaton, i.e. a model which calculates in parallel. In this article, a new kind of speed limit for quantum computation is established. An upper bound on the average velocity ("instructions per second ") for both computers is derived. One would expect a cellular automaton to have a computational velocity which scales with the number k of its cells. However, the upper bound on the average velocity is only proportional to p k in this case. This does not reflect the parallelism of the cellular automaton. Whether it is possible to construct a locally interacting quantum computer that really works in parallel remains an open problem. Introduction There is a growing interest in devices computing on a scale where quantum mechanic...
In previous work, the speed of locally coupled quantum computers with infinite size clocks has been investigated in detail. One of the results is that the Feynman quantum computer and the Margolus cellular automaton compute at a constant rate. We show that this is no longer true for computers with finite size clocks and we will argue that finite size clocks are more appropriate for the computers under consideration. Furthermore, we give alternative definitions for computational speed that seem to be appropriate for finite size computers. 1 Introduction In 1985, Feynman introduced a model for a serial computer that is able to model the computation of a deterministic computation in a closed, locally interacting quantum system [Fe85]. Margolus was able to generalize Feynman's ideas to a quantum model of a cellular automaton [Ma86, Ma90]. The result of a Feynman or Margolus computer is obtained by performing a quantum measurement. The outcome of such a measurement is not certain. A fina...
Since Richard Feynman introduced the notion of quantum computation in 1982, various models of "quantum computers" have been proposed (R. Feynman, 1992). These models include quantum Turing machines and quantum circuits. We define another quantum computational model, one dimensional quantum cellular automata, and demonstrate that any quantum Turing machine can be efficiently simulated by a one dimensional quantum cellular automaton with constant slowdown. This can be accomplished by consideration of a restricted class of one dimensional quantum cellular automata called one dimensional partitioned quantum cellular automata. We also show that any one dimensional partitioned quantum cellular automaton can be simulated by a quantum Turing machine with linear slowdown, but the problem of efficiently simulating an arbitrary one dimensional quantum cellular automaton with a quantum Turing machine is left open. From this discussion, some interesting facts concerning these models are easily deduced.
One version of the energy-time uncertainty principle states that the minimum time ${T}_{\ensuremath{\perp}}$ for a quantum system to evolve from a given state to any orthogonal state is $h/(4\mathrm{\ensuremath{\Delta}}E)$, where $\mathrm{\ensuremath{\Delta}}E$ is the energy uncertainty. A related bound called the Margolus-Levitin theorem states that ${T}_{\ensuremath{\perp}}\ensuremath{\ge}h/(2\ensuremath{\langle}E\ensuremath{\rangle})$, where $\ensuremath{\langle}E\ensuremath{\rangle}$ is the expectation value of energy and the ground energy is taken to be zero. Many subsequent works have interpreted ${T}_{\ensuremath{\perp}}$ as defining a minimal time for an elementary computational operation and correspondingly a fundamental limit on clock speed determined by a system's energy. Here we present local time-independent Hamiltonians in which computational clock speed becomes arbitrarily large relative to $\ensuremath{\langle}E\ensuremath{\rangle}$ and $\mathrm{\ensuremath{\Delta}}E$ as the number of computational steps goes to infinity. We argue that energy considerations alone are not sufficient to obtain an upper bound on computational speed, and that additional physical assumptions such as limits to information density and information transmission speed are necessary to obtain such a bound.
There were few basic aspects of computers and computation which intrigued Richard P. Feynman, and made the subject sufficiently interesting that he would spend time teaching it. Feynman himself did the lecture on quantum computation. Charles Bennett has already prepared the way by talking about reversible computation, and Norman Margolus on the billiard ball computer, so Feynman developed quantum computation in ways which made its connection to classical reversible computers obvious. His lecture was chiefly developing the idea that an entirely reversible quantum system, without damping processes, could perform universal computation. The insight that quantum computers were really different came only later, and to others, not to Feynman. Feynman only emphasized that the physical scale and speed of computers were not limited by the classical world, since conceptually they could be built of reversible components at the atomic level.