Peter Shor

Peter Wiliston Shor (* 14. August 1959 in New York) ist ein amerikanischer Mathematiker und Informatiker, bekannt als Erfinder eines Quantencomputer-Algorithmus.

Leben

Shor ging in Mill Valley, Kalifornien auf die High-School und gewann als Schüler einen zweiten Preis in der Mathematik-Olympiade 1977, bei der das US-Team die meisten Punkte erzielte.^[1] Er studierte als Putnam Fellow am Caltech in Pasadena bis zu seinem Bachelor-Abschluss 1981 und ging danach ans MIT, wo er 1985 bei Tom Leighton über die wahrscheinlichkeitstheoretische Analyse des Behälterproblems promovierte.^[2] Nach einem Jahr als Post-Doc in Berkeley nahm er eine Stelle am Bell Lab in Murray Hill, New Jersey, an. Daneben unterrichtete er am MIT, wo er auch seit 2003 Professor für angewandte Mathematik ist.

Shor ist vor allem bekannt für seine Entwicklung eines Faktorisierungsalgorithmus mit polynomieller Laufzeit für Quantencomputer, der diesem Teil der Informatik in den 1990er Jahren zum Durchbruch verhalf (Shor-Algorithmus). Der 1994 erstmals vorgestellte^[3] Algorithmus nutzt die sehr großen parallelen Rechenfähigkeiten (Superpositionsprinzip von Wellenfunktionen in der Quantenmechanik) eines potentiellen Quantencomputers aus und verwendet die Quanten-Fouriertransformation. Seine besondere Bedeutung liegt darin, dass es sich um den ersten Quantenalgorithmus handelt, der ein praktisch relevantes Problem löst und nachweislich exponentiell schneller ist als der beste bekannte Algorithmus für herkömmliche Computer.^[4] Ein zweites für die Entwicklung der Quanteninformatik entscheidendes Resultat von Shor war seine Entdeckung des ersten fehlerkorrigierenden Quantencodes (des 9-qubit Shor codes)^[5] und der kurz darauf folgende Nachweis, dass unter Verwendung solcher Codes ein fehlertoleranter Quantencomputer konstruiert werden kann.^[6] Von Shor stammen weiterhin wichtige Beiträge u. a. zur Theorie der Verschränkung^[7] und der Quantenkanäle.^[8]

Shor erhielt 1998 auf dem Internationalen Mathematikerkongress in Berlin den Nevanlinna-Preis und hielt dort einen der Plenarvorträge (Quantum Computing). 1999 erhielt er ein MacArthur-Stipendium.

1998 wurde Shor mit dem Dickson Prize in Science ausgezeichnet. 2002 wurde er in die National Academy of Sciences, 2011 in die American Academy of Arts and Sciences gewählt, 2020 in die National Academy of Engineering. 2017 erhielt er die Dirac-Medaille (ICTP) und 2019 den BBVA Frontiers of Knowledge Award.^[9] Seit 2019 ist Shor Fellow der Association for Computing Machinery. Für 2023 wurde ihm der Breakthrough Prize in Fundamental Physics zugesprochen, für 2025 der Claude E. Shannon Award.

Schriften (Auswahl)

Quanteninformatik

P. W. Shor: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. In: SIAM J. Comp. Band 26, 1997, S. 1484, doi:10.1137/S0097539795293172, arxiv:quant-ph/9508027.
P. W. Shor: Scheme for reducing decoherence in quantum computer memory. In: Phys. Rev. A. Band 52, 1995, S. 2493, doi:10.1103/PhysRevA.52.R2493.
Proceedings of the 1996 Symposium on Foundations of Computer Science
P.W. Shor, J. Preskill: Simple Proof of Security of the BB84 Quantum Key Distribution Protocol. In: Phys. Rev. Lett. Band 85, 2000, S. 441, doi:10.1103/PhysRevLett.85.441, arxiv:quant-ph/0003004.
P. W. Shor: Equivalence of Additivity Questions in Quantum Information Theory. In: Commun. Math. Phys. Band 246, 2004, S. 453, doi:10.1007/s00220-003-0981-7, arxiv:quant-ph/0305035.
Charles H. Bennett, Igor Devetak, Aram W. Harrow, Peter W. Shor, Andreas Winter: Quantum Reverse Shannon Theorem. In: IEEE Trans. Inf. Theory. Band 60, Nr. 5, 2014, S. 2926–2959, doi:10.1109/TIT.2014.2309968, arxiv:0912.5537.

Geometrie

A. Aggarwal, M.M. Klawe, S. Moran, P.W. Shor, R. Wilber: Geometric applications of a matrix-searching algorithm. In: Algorithmica. Band 2, Nr. 1, 1987, S. 195–208.
K.L. Clarkson, P.W. Shor: Applications of random sampling in computational geometry. In: Discrete & Computational Geometry. Band 4, Nr. 1, 1989, S. 387–421.
A. Aggarwal, L.J. Guibas, J. Saxe, P.W. Shor: A linear-time algorithm for computing the voronoi diagram of a convex polygon. In: Discrete & Computational Geometry. Band 4, Nr. 1, 1989, S. 591–604.
J.C. Lagarias, P.W. Shor: Keller’s cube-tiling conjecture is false in high dimensions. In: Bull. Am. Math. Soc. Band 27, Nr. 2, 1992, S. 279–283 (mit.edu [PDF]).

