Discover
/
Article

A question pertaining to Shor’s discovery

SEP 01, 2025

DOI: 10.1063/pt.wizl.mbfx

Terry Goldman

The recently published interview “Peter Shor on the genesis of Shor’s algorithm ” (Physics Today, April 2025, page 34), conducted by David Zierler and adapted and annotated by Ryan Dahn, was fascinating. I was interested in Shor’s discovery that there is a polynomial-time quantum computer factoring algorithm that violates the Church–Turing thesis, which in Shor’s words, says “basically, anything any computer can do in polynomial time, a Turing machine can do in polynomial time.” The presentation of the social aspects around this discovery provides an excellent view into the topic’s history. Of course, the now well-known implications are also discussed, but in so doing, the article also highlights, by omission, something missing in the field of theoretical computing.

PTO.v78.i9.11_2.f1.jpg

A classical Turing machine displayed at Harvard University in 2012. (Image by Rocky Acosta/CC BY 3.0 )

View larger

Since the Turing machine is classical, I am left with an obvious but unaddressed question: Is it possible that there is also a quantum Turing machine? I wonder if someone is studying this, but perhaps it is too much to expect that they would make themselves available to discuss it with Dahn for publication in Physics Today. That would only bring unwanted attention and competition to the issue.

More about the Authors

Terry Goldman. (tjgoldman@post.harvard.edu) Los Alamos, New Mexico.

This Content Appeared In
pto.2025.78.issue-9.largecover.png

Volume 78, Number 9

Related content
/
Article
/
Article
/
Article
/
Article
/
Article
/
Article

Get PT in your inbox

Physics Today - The Week in Physics

The Week in Physics" is likely a reference to the regular updates or summaries of new physics research, such as those found in publications like Physics Today from AIP Publishing or on news aggregators like Phys.org.

Physics Today - Table of Contents
Physics Today - Whitepapers & Webinars
By signing up you agree to allow AIP to send you email newsletters. You further agree to our privacy policy and terms of service.