Peter Williston Shor (born August 14, 1959) is an American mathematician and computer scientist renowned for his foundational contributions to quantum computing and quantum information theory.[1] He is the Morss Professor of Applied Mathematics at the Massachusetts Institute of Technology (MIT).[2] Shor's most celebrated achievement is the development of Shor's algorithm in 1994, a quantum algorithm that efficiently factors large integers and solves discrete logarithm problems, posing a profound threat to classical cryptographic systems like RSA.[3]Shor earned a B.A. in mathematics from the California Institute of Technology in 1981 and a Ph.D. in applied mathematics from MIT in 1985, advised by Tom Leighton.[2] Following a postdoctoral fellowship at the Mathematical Sciences Research Institute in Berkeley, he joined AT&T Bell Laboratories in 1986, where he conducted much of his groundbreaking research until 2003, when he returned to MIT as faculty.[4] At Bell Labs, Shor also pioneered quantum error correction, introducing in 1995 the first quantum error-correcting codes that protect quantum information from decoherence and noise, enabling fault-tolerant quantum computation.[5] His work demonstrated that quantum computers could, in principle, perform reliable computations despite environmental interference, a cornerstone for practical quantum devices.[6]Beyond algorithms, Shor's research spans combinatorial optimization, error-correcting codes, and the theoretical limits of quantum information processing, influencing fields from cryptography to condensed matter physics.[7] He has received numerous accolades, including the Rolf Nevanlinna Prize in 1998 for his quantum computing contributions, the MacArthur Fellowship in 1999, the Gödel Prize in 1999, the King Faisal International Prize in 2002, the Breakthrough Prize in Fundamental Physics in 2023 (shared), and the Claude E. Shannon Award in 2025.[2][8][9][10] Shor's innovations have catalyzed the global pursuit of quantum technologies, underscoring the potential of quantum mechanics to revolutionize computation.[11]
Biography
Early life
Peter Williston Shor was born on August 14, 1959, in New York City to parents S. W. Williston Shor and Joan Bopp Shor.[12] His mother, known as "Joby," was a long-time resident of Marin County, California, and passed away in 2016 at age 91.[13] The family included Shor's younger sister, Molly, and his father, S. W. Williston Shor, was a Captain in the U.S. Navy, whose career involved relocations during Shor's early years.[13]In 1963, Shor's family moved from New York to Washington, D.C., where he spent much of his early childhood.[13] In 1973, following his father's retirement, they relocated to Mill Valley, California, settling at 318 Montford Avenue in the Homestead Valley neighborhood.[14][13] There, Shor attended local schools, including Edna Maguire Middle School and later Tamalpais High School, which fostered his developing interests in academics and extracurricular activities.From a young age, Shor showed a strong aptitude for mathematics, influenced by both family encouragement and rigorous school programs. His passion deepened during high school, where he began participating in competitive mathematics events. In 1977, while at Tamalpais High School, he achieved third place in the USA Mathematical Olympiad, earning a spot on the U.S. team.[15] That same year, he represented the United States at the International Mathematical Olympiad in Belgrade, Yugoslavia, scoring 30 out of 42 points and securing a silver medal.[16] These accomplishments highlighted his early talent and paved the way for his pursuit of higher education at the California Institute of Technology.
Following his Ph.D. from MIT in 1985, Shor held a one-year postdoctoral fellowship as a research associate at the Mathematical Sciences Research Institute at the University of California, Berkeley, from 1985 to 1986, where he conducted research in theoretical computer science.[20]In 1986, Shor joined AT&T Bell Laboratories in Murray Hill, New Jersey, as a member of the technical staff, focusing on algorithms and computational theory; he remained there until 2003, relocating to the AT&T Laboratories in Florham Park, New Jersey, in 1996.[21][22]A key contribution from Shor's early non-quantum work was his co-development of the SMAWK algorithm in the mid-1980s, which finds the row minima of an n × m totally monotone matrix in O(n + m) time without evaluating all entries.[23] This algorithm exploits the property of totally monotone matrices—where, for any two rows i < j and columns k < l, if the entry M(i,l) ≤ M(j,l), then M(i,k) ≤ M(j,k)—to enable efficient solutions for optimization problems in areas like geometric computing and concave/convex programming.[23] For instance, in a small 3×3 totally monotone matrix such as\begin{bmatrix}
1 & 3 & 5 \\
2 & 2 & 6 \\
3 & 4 & 4
\end{bmatrix},the algorithm identifies the minima (1 in row 1, 2 in row 2, 3 in row 3) by reducing the search space through comparisons, avoiding full matrix evaluation.[23]During his time at Bell Labs, Shor began transitioning to quantum research in the early 1990s, initially sparked by seminars on quantum topics in 1989 and further motivated by a 1992 talk on quantum algorithms.[24]
MIT professorship
In 2003, Peter Shor joined the faculty of the Massachusetts Institute of Technology (MIT) as the Morss Professor of Applied Mathematics in the Department of Mathematics.[2] His extensive prior experience at Bell Labs, where he conducted pioneering research in theoretical computer science, laid a strong foundation for his transition to academia at MIT.[25]At MIT, Shor has taken on significant teaching responsibilities, delivering courses on quantum information theory and quantum algorithms, including the graduate-level Quantum Information Science I (course 8.370x) and Quantum Computation (course 18.435).[26] These classes introduce students to the foundational principles of quantum computation, emphasizing theoretical frameworks and algorithmic approaches while fostering interactive learning through problem sets and lectures.[27]Shor is actively involved in mentoring graduate students, guiding their research in quantum-related fields and highlighting the quality of MIT's student body as a key aspect of his academic experience.[28] He collaborates within MIT's quantum computing ecosystem, including interdisciplinary efforts at the Computer Science and Artificial Intelligence Laboratory (CSAIL) and other initiatives that bridge mathematics and physics.[22]As of 2025, Shor continues as an active researcher affiliated with MIT's Center for Theoretical Physics, where his work centers on quantum information theory and applications of error correction in quantum systems.[29] His ongoing contributions reflect a sustained commitment to advancing theoretical aspects of quantum technologies within this collaborative environment.[30]
Contributions to quantum computation
Shor's algorithm
Shor's algorithm, developed by Peter Shor in 1994 while at Bell Labs, is a quantum computing algorithm designed to solve the integer factorization problem and the discrete logarithm problem efficiently.[3] These problems are computationally intensive on classical computers and form the basis for widely used public-key cryptosystems. The algorithm operates in polynomial time relative to the input size, specifically O((\log N)^3) for an N-bit integer, providing a dramatic speedup over classical methods.[31]At its core, Shor's algorithm reduces factorization to finding the period of a function, leveraging quantum parallelism and interference. It begins by selecting a random base a coprime to the number N to be factored, then constructs a superposition of states to compute the modular exponential function f(x) = a^x mod N across many values of x simultaneously. The quantum period-finding subroutine uses the Quantum Fourier Transform (QFT) to detect the period r of this function efficiently. The QFT acts on an input state |x⟩ as follows:|x\rangle \rightarrow \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1} e^{2\pi i x y / N} |y\rangleThis transformation reveals peaks in the frequency domain corresponding to multiples of 1/r, allowing measurement to yield a value close to k/r for some integer k.[31] Following the quantum phase, classical post-processing employs the continued fraction algorithm to extract the rational approximation k/r from the measured value and identify the period r, provided r is odd or can be adjusted accordingly. Once r is obtained, factors of N are derived using gcd(a^{r/2} \pm 1, N).[31]The development of Shor's algorithm was motivated by the desire to demonstrate the potential of quantum computers to solve problems intractable for classical machines, particularly those underpinning RSAencryption, where security relies on the difficulty of factoring large semiprimes.[32] The first experimental demonstration occurred in 2001 using nuclear magnetic resonance (NMR) techniques, where researchers successfully factored the small number 15 into primes 3 and 5 on a 7-qubit liquid-state NMR quantum computer.[33] This proof-of-principle experiment highlighted the algorithm's feasibility despite noise and limited scale.Shor's algorithm demonstrates a provable quantum speedup, achieving factorization in polynomial time compared to the best-known classical algorithm, the general number field sieve, which runs in subexponential time O(exp(c (\log N)^{1/3} (\log \log N)^{2/3})) for some constant c.[31] This capability underscores the transformative threat to asymmetric cryptography and has driven research into post-quantum alternatives.[34]
Quantum error correction
In 1995, Peter Shor introduced the first quantum error-correcting code capable of protecting a logical qubit against arbitrary single-qubit errors, known as the 9-qubit Shor code.[35] This code encodes one logical qubit into nine physical qubits by first using a three-qubit repetition code to correct bit-flip errors (X errors) and then embedding each of those into another repetition code to handle phase-flip errors (Z errors), effectively concatenating classical repetition codes in a quantum framework.[35] The code's structure is described using the stabilizer formalism, where the logical state is stabilized by a set of commuting Pauli operators; for the Shor code, key stabilizer generators include XXX on qubits 1-3, XXX on qubits 4-6, XXX on qubits 7-9 for bit-flip detection, and ZZZ on qubits 1,4,7, ZZZ on qubits 2,5,8, and ZZZ on qubits 3,6,9 for phase-flip detection, allowing syndrome measurements to identify and correct errors without disturbing the logical information.[35]Building on this foundation, Shor collaborated with A. R. Calderbank in 1996 to develop the Calderbank-Shor-Steane (CSS) codes, a broader class of quantum error-correcting codes that generalize classical linear block codes to the quantum setting by constructing codes from pairs of orthogonal classical codes, one for X errors and one for Z errors.[36] These CSS codes enable the creation of families of quantum codes with better parameters, such as higher rates and distances, by leveraging self-orthogonal classical codes over finite fields, and they form the basis for many subsequent quantum code constructions.[36] For instance, the Steane code, an independently developed [[7,1,3]] CSS code, exemplifies this approach but stems from the same theoretical framework introduced by Shor and Calderbank.Shor's contributions extended to fault-tolerant quantum computation in his 1996 work, which laid the groundwork for the quantum threshold theorem—proved by Dorit Aharonov and Michael Ben-Or—demonstrating that quantum computers could perform reliable computations despite noise if the physical error rate per gate is below a certain constant threshold, typically around 10^{-4} to 10^{-3} depending on the noise model.[6][37] The theorem establishes that, under this threshold, errors can be suppressed exponentially by increasing the code distance, allowing arbitrarily long computations with polynomial overhead, though the exact threshold value emerges from the fault-tolerant gadget constructions that protect against gate failures and measurementerrors.[6] This result resolved a fundamental skepticism about the practicality of quantum computing by proving that error correction could scale to fault-tolerant regimes without requiring perfect hardware.[6]Shor's error-correction innovations profoundly influenced later developments, particularly the surface code, a topological CSS-based code that emerged in the late 1990s and has become the leading architecture for fault-tolerant quantum computing due to its high threshold (around 1%) and local interactions suitable for near-term hardware. By 2025, experimental demonstrations of surface code error correction below the threshold have been achieved on superconducting processors, such as Google's 2024 implementation of distance-7 and distance-5 memories with logical error rates suppressed by over an order of magnitude. In November 2025, IBM announced new quantum processors and architectures, such as IBM Loon, for high-efficiency quantum error correction, continuing to advance scalable implementations based on Shor's foundational principles.[38][39] By directly building on Shor's foundational codes, these efforts enable scalable quantum architectures.
Awards and honors
Major prizes
Peter Shor received the Rolf Nevanlinna Prize in 1998 from the International Mathematical Union for his foundational contributions to theoretical computer science, particularly his pioneering work in quantum computing that demonstrated the potential of quantum algorithms to solve classically intractable problems.[40]In 1999, Shor was awarded the Gödel Prize by the Association for Computing Machinery and the European Association for Theoretical Computer Science for his seminal paper introducing Shor's algorithm, which provided efficient quantum methods for integer factorization and discrete logarithms, revolutionizing the study of computational complexity in quantum settings.[41]That same year, Shor earned a MacArthur Fellowship from the John D. and Catherine T. MacArthur Foundation, recognizing his innovative research at the intersection of physics, computation, and information theory that advanced the field of quantum computing.[8]Shor received the King Faisal International Prize for Science (Mathematics) in 2002, shared with Yuri Manin, for his contributions to quantum computing and connections between number theory and quantum computers.[21]Shor was honored with the Distinguished Alumni Award from the California Institute of Technology in 2007 for his exceptional achievements in applied mathematics and quantum research following his undergraduate studies there.[42]Shor shared the 2017 Dirac Medal from the Abdus SalamInternational Centre for Theoretical Physics with Charles H. Bennett and David Deutsch for their collective advances in quantum computation, including Shor's development of algorithms that exploit quantum mechanics to perform computations unattainable by classical means.[43]In 2018, Shor received the Micius Quantum Prize, shared with Ignacio Cirac, David Deutsch, and Peter Zoller, for foundational contributions to quantum computation.[44]Also in 2018, Shor was awarded the IEEE Eric E. Sumner Award for Outstanding Contributions to Communications Technology, recognizing his work on quantum error-correcting codes and quantum algorithms.[45]In 2019, he received the BBVA Foundation Frontiers of Knowledge Award in Basic Sciences, shared with Charles H. Bennett and Gilles Brassard, for their groundbreaking contributions to quantum computation and cryptography that laid the groundwork for secure quantum communication protocols.[46]Shor was one of four recipients of the 2023 Breakthrough Prize in Fundamental Physics, alongside Bennett, Brassard, and Deutsch, honoring their transformative work in quantum information science that has reshaped our understanding of computation and physics at the quantum scale.[47]In 2025, Shor received the IEEE Claude E. Shannon Award from the IEEE Information Theory Society for his profound and consistent contributions to information theory, especially through quantum extensions that influence error correction and algorithmic efficiency in quantum systems.[10]
Academic memberships
Peter Shor was elected to the National Academy of Sciences in 2002 as a member in the Section 34: Computer and Information Sciences, recognizing his foundational work in quantum computing and related fields.[7] These academic memberships underscore his esteemed status among peers, stemming from pioneering advancements in quantum error correction and algorithms that have profoundly influenced theoretical computer science and information theory.In 2011, Shor was inducted as a fellow of the American Academy of Arts and Sciences, cited for seminal contributions to theoretical computer science, particularly the development of Shor's algorithm, which demonstrated that quantum computers can factor large integers in polynomial time—exponentially faster than known classical methods.[11]Shor received the ACM Fellowship in 2019 for his contributions to quantum computing, information theory, and randomized algorithms, highlighting his role in bridging classical and quantum paradigms.[48]He was elected to the National Academy of Engineering in 2020 in the Computer Science and Engineering section, honored for pioneering contributions to quantum computation that have advanced the feasibility and theoretical underpinnings of quantum information processing.[49]In 2022, Shor was named a fellow of the American Mathematical Society for contributions to quantum computing, in particular quantum algorithms and quantum error correction, affirming his impact on mathematical foundations of emerging computational technologies.[50]