Emerging Computing Technologies. By Marek Perkowski

CHAPTER 1. INTRODUCTION TO REVERSIBLE LOGIC AND QUANTUM CIRCUITS.

1. Lecture 1.1. Introduction to class. Administrativia. Background. Very short review of Karnaugh Maps. SOP logic. Covering. EXor Logic. ESOP circuits. PDF Format. Please note that in this lecture I specifically tell how the class will be graded. Please read it carefully and ask questions if something is not clear!!....
   
   
2. Lecture 1.2 Lecture on History of Computers. PDF Format. You do not have to learn this material. This is just to show you the tremendous speed of development in last 50 years and some basic principles of technology development in the area of computing. Knowing the past can help us to predict something about the future of computing. Dominating role of biology and system science. Programmability/evolvability tradeoffs. DNA Computing. Quantum Computing. DNA and quantum computers. Government initiatives in Information Technology. The price of programmability. CAD problems in nanotechnology. Biocomplexity. New multi-disciplinary areas of research. Human Genome sequence. Examples of DNA computers. Self-Assembly. Molecular computing. Quantum Computers. DNA assembly of quantum circuits. Research issues. What we can do.
   
   
3. Lecture 1.2 continued. Current research issues. Molecular, DNA and Quantum Computing. PDF Format.
   
   
4. Lecture 1.3. On Reversible logic and reversible gates. PDF Format. Motivation to do research in reversible computing. Moore's law. What may happen, strategic importance. Research issues in reversible/quantum computing. Landauer's Principle. Classical gates are irreversible. Examples of reversible gates. Information is physical. Definition of logical and physical reversibility. Gate as a constraint. Research of Charles Bennett. Mirror computation. Copying. Applications of reversible computing. Links to quantum. Toffoli gate. Width of gate. Ancilla bits. Constants and garbage. NOT and Feynman gates. Swap gates. Structures of reversible gates. Linear gates. Counting reversible functions and subgroups of it. Completing non-reversible functions to reversible. Fan out. Fredkin gates. Cascades and Generalized gates: Generalized Fredkin, Generalized Toffoli, Generalized Kerntopf. Multi-output ESOP cascades. Synthesis problems. Miller gate realization using Toffoli and Feynman gates. Graphical analysis of cascades. Full adder synthesis. Various kinds of garbage bits. Various notations for gates and circuits. Quantum notation. Ideas of search, backtracking and heuristics in synthesis of quantum cascades. Synthesis from inputs to outputs and from outputs to inputs. Bidirectional synthesis. Representation of binary reversible circuits using permutations. Cycles. Transpositions. Even and odd permutations. Zero-storage circuits and their importance. Basic facts about even odd problem. Rough proof. Reversible De Morgan Laws for reversible logic. Pushing gates through the reversible cascade. IDA* search. Exhaustive algorithms. Circuit Libraries. Grover Search. Pseudo-classical circuits (Permutative).
   
   
5. Lecture 1.3 (continued). On representation and analysis of reversible circuits. PDF Format. Classical versus quantum circuits. Transformation to reversible circuits: various methods. Quantum notation for permutative gates. Dirac notation intro. Unitary matrices of basic gates. Kronecker product and matrix product in analysis of quantum circuits. Hierarchical generalizations and construction of gates and especially controlled gates.
   
   
6. Lecture 1.4. On Billiard Ball model of reversible computing and Optical Reversible and Conservative Circuits. PDF Format. Review of basic properties of reversible logic. Landauer and Bennett. Balanced functions. Conservative functions. Typical balanced functions for few variables. Billiard Ball Model. Interaction gate and inverse interaction gate. Switch gate. Inverse switch gate. Using switch and interaction gates. Fredkin and inverse Fredkin gates. How to build it from switch and interaction gates. Uses of Fredkin gate. Examples of conservative property and its meaning. Importance of the Billiard Ball model.
   
   

1. REVERSIBLE 1.1. Edward Toffoli and Tommaso Toffoli, "Conservative Logic". PDF Format. This is the mentioned many times in class famous paper of Fredkin and Toffoli that started whole issue of reversible logic. It is one of background papers in quantum computing.

CHAPTER 2. RECENT RESEARCH IN REVERSIBLE LOGIC.

