Are there descriptive complexity representations of quantum complexity classes?

Question

The title more or less says it all, but I guess I could add a bit of background and some specific examples I'm interested in.

Descriptive complexity theorists, such as Immerman and Fagin, have characterized many of the most well-known complexity classes using logic. For example, NP can be characterized with second-order existential queries; P can be characterized with first-order queries with a least-fixed point operator added.

My question is: Have there been any attempts, especially successful ones, at coming up with such representations for quantum complexity classes, such as BQP or NQP? If not, why not?

Thank you.

Update(moderator): this question is completely answered by this post on mathoverflow.

Answer 1

I think Robins's answer to my question on MO also answers this one.

A descriptive complexity characterization of a complexity class $C$ gives a language whose queries (i.e. formulas) are exactly the functions computable in $C$. The syntax of the language is usually very simple, i.e. given a string $q$ it is easy to check if $q$ is a well-formed query of the language, at least it is expected to be decidable (but usually syntax checking cen be done in a small complexity class). This would entail effective enumerablity of the problems in the class $C$ and would give a syntactic characterization for $C$. (If the complexity of syntax checking is low it might also imply the existence of a complete problem for the class.)

In the comments above, Robin linked to Kord Eickmeyer and Martin Grohe's paper "Randomization and Derandomization in Descriptive Complexity Theory" which gives a "descriptive complexity" characterization of $BPP$. The authors themselves note in the introduction that this is different from what is usually meant by a descriptive complexity characterization:

We prove that $BPIFP+C$, the probabilistic version of fixed-point logic with counting, captures the complexity class $BPP$, even on unordered structures. For ordered structures, this result is a direct consequence of the Immerman-Vardi Theorem [7, 8], and for arbitrary structures it follows from the observation that we can define a random order with high probability in BPIFP+C. Still, the result is surprising at first sight because of its similarity with the open question of whether there is a logic capturing $P$, and because it is believed that $P = BPP$. The caveat is that the logic $BPIFP+C$ does not have an effective syntax and thus is not a “logic” according to Gurevich’s [9] definition underlying the question for a logic that captures $P$. Nevertheless, we believe that $BPIFP+C$ gives a completely adequate description of the complexity class $BPP$, because the definition of $BPP$ is inherently ineffective as well (as opposed to the definition of $P$ in terms of the decidable set of polynomially clocked Turing machines).

I am not an expert in finite model theory/descriptive complexity (and personally would like to hear more from experts), but my feeling is that there is a little bit cheating here in saying that this is a descriptive complexity characterization. The reason for my feeling is that if we are allowed to have non-effective syntax, we can use arbitrary semantical restrictions to restrict the class of well-formed queries and can give a "descriptive complexity" characterization for any complexity class. For example, consider $SO(TC)$ (which captures $PSpace$), and then take exactly those queries which are computable in $BQP$; or consider the language that has one function symbol for each machine in $BQP$. Both of these capture $BQP$ but don't have an effective syntax.

Answer 2

Gurevich in formulating the conjecture about a logic that could capture $\mathsf{P}$ requires the logic to be computable in two ways: (1) the set of sentences legally obtainable from the vocabulary $\sigma$ has to be computable, given $\sigma$; and (2) the satisfiability relation needs to be computable from $\sigma$, i.e., ordered pairs consisting of a finite structure $M$ and a sentence $\varphi$ such that all models isomorphic to $M$ satisfy $\varphi$. Also, significantly for comparison with this randomized logic result, the vocabulary $\sigma$ has to be finite. (A vocabulary is a set of constant symbols and relation symbols, for example, equals sign, less-than sign, $R_1,R_2,\ldots$) This is a paraphrase of Definition 1.14 of this paper by Gurevich, which is reference [9] in the quote Kaveh gave.

The paper about BPP and randomized logic presents a significantly different framework. It starts with a finite vocabulary $\sigma$, and then considers a probability space of all vocabularies that extend $\sigma$ with some disjoint vocabulary $\rho$. So a formula is satisfiable in the new randomized logic if it is satisfiable in "enough" logics based on extensions of $\sigma$ by different $\rho$. This is my butchering of Definition 1 in the Eickmeyer-Grohe paper linked to by Robin Kothari. In particular, the vocabulary is not finite (well, each vocabulary is, but we have to consider infinitely many distinct vocabularies), the set of sentences of this logic is undecidable, and the notion of satisfiability is different from the one put forth by Gurevich.