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, ${\mathsf{BQP}}$, 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:

1. 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.
2. 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.
3. 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 ${\dots}$

Recall Ken is an international master, almost a grandmaster.

Notation

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 ${V,A,B}$ be a vectors, then:

$\displaystyle V \rightarrow |V \rangle \ , V^T \rightarrow \langle V | \ , A^TB \rightarrow \langle A,B \rangle.$

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 ${\mathsf{BQP}}$

One of the major open problems in the understanding of the complexity class ${\mathsf{BQP}}$ is to see where its sits with respect to the polynomial hierarchy, ${\mathsf{PH}}$. It could be that ${\mathsf{BQP}}$ lies in some level of the hierarchy, or it could be that it lies above the whole of ${\mathsf{PH}}$. 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 ${\mathsf{BQP}}$ 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 ${A}$ so that

$\displaystyle \mathsf{BQP}^A \not \subset \mathsf{PH}^A$

is still open, as are many related questions about ${\mathsf{BQP}}$ 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 ${\mathsf{BQP}}$ in the polynomial hierarchy may be so difficult I thought the following simple result may be interesting. It shows that proving that ${\mathsf{BQP}}$ 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 ${\mathsf{BQP}}$ is not contained in the ${\Sigma_2}$ level of the ${\mathsf{PH}}$, then ${\mathsf{PSPACE}}$ requires super-polynomial sized circuits.

What this result says to me, is that it will be quite hard to prove that ${\mathsf{BQP}}$ 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

$\displaystyle A \implies B$

is the same as

$\displaystyle \neg B \implies \neg A.$

Proof: So assume that ${\mathsf{PSPACE}}$ has polynomial sized circuits. Then it follows that the following inclusions are true:

$\displaystyle \begin{array}{rcl} \mathsf{PSPACE} &\subseteq& \mathsf{P/poly}, \\ \mathsf{PSPACE} &\subseteq& \Sigma_2(\mathsf{poly}) \ \text{by known theorem}, \\ \mathsf{BQP} &\subseteq& \mathsf{PSPACE} \ \text{by known inclusion}, \\ \mathsf{BQP} &\subseteq& \Sigma_2(\mathsf{poly}) \ \text{by transitivity of the subset relation}. \end{array}$

$\Box$

Open Problems

Can the above simple theorem be improved in any substantial way? For example can we prove the following theorem: if ${\mathsf{BQP}}$ is not contained in the polynomial hierarchy, then ${\mathsf{BQP}}$ 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.

February 9, 2011 10:36 pm

I love your stories. I am old enough to remember that chess notation but also old enough to have forgotten it.

What is known about the quantum polynomial hierarchy? Do you believe Q = NQ? 🙂

• February 9, 2011 11:52 pm

Non, mon ami, et j’etais trés familier avec le rapport “Q = NQ?” il y a 25 ans… :-).

• August 20, 2012 1:46 pm

Pardon my French, there was actually a paper by Bruno Poizat in French with the title “Q = NQ?” around 1986. My comment about “having a portable pyramid” was meant to be New Age tongue-in-cheek as well.

2. February 9, 2011 11:58 pm

another important contribution maybe is the Fermi–Dirac statistics which Fermi and Dirac discovered independently.

3. February 10, 2011 12:32 am

It is very interesting for me to hear from you that Mr.Dirac likes Chinese chess.It is a game with almost two thousand year ,and I think it’s rule is very simple.There are some classic works on Chinese chess which of content is about the winning strategy,which I ‘d now think is algorithm to win.

4. February 10, 2011 7:04 am

Paul Dirac loved a good mystery, and one of the most important mysteries in all of science is the “Fine Structure Constant” .

Both Dirac and Richard Feynman conjectured that the Fine Structure Constant (which “appears” to be a purely “physical constant”) may actually turn out to be a “mathematical constant” .

Well, it is now quite clear that they were right all along!

The “counting function” for “polygonal numbers of order greater than 2”, which can be found here:

http://donblazys.com/on_polygonal_numbers_3.pdf

