3 improved

# 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 classone. 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 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 complexity a separation , e.g. result like time and space hierarchy theoremtheorems.

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 theorems theorem for semantic classes mentioned above.

The motivation for this question came from here. I used Google Scholar, the only result that seems 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.

2 fixed grammar

# 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 and a syntactic class. The complexity class P is 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. There are also other characterizations 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 complexity separation, e.g. time hierarchy theorem.

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 theorems for semantic classes mentioned above.

The motivation for this question came from here. I used Google Scholar, the only result that seems to be relevant was 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.

1

# Baackground

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 and a syntactic class. The complexity class P is 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. There are also other characterizations in descriptive complexity like $FO(LFP)$, first order logic with 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 complexity separation, e.g. time hierarchy theorem.

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 theorems for semantic classes mentioned above.

The motivation for this question came from here. I used Google Scholar, the only result that seems to be relevant was 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.