1. Lecture 2.1. On Davio expansions, Davio gates and Kronecker Functional Decision Diagrams. PDF Format. Shannon Expansion and Shannon Trees. Binary Decision Diagrams. BDD construction. Reduction types. Davio Expansions. Davio gates. KFDDs. Reduction types. Example of OKFDD. Analysis of paths. Flattening. Complement edges. Operations on KFDDs. XOR and AND. Optimization of OKFDDs. Use of simulated annealing to find a better variable ordering for a KFDD.
   
   
2. Lecture 2.2. On synthesis of reversible circuits with garbage bits. PDF Format. Review of gates. Kerntopf, Margolus. Use of inverse circuits and spies. Reduction of garbage. Goals of synthesis. Multi-Purpose Portland Decomposition CAD system. Synthesis of cascades from decision diagrams. Use of function Decision Diagrams. Synthesizing function or its inverse? Composition and decomposition methods. Use of libraries. Use of NPN matching. Forward and backward search. Bidirectional search. Examples of adder synthesis. Completion to reversible function during the synthesis process. Search and heuristics. Adaptation of functional decomposition methods. Levelized expansions of functions.
   
   
3. Basic Method of binary cascade synthesis with unlimited-input Toffoli gate model using Dueck-Maslov-Miller Method. In PPT format.
   
   
4. Synthesis of Multiple-Valued Quantum Cascades using methods of DMM/Curtis and binary cascades by Agarwal et al. Discussion of methods. In PPT format.
   
   
5. Equivalent Transformations of Reversible Circuits based on Kinoshita's DAC 2002 paper. In PPT format.
   
   
6. Efficient representation of quantum circuits for simulation, test and synthesis. QUIDDs. In PPT format. This method can be used for direct execution of matrix and Kronecker multiplications of unitary matrices.

EVOLUTIONARY APPROACHES.




1. Lukac et al paper on GA for binary quantum. This is the starting point.
   
   
2. Paper about evolutionary approach to ternary circuit synthesis.
   
   
3. Publications about LEM (Learnable Evolution Model) by Richard Michalski.
   
   
4. Web Page of Hugo De Garis. Here you will find information about LEM and its use for synthesis of reversible and quantum circuits. Look also to lecture notes for Brain Building class.
   
   
5. M. Khan and M. Perkowski. Genetic Algorithm Based Synthesis of Multi-Output Ternary Functions Using Quantum Cascade of Generalized Ternary Gates. In PDF format.
   
   
6. John Clark. Quantum Genetic Programming. Slides in PDF format.
   
   SYNTHESIS OF TERNARY QUANTUM CASCADES.
7. Fundamental paper of Ashok Muthukrishnan and C.Stroud on ion trap realization of multi-valued quantum gates.
   
   
8. Paper by Erik Curtis about ternary reversible cascade synthesis by an algorithm that generalizes DMM approach.
   
   
9. Erik Curtis and Marek Perkowski. A Transformation Based Algorithm for Ternary Reversible Logic Synthesis Using Universally Controlled Ternary Gates.
   
   
10. M. Khan and Marek Perkowski, Evolutionary Algorithm Based Synthesis of Multi-Output Ternary Functions Using Quantum Cascade of Generalized Ternary Gates. In Word format.
    
    SYNTHESIS OF BINARY QUANTUM CASCADES.
    
    
11. Synthesis of Reversible Circuits. Jiha and Agarwal. Report.
    
    
12. D. Maslov. Dynamic Programming Algorithms as Reversible Circuits: Symmetric Function Realization. In PDF format.

1. REVERSIBLE 1.2. D. Maslov and G. Dueck, "Garbage in Reversible Designs of Multiple Output Functions". PDF Format. This is a recent paper explaining garbage in synthesis of reversible logic.
   
   
2. REVERSIBLE 1.3. D.Maslov, G. Dueck and D.M. Miller, "Templates for Toffoli Networks Synthesis". PDF Format. This is a modern useful paper that explains local optimizing transformations on reversible circuits, which are the second step of most algorithms for reversible logic synthesis. Our system also uses such transformations in conjunction with exhaustive search and genetic algorithm.
   
   
3. REVERSIBLE 1.4. D.M.Miller and G.W.Dueck, "Spectral Techniques for Reversible Logic Synthesis". PDF Format. In class we learn about Reed-Muller Spectral Transformation and Walsh Transformation. Here is an example how spectra can be used to improve convergence of greedy algorithm for logic synthesis of reversible cascades.
   
   
4. REVERSIBLE 1.5. D. Maslov and G.W. Dueck,"Asymptotically Optimal Regular Synthesis of Quantum Networks. PDF Format. A recent paper on using generalized Toffoli gates in synthesis of reversible cascades. Good for projects and homeworks.
   
   
5. REVERSIBLE 1.6. G.W. Dueck and D. Maslov, "Reversible Function Synthesis with Minimum Garbage Outputs". PDF
   
   
   
   Format. This recent paper has good discussion of examples. You can compare your results with their results.
   
   
