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 Computational Power of Quantum Turing Machine

Takashi Mihara

Published May 1, 1996• 0 citations
OpenAlex

Abstract

A computation is an evolution from one physical state to another, and so are Today’s computers, i.e., the computations of them are changes of electric signals. What are differences of quantum computers from classical computers? The computational principles of classical computers are based on classical physics. In principle, we can construct them from devices based on classical physics

Related papers

Quantum computing and quantum complexity theory

Umesh V. Vazirani

There is strong evidence that computers based upon the principles of quantum physics represent an inherently new and more powerful model of computation. Such computers violate the modern form of the Church-Turing thesis (which lies at the foundations of computer science). This thesis can be informally summarized as follows: all physical implementations of computing devices can be described by the same abstract model of computation-the probabilistic Turing Machine or the equivalent random access machine. In this paper, we will describe two formal models for quantum computers: quantum circuits and quantum Turing Machines, introduced by Deutsch [1985].

IEEE International Symposium on Circuits and Systems proceedings•Jan 1, 2000•0 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

Quantum computation

Jiannis K. Pachos

Computation is a process of performing a large number of simple operations. The main building blocks of classical computers are bits. Each of them can take either the value 0 or 1. A series of gates can change these values by acting on them selectively. This process is structured to fulfil a purpose. For example, if we are interested in adding two numbers, the numbers are encoded into bits and gates are performed such that the final state of the bits reveals the desired answer: a number which is the sum of the initial ones. While it is possible to build algorithms that can perform almost any computation, it is also desirable to find the answer within a reasonable length of time or with a reasonable amount of resources. There is an ever-growing demand in computational power for both scientific and commercial purposes. Indeed, it is surprisingly easy to find an application that can jam even the fastest computer. This fuels a vast effort in the research of information science to increase the speed and processing power of computers. Modern computational models are based on the universal Turing machine (Turing, 1937). This is a theoretical information processing model that employs the elementary gate processes described above. It can efficiently simulate any other device capable of performing an algorithmic process. Since the introduction of the Turing machine, physics has influenced computation in many ways.

Cambridge University Press eBooks•Apr 12, 2012•0 citations

Quantum Computation

Cristopher Moore, Stephan Mertens

Abstract According to the Church-Turing Thesis, a Turing machine, and thus the programming languages and computers in existence, can simulate any reasonable computing device. However, there are physical devices that are exponentially more efficient than a Turing machine, and hence would prove exponentially difficult to simulate using such a machine. This chapter explores the concept of quantum computers and their potential not only to simulate quantum physics exponentially faster than classical computers but also to solve other problems exponentially faster. It considers algorithms that break cryptosystems, find needles in haystacks, and predict who can win a game. It first describes particles, waves, and amplitudes in quantum computation before turning to states and operators. It then examines how interference lets a quantum computer learn some things about a function, how quantum computers can solve factoring in polynomial time, the link between factoring and modern cryptography, graph isomorphism and the hidden subgroup problem, and quantum walks and scattering.

•Aug 11, 2011•0 citations

Computational Power of the Quantum Turing Automata

Sina Jafarpour, Mohammad Ghodsi, Keyvan Sadri +1 more

Lots of efforts in the last decades have been done to prove or disprove whether the set of polynomially bounded problems is equal to the set of polynomially verifiable problems. This paper will present an overview of the current beliefs of quantum complexity theorists and discussion detail the impacts these beliefs may have on the future of the field. We introduce a new form of Turing machine based on the concepts of quantum mechanics and investigate the domain of this novel definition for computation. The main object is to show the domain of these computation machines and the new definition of algorithms using these automata. In section one we give a brief fundamental overview of classical complexity theory, Turing machine and all the fundamental concepts required for the next chapters. In section two we describe various classes of classical complexity automata. In next chapter we introduce quantum complexity featuring quantum Turing machines and discuss its relationship to classical complexity. Section four presents a relationship between quantum complexity classes based on the quantum Turing machines and quantum oracles, and their relationship with corresponding classical complexity classes. And section five presents a discussion on the practical phenomena in problem solving using quantum computers. Finally in section five we speculate briefly on the direction we believe the field to be headed, and what might reasonably be expected in the future

•Apr 1, 2007•0 citations

Principles of quantum computing

David Peter Divincenzo

