Peter Shor, the Morss Professor of Applied Mathematics at MIT, has been named a recipient of the 2023 Breakthrough Prize in Fundamental Physics. He shares the $3 million award with three others for “fundamental work in quantum information”: David Deutsch of the University of Oxford, Charles Bennett of IBM Research and Gilles Brassard of the University of Montreal.
In announcing the award, the Breakthrough Prize Foundation highlighted Shor’s contributions to the field of quantum information, including the eponymous Shors algorithm for factoring extremely large numbers and an algorithm for correcting errors in quantum computers.
“These ideas not only paved the way for today’s rapidly evolving quantum computers; They are now also at the frontiers of fundamental physics, particularly in the study of metrology – the science of measurement – and quantum gravity,” the award announcement reads.
“I am very grateful that this year’s award goes to quantum information and quantum computing theory,” Shor commented MIT News. “My three co-winners were the most influential people in starting this space. I consider them friends and they all clearly deserve it.”
In addition, an MIT alumnus, Daniel A. Spielman PhD ’95, received the 2023 Breakthrough Prize in Mathematics for “contributions to theoretical computer science and mathematics, including spectral graph theory, the Kadison-Singer problem, numerical linear algebra, and optimization.” won and coding theory.”
“I’m delighted that both Peter Shor and Dan Spielman are receiving Breakthrough Prizes in Fundamental Physics and Mathematics, respectively,” said Michel Goemans, RSA professor and head of MIT’s mathematics department. “Both of course would have been nominees for the Breakthrough Prize in Theoretical Computer Science if such an award had existed. Peter and Dan are graduate students in our mathematics department, both have held tenured positions in our department and were members of the theory group at CSAIL, and both have received the same awards. It is a testament to the interdisciplinary importance of theoretical computer science, especially mathematics and physics.”
The first seeds of the potential of quantum computing were planted by the early algorithms derived by Deutsch, Bennett, Brassard and Shor.
In the early 1980s, Deutsch began thinking about problems whose solution could be accelerated using quantum algorithms – formulas derived using the laws of quantum mechanics rather than classical physics. He was the first to develop a quantum algorithm that could solve a simple, albeit contrived, problem far more efficiently than a classical algorithm.
Meanwhile, Bennett and Brassard were also exploring uses for quantum information. In 1984 they developed the first quantum cryptography protocol, BB84. They brought up the idea that two remote parties could agree on a secret encryption key that would be safe from eavesdroppers, based on a strange quantum principle where the value of the encryption key would be instantly corrupted and therefore unreadable when measured.
Their work demonstrated the first practical application of quantum information theory. It was also Shor’s first introduction to the field. The mathematician was working at AT&T Bell Labs at the time, and Bennett came to give a talk on his new quantum key encryption system. “Your work inspired me to do a little bit of thinking and research about quantum information,” Shor recalls. “But I didn’t really get any further at the time.”
A decade later, in 1994, Shor introduced his own groundbreaking algorithm. Shor’s algorithm describes how a sufficiently large quantum computer could efficiently factor extremely large numbers – a task that would take the most powerful classical supercomputer more than the age of the universe to solve.
Most data encryption schemes today rely on the difficulty of factoring to keep information secure. Shor’s algorithm was the first to show that a quantum system could theoretically breach most modern data security walls. However, to make this practical would require a system of many precisely controlled quantum bits. Even then, scientists assumed that the slightest noise in the environment would disturb the sensitive qubits, triggering a wave of errors in their calculations that could not be corrected without further disturbing the qubits.
“When I first came up with this factorization algorithm, people thought it was going to stay theoretical forever because there was this argument that you couldn’t correct errors on a quantum computer,” says Shor.
Shortly thereafter, in 1995, Shor worked out another algorithm, this time for quantum error correction, which showed that errors in a quantum system could actually be isolated and fixed without disturbing the qubit itself, leaving the quantum computation intact. The vision of a practical quantum computer became immediately tangible.
“With these two bombshell contributions, Peter has set the stage for quantum computing to become the vast field it is today,” says Alan Guth, Victor F. Weisskopf Professor of Physics at MIT and a past recipient of the Breakthrough Prize the one who called Shor to break the news of this year’s award.
“It was my great pleasure to be able to tell him that he is one of the winners,” says Guth. “His algorithms surprised the world and ignited the field of quantum computing. And despite his spectacular contributions, Peter continues to be a warm, friendly and smiling colleague to everyone around him.”
“Peter is a wonderful colleague and absolutely unique,” adds Goemans. “His thought process seems to correspond to the quantum algorithms that he designs and invents: From entangled ideas and a superposition of states, a brilliant solution often arises in a eureka moment!”
“One of the best things about MIT is that we have great students,” says Shor, who received his PhD from MIT in 1985 in applied mathematics. He then spent a year as a postdoc at the Mathematical Sciences Research Institute before joining AT&T Bell Labs where he developed Shor’s algorithm. In 2003 he returned to MIT, where he has continued his research and teaching for 20 years.
Today he is working on formulating a theory of quantum information that describes how data can be stored and transmitted using the principles of quantum physics. Will the day come when quantum computers are advanced enough to breach our classical security systems?
“In five or ten years, we could be at the beginning of a Moore’s Law where quantum computers will steadily improve every few years,” predicts Shor. “I suspect they will improve fast enough that within two or three decades we will have quantum computers that can do useful things. Hopefully by the time quantum computers are that big, we’ll be using other cryptosystems that aren’t vulnerable to quantum computing.”
Shor credits his father with encouraging his early interest in mathematics. As a young boy, he leafed through his father’s expenses Scientific Americanto find his favorite section.
“Martin Gardner had a column called ‘Math Games’ that was really amazing,” Shor recalls. “Sometimes it was a riddle, sometimes an account of a new discovery in mathematics, and often it was at a level I could understand. I looked forward to reading it every month and it was something that got me into math from an early age.”
Daniel Spielman, this year’s recipient of the Breakthrough Prize in Mathematics, received his PhD from MIT in 1995 in applied mathematics, under the guidance of Michael Sipser, the Donner Professor of Mathematics and former Dean of the MIT School of Science. Spielman then joined the math department and was on the MIT faculty until 2005 before transferring to Yale University, where he is currently the Sterling Professor of Computer Science, Mathematics, Statistics and Data Science.
Spielman specializes in the design and analysis of algorithms, many of which have yielded insights “not just for the math, but for highly practical problems in computing, signal processing, engineering, and even clinical trial design,” notes the Breakthrough Foundation in its report announcement today.
“Dan has made a number of important and beautiful breakthroughs over the years, from expander-based error correction codes to smoothed analysis of algorithms or spectral sparsification of graphs, all characterized by innovative mathematics,” says Goemans.
Among numerous discoveries, Spielman is best known for solving the Kadison-Singer problem, which for decades was considered unsolvable. The problem can be interpreted as raising a fundamental question for quantum physics: in a quantum system, can new information be deciphered just by observing or measuring some properties of the system? The answer, most mathematicians agreed, was no.
For decades, the Kadison-Singer problem has been reformulated and shown to be equivalent to problems in a wide range of mathematical domains. And in 2013, Spielman and his colleagues solved one of these equivalent formulations using linear algebra and matrices, proving that the answer was yes – in fact, it was possible to determine the sum of a quantum system from its parts.
The Breakthrough Prizes are a series of international awards recognizing the achievements of scientists in three categories – fundamental physics, mathematics and life sciences. The awards were founded by Sergey Brin; Priscilla Chan and Mark Zuckerberg; Julia and Yuri Milner; and Anne Wojcicki and were supported by foundations established by them. The 2023 awards will be presented at a festive award ceremony, and the winners will take part in lectures and discussions.