My favourite theorem in complexity theory is the Time hierarchy theorem. However, this was done in 1965.

I wanted to know then if there was anything similar for Quantum Computing.

Also, if not what are the people / groups working in this direction!

  • $\begingroup$ Somehow this question sounds like an accusation and I do not like that. $\endgroup$ – Tsuyoshi Ito Jan 21 '11 at 15:03
  • 13
    $\begingroup$ What is the accusation? $\endgroup$ – Zelah 02 Jan 21 '11 at 15:43
  • 2
    $\begingroup$ Interesting, but it seems that the answer is no. I read here that "similar theorems are not known for probabilistic time or quantum time." $\endgroup$ – M.S. Dousti Jan 21 '11 at 15:53
  • 4
    $\begingroup$ I think Tsuyoshi interpreted the exclamation mark in your last sentence as an accusation to quantum researchers of not working on important results. I am sure you simply meant to ask whether people are working towards a prob./quantum hierarchy theorem or not. $\endgroup$ – Alessandro Cosentino Jan 21 '11 at 16:53

A more recent citation for time hierarchy theorems is "A Generic Time Hierarchy for Semantic Models With One Bit of Advice" by Dieter van Melkebeek and Konstantin Pervyshev that you can get from Dieter's webpage. The techniques there give a time hierarchy with 1 bit of advice for "any reasonable" semantic model of computing, including quantum algorithms.

Also, it is normally relatively easy to obtain a hierarchy for the promise problems computed by semantic models. A promise problem only requires an algorithm to "behave nicely" (e.g., have bounded error) on some inputs -- those that are chosen to be part of the promise problem. For inputs not chosen to be part of the promise, the algorithm can behave arbitrarily (e.g., not have bounded error). A hierarchy for promise problems is a folklore result; a proof for the BPP setting is given in "Space Hierarchy Results for Randomized and Other Semantic Models" by Dieter van Melkebeek and Jeff Kinne (myself) that you can get from Dieter's or my webpage. This should apply to quantum algorithms also.

So the answer is, decent hierarchy theorems are known for quantum algorithms that either get 1 bit of advice or are allowed to ignore problematic inputs. Some of the techniques for these results rely on the properties of randomized algorithms. It would be interesting to try and exploit the properties of quantum algorithms in the area of hierarchy theorems.

A somewhat related area where there are results specific to quantum algorithms is the area of time-space lower bounds. There is a survey by Dieter van Melkebeek: "A Survey of Lower Bounds for Satisfiability and Related Problems".


The answer is no. We don't even have a time hierarchy theorem for bounded-error probabilistic polynomial time (i.e., BPTIME). The deterministic and non-deterministic time hierarchy theorems have a diagonalization argument, which does not seem to work for semantic classes. This is why we don't have strong hierarchy theorems for semantic classes.

The best result I'm aware of is a hierarchy theorem for BPTIME with 1 bit of advice: Fortnow, L.; Santhanam, R. (2004). Hierarchy Theorems for Probabilistic Polynomial Time.

I don't know of any groups working on a quantum time hierarchy theorem. I would guess that this is because it seems like the BPTIME hierarchy problem is easier, so researchers would attack that problem instead.

(Somewhat related questions: Is there a syntactic characterization for BPP, BQP, or QMA? on MathOverflow and Semantic vs. Syntactic Complexity Classes on cstheory.)

  • $\begingroup$ We do have a time hierarchy theorem for BPTIME (albeit with much weaker bounds than for DTIME): say, $\mathrm{BPTIME}(t(n))\subsetneq\mathrm{BPTIME}(2^{t(n)})$. $\endgroup$ – Emil Jeřábek Mar 3 at 7:18

The nondeterministic quantum time- and space- bounded classes are those where the languages are the sets of strings accepted by quantum Turing machines operating within the corresponding bounds with nonzero probability.

In Section 8 of "proving the power of postselection", we show that tight hierarchies for the nondeterministic quantum time- and space-bounded classes exist.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.