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. (A survey of basic concepts from complexity theory andmodels of COMPUTING . Additional exercises. Historical andbibliographical refrences.)4.

2 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 .. 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.

3 Compound QUANTUM systems .. QUANTUM theory interpretations .. 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 .. 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.

4 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 .. 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 .. 1 QFA versus 1FA .. Two-way QUANTUM finite automata.

5 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 .. 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.

6 QUANTUM communication versus computation complexity .. Computational Power of QUANTUM non-linear mechanics .. 2126 Prologue .. 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 .. Insecurity of QUANTUM one-sided two-party computation protocols .. QUANTUM Teleportation and Superdense Coding .. Basic principles .. Teleportation circuit.

7 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 .. Stabilization by projection into the symmetric subspace .. QUANTUM Error-Correcting Codes .. Classical error-detecting and -correcting codes .. Framework for QUANTUM error-correcting codes .. Case studies .. Basic methods to design QUANTUM error-correcting codes .. Stabilizer codes .. Fault-tolerant QUANTUM Computation .. Fault-tolerant QUANTUM error correction .. Fault-tolerant QUANTUM gates .. Concatenated coding .. Experimental QUANTUM Processors.

8 Main approaches .. Ion trap .. Cavity QED .. Nuclear magnetic resonance (NMR) .. Other potential technologies .. 3138 QUANTUM Entropy and Information .. Basic concepts of classical information theory .. QUANTUM entropy and information .. QUANTUM Channels and Data Compression .. QUANTUM sources, channels and transmissions .. Shannon s coding theorems .. Schumacher s noiseless coding theorem .. Dense QUANTUM coding .. QUANTUM Noisy Channel Transmissions .. Capacities of erasure and depolarizing channels .. QUANTUM Entanglement .. Transformation and the partial order of entangled states.. Entanglement purification/distillation .. Entanglement concentration and dilution .. Quantifying entanglement .. Bound entanglement .. QUANTUM information processing principles and primitives .. Search for QUANTUM information principles.

9 QUANTUM information processing primitives .. QUANTUM Theory .. Pre-history of QUANTUM theory .. Heisenberg s uncertainty principle .. QUANTUM theory versus physical reality .. QUANTUM measurements .. QUANTUM paradoxes .. The QUANTUM paradox .. Interpretations of QUANTUM theory .. Incompleteness of QUANTUM mechanics .. Hilbert Space Framework for QUANTUM COMPUTING .. Hilbert spaces .. Linear operators .. Mixed states and density matrices .. Probabilities and observables .. Evolution of QUANTUM states .. Measurements .. Tensor products and Hilbert spaces .. Generalized measurements-POV measurements .. Deterministic and Randomized COMPUTING .. COMPUTING models .. Randomized computations .. Complexity classes .. Computational theses .. Exercises .. Historical and Bibliographical References.

10 396 Bibliography403xiiCONTENTSP refacexiiiPREFACECome forth into the light of Nature be your Wordsworth (1770 1850)Asimplified view of the history of COMPUTING shows that com-puting was thought of mainly as mental processes in the 19th century; it is thought ofmainly as machine processes in the 20th century, and it will be thought of mainly as Natureprocesses in the 21st cannot tell, of course, how much of this vision will be true. Currently, we see vigorous,interesting and, we expect, very important attempts to go much deeper than before intoNature in order to discover its potential for information processing. In this way we alsohope to deepen our understanding of Nature. Perhaps the two areas of greatest potentialare QUANTUM COMPUTING and molecular amount of theoretical research and experimental developments in QUANTUM com-puting grows rapidly. At the same time, interest grows within the science and technologycommunity, especially in physics and theoretical COMPUTING , and this interest in turn givesrise to a need for a systematic presentation and summary of the main concepts, methodsand achievements through textbooks and courses.