MATH 217A (Winter quarter 2002). Topics in Applied Mathematics:
QUANTUM COMPUTATION AND INFORMATION SECURITY

Instructor: David A. Meyer
Room & time: AP&M 6438, MW 12:20
Office hours: AP&M 7256, T 2-3, F 1-3, or by appointment

Course description

Currently the most important applications of quantum information processing are to information security: Quantum key distribution has been demonstrated experimentally, and the security of cryptosystems based on the hardness of finding discrete logarithms or factoring is compromised, theoretically, by Shor's quantum algorithms.

In this seminar we will use these applications to motivate an introduction to quantum computing. Basic concepts in quantum mechanics (superposition, measurement, entanglement, ...) will be introduced as we study quantum protocols for cryptographic primitives such as key distribution, bit commitment, coin flipping, etc. Appreciation for these results will require a parallel discussion of the importance of, and classical protocols for, these cryptographic primitives. Additional related topics will be determined by the students' interests and background, and may include quantum versions of game theory, secret sharing, communication complexity, algorithms, ...

Some background in quantum mechanics, cryptography, complexity, coding, or game theory will be useful, but is not required. Although there is no text for this course, [1] provides an excellent reference for the whole subject. There will be no assignments or tests, but registered students will be asked to give a presentation on a relevant topic of their choice.

This course will continue in the spring quarter.

In the news

S. R. Das, "Quantum computing gets real", IEEE Spectrum (march 2002).
T. Freeman, "Emitter ensures safe internet connections", FibreSystems Europe (february 2002) 14.
M. Jacoby, "Nanowires come in two tones", Chemical & Engineering News 80 (11 february 2002) 7.
S. Finnie, "Encryption leaves DES behind", TechWeb (6 february 2002).
"Single-photon devices get closer", CERN Courier 42 (january/february 2002).
G. Mitchell, "Quantum games", BBC Radio 4, The Leading Edge (31 january 2002).
G. Glibert, "Quantum information science: the undiscovered country" and "Pushing the frontier of science: quantum cryptography research at MITRE", The Edge 6 (january 2002).
S. Lasserre, "Les propriétés des photons promettent des communications inviolables", Le Monde (11 janvier 2002).
A. Cho, "Multiple choice", New Scientist (5 january 2002).

Syllabus (incremental)