Kombinatorik

T. Leighton, P.W. Shor: Tight bounds for minimax grid matching with applications to the average case analysis of algorithms. In: Combinatorica. Band 9, Nr. 2, 1989, S. 161–187.
A. Björner, L. Lovász, P.W. Shor: Chip-firing Games on Graphs. In: Europ. J. Combinat. Band 12, Nr. 4, 1991, S. 283–291.

Weblinks

Homepage von Shor am MIT mit Publikationsliste und einigen Aufsätzen (englisch)
Ronald Graham: Laudatio Nevanlinna-Preis 1998 für Shor (englisch)
Bio anlässlich McArthur Fellowship 1999 (englisch)
Seine Einführung des Quanten-Faktorisierungsalgorithmus, 35. Annual Symposium Foundations Computer Science 1994, arxiv:quant-ph/9508027 (englisch)

Einzelnachweise

↑ Famous Residents. Mill Valley Historical Society, abgerufen am 3. März 2020 (englisch).
↑ P.W. Shor: Random Planar Matching and Bin packing. 1985 (mit.edu – PhD Thesis am Department of Mathematics des MIT).
↑ P.W. Shor: Algorithms for quantum computation: Discrete logarithms and factoring. In: Proceedings, 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, November 20–22, 1994. IEEE Computer Society Press, 1994, S. 124–134 (mit.edu [PDF]).
↑ M.A. Nielsen, I.L. Chuang: Quantum Computation and Quantum Information. Cambridge University Press, 2000, S. 6/7, S. 246.
↑ Fast zeitgleich und unabhängig von Shor entdeckte auch Andrew Steane einen solchen Code; vgl. M.A. Nielsen, I.L. Chuang: Quantum Computation and Quantum Information. Cambridge University Press, 2000, Kap. 10, S. 497f.
↑ Fault-tolerant quantum computation. In: 37th Symposium on Foundations of Computing. IEEE Computer Society Press, 1996, S. 56–65, arxiv:quant-ph/9605011.
↑ D.P. DiVincenzo, T. Mor, P.W. Shor, J.A. Smolin, B.M. Terhal: Unextendible Product Bases, Uncompletable Product Bases and Bound Entanglement. In: Comm. Math. Phys. Band 238, 2003, S. 379–410, doi:10.1007/s00220-003-0877-6, arxiv:quant-ph/9908070.
↑ M. Horodecki, P.W. Shor, M.B. Ruskai: General Entanglement Breaking Channels. In: Rev. Math. Phys. Band 15, 2003, S. 629–641, doi:10.1142/S0129055X03001709, arxiv:quant-ph/0302031.
↑ The BBVA Foundation recognizes Charles H. Bennett, Gilles Brassard and Peter Shor for their fundamental role in the development of quantum computation and cryptography. fbbva.es, 3. März 2020, abgerufen am 3. März 2020 (englisch).

Personendaten
NAME	Shor, Peter
ALTERNATIVNAMEN	Shor, Peter Wiliston (vollständiger Name)
KURZBESCHREIBUNG	amerikanischer Mathematiker
GEBURTSDATUM	14. August 1959
GEBURTSORT	New York

[1] Famous Residents. Mill Valley Historical Society, abgerufen am 3. März 2020 (englisch).

[2] P.W. Shor: Random Planar Matching and Bin packing. 1985 (mit.edu – PhD Thesis am Department of Mathematics des MIT).

[3] P.W. Shor: Algorithms for quantum computation: Discrete logarithms and factoring. In: Proceedings, 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, November 20–22, 1994. IEEE Computer Society Press, 1994, S. 124–134 (mit.edu [PDF]).

[4] M.A. Nielsen, I.L. Chuang: Quantum Computation and Quantum Information. Cambridge University Press, 2000, S. 6/7, S. 246.

[5] Fast zeitgleich und unabhängig von Shor entdeckte auch Andrew Steane einen solchen Code; vgl. M.A. Nielsen, I.L. Chuang: Quantum Computation and Quantum Information. Cambridge University Press, 2000, Kap. 10, S. 497f.

[6] Fault-tolerant quantum computation. In: 37th Symposium on Foundations of Computing. IEEE Computer Society Press, 1996, S. 56–65, arxiv:quant-ph/9605011.

[7] D.P. DiVincenzo, T. Mor, P.W. Shor, J.A. Smolin, B.M. Terhal: Unextendible Product Bases, Uncompletable Product Bases and Bound Entanglement. In: Comm. Math. Phys. Band 238, 2003, S. 379–410, doi:10.1007/s00220-003-0877-6, arxiv:quant-ph/9908070.

[8] M. Horodecki, P.W. Shor, M.B. Ruskai: General Entanglement Breaking Channels. In: Rev. Math. Phys. Band 15, 2003, S. 629–641, doi:10.1142/S0129055X03001709, arxiv:quant-ph/0302031.

[9] The BBVA Foundation recognizes Charles H. Bennett, Gilles Brassard and Peter Shor for their fundamental role in the development of quantum computation and cryptography. fbbva.es, 3. März 2020, abgerufen am 3. März 2020 (englisch).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]