Peter Shor The Early Years of Quantum Computing

Since its first meeting in 1911, the Solvay Conference on Physics has been a driving force in the development of quantum physics.

 

In May of this year, the 28th Solvay Conference was held in Brussels, with the theme "The Physics of Quantum Information". Peter Schorr, a pioneer of quantum computing, attended the conference and gave a presentation. This is the text of Schorr's presentation, which will be included in the conference proceedings.

 

01Abstract

 

I have refreshed my memory on some of the early advances in quantum computing. These advances include factorization algorithms, error-correcting codes, and the discovery of fault tolerance.

 

Peter Schorr Source: MIT

 

02Full text

 

This talk was originally prepared to commemorate the 40th anniversary of the 1981 Physics and Computation Conference in the Endicott Building, so I thought I'd start in 1981.

 

I was a senior at Caltech at the time, so I was already there when Feynman prepared the keynote for the Endicott Building conference, and that talk became one of the first few attempts to take a closer look at quantum computing.

 

I didn't hear anything about it while I was at Caltech, and in fact I didn't read Feynman's paper until much later.

 

I do want to mention another talk I heard him give at Caltech, though, because that talk showed that he was thinking about fundamental aspects of physics at the time.

 

Feynman's presentation was on negative probability.

 

At the beginning of his report, he explained that he had been thinking about Bell's theorem because it stated that quantum physics could not be a local, real theory of hidden variables.

 

This means that any interpretation of quantum mechanics requires either nonlocality or nonpositivity (where locality means that information cannot travel faster than the speed of light, and positivity means that what you can measure corresponds to the specific nature of the particle).

 

Feynman explained that what he did was to carefully examine the premises used to prove Bell's theorem to see if there were hidden assumptions in them.

 

He did find one - and that was that all probabilities must be between 0 and 1.

 

This is not as odd as it may sound at first - the Wigner function for simple harmonic oscillators behaves exactly like this, and Feynman mentions it as well.

 

He went on to show some results he found about negative probabilities; I don't remember this part of the report very well.

 

Much earlier, in a 1964 lecture series, Feynman had said.

 

"Let me tell you what nature is really like. If you accept her directly as she appears, you will find her fascinating and delightful. If you can resist, don't keep asking yourself, 'How can it be that way?' , because you'll be 'deep in the mud' and get into a dead end that no one can escape from. No one knows why it's that way."

 

But then, 15 years later, he's exploring a possible reason why nature is the way it is. You can see here that Feynman didn't take his own advice.

 

Of course, maybe his advice was not for tenured professors, but for graduate students; that might have been good advice for them - it's pretty hard to come up with new, significant results on the basis of quantum mechanics, so it's not a good subject for graduate students.

 

A few years later, in 1983, Feynman wrote down some of the ideas from the report in a paper called "Negative Probability," but it was years before it was published.

 

The interesting thing about that article is that it does not mention Bell's theorem as a motivation.

 

His article first discusses Wigner functions, which do give the probability of negative values. Feynman then extended the Wigner functions to quantum bits of spin systems.

 

And the original motivation that Feynman tells in his report has been replaced by the elimination of infinity in quantum field theory. So it must be that Feynman's original idea didn't work - he failed to solve the Einstein-Podolsky-Rosen (EPR) paradox using negative probabilities.

 

I don't know exactly what caused the change in motivation. Did he find the motivation of trying to figure out a better way to understand Bell's theorem too humiliating because it involved the foundations of quantum mechanics, so he came up with a more decent one? Or was there something else going on?

 

I'd also like to mention another interesting article from that era.

 

In 1985, David Deutsch wrote an article about quantum Turing machines, quantum computing, and the quantum Church-Turing thesis.

 

Deutsch's motivation stems in part from the foundations of quantum mechanics - he claims that with quantum computers, it is possible to test the Everett (many-worlds) interpretation of quantum mechanics.

 

In his article, he says: "An intuitive account of these properties puts an unbearable strain on all quantum-theoretic interpretations beyond Everett."

 

I want to make it clear that I don't agree with him on this point, although he has not been changing his mind.

 

In 1985, Feynman wrote a sequel to his 1982 article, which gave a much more detailed proposal of how to build a quantum computer. This proposal was still not very practical, however, because it required an extremely high degree of precision in constructing the initial states and the amplitudes of the leaps.

 

As an interesting side note, I would like to point out that when David Deutsch and Richard Feynman were thinking about quantum computing, they were both thinking about quantum foundations. My gut feeling is that this is important.

 

