Talking Quantum Algorithms with Peter Shor

Talking Quantum Algorithms with Peter Shor

Jun 9, 2010

 

A year ago when Dr. Dobb's began publishing these essays on quantum computing, high-level quantum algorithms were the jumping off point. The series which followed diverged quickly towards quantum computing hardware implementations. Our return to the exploration of algorithms commences with Peter W. Shor, Henry Adams Morss and Henry Adams Morss, Jr. Professor of Applied Math of the Massachusetts Institute of Technology.

In the words¹ of Michele Mosca of the Institute for Quantum Computing, Prof. Shor "transformed the field of quantum computing" with the publication of a quantum factoring algorithm ["Shor's Algorithm"] in his 1994 paper Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer.

Prof. Shor spoke from his office at MIT.

JW: May I ask you what you think of the current attempts to build quantum computers?

PS: I think they're all a long way from getting anywhere near a quantum computer. Most of them are cutting edge science, and we've come a lot farther than people imagined we would 15 years ago.

JW: How far are quantum algorithms progressing in default of hardware?

PS: There have been a couple of recent survey papers. While there's nothing really exciting, there is some interesting stuff. Harrow, Hassidim and Lloyd² and others showed that in some sense you can solve linear equations on a quantum computer, a very important problem, although this algorithm only speeds it up in certain special cases.

JW: What are you working on these days?

PS: My most interesting thing recently is on quantum money³, a cryptographic protocol in which a mint can produce a quantum state, no one else can copy the state, and anyone with a quantum computer can verify that the state came from the mint.

JW: I recently wrote that quantum algorithms on real quantum computers will immediately invalidate all currently used encryption algorithms. Is that really true?

PS: No.

JW: I kind of thought I was being hyperbolic there!

PS: Quantum computers invalidate public key, but not private key algorithms. There are proposals for public key systems which havenot been shown to be invalidated by quantum computers, but most of these are not in widespread use. All the ones in widespread use can be invalidated by quantum computers.

JW: Is the following something like a quantum algorithm?

Accordions are tuned with multiple reeds tuned a few hertz apart so that there is a beat between two frequencies, e.g., the two reeds for the note A will be tuned to 438 and 442 and produce a 4Hz beat. In the sound chamber of an accordion the wave form of multiple notes is combined. If two pairs of reeds were tuned for differing numbers of beats, and if you could pick out the interference of two beat rates, the accordion could compute, say, the difference 5 minus 4. At no time in that experiment could you experience the individual waves from the individual contributors to the resulting wave form without destroying the resultant wave form.

PS: It's something like one. If you think about the factoring algorithm [Shor's algorithm] reducing factoring to periodicity, and you get this periodicity by interference, the big difference is that in reading out this periodicity you do something you could never do on an analog computer because the period is exponentially long. In reading out this period you take advantage of the wave / particle duality that quantum mechanics deals with. So this frequency, which is analog, can be read out digitally as a sequence of ones and zeroes so that you get it in enough precision. You can put this 500-digit number through number theory calculations on a digital computer and it spits out the factors.

So interference is part of what makes a quantum computer, but it's not enough.

JW: When I look at sunset over the Rockies, the clouds form bars of darkness in the light, bands of interference that stretch out towards the eastern plains. Is that pattern the solution to some long polynomial equation, e.g., one describing somehow the precise location and density and meteorological characteristics of the clouds which formed it? And is that a quantum computer?

PS: In some sense it is, but in this case, you don't lose anything by thinking of light entirely as a wave, and you don't use this wave / particle duality, so I would say it is an analog, rather than a quantum computation.

My view of quantum computation is that it has to use the fact that quantum objects are both waves and particles.

JW: Why is that duality the nugget of what is quantum computation?

PS: In the early days of quantum computation people had all sorts of arguments for what you really need for quantum computation. People still have different opinions about what makes quantum computing behave so differently from classical computing. Some are going to say entanglement is the nugget, some are going to say it's the exponential size of the quantum state space. I think of duality as the nugget, but all these phenomena are closely related.

Why do I think it's the duality? Good question!

JW: It's been difficult to find a hard definition of quantum computing. Your algorithm yields a range in which the probability of finding factors is elevated. Then I look at other quantum computing communities and they are designing quantum logic gates like CNOT and iSwap. What is the taxonomy of that continuum?

PS: If you look at conventional computers, someone is going to describe a high-level algorithm which may involve steps such as sorting and blah-blah-blah. Then you talk to the people building the chips, and they are building NOT and AND and OR and NAND gates.

I'm describing the factoring algorithm in high-level terms, and the people who are building CNOT gates are trying to build the machine that executes that factoring algorithm.

JW: It seems like people would have been theorizing about building these CNOT and iSwap gates long before your high-level algorithm was published. There was interest in quantum computing before. Was it just that your paper demonstrated for the first time the polynomial time versus exponential time advantage in a recognizable context?

PS: Yes. It was the first problem folks were interested in, the first that wasn't a completely contrived problem which was sped up by quantum computing. Of course you can say that Richard Feynman and Yuri Manin were first because they had the idea of solving quantum mechanics using quantum computers, which, when you get down to it, is probably a more important application than factoring.

JW: What will quantum computing do and what will its use be to humanity?

PS: Nobody really knows. We can hope! There are some things which people spend huge amounts of computational time on now which, I think, are very likely to be helped by quantum computing.

Drug companies spend enormous amounts of computational resources on drug design because it's much easier to try to find out on a computer what a molecule will do than to build the molecules and experiment. It doesn't always work now, but I think quantum computing will help. I'm certain there are significant quantum effects in protein folding which are not being modeled by digital computers.

One of the most amazing things recently is the discovery that chloroplasts have a coherent quantum walk⁴. Chloroplasts use some of the same means we study in quantum algorithms to transfer energy, increasing their efficiency.

This electron transfer quantum walk is a quantum effect that we had studied and already understood, and then the biologists discovered it occurring in chloroplasts.

This says to me that there are quantum effects happening in biological molecules. There are probably many other significant quantum effects happening in biological molecules that we don't understand because we don't yet have a quantum computer to model them.

JW: I've seen quantum computer machine language simulators on the web. What would an implementation of Shor's Algorithm in a high-level quantum computing language look like?

PS: Good question. Certainly I can imagine a Fortran-style high-level language that would make Shor's Algorithm easier, but really, you'd want something more high-level than that.

JW: What are these high-level operators?

PS: Maybe things like a fourier transform operator that would expand into a large number of steps. As we understand more algorithms, we'll understand what higher-level operations we need to implement them.

If you look at the history of computing, the algorithmic stuff that was done before there were real computers around to experiment on is much more primitive than what came after there were real computers to experiment on.

Notes
1Video of a panel discussion including Prof. Peter W. Shor on quantum computing at the Q2C (Quantum to Cosmos) Festival 2009.

2Quantum algorithm for linear systems of equations, Aram W. Harrow, Avinatan Hassidim and Seth Lloyd

3Quantum money from knots, Edward Farhi, David Gosset, Avinatan Hassidim, Andrew Lutomirski, Peter Shor (arXiv:1004.5127v1 [quant-ph])

4Quantum-Coherent Electronic Energy Transfer: Did Nature Think of It First?, Gregory D. Scholes, J. Phys. Chem. Lett., 2010, 1 (1), pp 2–8 DOI: 10.1021/jz900062f