Vorlesung im Sommersemester 2015

Quantum Computing – Grundlagen der Quanteninformationsverarbeitung

(Dr. Markus Grassl, Prof. Dr. Gerd Leuchs)

Vorlesung, 2,5 SWS, ECTS-Studium, ECTS-Credits: 5
Zeit:	dienstags, 14:00-15:45 Uhr
Ort:	Hörsaal D HD (Physikum)
Prüfung:	mündlich, nach Vereinbarung (Terminvereinbarung per E-Mail) vorraussichtliche Termine: Mo., 03.08.2015, Do., 06.08.2015, Mi., 02.09.2015

Quantenrechner bieten die Perspektive, zumindest bestimmte Probleme mit einer geringeren Komplexität zu lösen als klassische Computer. Allen voran sind als Beispiele der Algorithmus von Shor zur Faktorisierung ganzer Zahlen in polynomialer Zeit sowie der Algorithmus von Grover zur Urbildsuche zu nennen.
Nach einer Einführung in das auf den Prinzipien der Quantenmechanik basierende Berechnungsmodell werden verschiedene Quantenalgorithmen genauer betrachtet. Ergänzend werden grundlegende Verfahren zur Implementierung von Quantentransformationen, Fehlerkorrektur und Fehlertoleranz besprochen. Ein weiteres Themengebiet umfasst Grundbausteine der Quantenkryptographie.

Die Vorlesung wendet sich an Studierende der Fachrichtungen Physik, Informatik, Mathematik sowie Elektrotechnik im letzten Jahr des Bachelorstudiums oder im Masterstudium. Die erforderlichen Grundlagen werden in der Vorlesung vermittelt.

Interessenten werden gebeten, per E-Mail Kontakt aufzunehmen. Sprechstunde nach Vereinbarung.

• Lecture 1
  • Hilbert space
  • bra/ket notation
  • inner product, projection operators, matrices
  • tensor product
• Lecture 2
  • postulates of quantum mechanics
  • observables/measurement in quantum mechanics and quantum information processing
  • dynamics: unitary, time-discrete evolution vs. Schrödinger equation
  • partial measurement, entanglement
• Lecture 3
  • qubit, n qubit system
  • Boolean functions, reversible functions
  • single-qubit transformations X=σ_x, Z=σ_z, σ_y
  • unitary transformation U_f :|x⟩|y⟩→|x⟩|y⊕f(x)⟩
  • CNOT
  • no cloning theorem
  • "garbage collection"
• Lecture 4
  • fair coin toss
  • graph of a Boolean function, partial measurements
  • preparing the superposition of all pre-images of a random function value
  • Deutsch algorithm
    

    David Deutsch.
    "Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer".
    Proceedings of the Royal Society A, vol. 400, no. 1818, pp. 97-117, July 1985.
    DOI: 10.1098/rspa.1985.0070

• Lecture 5
  • Deutsch algorithm revisited
  • identities for CNOT
  • Deutsch-Jozsa algorithm
    

    David Deutsch and Richard Jozsa.
    "Rapid Solution of Problems by Quantum Computation".
    Proceedings of the Royal Society A, vol. 493, no. 1907, pp. 553-558, December 1992.
    DOI: 10.1098/rspa.1992.0167

• Lecture 6
  • Bernstein-Vazirani:
    • find a∈{0,1}ⁿ from f(x)=(-1)^a⋅x
    • classical function provides only one bit per evaluation
  • Simon's algorithm:
    • find s∈{0,1}ⁿ given f(x) with f(x)=f(y) iff x=y⊕s
    • after Hadamard transformation, measurements yiels vectors z which are orthogonal to s
    • repetiton until n-1 linearly independent vectors z_i have been found
    • hybrid quantum algorithm: classical while-loop with quantum subroutine

    D. R. Simon.
    "On the power of quantum computation."
    Proceedings 35th Annual Symposium on Foundations of Computer Science (FOCS 1994), pp. 116-123, November 1994.
    DOI: 10.1109/SFCS.1994.365701

• Lecture 7
  • RSA encryption
  • reduction of factoring to order finding:
    • find the smallest integer r>0 such that a^r≡1 mod N
    • if r is even and a^r/2≠-1 mod N, then gcd(a^r/2±1,N) yields a factor of N
    • periodic function f(x)=a^x mod N

    Peter W. Shor.
    "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer."
    arXiv:quant-ph/9508027