can be used to approximate how many “polygonal numbers of order greater than 2” there are under a given number x, in exactly the same way that Li(x) can be used to approximate how many “prime numbers” there are under a given number x.

The properties of polygonal numbers are even more fundamental than the properties of primes, and strangely enough, the ancient Greeks considered them to be “atomistic”!

Don.

• February 10, 2011 11:02 am

HMM,And there are links or correlation between Riemann Hypothesis and Quantum theory that I just read from some popular articles.

5. February 10, 2011 9:15 am

I can’t speak much to the polynomial hierarchy … for engineers, the most natural “solution” is to restrict P’⊂P such that the polynomial hierarchy collapses trivially … problem solved!

Of course, then a new problem arises: experimentally disprove the extended Geroch-Hartle postulate … and so it never ends.

There *is* however a Dirac quote that exerted considerable influence on me as a student, that Valentine Telegdi told to all his students:

“A golden age is a time when ordinary people can make extraordinary contributions.”

Telegdi would then forcibly argue that physics (in the late 1970s) was entering a Golden Age.

Nowadays I appreciate that Telegdi almost certainly was not quoting Dirac verbatim; rather Telegdi’s attitude toward quotation was more like Mark Twain’s “Truth is the most valuable thing we have. Let us economize it.” However, there are several verifiable quotes by Dirac that make Telegdi’s point; here is one:

I have the best of reasons for admiring Heisenberg. He and I were young students at the same time, about the same age, working on the same problem. Heisenberg succeeded where I failed. … [He] started the golden age of theoretical physics, and for a few years after that it was easy for any second rate student to do first rate work.

Are we presently entering a golden age of computer science, complexity theory, and quantum information theory? There are pretty good reasons to foresee that the answer is “yes” … we can all hope so, anyway! … and on an increasingly over-heated, over-crowded, resource-poor planet, this kind of good news is vital. 🙂

This line of thought is commended, especially, to the (many) unhappy young complexity theorists who presently are posting on the Fortnow/GASARCH Computational Complexity weblog under the topic “The Theory Postdoc Culture.” It does not solve all problems, but it helps us make a good start toward retiring some of them.

6. February 11, 2011 8:12 am

