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

CRC Press eBooks

Physics of Computation

Wojciech H. Zurek

Published Mar 8, 2018• 0 citations
Publisher

Abstract

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.

DOI
10.1201/9780429502880-8

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

PARALLELISM IN QUANTUM INFORMATION PROCESSING DEFEATS THE UNIVERSAL COMPUTER

Marius Nagy, Selim G. Akl

This paper is structured around the idea that a finite Universal Computer cannot be realized and presents in detail a series of unconventional computing paradigms supporting this idea from a quantum mechanical perspective.

Parallel Processing Letters•Sep 1, 2007•13 citations

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 computation and complexity theory

Karl Svozil

The Hilbert space formalism of quantum mechanics is reviewed with emphasis on applications to quantum computing. Standard interferomeric techniques are used to construct a physical device capable of universal quantum computation. Some consequences for recursion theory and complexity theory are discussed.

arXiv:hep-th/9412047•Dec 6, 1994•8 citations

Quantum Telecomputation

Lov K. Grover

Quantum mechanics permits certain kinds of non-local effects. This paper demonstrates how these can be used for distributed computation with minimal communication between various processors. The problem considered is that of estimating the mean of N items to a certain precision. First a serial quantum mechanical algorithm for this is presented that is faster than any classical algorithm. Next it is shown how this can be efficiently parallelized with quantum mechanical processors that are remotely located. These processors consist of coupled EPR particles. Each processor has just to communicate one bit of classical information to a central location at the end of its local computation.

arXiv:quant-ph/9704012•Apr 7, 1997•51 citations

Quantum mechanical computation

James D. Brasher

The physics and the mathematics of computation are examined to provide a foundation and perspective for the investigation of the quantum mechanics of computation. Our purpose is to explore the fundamental limits and constraints imposed on computation by Nature through the laws of physics and the mathematics of computational complexity. Inasmuch as information storage and transmission are an integral part of computation, their physical bounds are considered. The computer is viewed both physically and mathematically as a dynamical system, and is depicted in terms of the basic Turing machine paradigm. Three fundamental classes of the Turing machine are defined; the deterministic, stochastic and quantum Turing machines. Hamiltonian models and physical realizations of quantum computing are described. Quantum computers can perform some tasks which have no classical analogue, but they cannot compute functions that are non-computable by classical means. Some classically intractable problems can be solved with quantum computers.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Mar 1, 1994•0 citations
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.
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...
Quantum mechanics permits certain kinds of non-local effects. This paper demonstrates how these can be used for distributed computation with minimal communication between various processors. The problem considered is that of estimating the mean of N items to a certain precision. First a serial quantum mechanical algorithm for this is presented that is faster than any classical algorithm. Next it is shown how this can be efficiently parallelized with quantum mechanical processors that are remotely located. These processors consist of coupled EPR particles. Each processor has just to communicate one bit of classical information to a central location at the end of its local computation.
The physics and the mathematics of computation are examined to provide a foundation and perspective for the investigation of the quantum mechanics of computation. Our purpose is to explore the fundamental limits and constraints imposed on computation by Nature through the laws of physics and the mathematics of computational complexity. Inasmuch as information storage and transmission are an integral part of computation, their physical bounds are considered. The computer is viewed both physically and mathematically as a dynamical system, and is depicted in terms of the basic Turing machine paradigm. Three fundamental classes of the Turing machine are defined; the deterministic, stochastic and quantum Turing machines. Hamiltonian models and physical realizations of quantum computing are described. Quantum computers can perform some tasks which have no classical analogue, but they cannot compute functions that are non-computable by classical means. Some classically intractable problems can be solved with quantum computers.