• Lecture 8
  • quantum Fourier transformation, continued fraction approximation
  • order finding/phase estimation using eigenstates of U_a|y⟩=|ay mod N⟩

    A. Yu. Kitaev.
    "Quantum measurements and the Abelian Stabilizer Problem."
    arXiv:quant-ph/9511026

  • random/mixed state for register |y⟩

    S. Parker and M. B. Plenio
    "Efficient factorization with a single pure qubit and logN mixed qubits."
    Physical Review Letters, vol. 85, 3049, October 2000.
    DOI: 10.1103/PhysRevLett.85.3049
    arXiv:quant-ph/0001066

• Lecture 9
  • Diffie-Hellman-Merkle key exchange
  • discrete logarithm of x=g^m:
    • function f(a,b)=g^ax^-b=g^a(g^m)^-b=g^a-mb
    • periodicity (m,1)
    • use two-dimensional Fourier transformation
• Lecture 10
  • Classical & Quantum Oracle Functions

    Niklas Johansson, Jan-Åke Larsson.
    "A classical Deutsch-Jozsa algorithm".
    arxiv.org:1506.04627 [quant-ph]

  • (Abelian) Hidden Subgroup Problem (HSP):
    • Simon's algorithm
    • factoring via order finding
    • discrete logarithm
    • graph isomorhpism (symmetric group, open)
  • Grover's search algorithm
    • search a pre-image of a Boolean function (satisfiability problem 3-SAT)
    • NOT a database/phonebook search
    • basic principle

    Lov K. Grover.
    "A fast quantum mechanical algorithm for database search."
    arXiv:quant-ph/9605043

• Lecture 11 Grover's search algorithm
  
  • special case N=4, t=1 solutions
  • inversion about average as unitary transformation
  • reduction to two-dimensional dynamics
  • geometric interpretation
    see, e.g., Kapitel 6.3 in

    Matthias Homeister.
    Quantum Computing verstehen.
    Heidelberg: Springer, 2013.
    ISBN: 978-3-8348-1868-3

  • exact solution of the recursion equation

    Michel Boyer, Gilles Brassard, Peter Høyer and Alain Tapp.
    "Tight bounds on quantum searching."
    Fortschritte der Physik, vol. 46, no. 4-5, pp. 493-505, June 1998.
    DOI: 10.1002/(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO;2-P
    arXiv:quant-ph/9605034

• Lecture 12 Grover's search algorithm (part II)
  
  • reducing the expected number of iterations
  • optimality of the algorithm
  • unkown number of solutions
    
  • amplitude amplification

    Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp.
    "Quantum Amplitude Amplification and Estimation."
    arXiv:quant-ph/0005055

  • deterministic quantum algorithms

    Gilles Brassard and Peter Hoyer.
    "An Exact Quantum Polynomial-Time Algorithm for Simon's Problem."
    arXiv:quant-ph/9704027

• Lecture 13 Quantum Key Distribution/Generation (QKD)
  
  • one-time pad
  • prepare & measure scheme

    Charles H. Bennett and Gilles Brassard.
    "Quantum cryptography: Public key distribution and coin tossing".
    In Proceedings of IEEE International Conference on Computers, Systems and Signal Processing, 1984.
    http://researcher.watson.ibm.com/researcher/files/us-bennetc/BB84highest.pdf

  • entanglement bases protocol

    Artur K. Ekert.
    "Quantum cryptography based on Bell's theorem."
    Physical Review Letters vol. 67, pp. 661-663, 1991.
    DOI: 10.1103/PhysRevLett.67.661

  • error correction
  • privacy amplification

• Dagmar Bruß und Gerd Leuchs (Eds.)
  Lectures on Quantum Information
  Weinheim: Wiley-VCH, 2006.
  ISBN 3-527-40527-5

• Matthias Homeister.
  Quantum Computing verstehen
  Heidelberg: Springer, 2013.
  ISBN: 978-3-8348-1868-3

• Michael Nielsen und Isaac Chuang.
  Quantum Computation and Information
  Cambridge University Press, 2000.
  ISBN: 978-0-5216-3503-5
  DOI: 10.2277/0521635039

Markus Grassl Max-Planck-Institut für die Physik des Lichts Günther-Scharowsky-Straße 1, Bau 24 91058 Erlangen Telefon: +49 9131 6877 132 E-Mail: Markus.Grassl[at]mpl.mpg.de