<p>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.</p>

<p>The best result I'm aware of is a hierarchy theorem for BPTIME with 1 bit of advice: <a href="http://www.cs.uchicago.edu/~fortnow/papers/probhier.ps" rel="nofollow noreferrer">Fortnow, L.; Santhanam, R. (2004). Hierarchy Theorems for Probabilistic Polynomial Time</a>.</p>

<p>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.</p>

<p>(Somewhat related questions: <a href="https://mathoverflow.net/questions/35236/is-there-a-syntactic-characterization-for-bpp-bqp-or-qma">Is there a syntactic characterization for BPP, BQP, or QMA?</a> on MathOverflow and <a href="https://cstheory.stackexchange.com/questions/1233/semantic-vs-syntactic-complexity-classes">Semantic vs. Syntactic Complexity Classes</a> on cstheory.)</p>

CC BY-SA 4.0
2021-03-03T07:18:39.580Z
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)})$.
Emil Jeřábek
CC BY-SA 2.5
2011-01-21T16:14:05.810Z
2011-01-21T16:14:05.810Z
2017-04-13T12:57:54.777Z
Robin Kothari
<p>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.</p>

<p>In Section 8 of "<a href="http://arxiv.org/abs/1111.3125" rel="noreferrer">proving the power of postselection</a>", we show that tight hierarchies for the nondeterministic quantum time- and space-bounded classes exist.</p>

CC BY-SA 3.0
2011-11-25T23:02:39.727Z
2011-11-26T06:51:39.677Z
2011-11-26T06:51:39.677Z
Cem Say
<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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".  </p>

CC BY-SA 2.5
2011-01-25T02:35:18.333Z
2011-01-25T02:35:18.333Z
Jeff KInne
<p>My favourite theorem in complexity theory is the Time hierarchy theorem. However, this was done in 1965. </p>

<p>I wanted to know then if there was anything similar for Quantum Computing. </p>

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

CC BY-SA 2.5
2011-01-21T15:03:27.860Z
Somehow this question sounds like an accusation and I do not like that.
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-21T15:43:19.713Z
What is the accusation?
Zelah 02
CC BY-SA 2.5
2011-01-21T15:53:37.923Z
Interesting, but it seems that the answer is **no**. I read [here](http://www.worldlingo.com/ma/enwiki/en/Time_hierarchy_theorem#Extension) that "similar theorems are not known for probabilistic time or quantum time."
Sadeq Dousti
CC BY-SA 2.5
2011-01-21T16:53:23.403Z
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.
Alessandro Cosentino
<cc.complexity-theory><quantum-computing>
Is there a Quantum equivalent of the Time hierarchy theorem ?
Zelah 02
# Is there a Quantum equivalent of the Time hierarchy theorem ?

(Asked by: username_0 on 2011-01-21)

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!

**Tags:** cc.complexity-theory, quantum-computing
> **Comments:**
> **username_1**: Somehow this question sounds like an accusation and I do not like that.  
> **username_0**: What is the accusation?  
> **username_2**: Interesting, but it seems that the answer is **no**. I read [here](http://www.worldlingo.com/ma/enwiki/en/Time_hierarchy_theorem#Extension) that "similar theorems are not known for probabilistic time or quantum time."  
> **username_3**: 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.  

---

## 3 answers

### Answer by username_7 on 2011-01-25. Score: 18 | Accepted answer

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".


---

### Answer by username_4 on 2011-01-21. Score: 19

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](http://www.cs.uchicago.edu/~fortnow/papers/probhier.ps).

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?](https://mathoverflow.net/questions/35236/is-there-a-syntactic-characterization-for-bpp-bqp-or-qma) on MathOverflow and [Semantic vs. Syntactic Complexity Classes](https://cstheory.stackexchange.com/questions/1233/semantic-vs-syntactic-complexity-classes) on cstheory.)

> **Comments:**
> **username_5**: 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)})$.  

---

### Answer by username_6 on 2011-11-25. Score: 6

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](http://arxiv.org/abs/1111.3125)", we show that tight hierarchies for the nondeterministic quantum time- and space-bounded classes exist.


---

