Peter Shor
# 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. 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. 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 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. Ein zweites für die Entwicklung der Quanteninformatik entscheidendes Resultat von Shor war seine Entdeckung des ersten fehlerkorrigierenden Quantencodes (des 9-qubit Shor codes) und der kurz darauf folgende Nachweis, dass unter Verwendung solcher Codes ein fehlertoleranter Quantencomputer konstruiert werden kann. Von Shor stammen weiterhin wichtige Beiträge u. a. zur Theorie der Verschränkung und der Quantenkanäle.

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. Seit 2019 ist Shor Fellow der Association for Computing Machinery. Für 2023 wurde ihm der Breakthrough Prize in Fundamental Physics zugesprochen.

## 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.
