Background
==========


The complexity classes [BPP](http://en.wikipedia.org/wiki/BPP), [BQP](http://en.wikipedia.org/wiki/BQP), and [QMA](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/P_%28complexity%29) 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](http://en.wikipedia.org/wiki/Least_fixed_point) operator. 
The situation is similar for [PP](http://en.wikipedia.org/wiki/PP_%28complexity%29#Complete_problems_and_other_properties). 
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](http://en.wikipedia.org/wiki/Time_hierarchy_theorem) and [space](http://en.wikipedia.org/wiki/Space_hierarchy_theorem) 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](https://mathoverflow.net/questions/35189).
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.



Is there a syntactic characterization for BPP, BQP, or QMA?
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](http://arxiv.org/abs/0804.3401), 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](http://www.cs.uchicago.edu/~fortnow/papers/probhier.ps).


