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$
$\endgroup$
4
-
1$\begingroup$ Somehow this question sounds like an accusation and I do not like that. $\endgroup$– Tsuyoshi ItoJan 21, 2011 at 15:03
-
13$\begingroup$ What is the accusation? $\endgroup$– Zelah 02Jan 21, 2011 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$– Sadeq DoustiJan 21, 2011 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 CosentinoJan 21, 2011 at 16:53
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
0
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".
$\begingroup$
$\endgroup$
1
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.)
answered Jan 21, 2011 at 16:14
-
$\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$ Mar 3, 2021 at 7:18
$\begingroup$
$\endgroup$
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.