6. REVERSIBLE 1.7. D.M. Miller, D. Maslov, and G.W. Dueck, "A Transformation Based Algorithm for Reversible LOgic Synthesis. PDF Format. Several issues such as algorithm, backtracking and transformations, as well as good examples.
   
   
7. REVERSIBLE 1.8. G.w.Dueck, D. Maslov, and D.M. Miller, "Transformation-based Synthesis of Networks of Toffoli/Fredkin Gates. PDF Format. More ideas and examples from Dueck's group. This paper will be easy to understand if you read their previous papers.
   
   

1. REVERSIBLE 1.9. M. Perkowski, P. Kerntopf, A. Buller, M. Chrzanowska-Jeske, A. Mishchenko, X. Song, A. Al-Rabadi, L. Jozwiak, A. Coppola, B. Massey, "Regularity and Symmetry as a Base for Efficient Realization of Reversible Logic Circuits". PDF Format. Ideas about regularity in reversible logic. A base of modern methods based on regular structures of Toffoli gates that I teach in the class.
   
   
2. REVERSIBLE 1.10. P. Kerntopf, "A Comparison of Logic Efficiency of Reversible and Conventional Gates". PDF Format. Recent paper by Pawel Kerntopf on reversible logic. It has definitions of important gates and interesting statistical results that may be useful to create new synthesis methods and new gates with more qubits.
   
   
3. REVERSIBLE 1.11. P. Kerntopf, M.A. Perkowski, M.H.A. Khan, "On Universality of Ternary Reversible Logic Gates." PDF Format. This is a recent paper from 2003 Ultra Large Scale LSI (ULSI) Symposium. Ideas can be used on exam. We discussed ternary reversible gates in additional meetings. These are first experimental results on ternary gates and their universality. Can be useful in project on GA approach to ternary synthesis, as discussed in class.
   
   
4. REVERSIBLE 1.12. M. Perkowski, P. Kerntopf, A. Buller, M. Chrzanowska-Jeske, A. Mishchenko, X. Song, A. Al-Rabadi, L. Jozwiak, A. Coppola, B. Massey, "Regular Realization of Symmetric Functions using Reversible Logic." PDF Format. Here are multi-valued regular gates and structures. Year 2001 paper by Perkowski et al about regular reversible logic. Source of ideas for exams and homeworks.
   
   
5. REVERSIBLE 1.13. Marek Perkowski, "Regular Structures." PDF Format. Slides to a new paper about reversible logic and regularity. Source of class ideas and for projects.
   
   
6. REVERSIBLE 1.14. T. Hirayama, K. Nagasawa, Y. Nishitani, K. Shimizu, "Double Fixed-Polarity Reed-Muller Expressions: A New Class of AND-EXOR EXpressions for Compact and Testable Realization." PDF Format. A very recent paper about ESOP circuit synthesis for increased testability. ESOP circuits are fundamental in reversible and quantum synthesis. This paper presents more advanced methods than the algorithms presented in class and can become a source of ideas for modern ESOP minimizer for quantum logic.
   
   
7. REVERSIBLE 1.15. Introduction and Overview of Multiple-Valued Logic. PDF format. This is an easy introduction to multiple-valued logic. It is sufficient for the material covered in this class.
   
   
8. QUANTUM 7.3. A. Buller, "Quantrix. Toward Automated Synthesis of Quantum Cascades."
   Elementary introduction to quantum circuits with calculated examples. Useful to Lecture 7.1.
   Word format
   PDF Format
   
   
9. QUANTUM 7.4. Goran Negovetic. Hardware Implementation of Quantum Circuits. First Proposal of student's class project. PDF format.
   
   
10. QUANTUM 7.5. G. Negovetic, "Quantum Gates - Hardware Implementation. Verilog Hardware simulator of quantum gates. PDF format.
    
    
11. QUANTUM 7.6. M. Perkowski, A. Al-Rabadi, P. Kerntopf, "Multiple-Valued Quantum Logic Synthesis." PDF Format.
    A recent paper about multiple-valued quantum logic synthesis. Useful for definition of new quantum gates and their use in synthesis.
    
    
12. QUANTUM 7.7. Mozammel H.A. Khan, Marek Perkowski and Pawel Kerntopf, "Multi-Output Galois Field Sum of Products Synthesis with New Quantum Cascades." PDF Format. Recent paper by Mozammel Khan, et al for ISMVL 2003 conference. New approach to multiple-valued cascades with complex gates. New type of MV logic factorization for reversible gates.
    
    
13. Introduction to Reversible Computing and Fredkin Gates. PDF format.
    
    

