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
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.
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). |
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] |
16 jan 02 |
counterfeiting by measurement fails with probability near 1 unitary counterfeiting fails |
21 jan 02 | no lecture (Martin Luther King day) |
23 jan 02 |
BB84 quantum key distribution (QKD) protocol
[6] formal definition of cryptosystem/perfect security 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 begin with review of classical codes [11] |
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] |
4 feb 02 |
Ekert protocol for QKD with EPR-B pairs [16] equivalence to BB84 [17] |
6 feb 02 |
until outcome is conveyed to subsystem |
11 feb 02 |
definition of quantum operations [19] definition of quantum error correction [20] bit flip error example |
13 feb 02 |
definition of fidelity [21] phase error example Shor's 9 qubit code [22] the conditions for quantum error correction[20] |
18 feb 02 | no lecture (`Presidents' Day') |
21 feb 02 |
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 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 encoding EPR-B pairs with CSS codes [10] modified [10] Lo-Chau QKD protocol [26] definition of arbitrary security for QKD protocol |
13 mar 02 |
proof of arbitrary security for modified Lo-Chau QKD protocol reduction to CSS QKD protocol reduction to BB84 QKD protocol |
[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. |