If you subscribe to David Mehlman's version of the Copenhagen interpretation - "shut up and do the math" - then you won't be thinking about quantum quirkiness, so that you probably won't think about the possible uses of quantum quirkiness.

 

At Caltech, I took some physics courses, but majored in math.

 

I then went to MIT's Graduate School of Applied Mathematics, where I studied the intersection of mathematics and computer science, and eventually got a job at Bell Labs in mathematics and computer science.

 

I first heard about quantum information at a presentation Charlie Bennett gave at Bell Labs, where he talked about the BB84 quantum key distribution protocol (translation: the protocol was proposed by Bennett and Brassard in 1984, hence the name). I don't remember what year that was, but it must have been in the late 80s.

 

I remember being fascinated by his report, and thinking for a while about an unsolved problem that Charlie had posed. That puzzle was whether you could rigorously prove that the BB84 protocol was secure.

 

In thinking about it, it was completely unclear to me how to formulate quantum mechanics into some mathematical form in order to rigorously prove that the protocol was secure. So I gave up on that problem.

 

It's kind of funny to say that by 2000, after I was familiar with quantum computing, quantum information, and quantum error correction codes, John Preskill and I did come up with a simple way of proving that BB84 was secure.

 

This is the third proof of BB84 security, though the first two, done by Meyers and Beahm, among others, are quite complicated.

 

I read Meyers' proof carefully and realized that CSS codes (translation: i.e., Calderbank-Shor-Steane codes, described in detail later) are implicitly included, and that you can get a much simpler proof if you use these codes.

 

After Bennett's presentation at Bell Labs, I never thought of quantum computing again until Youmansch Woznanie came to Bell Labs in 1992 to give a presentation about his and Ethan Bernstein's article on quantum Turing machines.

 

This article was later published in June 1993 at the Theory of Computing Workshop (STOC), one of the two most prestigious conferences on theoretical computer science.

 

I was extremely fascinated by that presentation, and I probably understood it a little better than any other computer scientist, because I had studied some physics in college.

 

Bernstein and Voznesny gave an elaborate problem that made quantum computers look like they could do better, but I wasn't too happy with that problem.

 

So I started thinking about whether I could use a quantum computer to solve a real problem more efficiently.

 

I wasn't really making progress until I read an article by Dan Simon.

 

In his article he solves a man-made problem, the "Simon problem", with a quantum computer algorithm and does it much better than the best classical algorithm.

 

I would read the article because I was on the program committee for the 1994 STOC conference, and the committee rejected that article (although I fought for it).

 

I was told that Dan Simon's starting point was to show that digital computers are no longer more powerful than quantum computers, but he eventually found a problem that showed the opposite result.

 

Simon used the Fourier transform on a binary vector space to find the period of a function on that vector space.

 

I knew that the Fourier transform was useful for finding periods, and I knew that the discrete logarithm problem was related to periodicity, so I started looking for ways to solve the discrete logarithm problem on a quantum computer.

 

The discrete logarithm problem is a well-known puzzle, and if you solve it, you can crack some public key cryptosystems.

 

The difference between Simon's algorithm and period finding in the discrete logarithm problem is that for the Simon problem, you need to find the period of a function on an n-dimensional hypercube, whereas for the discrete logarithm problem, you need to find the period on the P-1×P-1 torus.

 

Left, an example of period finding on a hypercube vertex. Here the period is (1,1,0). Right, example of cycle finding on a 2-dimensional torus. Here the period is (2,1).

 

It is not at all clear how to move from period finding on a high-dimensional hypercube to period finding on a large torus. For these you need a different quantum Fourier transform.

 

The first thing I did was to solve the discrete logarithm problem in a special case that had already been solved in polynomial time by classical computers.

 

Although this didn't really give anything new, the algorithm was quite different from the classical algorithm, so it gave me a lot of encouragement to go ahead and eventually solve the general case.

 

My epiphany from the special case to the general case was the realization that for the general case I didn't need to use the Fourier transform modulo P-1; I just needed to modulo a number slightly larger than P-1.

 

I didn't tell anyone that I was working on the discrete logarithm problem, because I didn't feel really sure about it.

 

After I solved it in April 1994, I told some people I knew and had worked with, including my boss, David Johnson, and a colleague at Bell Labs, Jeff Lagarias, who verified that my algorithm was right. Actually, not exactly right - Jeff identified a small error that was easily corrected.

 

Afterwards, David Johnson suggested that I give a presentation on this at the Henry Landau Seminar.

 