1. 5.1. Homework 2. Instruction what to do. PDF Format. This homework requires to read about quantum and reversible computing and evolutionary algorithms. It is enough if you read the slides given below.
   
   
2. 5.2. Some Recent Research Issues in Quantum Logic. Auxiliary slides for homework 2. Part 1. PDF Format.
   
   
3. 5.3. Some Recent Research Issues in Quantum Logic. Auxiliary slides for homework 2. Part 2. PDF Format. Kronecker Functional Decision Diagrams.
   
   
4. 5.4. Some Recent Research Issues in Quantum Logic. Auxiliary slides for homework 2. Part 3. PDF Format.
   
   
5. 5.5. Paper about multiple-valued quantum gates. PDF Format. A. Al-Rabadi, L. Casperson, M. Perkowski, and X. Song, "Multiple-Valued Quantum Logic". New paper about synthesis of mv quantum circuits - your evolutionary algorithm can be adapted from binary to multiple-valued circuits, such as these.
   
   
   Student presentations.
   
   
6. 5.6. Ki-yong Ahn, Introduction to Reed-Muller Logic. PDF Format.
   PPT Format.
   
7. 5.7. Seon Pil Kim, Layout Driven Synthesis for Submicron Technology: Mapping Expansions to Regular Lattices. PDF Format.
   PPT Format.
   
8. 5.8. HeeJun Shim, Lattice Diagrams Using Reed-Muller Logic. PDF Format.
   PPT
   
9. 5.9. Hyungock Kim, Multi-Level Programmable Array. PDF Format.
   PPT Format.
   
10. 5.10. Hwangbo Woong, Layout Driven Synthesis for Submicron Technology Mapping Expansion to Regular Lattices.
    PPT Format.
    
11. 5.11. Jung-wook Kim, Introduction to quantum logic. I. PDF Format.
    PPT Format.
    
12. 5.12. Yong-woo Choi, Introduction to quantum logic. II. PDF Format.
    PPT Format.
    
13. 5.13. Dongsoo Lee, GRASP: A Search Algorithm for Propositional Satisfiability. PDF Format.
    PPT Format.
    

CHAPTER 3. QUANTUM COMPUTING FUNDAMENTALS.

SECTION 3.1. INTRODUCTION TO QUANTUM COMPUTING.

1. Lecture 3.1.1. Motivation and Introduction to Quantum Computing.
   PDF Format History and background of Quantum Computing. What is quantum computation. Why bother with quantum computation. The power of quantum computation. Nobody understands quantum mechanics. A beam splitter. An interferometer. Possibilities count. Calculating inteference. Double Slit interference. Quantum Interference: Amplitudes are added and not intensities. Interference in the interferometer. Notation for quantum interference. More experimental data. A new theory. Probability amplitude and Measurement. Quantum operations. Linear Algebra. Abstraction. More than one qubit. Entanglement. Measuring multi-qubit systems. Measurement. Classical versus quantum. Quantum circuits characteristics. Reversible circuits. Quantum gates. Polarizing Beam-Splitter CNOT gate. Barenco. Quantum gates and circuits. Simulation of a quantum circuit. Operations on matrices.
   
   

1. Topics to Chapter 1 from the Chuang/Nielsen textbook. This includes also additional material. Only material covered in class is required for final exam.
   In Word format.
   In PDF Format.
   
   
2. QUANTUM 3.1.2. Eleanor Rieffel and Wolfgang Polak, "An Introduction to Quantum Computing for Non-Physicists." Well-known tutorial of Rieffel and Pollak - An easy to follow Overview of Quantum Computing.
   PDF Format

SECTION 3.2. COMPUTER SCIENCE AND QUANTUM COMPUTING.

1. Lecture 3.2.1. On Computer Science related to Quantum Computing. Mostly undecidability and complexity.
   PDF Format Review. Artificial Intelligence. Turing Test. Time Complexity. Computational Complexity. Hard problems and common sense. Factoring is tough. Computer Science and models of computation. The Hilbert Problems. Kurt Goedel. Goedel's Incompleteness Theorem. Implications. Turing Machines. Probabilistic Turing Machines. Universal Computation. Church-Turing Thesis. Univeral Turing Machines. The Halting Problem. Circuits. Universality of Circuit Model. Families of Circuits. Turing Machine Countability. Strong Turing-Church Thesis. Computational Complexity Classes. What is a Language? Computability/Decidability versus Languages. Why a Formalization is necessary? Single Instance Problems. Computable functions. Decidability. Mass Problems. Two Examples of Mass Problems. Computable function for a Mass Problem? Decision Problems; Computational complexity. Computability versus Decidability. Asymptotic notation for complexity. Division to tractable versus intractable problems. Slightly finer division to complexity classes. Class P. The Class P in terms of languages. Class NP. How are NP and P related? A corollary about witnesses. Class Co-NP. Class NP-Complete. Example: Hamiltonian Cycle. Example: Euler Cycle. Euler is easy. Class NPI. Classes PSPACE and EXP. Class Inclusion. Class BPP. Chernoff bound and BPP. What are efficient problems? How it relates to quantum. Feynman's question. Classical simulation. Classical Probabilistic simulation. The Feynman Processor. Quantum Turing Machines. Deutsch and Quantum Parallelism. Deutsch Processor. Computational Complexity Classes - role of quantum. Exam Problems.

