Quantum computing and quantum complexity theory

Author

Vazirani, Umesh

Author_Institution

Div. of Comput. Sci., California Univ., Berkeley, CA, USA

Volume

1

fYear

2000

fDate

2000

Firstpage

737

Abstract

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]

Keywords

Turing machines; quantum computing; Church-Turing thesis; abstract model; equivalent random access machine; formal models; probabilistic Turing Machine; quantum Turing Machines; quantum circuits; quantum complexity theory; quantum computing; Circuits; Complexity theory; Computer science; Electrons; Physics computing; Polynomials; Quantum computing; Quantum mechanics; Turing machines; Web pages;

fLanguage

English

Publisher

ieee

Conference_Titel

Circuits and Systems, 2000. Proceedings. ISCAS 2000 Geneva. The 2000 IEEE International Symposium on

Conference_Location

Geneva

Print_ISBN

0-7803-5482-6

Type

conf

DOI

10.1109/ISCAS.2000.857201

Filename

857201