The Henry Landau seminar was held every Tuesday and had an extremely active audience - they kept interrupting the presenters to ask questions, so it was a bit intimidating. I remember one time, the presenter didn't get to turn to the second slide.

 

Anyway, I gave a presentation on how to solve discrete logarithms on a quantum computer, and it went pretty well.

 

Later that week, I solved the factorization problem as well. There is a strange connection between discrete logarithms and factorization. There is no formula that tells you how to apply an algorithm for one of the problems to the other.

 

However, every time someone found an improved algorithm for one of the problems, people came up with a similar solution to the other problem fairly quickly.

 

This time was no exception - knowing the discrete logarithm algorithm, it was easy to find the factorization algorithm.

 

That weekend, I was at home with a bad cold, and Youmansch Woznanie called me and said, "I heard you can factorize effectively with a quantum computer.

 

This was a bit surprising for a number of reasons. First, it suggested that the rumors I reported on Tuesday had spread to Youmansch. Second, the report was about discrete logarithms, but by the time the rumors reached Youmansch, they had already become factorized (it's kind of like a game of telephone, also called a passing game, in which a tidbit of information is passed from one player to the next and changes along the way).

 

Fortunately, however, I had also solved the factorization problem, so I was able to explain the factorization algorithm to Umansh without having to tell him that the information was wrong.

 

After that, the news spread like wildfire.

 

There was a theory day (on theoretical computer science) at Columbia University in late April. Charlie Bennett, John Smolin, and I arranged to meet there, and then I explained the algorithm to them.

 

If I remember correctly, Bennett explained to me his newer invisible transfer protocol, and the newer Eliezer-Wiedemann bomb test protocol. It was clear that the time had come on the subject of quantum information.

 

I was urgently invited to give a talk at a symposium on algorithmic number theory at Cornell in early May.

 

There was a conference on quantum mechanics in Santa Fe in mid-May; I couldn't go, but Youmansch presented my algorithms there. Artur Eckert and David Jossa wrote a paper explaining my algorithm to physicists, and Artur Eckert gave a presentation on it at the Atomic Physics Conference in Boulder, Colorado that August.

 

That's how many physicists learned about it, as you heard from David Warnand's report at this meeting.

 

In the meantime, I received many requests for interviews in magazines, and many requests for copies of the article. (I started sending them out before the article was completely finished, but that may have been a mistake because people were asking questions about errors in the early first draft long after I had corrected the errors in the article.)

 

That August, the National Institute of Standards and Technology (NIST) organized a conference in Gaithersburg, Maryland, specifically for the discovery of factorization algorithms, and focused on quantum computing.

 

In October, there was a workshop on quantum computing in Turin, Italy, which was actually the second or third in a series of conferences. It started with a few participants, and then the number of attendees grew each year until it exceeded the capacity of the conference facilities at the Hotel Guarino Manor and was discontinued.

 

The '94 Physics and Computation Conference in Texas was a follow-up to the 1981 Endicott Building conference (three follow-up conferences were held, in '92, '94, and '96), and I gave a presentation there.

 

A few days immediately after that, I spoke about my paper at the Foundations of Computer Science (FOCS) conference in Santa Fe, New Mexico, and it was published in the conference proceedings.

 

There is a strong objection to quantum computing, which Rolf Randall raised at the Santa Fe Institute conference in May.

 

Quantum computers do not appear to be able to provide fault tolerance. And without fault tolerance, if you want to run N steps on a quantum computer, you have to make sure that each step is accurate to 1/N.

 

When N is very large, say 1 billion (which is pretty much what you need to do to factorize a cryptographically meaningful large number), this seems absolutely impossible to experimental physicists.

 

There are two main quantum mechanical principles, the Heisenberg uncertainty principle and the quantum unclonability theorem, that are seen as hindrances to error correction.

 

The Heisenberg uncertainty principle says that you cannot measure the state of a quantum computer in its entirety. The quantum unclonability theorem, on the other hand, says that you cannot replicate an unknown quantum state.

 

Assuming you build a classical computer with unreliable components and want to make it error tolerant, there are a number of techniques you can use.

 

One is the checkpoint - you periodically write down the state of your computation, and once the computation is off at some point, you don't have to start from scratch, you just start at the checkpoint.

 

Another technique is error-correcting codes. These codes use redundancy to help you repair bits that are corrupted in storage.

 

Finally, there is another technique that is heavily redundant. You keep multiple copies of each bit in the computation and constantly compare them to each other to fix the ones that are wrong. Mass redundancy is probably the most powerful of these techniques, and was studied by von Neumann in 1956.

 