It has recently been recognized that computers could be profoundly more powerful, if the possibilities offered by the basic principles of quantum mechanics were exploited more completely in machine design. It is physically possible for the binary state of a computer itself to obey quantum mechanics, i.e., to evolve along a superposition of different (logical) pathways that could interfere with one another. This is what is meant by a quantum computer. It has recently been shown that such a computer can perform a class of computational problems, including prime factorization, very rapidly. Quantum computers will require an art that is radically different from any that the computer industry practices today. The bits of such a computer will have to be represented by the states of individual atoms. The use of one such atomic degree of freedom, the "spin", is illustrated below.

Digest of technical papers/Digest of technical papers - IEEE International Solid-State Circuits Conference•Nov 19, 2002•7 citations
A computation is an evolution from one physical state to another, and so are Today’s computers, i.e., the computations of them are changes of electric signals. What are differences of quantum computers from classical computers? The computational principles of classical computers are based on classical physics. In principle, we can construct them from devices based on classical physics
There is strong evidence that computers based upon the principles of quantum physics represent an inherently new and more powerful model of computation. Such computers violate the modern form of the Church-Turing thesis (which lies at the foundations of computer science). This thesis can be informally summarized as follows: all physical implementations of computing devices can be described by the same abstract model of computation-the probabilistic Turing Machine or the equivalent random access machine. In this paper, we will describe two formal models for quantum computers: quantum circuits and quantum Turing Machines, introduced by Deutsch [1985].
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.
Computation is a process of performing a large number of simple operations. The main building blocks of classical computers are bits. Each of them can take either the value 0 or 1. A series of gates can change these values by acting on them selectively. This process is structured to fulfil a purpose. For example, if we are interested in adding two numbers, the numbers are encoded into bits and gates are performed such that the final state of the bits reveals the desired answer: a number which is the sum of the initial ones. While it is possible to build algorithms that can perform almost any computation, it is also desirable to find the answer within a reasonable length of time or with a reasonable amount of resources. There is an ever-growing demand in computational power for both scientific and commercial purposes. Indeed, it is surprisingly easy to find an application that can jam even the fastest computer. This fuels a vast effort in the research of information science to increase the speed and processing power of computers. Modern computational models are based on the universal Turing machine (Turing, 1937). This is a theoretical information processing model that employs the elementary gate processes described above. It can efficiently simulate any other device capable of performing an algorithmic process. Since the introduction of the Turing machine, physics has influenced computation in many ways.
Abstract According to the Church-Turing Thesis, a Turing machine, and thus the programming languages and computers in existence, can simulate any reasonable computing device. However, there are physical devices that are exponentially more efficient than a Turing machine, and hence would prove exponentially difficult to simulate using such a machine. This chapter explores the concept of quantum computers and their potential not only to simulate quantum physics exponentially faster than classical computers but also to solve other problems exponentially faster. It considers algorithms that break cryptosystems, find needles in haystacks, and predict who can win a game. It first describes particles, waves, and amplitudes in quantum computation before turning to states and operators. It then examines how interference lets a quantum computer learn some things about a function, how quantum computers can solve factoring in polynomial time, the link between factoring and modern cryptography, graph isomorphism and the hidden subgroup problem, and quantum walks and scattering.
Lots of efforts in the last decades have been done to prove or disprove whether the set of polynomially bounded problems is equal to the set of polynomially verifiable problems. This paper will present an overview of the current beliefs of quantum complexity theorists and discussion detail the impacts these beliefs may have on the future of the field. We introduce a new form of Turing machine based on the concepts of quantum mechanics and investigate the domain of this novel definition for computation. The main object is to show the domain of these computation machines and the new definition of algorithms using these automata. In section one we give a brief fundamental overview of classical complexity theory, Turing machine and all the fundamental concepts required for the next chapters. In section two we describe various classes of classical complexity automata. In next chapter we introduce quantum complexity featuring quantum Turing machines and discuss its relationship to classical complexity. Section four presents a relationship between quantum complexity classes based on the quantum Turing machines and quantum oracles, and their relationship with corresponding classical complexity classes. And section five presents a discussion on the practical phenomena in problem solving using quantum computers. Finally in section five we speculate briefly on the direction we believe the field to be headed, and what might reasonably be expected in the future
It has recently been recognized that computers could be profoundly more powerful, if the possibilities offered by the basic principles of quantum mechanics were exploited more completely in machine design. It is physically possible for the binary state of a computer itself to obey quantum mechanics, i.e., to evolve along a superposition of different (logical) pathways that could interfere with one another. This is what is meant by a quantum computer. It has recently been shown that such a computer can perform a class of computational problems, including prime factorization, very rapidly. Quantum computers will require an art that is radically different from any that the computer industry practices today. The bits of such a computer will have to be represented by the states of individual atoms. The use of one such atomic degree of freedom, the "spin", is illustrated below.