7 jan 02 importance of quantum computing to information security
unconditional versus computational security
use quantum cryptography to introduce basics of quantum mechanics (QM)
9 jan 02 no lecture (AMS meeting)
14 jan 02 prehistory of BB84: Weisner's unconterfeitable money [2]
QM Postulate 0 (states)
tensor product
QM Postulate 1 (measurement)
adjoint
16 jan 02 projective (von Neumann) measurement [3]
Hermitian operators
counterfeiting by measurement fails with probability near 1
QM Postulate 2 (evolution)
independence of postulates [4]
No-Cloning Theorem [5]
unitary counterfeiting fails
21 jan 02 no lecture (Martin Luther King day)
23 jan 02 BB84 quantum key distribution (QKD) protocol [6]
quantum measurement can produce random bits
formal definition of cryptosystem/perfect security
Vernam one-time pad [7]
proof of perfect security of Vernam cipher [8]
usefulness of QKD
28 jan 02 initial proofs of security of BB84 considered only restricted attack set [9]
unconditional security proof [10] requires more background
EPR pairs; entanglement
quantum error correcting codes
begin with review of classical codes [11]
binary symmetric channel
repetition codes
minimum error, maximum likelihood and minimum distance decoding
definition of [n,k,d] classical binary codes
Hamming and Gilbert-Varshamov bounds
linear codes
error syndrome; decoding
[7,4,3] Hamming code
30 jan 02 Pauli matrices
simultaneous diagonalization of commuting Hermitian matrices
EPR-B state [12] is simultaneous eigenvalue +1 eigenstate of Z1Z2 and X1X2
definition of entanglement [13]
CHSH inequality [14]
example of a Bell inequality [15]
violated by EPR-B state
proves separation of quantum from classical
locality is relativistic concept
4 feb 02 Ekert protocol for QKD with EPR-B pairs [16]
equivalence to BB84 [17]
definition of density matrix
measurement in density matrix formalism
6 feb 02 definition of reduced density matrix for subsystem
describes outcome of measurements on subsystem
reduced density matrix is independent of measurement of rest of system ...
until outcome is conveyed to subsystem
which resolves EPR paradox [12,18]
11 feb 02 definition of quantum operations [19]
completely positive operators
definition of quantum error correction [20]
bit flip error example
relation to classical linear code
13 feb 02 definition of fidelity [21]
completely positive operators
phase error example
Shor's 9 qubit code [22]
the conditions for quantum error correction[20]
equivalence between ensembles for density matrices [23]
equivalence between sets of operation elements for quantum operations
18 feb 02 no lecture (`Presidents' Day')
21 feb 02 polar decomposition of matrices
proof of quantum error correction conditions
suffices to correct a basis of quantum errors
26 feb 02 construction of Shor's 9 qubit code [22] from two classical codes
exemplifies CSS [24], or homological [25], quantum codes
28 feb 02 error correction procedure for CSS codes
the [7,1,3] CSS code [24]
definition of degenerate quantum code
quantum Hamming bound
6 mar 02 review of the classical Gilbert-Varshamov bound
definition of H2
Sterling's formula
asymptotic form of Gilbert-Varshamov bound
definition of weakly self-dual classical codes
Gilbert-Varshamov bound for weakly self-dual codes
quantum Gilbert-Varshamov bound for CSS codes [24]
11 mar 02 unitary encoding for quantum codes
applies to entangled states
and to mixed states
encoding EPR-B pairs with CSS codes [10]
modified [10] Lo-Chau QKD protocol [26]
definition of arbitrary security for QKD protocol
definition of Shannon entropy and mutual information
13 mar 02 definition of von Neumann entropy
Holevo's theorem [27]
proof of arbitrary security for modified Lo-Chau QKD protocol
reduction to CSS QKD protocol
reduction to BB84 QKD protocol

Bibliography

[1] M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge: Cambridge University Press 2000) [website].
[2] S. Wiesner, "Conjugate coding", SIGACT News 15 (1983) 78-88;
C. H. Bennett, G. Brassard, S. Breidbart and S. Wiesner, "Quantum cryptography, or unforgeable subway tokens", in D. Chaum, R. L. Rivest and A. T. Sherman, eds., Advances in Cryptology: Proceedings of Crypto 82 (New York: Plenum Press 1982) 267-275.
[3] J. von Neumann, Mathematische Grundlagen der Quantenmechanik (Berlin: Springer-Verlag 1932); transl. by R. T. Beyer as Mathematical Foundations of Quantum Mechanics (Princeton: Princeton University Press 1955).
[4] for a recent discussion, see: S. L. Adler, "Why decoherence has not solved the measurement problem: a response to P. W. Anderson", quant-ph/0112095.
[5] D. Dieks, "Communication by EPR devices", Physics Letters A 92 (1982) 271-272;
W. K. Wootters and W. H. Zurek, "A single quantum cannot be cloned", Nature 299 (1982) 802-803.
[6] C. H. Bennett and G. Brassard, "Quantum cryptography: public key distribution and coin tossing", Proceedings of the International Conference on Computers, Systems and Signal Processing (1984) 175-179 [pdf];
C. H. Bennett and G. Brassard, "Quantum public key distribution system", IBM Technical Disclosure Bulletin 28 (1985) 3153-3163;
C. H. Bennett, F. Bessette, G. Brassard, L. Salvail and J. Smolin, "Experimental quantum cryptography", Journal of Cryptology 5 (1992) 3-28 [ps];
C. H. Bennett, "Interferometric quantum cryptographic key distribution system", U.S. Patent No. 5,307,410;
C. H. Bennett and S. J. Wiesner, "Quantum key distribution using non-orthogonal macroscopic signals", U.S. Patent No. 5,515,438.
[7] G. S. Vernam, "Cipher printing telegraph systems for secret wire and radio telegraphic communications", Journal of the American Institute of Electrical Engineers 55 (1926) 109-115.
[8] C. E. Shannon, "Communication theory of secrecy systems", Bell System Technical Journal 28 (1949) 657-715.
[9] see, e.g., E. Biham and T. Mor, "Security of quantum cryptography against collective attacks", quant-ph/9605007, Physical Review Letters 78 (1997) 2256-2259;
C. A. Fuchs, N. Gisin, R. B. Griffiths, C.-S. Niu and A. Peres, "Optimal eavesdropping in quantum cryptography. I. Information bound and optimal strategy", quant-ph/9701039, Physical Review A 56 (1997) 1163-1172;
and references therein.
[10] P. W. Shor and J. Preskill, "Simple proof of security of the BB84 quantum key distribution protocol", quant-ph/0003004, Physical Review Letters 85 (2000) 441-444.
[11] perhaps the standard reference is F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes (Amsterdam: North-Holland 1977);
for connections to cryptography see, e.g., D. Welsh, Codes and Cryptography (Oxford: Oxford University Press 1988).
[12] A. Einstein, B. Podolsky and N. Rosen, "Can quantum-mechanical description of physical reality be considered complete?", Physical Review 47 (1935) 777-780;
D. Bohm, Quantum Theory (New York: Prentice-Hall 1951).
[13] E. Schrödinger, "Die gegenwärtige Situation in der Quantenmechanik", Naturwissenschaften 23 (1935) 807-812; 823-828; 844-849.
[14] J. F. Clauser, M. A. Horne, A. Shimony and R. A. Holt, "Proposed experiment to test local hidden-variable theories", Physical Review Letters 49 (1969) 1804-1807.
[15] J. S. Bell, "On the Einstein-Podolsky-Rosen paradox", Physics 1 (1964) 195-200.
[16] A. K. Ekert, "Quantum cryptography based on Bell's theorem", Physical Review Letters 67 (1991) 661-663.
[17] C. H. Bennett, G. Brassard and N. D. Mermin, "Quantum cryptography without Bell's theorem", Physical Review Letters 68 (1992) 557-559.
[18] for further discussion of causality, locality and quantum operations, see: D. Beckman, D. Gottesman, M. A. Nielsen and J. Preskill, "Causal and localizable quantum operations", quant-ph/0102043, Physical Review A 64 (2001) 052309.
[19] see K. Kraus, States, Effects, and Operations: Fundamental Notions of Quantum Theory, Lecture Notes in Physics 190 (Berlin: Springer-Verlag 1983);
and references therein
[20] C. H. Bennett, D. P. DiVincenzo, J. A. Smolin and W. K. Wootters, "Mixed state entanglement and quantum error correction", quant-ph/9604024, Physical Review A 54 (1996) 3824-3851;
E. Knill and R. Laflamme, "Theory of quantum error-correcting codes", quant-ph/9604034, Physical Review A 55 (1997) 900-911.
[21] D. Bures, "An extension of Kakutani's theorem on infinite product measures to the tensor product of semifinite w*-algebras", Transactions of the American Mathematical Society 135 (1969) 199-212;
R. Jozsa, "Fidelity for mixed quantum states", Journal of Modern Optics 41 (1994) 2315-2323;
C. Fuchs, Distinguishability and Accessible Information in Quantum Theory, quant-ph/9601020, Ph.D. thesis (physics), University of New Mexico (1995).
[22] P. W. Shor, "Scheme for reducing decoherence in quantum computer memory", Physical Review A 52 (1995) 2493-2496;
P. W. Shor, "Method for reducing decoherence in quantum computer memory", U.S. Patent No. 5,768,297.
[23] E. Schrödinger, "Probability relations between separated systems", Proceedings of the Cambridge Philosophical Society 32 (1936) 446-452.
[24] A. R. Calderbank and P. W. Shor, "Good quantum error-correcting codes exist", quant-ph/9512032, Physical Review A 54 (1996) 1098-1105;
A. M. Steane, "Multiple particle interference and quantum error correction", quant-ph/9601029, Proceedings of the Royal Society of London A 452 (1996) 2551-2576.
[25] A. Yu. Kitaev, "Fault-tolerant quantum computation by anyons", quant-ph/9707021;
M. H. Freedman and D. A. Meyer, "Projective plane and planar quantum codes", quant-ph/9810055, Foundations of Computational Mathematics 1 (2001) 325-332.
[26] H.-K. Lo and H.-F. Chau, "Unconditional security of quantum key distribution over arbitrarily long distances", quant-ph/9803006, Science 283 (1999) 2050-2056;
H.-K. Lo and H.-F. Chau, "Quantum cryptographic system with reduced data loss", U.S. Patent No. 5,732,139.
[27] A. S. Holevo, "Statistical problems in quantum physics", in G. Maruyama and J. V. Prokhorov, eds., Proceedings of the Second Japan-USSR Symposium on Probability Theory, Lecture Notes in Mathematics 330 (Berlin: Springer-Verlag 1973) 104-119.

Suggested presentation topics

Last modified: 07 jan 07.