1. Computational Complexity. To Lecture 3.2.
   QUANTUM 3.2.a. Review of Post and Markov algorithms in PDF format. Production Systems. Basis idea. Example. Lack of control strategy. Markov Algorithm. Applying Production rules.
   
   
   QUANTUM 3.2.b. Review of Predicate Calculus in PDF format. Clausal logic. Deduction. Trees. Resolution. Substitution. Herbrand Universe. Propositional - Relational - Full Clausal Logic.

1. Topics to Chapter 3 from the textbook. This includes also additional material. Only material covered in class is required for final exam.
   In Word format.
   In PDF Format.
   
   
2. QUANTUM 7.8. Daniel S. Abrams and Seth Lloyd, "Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems." PDF Format. A very interesting and potentially revolutionary paper by Abrams et al that links P=NP problem solution to non-linearity versus linearity of quantum mechanics. Read it for fun.
   
   
3. NEW DISCOVERY.
   Student Hyunkoo Jee found this interesting information about a new important discovery, which I did not cover in class. It may lead to new non-quantum factorization algorithms and to new discoveries in quantum computing as well.
   Three Indian computer-scientests found an algotithm that can distinguish whether a given number is prime or not... (primality test problem) in P (ploynomial time). It is a deterministic algorithm (not stochastic!).
   Here is an introduction page (It's in Korean language, but the important part is written in English). Internet Information 1.
   
   
   And here is an article in 'Science Magazine'
   Internet Information 2.
   And here is the original webpage from the inventers of the algorithm. This page contains full material about this (including the original papers)
   Internet Information 3.

CHAPTER 4. MINIMAL QUANTUM MECHANICS FOR QUANTUM COMPUTING.

1. Lecture 4.3.1. On algebra used in quantum computing.
   PDF format Review. Complex numbers. Complex exponentiation. Qubit. Properties of qubits: complex numbers. Abstract Vector Spaces. Hilbert Spaces. Vector representation of states. Dirac's Ket Notation. Vectors. Vector Space. Basis vectors. Bases and linear independence. Quantum Notation. Linear Operators. Pauli Matrices. Inner Products. Eigenvalues and Eigenvectors. Inner and Outer Products. Hermitian operators. Unitary and Positive Operators. Tensor Products. Functions of Operators. Trace and Commutator. Polar Decomposition.
   
   
2. Lecture 4.3.2. On Postulates of Quantum Mechanics.
   PDF format Linear Operators. Eigenvalues and Eigenvectors. Unitary Transformations. Postulates of QM: objectives. Connections between physical systems and quantum mechanics. Postulate 1. State Space. Systems and Subsystems. Closed versus Open Systems. Concrete versus Abstract Systems. States and State Spaces. Distinguishability of states. State Space. Qubit as the simplest State Space. Distinguishability of states: more precisely. State Vectors and Hilbert Space. Postulate 2: Evolution. Example of Evolution: Hadamard Gate. Time Evolution. Wavefunctions. Schroedinger Wave Equation. Features of the wave equation. Heisenberg and Schroedinger views of Postulate 2. Postulate 3: Quantum Measurement. Probability and Measurement. Simple example of states and measurements. Observables. Measurement and general formulas. Notation for Quantum Measurement. What happens to a system after measurement? Distinguishability. Projective Measurements. Uncertainty Principle. Positive Operator-Valued Measurements (POVM). Phase. Density Operators. Mixed States. Postulate 4: Composite Systems. Compound Systems. Composition example. Entanglement. Size of Compound State Spaces. General Measurements in Compound Spaces. Superdense Coding. Key points to remember.
   

1. Topics to Chapter 2 from the Chuang/Nielsen textbook. This includes also additional material. Only material covered in class is required for final exam.
   In Word format.
   In PDF Format.

CHAPTER 5. QUANTUM CIRCUITS.

1. Lecture 5.1. On Quantum gates and Circuits. Deutsch, Deutsch-Jozsa and Simon algorithms.
   PDF format MISSING!!!
   
   
2. Lecture 5.2. On Shor algorithm.
   PDF format Quantum Circuits: Quantum Fourier Transform. Shor's Factoring Algorithm. Main idea of factoring. Powers of numbers mod N. Discrete Log Example. The order of x mod N. Order-finding permits factoring. Factoring Example. Number-Theory Trick. Example. Quantum Approach. Using Fourier Transform. Quantum Order Finding.
   
   

1. Topics to Chapter 4 from the textbook. This includes also additional material. Only material covered in class is required for final exam.
   In Word format.
   In PDF Format.
   

CHAPTER 6. QUANTUM CRYPTOGRAPHY.

1. Lecture 6.1. On Quantum Key Distribution.
   PDF format Cryptology. Enigma. Turing. Computers and Ciphers. From Enigma to Colossus. Public Key Cryptosystems. Factorization. Quantum Cryptology. What is the problem with classical cryptography? Key distribution. Crypto Definitions. Alice, Bob, and Eve. Quantum Cryptography. Key. Secure Cipher. Key Distribution. Quantum Key Distribution (QKD). Photons. Qubit: Polarization state of a single photon. Polarization. Photon Qubits. Quantum Cryptography - polarized bases. State of the Art. Eavesdropping with wrong reference system. Complete example. Setup. Encoding Process. Alice's choice. Bob's task. Decoding. Eavesdropping test. Common Key. Quantum Cryptography - bad Eve. The effect of Eve. Commercial status. Quantique Corporation.

CHAPTER 7. ERROR CORRECTION CODES, TESTING AND FAULT-TOLERANT QUANTUM COMPUTING.

SECTION 7.1. QUANTUM ERROR CORRECTION AND FAULT TOLERANT COMPUTING.

1. On Quantum Error Correction.
   Lecture 7.6.1. in PDF format Quantum errors. Classical error codes. Parity checking. Quantum Error correction by Shor. Reversible networks for encoding and decoding. 3-qubit error correction. Encoder, decoder, decoder without measurement. Reversible 5-qubit network for error correction. Stabilizer measurement. Notations. Operations on logical bits. Quantum network for correcting errors.

1. Auxiliary reading about error correcting codes. Chapter 10 from Nielsen and Chuang.
   1. Introduction.
   2. The three qubit bit flip code. (recall no-cloning).
   3. The three qubit phase flip code.
   4. The Shor code.
   5. Theory of quantum error-correction.
   6. Quantum error-correction without measurement (page 439).
   7. Independent error models.
   8. Degenerate codes.
   9. The quantum Hamming bound.
   10. Constructing quantum codes.
   11. Classical linear codes.
   12. Calderbank-Shor-Steane Codes.
   13. Stabilizer Codes.
   14. The Stabilizer Formalism.
   15. Unitary gates and the Stabilizer Formalism.
   16. Measurement in the Stabilizer Formalism.
   17. The Gottesman-Knil Theorem.
   18. The three qubit bit flip stabiliser code (page 467).
   19. The nine qubit Shor code (page 468).
   20. The five qubit code (page 468).
   21. CSS codes and the seven qubit code. (page 469).
   22. Standard form for a stabiliser code. (page 470).
   23. Quantum circuits for encoding, decoding, and correction.
2. Auxiliary reading about fault-tolerant quantum computation. Chapter 10 from Nielsen and Chuang.
   1. Fault-tolerance: the big picture.
   2. Fundamental issues.
   3. Fault-tolerant operations. Definitions.
   4. Example: Fault-tolerant CNOT.
   5. Concatenated codes and the threshold theorem.
   6. Fault-tolerant quantum logic.
   7. Normalizer operations.
   8. Fault-tolerant Pi/8 gate.
   9. Fault-tolerant Toffoli gate.
   10. Fault-tolerant measurement.
   11. Measurement of stabilizer generators.
   12. Resilient quantum computation.
   13. Encoding by teleportation.

1. Sowmya Aligala, Sreecharani Ratakonda, Kiran Narayan, Kanagalakshmi Nagarajan, Martin Lukac, Jacob Biamonte and Marek Perkowski, Deterministic and Probabilistic Test Generation for Binary and Ternary Quantum Circuits. ULSI 2004 Workshop, Toronto, Canada, May 19, 2004. In PDF format.
   
   
2. Kavitha Ramasamy, Radhika Tagare, Ed Perkins, and Marek Perkowski, An efficient greedy algorithm to create adaptive trees for fault localization in binary reversible circuits. Proc. IWLS 2004, Temecula, California, June 2004. This paper demonstrates that fault localization for reversible logic circuits is simpler than for traditional circuits. OLD VERSION.
   
   
3. K. Ramasamy, R. Tagare, E. Perkins, and M. Perkowski, Fault Localization in Reversible Circuits is easier than for Classical Circuits. In PDF format.
   
   
4. Cherrie Huang. Introduction to Quantum Error Correction and Fault-Tolerant Quantum Logic. Student Slides in PPT format. Not finished.
   
   

1. For ULSI workshop. OUR SLIDES not ready. In PPT format.
   
   
2. Notations of binary versus ternary controlled quantum gates.
3. P. Cameron. Easy slides about Quantum Error Correction. For beginners. In PDF format. Classical versus quantum. Classical Error Correction. States and observables. Quantum errors. Bits and Qubits. Quantum errors. Quantum Codes. GF(4) to quantum. Quantum Error Correction.
   
   
4. G.E.Moorhouse. Quantum Codes. Easy intro slides in PDF format. References. The No-Cloning Theorem. Discretized Quantum Errors. Encoding one qubit as three qubits. Decoding the three-qubit code. Encoding one qubit as seven qubits. Decoding bit-flip errors in the seven-qubit code. Decoding Phase errors in the seven-qubit code. Application of Logic Gates to Encoded Qubits. Correcting many qubit errors.
   
   
5. Johannes Vrana. Elementary slides on basics of Quantum Error Correction. In PDF format. Decoherence and Errors. Errors. Classical 3 Bit Error Correction. Initial Consideration of Quantum Error Correction. Error Types: Bit-Flip and Phase Errors. Three Qubit Error Correction for Bit-Flip Errors. Three Qubit Error Correction for Phase-Flip Errors. The Shor Code. Restrictions and the Laws of Fault-Tolerant Computation. Bibliography.

1. Markus Grassl. Quantum Error Correction Codes. Good Intro. In PDF format. Quantum Error Correction. Constructions. Algorithms. Encoder based on Quantum Shift Registers. Graph Codes. Graph Codes and Stabilizer Codes. Fault-Tolerant Quantum Computing. Decoherence Free Subspaces. DFS: Fault-Tolerant Operations. Jump codes. QECC: Possible directions to proceed. Exhaustive references on the subject.
   
   
2. WEB page of Knill. Very good.
   
   
3. Dave Bacon. Advanced Topics in Error Correcting Codes. Slides in PDF format. Good slides on a very advanced topics. Pauli Group. Abelian Subgroup. Pauli Stabilizer Code. Truth by example. Sizing up the code. Stabilizer Subspaces. Stabilizer Nerror. Surfing the subspaces. Examples. Quantum Hamming Bound. Detect Distinguishable Correct. Clifford and codes. Error Codes in Physical Systems. Supercoherence. Making Decohorence work hard. Toric codes.
   
   
4. Isaac Chuang. Threshold for life. Life can be constructed from faulty components. How Faulty? Slides in PPT format. Relations of QC to biology. Reliable computers can be constructed from faulty components. Classical fault-tolerant circuits of Winograd and Cowan. The Fault-Tolerance Threshold. Efficient Fault-Tolerance. What is life? Fault-Tolerant Life? Von-Neumann's Automaton. What is the fault-tolerant threshold for Life?
   
   
5. Computing with Noisy Quantum Computers. Dorit Aharnov. UC. Berkeley. Slides in PPT format. Correcting quantum noise. Polynomial quantum codes. Error Correction. Computing on Encoded states. How faults spread. Universality. Threshold results. Concatenated simulations.
   
   
6. Aharonov. Quantum Computation in the presence of noise. Slides in PPT format. Noise model. The Accuracy Threshold Theorem. Quantum Error Correcting Codes. How to correct errors. Correcting Errors over F_p. Polynomial Codes. Fourier Transform. Computing on Encoded states. Fault Tolerant Procedures. Gegree Reduction. Error Correction. Ancilla Factory. Analysis for purification. Threshold calculation. Fractal Protected Manifold.
   
   
7. D. Aharonov, M. Ben-Or. Fault-Tolerant Quantum Computation with Constant Error. Paper in PDF.
   
   
8. Daniel Gottesman. Beyond the DiVincenzo Criteria. Requirements and Desiderata for Fault-Tolerance. PPT slides. Di Vincenzo Criteria. Requirements for Fault-Tolerance. Additional Desiderata. Concatenated Codes. Parallel Operations. Erasure Errors. Fresh Ancilla States. Large-Scale Error Rates. Correlated Errors. Error Threshold. The Meaning of Error Rates. Long-Range Gates. Fast Classical Processing. Correlated Error Redux. Coherent Errors. Restricted error model.
   
   
9. Bartosz Blimke. Fault-Tolerant Quantum Computation. What is fault-tolerant computation ? Why error-correcting codes are not sufficient guarantee for successful error-correction? Some Solutions for fault tolerant quantum networks. Error Propagation. Faul-tolerant ancilla. Verification of ancilla state. Testing of syndrome measurements. Fault-tolerant software quantum gates. Fault-tolerant hardware quantum gates. Concatenated coding.
   
   
10. Scribe J Hodges. MIT Lecture 23. Fault-tolerant quantum computation. In PDF format. Classial theorem of Fault-Tolerance. Using classical techniques for quantum computation. Quantum Fault Tolerance. Fault Tolerance of Hadamard gate. Fault Tolerance of CNOT gate. Error Correction with Fault-Tolerant Precision.
    
    
11. Jean Bellissard, Quantum Computing, an Introduction (with fault tolerance discussed). Slides from Georgia Tech in PDF format. History of ideas in quantum computing. CSS error-correcting code. Kitaev and topological error correcting codes. Density matrices and Bloch Ball. Quantum gates and circuits with measurements. Quantum computers and laws of physics. Principles of Quantum Mechanics.
    
    
12. Oskin. A Practical Architecture for Reliable Quantum Computers. Easy to understand overview paper in PDF format. Quantum computation. Programming Model. Quantum Error Correction. Recursive Error Correction. Error Correction costs. Quantum Computer Architecture. Quantum ALU. Quantum Memory. Quantum wires. Code Teleportation. Dynamic Scheduler. Application-specific error optimization.
    
    
13. Semion Saikin. Slides in PPT format about quantum computing and qubit decoherence. Modeling of quantum systems. Applications. Entanglement. Stability criteria. Physical realization of a qubit. Decoherence: interaction with macroscopic environment. Measure of decoherence. Donor Electron Spin in Si.
    
    
14. Van Dam et al. Self-testing of Universal and Fault-Tolerant sets of quantum gates. Paper in PDF format.
    
    
15. B.Marthi, M. Whitney. Fault-tolerant Quantum Computing. tutorial in PDF format. Shor's result. Threshold calculation. Degree Reduction.
    
    
16. D. Gottesman. Theory of fault-tolerant quantum computation. Paper in PDF format.
    
    
17. Knill, Laflamme and Zurek. Resilient Quantum Computation. Easy to understand paper in PDF format.
    
    
18. Shor. Fault Tolerant Quantum Computation. Important paper by Shor in PDF format.
    
    
19. K.H. Kim. Issues Insufficiently resolved in Century 20 in the Fault-Tolerant Distributed Computing Field. A source of great ideas. Discussion paper in PDF format.
    
    
20. Steane. General Theory of Quantum Error Correction and Fault Tolerance. Lectures in PDF format.
    
    
21. Hayes. Short goals of their research.
    
    
22. Maxim Raginsky. Scaling and renormalization in fault-tolerant quantum computers. Paper. In PDF format.
    
    
23. J. Niwa and K. Matsumoto. Simulating the Effects of Quantum Error Correction Schemes. Research Paper in PDF format. A source of good methodology to be used by us.
    
    
24. Literature on quantum error correction experimental work. In PDF format.

CHAPTER 8. PHYSICAL REALIZATION OF QUANTUM COMPUTERS.

1. Lecture 8.1. On Physical Realization of Quantum Computers.Nuclear Magnetic Resonance.
   Lecture 7.7.1 in PDF format Two Level Atom as a qubit. Physical Implementation. Main contenders. Quantum technology requirements for physical implementation. Decoherence. Decoherence-related figure of merit. Using a single molecule. Nuclear Magnetic Resonance. How to implement a logic operation NMR. Controlling spins. Protons and their spins. Physical implementation of NMR. Spins and coherence. Inte-atomic bonds. Electromagnetic Fields. RF pulses. CNOT gate and machine language. Liquid State NMR Ensemble Computers. RF Coils and Static Field Coils. NMR in the works. Advantages of NMR. Disadvantages of NMR. Example: 7-qubit Quantum Computer by IBM. Experimental realization of Shor's Factoring Algorithm. The molecule. Pulse sequence. Results: Spectra. Result: circuit simplifications. Linear ion trap. What about scaling. Are scaling problems technical or fundamental? Other realized circuits: error correction.

CHAPTER 9. QUANTUM TRANSFORMS AND WAVELETS.