Dear Dick and Ken, one remark (also related to the posts about factoring): The computational power described by “what quantum computers do in polynomial time” might not be the same as the computational power described by the complexity class “BQP”. I always regarded these as expressing essentially the same computational power (and this may be true) but there are indications to the contrary. (A related blog post is http://gilkalai.wordpress.com/2010/11/17/aaronson-and-arkhipovs-result-on-hierarchy-collapse/ .)

• February 11, 2011 10:30 am

Dear Gil, well understood! We intend something about that, sometime after the Feb. 15 ICALP deadline. Thanks.

• February 11, 2011 10:50 am

Gil, I hope you are not embarrassed by my pointing that your weblog and your many fine queries on MathOverflow and on TCS StackExchange qualify you as one of TCS community’s lamed vavniks. In particular, I definitely agree with your to-the-point remarks on BQP.

Nowadays a lot of complexity theory insights, that once were confined to the platonic universe of mathematical formalism, are instantiated in earthly hardware and even human physiology (why else would a medical researcher like me be writing this post?). In consequence, obstructions to our understanding that once were perceived purely technical, are now understood to amount to practical obstructions too.

In particular, whenever complexity-theoretic results rely upon oracles, misunderstandings generically arise in communicating these results to engineers. For example, given a concrete algorithm M, asserted to be in P, an engineer expects to feasibly upper-bound its runtime R(M,n) as a function of the input length n … and yet this is infeasible. As another example, given a concrete dataset {d_i}, asserted to be sampled from a distribution D, an engineer expects that statistical tests will exist that feasibly (and stringently) verify this assertion … and yet this too is infeasible. Here “feasible” has its commonplace meaning, that the computational resources required to bound runtimes and verify datasets are themselves verifiably in P (not EXP).

In consequence, to engineers complexity theory appears (metaphorically) as a large, beautifully designed aircraft that spends all its time taxiing up-and-down a runway. Week-by-week, month-by-month, and year-by-year, skilled technicians install larger engines, more cleverly shaped wings, and better controls to the aircraft … such that the aircraft becomes steadily more sophisticated and beautiful … and yet the aircraft does not fly. And here by “fly” is meant the achievement of practical objectives like concrete separations of P from NP, one-way functions, lower bounds to common algorithms, and feasible sampling verification.

It is natural for engineers to wonder “Uhhh … maybe the cargo loaded onto the plane is too heavy? How much does that complexity class P weigh, that was in the initial loading of the plane? Can we not lighten the plane, by carrying only the essential parts of P?” And needless to say, similar considerations apply to quantum classes like BQP, which similarly are gaining in practical engineering significance.

The not-too-reassuring answer from complexity theorists seemingly amounts to “We have never weighed P (or BQP) and there are reasons to believe that it may not be feasible to do so. Moreover, we are reluctant to unpack P (or BQP), on the grounds that some of the members may be so hard-to-describe, that (without real-world oracles to help us) we might never succeed in reloading the plane with any meaningful subset of it. Therefore, we recommend that engineers simply relax, and admire our highly advanced plane-taxiing technology.”

Engineers definitely do admire aircraft that taxi well … taxiing is a immensely sophisticated function for any aircraft. And yet, we wonder whether—with a lighter loading—the aircraft that is modern complexity theory, might not be ready to fly, pretty soon, to some mighty interesting places. Perhaps there we will find better answers to all the wonderful questions that have been raised here.

• February 13, 2011 2:45 am

Thanks a lot, John

February 18, 2011 4:53 pm

I was not sure what you meant by this at first. I see these are the relevant bits of your blog entry (below). It is true that there is not an obvious way of using a decision oracle to get a sampling oracle. On the other hand, I do not know of any cases where having a decision quantum algorithm is essential, e.g., threshold theorems obviously hold for sampling problems.

“Question 5: If QSAMPLE is in BQP, does this imply unreasonable computational complexity consequences?

What I mean is this: Suppose you are given a classical computer with BQP subroutine. So every decision problem in BQP the subroutine can solve in polynomial time. How strong is this computer? Lets call it a BQP machine. Can this computer create (or well approximate) probability distributions in QSAMPLE? If the answer is yes then already P=BQP collapses the hierarchy by AA’s result. But it is possible that if a BQP machine can approximate QSAMPLE then this already will have unreasonable computational complexity consequences.

But again what I ask about is this. Perhaps QSAMPLE represents much stronger computational power compared to BQP, so that AA’s theorem (perhaps even their proof) can be extended to show that simulating QSAMPLE by BQP-machines already has surprising computational-complexity consequences.”

• February 18, 2011 8:05 pm

Guided by Scott Aaronson’s sensibly good-hearted advice to post questions on TCS StackExchange and on MathOverflow … and with the subsequent vital help of proof sketches provided by Emanuele Viola and Luca Tevisan … I have posted a brief engineer-oriented summary as a (hopefully) well-posed answer to the MathOverflow question What are the most attractive Turing undecidable problems in mathematics?

7. February 22, 2011 2:35 pm

Hi Dick, just came across this post!

I agree that it’s a wonderful problem to construct an oracle relative to which BQP is not in PH. As you probably know, I proposed a candidate oracle a couple years ago, and more recently, Fefferman et al. generalized my candidate, and also showed that proving these constructions work is closely related to beating the Nisan-Wigderson hybrid argument, and even to the L vs. RL problem (!). So while we haven’t solved the relativized BQP vs. PH problem, I think it’s fair to say that we’ve thrown the ball firmly back into classical complexity theory’s court! 🙂

As for your closing question, whether BQP in P/poly implies BQP in PH — alas, at the moment we can’t prove any implication of the kind! Furthermore, I strongly conjecture that if we had an oracle relative to which BQP was not in PH, then we could also put BQP in P/poly relative to the same oracle.