VIEN TOAN - Viện Toán học

Classical and quantum computation
Kitaev, A. Yu. , Shen, A. H.
Providence
2002

Classical and quantum computation

Tác giả: Kitaev, A. Yu. , Shen, A. H.

Loại tài liệu: Sách, chuyên khảo, tuyển tập

Ký hiệu: Lv4083

Mã giá: 81KI

Nội dung tóm tắt: Xem chi tiết

In recent years interest in what is called quantum computers has grown extraordinarily. The idea of using the possibilities of quantum mechanics in organizing computation looks all the more attractive now that experimenta work has begun in this area. However, the prospects for physical realization of quantum computers are presently entirely unclear. Most likely this will be a matter of several decades. The fundamental achievements in this area bear at present a purely mathematical character. This book is intended for a first acquaintance with the mathematical theory of quantum computation. For the convenience of the reader, we give at the outset a brief introduction to the classical theory of computational complexity. The second part includes the descriptions of basic effective quantum algorithms and an introduction to quantum codes.

Mục lục: Xem chi tiết

Introduction

Part 1. Classical Computation

Turing machines
1. Definition of a Turing machine
2. Computable functions and decidable predicates
3. Turing's thesis and universal machines
4. Complexity classes

Boolean circuits
1. Definitions. Complete bases
2. Circuits versus Turing machines
3. Basic algorithms. Depth, space and width

 The class NP: Reducibility and completeness
1. Nondeterministic Turing machines
2. Reducibility and NP-completeness

Probabilistic algorithms and the class BPP
1. Definitions. Amplification of probability
2. Primality testing
3. BPP a.nd circuit complexity

The hierarchy of complexity classes
1. Games machines play
2. The class PSPACE


Part 2.  Quantum Computation


Definitions and notation
1. The tensor product
2. Linear algebra in Dirac's notation
3. Quantum gates and circuits

 Correspondence between classical and quantum computation

Bases for quantum circuits
1. Exact realization
2. Approximate realization
3. Efficient approximation over a complete basis

Definition of Quantum Computation. Examples
1. Computation by quantum circuits
2. Quantum search: Grover's algorithm
3. A universal quantum circuit
4. Quantum algorithms and the class BQP

Quantum probability
1. Probability for state vectors
2. Mixed states (density matrices)
3. Distance functions for density matrices

Physically realizable transformations of density ma.t.rices
1. Physically realizable superoperators: characterization
2. Calculation of the probability for quantum computatiol
3. Decoherence
4. Measurements
5. The superoperator norm

Measuring operators
1. Definition and examples
2. General properties
3. Garbage removal and composition of measurements

Quantum algorithms for Abelian groups
1. The problem of hidden subgroup in (Z_2^)k;  Simon's algorithm
2. Factoring and finding the period for raising to a power
3. Reduction of factoring to period finding
4. Quantum algorithm for finding the period: the basic idea
5. The phase estimation procedure
6. Discussion of the algorithm
7. Parallelized version of phase estimation. Applications
8. The hidden subgroup problem for Z^k

The quantum analogue of NP: the class BQNP
1. Modification of classical definitions
2. Quantum definition by analogy
3. Complete problems
4. Local Hamiltonian is BQNP-complete
5. The place of BQNP among other complexity classes

Classical and quantum codes
1. Classical codes
2. Examples of classical codes
3. Linear codes
4. Error models for quantum codes
5. Definition of quantum error correction
6. Shor's code
7. The Pauli operators and symplectic transformations
8. Symplectic (stabilizer) codes
9. Toric code
10. Error correction for symplectic codes
11. Anyons (an example based on the toric code)


Part 3. Solutions

S1. Problems of Section 1
S2. Problems of Section 2
S3. Problems of Section 3
S5. Problems of Section 5
S6. Problems of Section 6
S7. Problems of Section 7
S8. Problems of Section 8
S9. Problems of Section 9
S10. Problems of Section 10
S11. Problems of Section 11
S12. Problems of Section 12
S13. Problems of Section 13
S15.  Problems of Section 15

Appendix A.  Elementary Number Theory
A.1. Modular arithmetic and rings
A.2. Greatest common divisor and unique factorization
A.3. Chinese remainder theorem
A.4. The structure of finite Abelian groups
A.5. The structure of the group (Z/qZ)*
A.6. Euclid's algorithm
A.7. Continued fractions

Bibliography

Index 

Thông tin chi tiết

Dạng tài liệu:	Bản in
Chỉ số ISBN:	0-8218-2161-X
Ngôn ngữ:	eng
Mã giá:	81KI
Mã MSC:	Đang cập nhật ...
Tác giả:	Kitaev, A. Yu, Shen, A. H, Vyalyi, M. N
Nhan đề:	Classical and quantum computation
Xuất bản, phát hành:	H : Providence , 2002
Số trang:	257;
Kích thước:	24 cm
Từ Khóa:	computational complexity , machine theory , quantum computers
Bộ sách:	Graduate Studies in Mathematics. 47.

Thông tin xếp giá

ĐKCB: 8145020062873
Tổng số bản: 1
Tổng số bản rỗi: 1
Tổng số đang đặt chỗ: 0

