An Introduction to Quantum Complexity Theory
-
- Nishino, Tetsuro
- Department of Communications and Systems Engineering The University of Electro-Communications
Bibliographic Information
- Other Title
-
- Introduction to Quantum Complexity Theory
Search this article
Abstract
In 1985, D. Deutsch introduced quantum Turing machines (QTMs for short) as Turing machines which can perform so called quantum parallel computations. Then, in 1994, P. Shor showed that QTM can factor integers with arbitrary small error probability in polynomial time. The quantum complexity theory is the computational complexity theory based on QTMs. In this paper, we first review the definitions of the QTM and major quantum complexity classes EQP, BQP, ZQP, etc. Then, we present the known results and major open questions in this field.
Journal
-
- 物性研究
-
物性研究 72 (3), 372-376, 1999-06-20
物性研究刊行会
- Tweet
Details 詳細情報について
-
- CRID
- 1050845760558078464
-
- NII Article ID
- 110006410600
-
- NII Book ID
- AN0021948X
-
- ISSN
- 05252997
-
- HANDLE
- 2433/96622
-
- NDL BIB ID
- 4765701
-
- Text Lang
- en
-
- Article Type
- departmental bulletin paper
-
- Data Source
-
- IRDB
- NDL
- NDL-Digital
- CiNii Articles