Computational Complexity Theory of Quantum Turing Machines and Quantum Circuits

DOI 機関リポジトリ 機関リポジトリ (HANDLE) NDLデジタルコレクション Web Site

書誌事項

タイトル
Computational Complexity Theory of Quantum Turing Machines and Quantum Circuits
著者
Nishimura, Harumichi
著者
西村, 治道
学位授与大学
名古屋大学
取得学位
博士(学術)
学位授与番号
甲第4968号
学位授与年月日
2001-03-26

この論文をさがす

説明

名古屋大学博士学位論文 学位の種類:博士(学術) (課程) 学位授与年月日:平成13年3月26日

博士論文

資料形態 : テキストデータ プレーンテキスト
コレクション : 国立国会図書館デジタルコレクション > デジタル化資料 > 博士論文
博士論文

目次

Contents

1 Introduction

2 Preliminaries

2.1 Numbers and strings

2.2 Matrices

3 Quantum Turing machines

3.1 Quantum Turing machine as a physical system

3.2 Local transition functions

3.3 Quantum Turing machine as a mathematical structure

3.4 Alternative approaches to characterization

3.5 Multi-tape quantum Turing machines

4 Quantum circuits and universal QTMs

4.1 Programming quantum algorithms by QTMs

4.2 Quantum gates and quantum circuits

4.3 Simulation of a QTM by a quantum circuit

4.4 Existence of an efficient universal QTM

5 Computational complexity of QCFs and QTMs

5.1 Uniformity of quantum circuit families

5.2 Efficient complexity classes of QTMs and QCFs

5.3 Quantum complexity classes with unrestricted amplitudes

5.4 Equivalence of various types of QTMs

A Appendix

A.1 Bound of Mσ

A.2 Proof of the synchronization theorem

A.3 Proof of the unitary theorem

A.4 Proof of the reversal lemma

A.5 Generalization of Theorem 4.3.1 to multi-tape QTMs

詳細情報 詳細情報について

問題の指摘

ページトップへ