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/9702021 · Physica D Nonlinear Phenomena

The Landauer resistance and band spectra for the counting quantum turing machine

Paul A. Benioff

Published Sep 1, 1998• 4 citations
arXivHTMLPDF
DOI
10.1016/s0167-2789(98)00041-4

Related papers

Simulations of Quantum Turing Machines by Quantum Multi-Stack Machines

Daowen Qiu

As was well known, in classical computation, Turing machines, circuits, multi-stack machines, and multi-counter machines are equivalent, that is, they can simulate each other in polynomial time. In quantum computation, Yao [11] first proved that for any quantum Turing machines $M$, there exists quantum Boolean circuit $(n,t)$-simulating $M$, where $n$ denotes the length of input strings, and $t$ is the number of move steps before machine stopping. However, the simulations of quantum Turing machines by quantum multi-stack machines and quantum multi-counter machines have not been considered, and quantum multi-stack machines have not been established, either. Though quantum counter machines were dealt with by Kravtsev [6] and Yamasaki {\it et al.} [10], in which the machines count with $0,\pm 1$ only, we sense that it is difficult to simulate quantum Turing machines in terms of this fashion of quantum computing devices, and we therefore prove that the quantum multi-counter machines allowed to count with $0,\pm 1,\pm 2,...,\pm n$ for some $n>1$ can efficiently simulate quantum Turing machines. Therefore, our mail goals are to establish quantum multi-stack machines and quantum multi-counter machines with counts $0,\pm 1,\pm 2,...,\pm n$ and $n>1$, and particularly to simulate quantum Turing machines by these quantum computing devices.

arXiv:quant-ph/0501176•Jan 30, 2005•4 citations

Quantum mechanical hamiltonian models of turing machines

Paul A. Benioff

Journal of Statistical Physics•Nov 1, 1982•412 citations

On the simulation of quantum turing machines

Marco Carpentieri

Theoretical Computer Science•Mar 26, 2003•7 citations

Introduction to classical computation

This chapter introduces the basic concepts of computer science that are necessary for an understanding of quantum computation and information. We discuss the Turing machine, the fundamental model of computation since it formalizes the intuitive notion of an algorithm: if there exists an algorithm to solve a given problem, then this algorithm can be run on a Turing machine. We then introduce the circuit model of computation, which is equivalent to the Turing machine model but is nearer to real computers. In this model, the information is carried by wires and a small set of elementary logical operations (gates) allows implementation of any complex computation. It is important to find the minimum resources (computer memory, time and energy) required to solve a given problem with the best possible algorithm. This is the task of computational complexity, for which we provide a quick glance at the key concepts. We also examine the energy resources necessary to perform computations. Here we discuss the relation between energy and information, which was explained by Landauer and Bennett in their solution of Maxwell’s demon paradox. In particular, Landauer’s principle sets the minimum energy requirements for irreversible computation. On the other hand, it turns out that it is, in principle, possible to perform any complex computation by means of reversible gates, without energy dissipation. A concrete model of reversible computation, the so-called billiard-ball computer, is briefly discussed. Finally, we address the problem of energy dissipation in a real computation and show how it may be managed using reversible computation techniques.

WORLD SCIENTIFIC eBooks•Dec 1, 2018•0 citations

Quantum Turing Machines

Margherita Zorzi

•Jan 1, 2009•1 citation

Universality in Quantum Computation

David Deutsch, Adriano Barenco, Artur Ekert

We show that in quantum computation almost every gate that operates on two or more bits is a universal gate. We discuss various physical considerations bearing on the proper definition of universality for computational components such as logic gates. Introduction It has been known for several years that the theory of quantum computers --- i.e. machines that rely on characteristically quantum phenomena to perform computations [1] --- is substantially different from the classical theory of computation, which is essentially the theory of the universal Turing machine. We may identify three important differences. Firstly, the properties of quantum computers are not postulated in abstracto but are deduced entirely from the laws of physics. Logically, this was already true of the classical theory, as Landauer [2] has pointed out, but the intuitive nature of the classically-available computational operations, and the millennia-long history of their study, allowed pioneers such as Turing, Chu...

•May 24, 1995•322 citations
As was well known, in classical computation, Turing machines, circuits, multi-stack machines, and multi-counter machines are equivalent, that is, they can simulate each other in polynomial time. In quantum computation, Yao [11] first proved that for any quantum Turing machines MMM, there exists quantum Boolean circuit (n,t)(n,t)(n,t)-simulating MMM, where nnn denotes the length of input strings, and ttt is the number of move steps before machine stopping. However, the simulations of quantum Turing machines by quantum multi-stack machines and quantum multi-counter machines have not been considered, and quantum multi-stack machines have not been established, either. Though quantum counter machines were dealt with by Kravtsev [6] and Yamasaki {\it et al.} [10], in which the machines count with 0,±10,\pm 10,±1 only, we sense that it is difficult to simulate quantum Turing machines in terms of this fashion of quantum computing devices, and we therefore prove that the quantum multi-counter machines allowed to count with 0,±1,±2,...,±n0,\pm 1,\pm 2,...,\pm n0,±1,±2,...,±n for some n>1n>1n>1 can efficiently simulate quantum Turing machines. Therefore, our mail goals are to establish quantum multi-stack machines and quantum multi-counter machines with counts 0,±1,±2,...,±n0,\pm 1,\pm 2,...,\pm n0,±1,±2,...,±n and n>1n>1n>1, and particularly to simulate quantum Turing machines by these quantum computing devices.
This chapter introduces the basic concepts of computer science that are necessary for an understanding of quantum computation and information. We discuss the Turing machine, the fundamental model of computation since it formalizes the intuitive notion of an algorithm: if there exists an algorithm to solve a given problem, then this algorithm can be run on a Turing machine. We then introduce the circuit model of computation, which is equivalent to the Turing machine model but is nearer to real computers. In this model, the information is carried by wires and a small set of elementary logical operations (gates) allows implementation of any complex computation. It is important to find the minimum resources (computer memory, time and energy) required to solve a given problem with the best possible algorithm. This is the task of computational complexity, for which we provide a quick glance at the key concepts. We also examine the energy resources necessary to perform computations. Here we discuss the relation between energy and information, which was explained by Landauer and Bennett in their solution of Maxwell’s demon paradox. In particular, Landauer’s principle sets the minimum energy requirements for irreversible computation. On the other hand, it turns out that it is, in principle, possible to perform any complex computation by means of reversible gates, without energy dissipation. A concrete model of reversible computation, the so-called billiard-ball computer, is briefly discussed. Finally, we address the problem of energy dissipation in a real computation and show how it may be managed using reversible computation techniques.
We show that in quantum computation almost every gate that operates on two or more bits is a universal gate. We discuss various physical considerations bearing on the proper definition of universality for computational components such as logic gates. Introduction It has been known for several years that the theory of quantum computers --- i.e. machines that rely on characteristically quantum phenomena to perform computations [1] --- is substantially different from the classical theory of computation, which is essentially the theory of the universal Turing machine. We may identify three important differences. Firstly, the properties of quantum computers are not postulated in abstracto but are deduced entirely from the laws of physics. Logically, this was already true of the classical theory, as Landauer [2] has pointed out, but the intuitive nature of the classically-available computational operations, and the millennia-long history of their study, allowed pioneers such as Turing, Chu...