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

wouldimply a time hierarchy for BPP. I think the survey in Robin's nice answer covers this. $\endgroup$ – Ryan Williams Aug 12 '10 at 3:09