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 Computers with Finite Size Clocks

Tino Gramß

Published Oct 1, 1995• 2 citations
OpenAlex

Abstract

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

Related papers

On the Speed of Quantum Computation

Tino Gramß

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

•Apr 1, 1994•3 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

Reversible quantum cellular automata

Benjamin W. Schumacher, Reinhard F. Werner

We define quantum cellular automata as infinite quantum lattice systems with discrete time dynamics, such that the time step commutes with lattice translations and has strictly finite propagation speed. In contrast to earlier definitions this allows us to give an explicit characterization of all local rules generating such automata. The same local rules also generate the global time step for automata with periodic boundary conditions. Our main structure theorem asserts that any quantum cellular automaton is structurally reversible, i.e., that it can be obtained by applying two blockwise unitary operations in a generalized Margolus partitioning scheme. This implies that, in contrast to the classical case, the inverse of a nearest neighbor quantum cellular automaton is again a nearest neighbor automaton. We present several construction methods for quantum cellular automata, based on unitaries commuting with their translates, on the quantization of (arbitrary) reversible classical cellular automata, on quantum circuits, and on Clifford transformations with respect to a description of the single cells by finite Weyl systems. Moreover, we indicate how quantum random walks can be considered as special cases of cellular automata, namely by restricting a quantum lattice gas automaton with local particle number conservation to the single particle sector.

arXiv:quant-ph/0405174•May 28, 2004•98 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

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

Autonomous quantum machines and the finite sized Quasi-Ideal clock

Mischa P. Woods, Ralph Silva, Jonathan Oppenheim

Processes such as quantum computation, or the evolution of quantum cellular automata are typically described by a unitary operation implemented by an external observer. In particular, an interaction is generally turned on for a precise amount of time, using a classical clock. A fully quantum mechanical description of such a device would include a quantum description of the clock whose state is generally disturbed because of the back-reaction on it. Such a description is needed if we wish to consider finite sized autonomous quantum machines requiring no external control. The extent of the back-reaction has implications on how small the device can be, on the length of time the device can run, and is required if we want to understand what a fully quantum mechanical treatment of an observer would look like. Here, we consider the implementation of a unitary by a finite sized device which we call the "Quasi-Ideal clock", and show that the back-reaction on it can be made exponentially small in the device's dimension with only a linear increase in energy. As a result, an autonomous quantum machine need only be of modest size and or energy. We are also able to solve a long-standing open problem by using a finite sized quantum clock to approximate the continuous evolution of an Idealised clock. The result has implications on the equivalence of different paradigms of quantum thermodynamics, some which allow external control and some which only allow autonomous thermal machines.

arXiv:1607.04591•Jul 15, 2016•80 citations
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...
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...
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.
We define quantum cellular automata as infinite quantum lattice systems with discrete time dynamics, such that the time step commutes with lattice translations and has strictly finite propagation speed. In contrast to earlier definitions this allows us to give an explicit characterization of all local rules generating such automata. The same local rules also generate the global time step for automata with periodic boundary conditions. Our main structure theorem asserts that any quantum cellular automaton is structurally reversible, i.e., that it can be obtained by applying two blockwise unitary operations in a generalized Margolus partitioning scheme. This implies that, in contrast to the classical case, the inverse of a nearest neighbor quantum cellular automaton is again a nearest neighbor automaton. We present several construction methods for quantum cellular automata, based on unitaries commuting with their translates, on the quantization of (arbitrary) reversible classical cellular automata, on quantum circuits, and on Clifford transformations with respect to a description of the single cells by finite Weyl systems. Moreover, we indicate how quantum random walks can be considered as special cases of cellular automata, namely by restricting a quantum lattice gas automaton with local particle number conservation to the single particle sector.
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.
Processes such as quantum computation, or the evolution of quantum cellular automata are typically described by a unitary operation implemented by an external observer. In particular, an interaction is generally turned on for a precise amount of time, using a classical clock. A fully quantum mechanical description of such a device would include a quantum description of the clock whose state is generally disturbed because of the back-reaction on it. Such a description is needed if we wish to consider finite sized autonomous quantum machines requiring no external control. The extent of the back-reaction has implications on how small the device can be, on the length of time the device can run, and is required if we want to understand what a fully quantum mechanical treatment of an observer would look like. Here, we consider the implementation of a unitary by a finite sized device which we call the "Quasi-Ideal clock", and show that the back-reaction on it can be made exponentially small in the device's dimension with only a linear increase in energy. As a result, an autonomous quantum machine need only be of modest size and or energy. We are also able to solve a long-standing open problem by using a finite sized quantum clock to approximate the continuous evolution of an Idealised clock. The result has implications on the equivalence of different paradigms of quantum thermodynamics, some which allow external control and some which only allow autonomous thermal machines.