The problem is that the quantum unclonability theorem seems to indicate that all of these are not feasible. For checkpoints, you can't write down the state of your computation before continuing it - it's making a backup. For massive redundancy, fixing errors involves backups - if you have four good copies of the computation and one bad copy, the resulting five good copies is also something that the unclonable theorem considers impossible.

 

Fortunately, error-correcting codes work, even though they also seem to require redundancy.

 

Although I didn't learn much about it when I was in school, I spent time in the math center at Bell Labs, so I know something about error correction codes.

 

The simplest classical error-correcting codes are repetition codes, which is when you make multiple backups of the bits and then use majority vote to fix the errors. The shortest code that can work is a three-bit code (because you need a majority).

 

You can do the same for quantum codes. This code is as follows, it codifies one quantum bit into three quantum bits

 

 

Here, the pictures represent logical quantum bits that are encoded into three physical quantum bits. This encoding corrects the bit error, but it makes the possibility of a phase error three times more likely.

 

I realized that there exists a transformation of quantum coding, what we now call the Adama transformation, that can turn a bit error into a phase error and vice versa. This transformation is

 

 

If you apply this transformation, you get a phase error correction code, which corrects phase errors, but makes the bits three times more likely to be wrong. This code is

 

 

You can combine these two codes by a process called cascading, which is a very important technique in classical coding theory: first, you encode the quantum bits you want to protect in one of the quantum codes; then you encode each quantum bit in the resulting state in the other code.

 

When you combine them in this way, you get the following 9-qubit code that can correct both bit errors and phase errors.

 

 

Classically, repetition codes have unofficially had to have been around for thousands of years.

 

However, more complex classical error correction codes, much more effective than repetition codes, have only been discovered for less than fifty years, the earliest of which was discovered by Richard Hamming.

 

By analogy, I decided to go in search of more complex quantum error correction codes.

 

I started playing with the classical 7-bit Hamming code - a classical code that is only more complex than a repetition code - and discovered its quantum version, which encodes a quantum bit into seven quantum bits and corrects an error.

 

The key here again is the Adama transform, which converts the bit error and the phase error back and forth. The classical Hamming code corrects the bit error. However, if you make its codeword a superposition state in a proper way, it will be invariant under the Adama transform, and thus can correct both bit errors and phase errors.

 

This gives the 7-qubit quantum Hamming code.

 

 

I showed this construction to Rob Keldbank, and then we generalized it to a large class of quantum error correction codes by combining two classical codes that are weakly paired with each other.

 

Andrew Szydian discovered quantum Hamming codes and this construction at about the same time, so these codes are now named CSS codes after their discoverer.

After these developments, the search for other quantum error correction codes began.

 

Two groups, one at Los Alamos National Laboratory and one at IBM, took the problem to the computer and both discovered a 5-quantum bit code.

 

The two 5-quantum bit codes look completely different, but you can act on a series of transformations and then see that they are actually the same. In addition, although it seemed obvious that they had some kind of structure, it was not clear what that structure was.

 

When I tried to figure out the structure of this code, the first thing I decided to do was to find its symmetry group.

 

I asked Neil Sloan how he found the symmetry group, and he told me about some software - MAGMA, to be exact - and gave me an example of a MAGMA program that he had written to calculate the size of a group used in his research.

 

The software showed that my group was the same size as his, 5160960, and not only that, but if you look closely, you can see that they are in fact the same group and that there is a deep connection between the two problems.

 

This led us to the discovery of stable subcode theory (which was also discovered by Daniel Gottesman at the same time).

 

There were some other interesting developments during this period.

 

Alexey Kitayev heard about the results of factorization, but he could not really get the article because he was in Russia. So he came up with an alternative proof of the result, which gave us the phase estimation algorithm.

 

And Love-Grover at Bell Labs discovered a quantum search algorithm that was as efficient as the square of the best classical search algorithm.

 

The last thing I want to talk about is fault tolerance.

 

In order to build a quantum computer, it's not enough to be able to correct errors with noiseless gates; you also have to be able to correct errors with noisy gates. This means that you have to be able to correct errors faster than you can introduce new errors.

 

Von Neumann 1956 showed how to do this with classical noise-containing gates. But with quantum bits it's a little trickier - you have to figure out how to perform operations on the encoded quantum bits before you decode them, because once you decode the logical bits, you may have already exposed them to errors.

 

