QUANTUM COMPUTING - Masaryk University

1 IQUANTUM COMPUTINGJ ozef Gruskaquantum measurement has the effect of magnifying one of the outcomes of QUANTUM superpositionprobabilistic, sequentialOnly at this point do indeterminacy and WORLDCLASSICAL WORLDQ uantum computationisdeterministichighly (exponentially) parallelunitarydescribed by Schrodinger equationusing entanglement as a computationalresourcequantumcomputation( evolution)Classical computationisworking with real probabilities of computation are irreversibly lostMEASUREM ENT come inquantum events from QUANTUM to classical with complex is randomly picked up - all other results amplitudesiiiiiivOn the book web Basic information about the contents of the Ordering and price Second part of the Appendix.

2 (A survey of basic concepts from complexity theory andmodels of COMPUTING . Additional exercises. Historical andbibliographical refrences.)4. eps-versions of figures from the my parentsfor their love and my wifefor her ever increasing care, support and my childrenwith best wishes for their my grandsonwith best wishes for QUANTUM COMPUTING Why QUANTUM COMPUTING .. Prehistory of QUANTUM COMPUTING .. From Randomized to QUANTUM computation .. Probabilistic Turing machines .. QUANTUM Turing machines.

3 Hilbert Space Basics .. Orthogonality, bases and subspaces .. Operators .. Observables and measurements .. Tensor products in Hilbert spaces .. Mixed states and density operators .. Experiments .. Classical experiments .. QUANTUM experiments single particle interference .. QUANTUM experiments measurements .. QUANTUM Principles .. States and amplitudes .. Measurements the projection approach .. Evolution of QUANTUM systems .. Compound QUANTUM systems .. QUANTUM theory interpretations.

4 Classical Reversible Gates and COMPUTING .. Reversible gates .. Reversible Turing machines .. Billiard ball model of (reversible) COMPUTING .. 542 QUANTUM Bits and Registers .. Qubits .. Two-qubit registers .. No-cloning theorem .. QUANTUM registers .. QUANTUM Entanglement .. Entanglement of pure states .. Quantifying entanglement .. Substituting entanglement for communication .. QUANTUM Circuits .. QUANTUM gates .. Measurement gates .. Universality of QUANTUM gates.

5 Arithmetical circuits .. QUANTUM superoperator circuits .. 973 QUANTUM Parallelism and Simple Algorithms .. Deutsch s problem .. The Deutsch Jozsa promise problem .. Simon s problems .. Shor s Algorithms .. Number theory basics .. QUANTUM Fourier Transform .. Shor s factorization algorithm .. Shor s discrete logarithm algorithm .. The hidden subgroup problems .. QUANTUM Searching and Counting .. Grover s search algorithm .. G-BBHT search algorithm .. Minimum-finding algorithm.

6 Generalizations and modifications of search problems.. Methodologies to Design QUANTUM Algorithms .. Amplitude amplification boosting search probabilities .. Amplitude amplification speeding of the states searching .. Case studies .. Limitations of QUANTUM Algorithms .. No QUANTUM speed-up for the parity function .. Framework for proving lower bounds .. Oracle calls limitation of QUANTUM COMPUTING .. 1474 QUANTUM Finite Automata .. Models of classical finite automata .. One-way QUANTUM finite automata.

7 1 QFA versus 1FA .. Two-way QUANTUM finite automata .. 2 QFA versus 1FA .. QUANTUM Turing Machines .. One-tape QUANTUM Turing machines .. Variations on the basic model .. Are QUANTUM Turing machines analogue or discrete? .. Programming techniques for QUANTUM Turing machines .. QUANTUM Cellular Automata .. Classical cellular automata .. One-dimensional QUANTUM cellular automata .. Partitioned QUANTUM one-dimensional cellular automata .. QUANTUM cellular automata versus QUANTUM Turing machines.

8 1855 Universal QUANTUM Turing Machines .. Efficient implementation of unitary transformations .. Design of a universal QUANTUM Turing machine .. QUANTUM Computational Complexity .. Basic QUANTUM versus classical complexity classes .. Relativized QUANTUM complexity .. QUANTUM Communication Complexity .. Classical and QUANTUM communication protocols and complexity .. QUANTUM communication versus computation complexity .. Computational Power of QUANTUM non-linear mechanics .. 2126 Prologue.

9 QUANTUM Key Generation .. Basic ideas of two parties QUANTUM key generation .. Security issues of QKG protocols .. QUANTUM key generation protocols BB84 and B92 .. Multiparty key generation .. Entanglement-based QKG protocols .. Unconditional security of QKG .. Experimental QUANTUM cryptography .. QUANTUM Cryptographic Protocols .. QUANTUM coin-flipping and bit commitment protocols .. QUANTUM oblivious transfer protocols .. Security of the QUANTUM protocols .. Security limitations of the QUANTUM cryptographic protocols.

10 Insecurity of QUANTUM one-sided two-party computation protocols .. QUANTUM Teleportation and Superdense Coding .. Basic principles .. Teleportation circuit .. QUANTUM secret sharing .. Superdense coding .. 2567 Early QUANTUM Computers Ideas .. Benioff s QUANTUM computer .. Feynman s QUANTUM computer .. Peres QUANTUM computer .. Deutsch s QUANTUM computer .. Impacts of Imperfections .. Internal imperfections .. Decoherence .. QUANTUM computation and Memory Stabilization .. The symmetric space.