020	##	$a0-8218-2161-X
024	1#	$a2003e:81004 $dpre01776257
041	##	$aeng
084	##	$a81KI
090	##	$cLv4083
100	1#	$aKitaev, A. Yu.
245	##	$aClassical and quantum computation
260	##	$aH:$bProvidence,$c2002
300	##	$a257;$c24 cm
505	0#	$aIntroduction Part 1. Classical Computation 1. Turing machines 1.1. Definition of a Turing machine 1.2. Computable functions and decidable predicates 1.3. Turing's thesis and universal machines 1.4. Complexity classes 2. Boolean circuits 2.1. Definitions. Complete bases 2.2. Circuits versus Turing machines 2.3. Basic algorithms. Depth, space and width 3. The class NP: Reducibility and completeness 3.1. Nondeterministic Turing machines 3.2. Reducibility and NP-completeness 4. Probabilistic algorithms and the class BPP 4.1. Definitions. Amplification of probability 4.2. Primality testing 4.3. BPP a.nd circuit complexity 5. The hierarchy of complexity classes 5.1. Games machines play 5.2. The class PSPACE Part 2. Quantum Computation 6. Definitions and notation 6.1. The tensor product 6.2. Linear algebra in Dirac's notation 6.3. Quantum gates and circuits 7. Correspondence between classical and quantum computation 8. Bases for quantum circuits 8.1. Exact realization 8.2. Approximate realization 8.3. Efficient approximation over a complete basis 9. Definition of Quantum Computation. Examples 9.1. Computation by quantum circuits 9.2. Quantum search: Grover's algorithm 9.3. A universal quantum circuit 9.4. Quantum algorithms and the class BQP 10. Quantum probability 10.1. Probability for state vectors 10.2. Mixed states (density matrices) 10.3. Distance functions for density matrices 11. Physically realizable transformations of density ma.t.rices 11.1. Physically realizable superoperators: characterization 11.2. Calculation of the probability for quantum computatiol 11.3. Decoherence 11.4. Measurements 11.5. The superoperator norm 12. Measuring operators 12.1. Definition and examples 12.2. General properties 12.3. Garbage removal and composition of measurements 13. Quantum algorithms for Abelian groups 13.1. The problem of hidden subgroup in (Z_2^)k; Simon's algorithm 13.2. Factoring and finding the period for raising to a power 13.3. Reduction of factoring to period finding 13.4. Quantum algorithm for finding the period: the basic idea 13.5. The phase estimation procedure 13.6. Discussion of the algorithm 13.7. Parallelized version of phase estimation. Applications 13.8. The hidden subgroup problem for Z^k 14. The quantum analogue of NP: the class BQNP 14.1. Modification of classical definitions 14.2. Quantum definition by analogy 14.3. Complete problems 14.4. Local Hamiltonian is BQNP-complete 14.5. The place of BQNP among other complexity classes 15. Classical and quantum codes 15.1. Classical codes 15.2. Examples of classical codes 15.3. Linear codes 15.4. Error models for quantum codes 15.5. Definition of quantum error correction 15.6. Shor's code 15.7. The Pauli operators and symplectic transformations 15.8. Symplectic (stabilizer) codes 15.9. Toric code 15.10. Error correction for symplectic codes 15.11. Anyons (an example based on the toric code) Part 3. Solutions S1. Problems of Section 1 S2. Problems of Section 2 S3. Problems of Section 3 S5. Problems of Section 5 S6. Problems of Section 6 S7. Problems of Section 7 S8. Problems of Section 8 S9. Problems of Section 9 S10. Problems of Section 10 S11. Problems of Section 11 S12. Problems of Section 12 S13. Problems of Section 13 S15. Problems of Section 15 Appendix A. Elementary Number Theory A.1. Modular arithmetic and rings A.2. Greatest common divisor and unique factorization A.3. Chinese remainder theorem A.4. The structure of finite Abelian groups A.5. The structure of the group (Z/qZ)* A.6. Euclid's algorithm A.7. Continued fractions Bibliography Index
520	##	$a In recent years interest in what is called quantum computers has grown extraordinarily. The idea of using the possibilities of quantum mechanics in organizing computation looks all the more attractive now that experimenta work has begun in this area. However, the prospects for physical realization of quantum computers are presently entirely unclear. Most likely this will be a matter of several decades. The fundamental achievements in this area bear at present a purely mathematical character. This book is intended for a first acquaintance with the mathematical theory of quantum computation. For the convenience of the reader, we give at the outset a brief introduction to the classical theory of computational complexity. The second part includes the descriptions of basic effective quantum algorithms and an introduction to quantum codes.
653	##	$acomputational complexity
653	##	$amachine theory
653	##	$aquantum computers
700	1#	$aShen, A. H.
700	1#	$aVyalyi, M. N.
773	0#	$tGraduate Studies in Mathematics. 47.
900	##	1
911	##	ELIB
912	##	Converted
927	##	Sách, chuyên khảo, tuyển tập

Tổng số ấn phẩm đơn bản:	11285
Tổng số xếp giá:	9118
Tổng số ấn phẩm định kỳ:	392
Tổng số tài liệu điện tử:	63
Lượt truy cập:	37

Classical and quantum computation

Thông tin chi tiết

Thông tin xếp giá

Từ khóa

Thư viện - Viện Toán học

Thông tin tài liệu