1ª aula
Apresentação: Organization, Program, Introduction
1ª aula
Apresentação: Organization, Program, Introduction
2ª aula
Thermodynamics, Entropy, Macroscoping and Microscoping state, Dice model , Information and Entropy, Definition of Entropy as the number of Questions, Information Theory
3ª aula
Communication, Message, Information Theory, Representation of information, Signal alphabet, Surprise, Information and probability, Statistical encoding, Conditional Entropy
4ª aula
Entscheidungsproblem, Turing machine, Halting Problem, Godel, Computability, Univerality, Complexity, Church-Turing thesis, Strong Church-Turing thesis, Reformulation of the Strong Church-Turing thesis by Deutsch, Probabilistic Turing Machine, Quantum Turing Machine, Reversible gates
5ª aula
Overview of Quantum Computers, Qubit, Notation, Bra, Ket, Hilbert Space, Suprposition, Quantum Memory, Eigenstrates, Unitary Evolution, Observables as Hermitian Operators
6ª aula
Classical Physics, Hamiltonian equation of motion, Probabilistic System, Markov chain, Quantum coin, destructive interference, Hilbert Spaces, Operators, adjoint operator,self-adjoint operator, unitary operator, Spectral representation, Spectral Representation of Unitary Operators
7ª aula
Quantum States as Hilbert Space Vectors, Compound systems, Quantum Time Evolution, Observables, Spectral representation, Density Matrices
8ª aula
Unitary operators, NOT gate, square root of the not-gate, Hamarad-Walsh matrix, decomposable is entangled states, controlled not gate
9ª aula
No-cloning Theorem, Quantum Copymachine, Observation procedure, Properties of QTM, Reversible Circuits, Toffoli gate, Quantum Circuits
10ª aula
Properties of QTM, Reversible Circuits, Toffoli gate, Uncomputing auxiliary bits, entangelment
11ª aula
Hadamard Gates, Matrix representation of serial and parallel operations, Deutsch Algorithm, Deutsch-Jozsa Algorithm
12ª aula
Discrete Fourier Transform, Fast Fourier Transform, The quantum Fourier Transform (QFT), QFT circuit
13ª aula
Symmetric Cryptography, Asymmetric Cryptography, RSA, Number Field Sieve" heuristic algorithm, Code-Breaking on a Quantum Computer, Shor's Algorithm, period of x modulo n, quantum algorithm
14ª aula
Shor's Algorithm, Quantum Core, Example, Euclid's Algorithm,continuous fraction, convergent, omitting the internal measurement, generalization
15ª aula
Search Problems, Quantum Search with One Query, Quantum Blackbox
16ª aula
Operators for Grover's Amplification, Amplitude Amplification, inversion about average, probability to find the answer, Iterative use, what is the requiered number of queries?, NP problems and the complexity O(sqrt(2**n))
17ª aula
Geometric Visualization, Housholder Matrix, Example, Periodic behavior, visualization, quantum counting
18ª aula
Optimality of the search algorithm (proof), NP-complete problem (proof given on blackboard)
19ª aula
Problem-solving and Quantum Computation, Example 8-Puzzle, 3-Puzzle, Board Configurations, Black Box, Operator, Oracle, Groaver's amplification algorithm, L. Tarrataca and A. Wichert: Problem solving and quantum computation, Cognitive Computation, in press doi:10.1007/s12559-011-9103-6
20ª aula
Tree Search and Quantum Computation, Constant branching factor, speedup in search with non constant branching factor, Heuristics and Quantum Search
21ª aula
What is Teleportation? EPR effect, local interaction, nonlocal interaction, entangled state, ebit, teleporitng a qubit
22ª aula
Kolmogorov Probability and van Neumann Probability, Theorem of total probability, Joint distribution, Relation to Quantum Computing, Tensor Product, Collapse corresponds to the updating of a probability distribution in light of new information, Busemeyer: Experiments
23ª aula
Quantum Cognition by Catarina Moreira
24ª aula
Classical physics information , Shannon information, Von Neumann entropy, density matrix, Conjugate pairs, Heisenberg Uncertainty, Polarization, Quantum Cryptography, Detection of eavesdropping
25ª aula
Overview: The Library of Babel, What is an A?, Entropy - Information, Measurment, Hierarchy, Information Gain, Entscheidungsproblem, The Church-Turing thesis, Simple 2-state system, qubit, Compound systems, Toffoli gate, Spectral Representation of Unitary Operators, Shor's Algorithm for factoring n, Grover's Amplification, Quantum Production Systems, Quantum Tree Search, No teleportation theorem, ebit, von Neuman probabilities, von Neumann entropy