Unmasking Quantum Computation
Is BQP in the polynomial hierarchy?
Paul Dirac is one of the founders of quantum mechanics, for which he received the Nobel Prize in 1933. His seminal contributions include: the discovery of the equation named after him and the prediction of antimatter. Pretty amazing that he could predict an entire new type of matter just from equations.
Today I plan on talking about notation, , and the polynomial hierarchy.
Dirac was known for his taciturn manner, his careful choice of words in both speech and writing. There is a wonderful book on his life called “The Strangest Man,” by Graham Farmelo. I definitely recommend reading it—I certainly enjoyed it very much.
There is a interview that was real, but as I understand it, the interview was only partly real. As we would say today it was “reality based.”
Then we sat down and the interview began.
“Professor,” says I, “I notice you have quite a few letters in front of your last name. Do they stand for anything in particular?”
“No,” says he.
“You mean I can write my own ticket?”
“Yes,” says he.
“Will it be all right if I say that P.A.M. stands for Poincare’ Aloysius Mussolini?”
“Yes,” says he.
“Fine,” says I, “We are getting along great! Now doctor will you give me in a few words the low-down on all your investigations?”
“No,” says he.
“Good,” says I. “Will it be all right if I put it this way—`Professor Dirac solves all the problems of mathematical physics, but is unable to find a better way of figuring out Babe Ruth’s batting average’?”
“Yes,” says he.
“What do you like best in America?”, says I.
“Potatoes,” says he.
“Same here,” says I. “What is your favorite sport?”
“Chinese chess,” says he.
That knocked me cold! It was sure a new one on me! Then I went on: “Do you go to the movies?”
“Yes,” says he.
“When?”, says I.
“In 1920—perhaps also in 1930,” says he.
“Do you like to read the Sunday comics?”
“Yes,” says he, warming up a bit more than usual.
“This is the most important thing yet, doctor,” says I. “It shows that me and you are more alike than I thought. And now I want to ask you something more: They tell me that you and Einstein are the only two real sure-enough high-brows and the only ones who can really understand each other. I won’t ask you if this is straight stuff for I know you are too modest to admit it. But I want to know this—Do you ever run across a fellow that even you can’t understand?”
“Yes,” says he.
“This well make a great reading for the boys down at the office,” says I. “Do you mind releasing to me who he is?”
“Weyl,” says he.
The interview came to a sudden end just then, for the doctor pulled out his watch and I dodged and jumped for the door. But he let loose a smile as we parted and I knew that all the time he had been talking to me he was solving some problem that no one else could touch.
But if that fellow Professor Weyl ever lectures in this town again I sure am going to take a try at understanding him! A fellow ought to test his intelligence once in a while.
Let’s turn from this interview to today’s discussion: the “unmasking” of quantum computation. This unmasking takes place at several levels:
- Quantum computation is filled with many deep mysteries. Of course we are not much better off with classical computation, but quantum seems even more difficult.
- Quantum computation is an area that I am not an expert—not even close. But it is an area that a few of us have decided to try to unmask; in the sense not of solving open problems, but of beginning to understand what the experts already know. As we do this my plan is to share it with you all, which I hope you find interesting.
- Quantum computation is the domain of some of best minds in the world—I hesitate to make even a partial list lest I leave someone out. But the experts in the area know so much that they sometimes are way ahead of the rest of us. This is a common feature of expertise: often an expert in a field cannot explain some things precisely because they have known them for so long.
An example from another area is chess. I recall many years ago watching the 1985 world champion match between Garry Kasparov and Anatoly Karpov on TV. One of the commentators was the past world champion Boris Spassky, who helped PBS cover the matches. At one point Spassky, was asked: “how do you decide what move to make next?” A reasonable question. But his answer was strange, at least to a weak player like myself:
“I move the piece whose aura is the brightest.”
As I said experts do not always know how to best explain what they do. Ken Regan added:
Spassky got that right! That’s actually a good exercise: set up a position and find the most glittering piece. Helps if you have a portable pyramid
Recall Ken is an international master, almost a grandmaster.
Dirac introduced the notation that is standard now in quantum computation and mechanics. It is a clever shorthand for denoting row and column vectors, and more. Let be a vectors, then:
I have to say that the notation is used throughout quantum computing and I feel that I am an outsider because while I understand the notation I really do not feel comfortable yet with it. Perhaps I never will. I have discussed notation before here, and its ability to help shape our thinking in mathematics.
It reminds me of chess notation. When I was in high school I played a great deal of chess, was never very good, but studied it quite a bit. At that time the so called descriptive notation was used: squares had names based on the piece that started in that column. One strange feature is each square had two names: one from white’s point of view and one from black’s point of view. It may not have been the best notation but it became hardwired into my brain—I could look at any square on the board and instantly know its name(s).
When I looked again at chess many years later the notation system had changed to the algebraic system. This system is very computer science like: just label the columns “a-h” and the rows “1-8.” What could be more natural, and now each square has a unique name. A great system, but I do not feel comfortable with it. Perhaps I will someday.
Polynomial Hierarchy and
One of the major open problems in the understanding of the complexity class is to see where its sits with respect to the polynomial hierarchy, . It could be that lies in some level of the hierarchy, or it could be that it lies above the whole of . It could even be the case that they are incomparable.
A great summary: in this case complexity classes, could be related in only one of three ways. Not a great insight, but it is a great problem. If is in the hierarchy, then it would be much weaker than we currently know; if it is above the hierarchy, then it would be much more powerful than we currently know. If they are incomparable, then we are in a more complex situation.
There are many results known about this basic question, but none are definitive. The question whether or not there is an oracle so that
is still open, as are many related questions about and where it sits. As a non-expert I do not even have a good guess about what the correct result should be. You all known, probably, that I often go against the conventional wisdom, yet here there is not even complete agreement on what the best guess is. At least that is how I read the literature.
A Simple Result
In an attempt to understand why placing in the polynomial hierarchy may be so difficult I thought the following simple result may be interesting. It shows that proving that is not in the hierarchy will be hard. I am sure that this is not new, but I still think pointing it out is helpful.
Theorem: If is not contained in the level of the , then requires super-polynomial sized circuits.
What this result says to me, is that it will be quite hard to prove that is not in the polynomial hierarchy. The reason is that we have no tools to prove super-polynomial lower bounds on general circuits. Well pretty close to none. There even are results, such as the famous work of Sasha Razborov and Steven Rudich on natural proofs, that show proving such results may be quite impossible. At least impossible without some new insights.
The proof of this theorem is really simple. We will prove the contra-positive: recall
is the same as
Proof: So assume that has polynomial sized circuits. Then it follows that the following inclusions are true:
Can the above simple theorem be improved in any substantial way? For example can we prove the following theorem: if is not contained in the polynomial hierarchy, then has super-polynomial sized circuits? I believe that this is true, perhaps it is known and I am just unaware of it. But it seems like it should be true.