Is there a syntactic characterization for BPP, BQP, or QMA? - MathOverflow

Is there a syntactic characterization for BPP, BQP, or QMA?

2010-08-11T15:02:25Z

Background

The complexity classes BPP, BQP, and QMA are defined semantically. Let me try to explain a little bit what is the difference between a semantic definition and a syntactic one. The complexity class P is usually defined as the class of languages accepted in polynomial time by a deterministic Turing machine. Although it seems to be a semantic definition at first, $P$ has an easy syntactic characterization, i.e. deterministic Turing machines with a clock counting the steps up to a fixed polynomial (take a deterministic Turing machine, add a polynomial clock to it such that the new machine will calculate the length of the input $n$, then the value of the polynomial $p(n)$, and simulate the original machine for $p(n)$ steps. The languages accepted by these machines will be in $P$ and there is at least one such machine for each set in $P$). There are also other syntactic characterizations for $P$ in descriptive complexity like $FO(LFP)$, first-order logic with the least fixed point operator. The situation is similar for PP. Having a syntactic characterization is useful, for example a syntactic characterization would allow us to enumerate the sets in the class effectively, and if the enumeration is efficient enough, we can diagonalize against the class to obtain a separation result like time and space hierarchy theorems.

My main question is:

Is there a syntactic characterization for BPP, BQP, or QMA?

I would also like to know about any time or space hierarchy theorem for semantic classes mentioned above.

The motivation for this question came from here. I used Google Scholar, the only result that seemed to be relevant was a citation to a master's thesis titled "A logical characterization of the computational complexity class BPP and a quantum algorithm for concentrating entanglement", but I was not able find an online version of it.

Answer by Artem Kaznatcheev for Is there a syntactic characterization for BPP, BQP, or QMA?

2010-08-11T22:21:39Z

This is more a comment than an answer (since I can't leave comments, yet):

I've looked into this question briefly this past winter. As far as I know there is no syntactic definitions of BPP, BQP, or QMA. If you introduce post selection to BQP then you have a syntactic definition, but that is only because PostBQP = PP and PP is syntactic.

@Henry Yuen I also don't understand why a syntactic definition of anything would imply derandomization... of course if BPP was also FOL + LFP then we would have derandomization but if BPP was FOL + other gadget then we would not know that without proving that LFP and the other gadget do the same things.

Answer by Robin Kothari for Is there a syntactic characterization for BPP, BQP, or QMA?

2010-08-12T00:18:40Z

No, I don't think any syntactic characterization is known for BPP, BQP or QMA. (BPP might turn out to be P, and then we'd have such a characterization of course.)

In particular we don't know any languages that are complete for either of these classes. A lot of people believe that classes like QMA do not even have complete languages. (See John Watrous' survey, where he says that "indeed it would be surprising if QMA were shown to have a complete problem having a vacuous promise.")

There are hierarchy theorems for BPP with 1 bit of advice, but I don't think we have any for BPP, BQP or QMA. For the advice-based results, see Hierarchy Theorems for Probabilistic Polynomial Time.