I realized that for the Clifford group (translation: the group generated by the Adama gate H, the phase gate S, and the controlled non-gate CNOT, where the effect of the S gate is to rotate the quantum bit by π/2 angle around the z-axis.) The gates in the RI this is fairly straightforward because for a certain class of CSS codes you can perform these gates horizontally, i.e., it is possible to have the ith quantum bit encoding a logical quantum bit act only with the ith quantum bit of other logical quantum bits.

 

This separates the ith quantum bit of the codeword from the jth quantum bit, so the error does not propagate very far. However, this only works for the gates in the Clifford group, and the gates in the Clifford group do not allow you to do generic computations.

 

In fact, if your quantum circuit contains only gates in the Clifford group, it can be simulated with a classical computer.

 

How to perform non-Clifford gates on encoded quantum bits?

 

Actually, we just need to figure out how to implement a gate that is not in the Clifford group. The first thing I tried was to implement this gate on encoded quantum bits

 

 

What happens when we act this gate on an arbitrary coded quantum bit, picture? We will get

 

 

Compare it with the following state

 

 

How to turn this state into the desired state 

 

We can act a controlled picture gate to change the sign of the state picture, and then act the CNOT, or controlled picture gate, from the second quantum bit to the first quantum bit. (The controlled bubble gate is in the Clifford group, so we can run it fault-tolerantly.) This will give us this state

 

 

Now, if we measure the first encoded quantum bit under the base  and get the result , we get the desired state . Conversely, if we get the result picture, we will have the state .

 

So we found a process where we can turn a state clockwise or counterclockwise by 2π/3, with probability 1/2 in each direction.

 

However, since turning this angle clockwise twice will give a counterclockwise rotation, we can repeat the process until we get the state, and the number of rotations we expect to do is only two.

 

The difficulty with the above idea is that it is not clear how to prepare the encoded state .

 

It took me some time and effort to figure out how to use a similar approach to construct the Toffoli gate (translation: i.e., quantum-controlled-controlled-not gate, also called quantum-and-gate).

I

nstead of using an auxiliary state picture, we use a .

 

The key to preparing this auxiliary state is to use the cat-state .

 

The key to preparing this auxiliary state is to use the cat state . You can examine this state to ensure that it is a superposition of a state containing at most zeros and a state containing at most ones.

 

You cannot easily verify the phase of the superposition; however, if you build your circuit carefully, errors in this phase will only lead to correctable errors in the quantum code, which can be handled by error correction circuits.

 

My article does not give the error tolerance result I wanted to prove, which is the threshold theorem.

 

The threshold theorem says that if you have a low enough constant error rate, you can construct an error-tolerant version of it for any quantum circuit and only incur no more than a polynomial level of extra expense.

 

One shortcoming of my paper is that it only shows how to implement finite sets of gates. I showed how to implement all Clifford and Toffoli gates. You can also find some other ways of constructing gates strictly. However, based on the nature of quantum fault tolerance, any fault-tolerant protocol can only implement a finite set of gates.

 

This is because, if it can fault-tolerantly implement a family of gates that depend on a continuous parameter, you cannot distinguish between two similar values of that continuous parameter.

 

Therefore, all you need to do is to find a set of discrete gates that give a good approximation to an arbitrary smallest positive transformation on a smaller number of quantum bits.

 

The Solovy-Kitaev theorem shows that this is possible. In fact, this theorem states that if any finite set of gates in SU(k) can generate a dense group in SU(k), then any gate in SU(k) can be well approximated by a relatively short sequence of this gate set.

 

Using this you can show that if fault-tolerant operations are implemented for any set of gates that can generate a dense one group in SU(k), you can use these approximations to build a fault-tolerant circuit such that it approximates any circuit well enough and only has to incur the extra expense of multiple logarithms.

 

My article also does not show that quantum computers can be built fully fault-tolerant.

 

It shows that if the error rate of your quantum hardware is ε, you can run gates of the order of magnitude of the picture to make the total error rate smaller, where c is some constant.

 

However, what I really want to prove is that there is some threshold below which arbitrarily long operations can be performed error-tolerantly if the error rate ε is below that threshold.

 

Two research groups eventually proved this result, by self-cascading my construction many times. To compute n steps, you need to cascade loglogn layers and pay a multilogarithmic expense for this.

 

Alexei Kitayev discovered another way to perform fault-tolerant quantum computation, by using topological codes.

 

The discovery of the threshold theorem showed that quantum computers might be technically feasible (though still difficult), leading to a major explosion of research into various practical routes of construction.

 

Link to original article：

The Early Days of Quantum Computation，Peter W. Shor, arxiv:2208.09964, https://arxiv.org/abs/2208.09964