Short Question.
What is the computational power of "quantum" circuits, if we allow non-unitary (but still invertible) gates, and require the output to give the correct answer with certainty?
This question is in a sense about what happens to the class $\mathsf{EQP}$ when you allow the circuits to use more than just unitary gates. (We're still forced to restrict ourselves to invertible gates over $\mathbb C$ if we want to be able to have a well-defined model of computation.)
(This question has undergone some revisions in light of some confusion on my part about the known results about such circuits in the unitary case.)
About "exact" quantum computation
I define $\mathsf{EQP}$ for the sake of this question to be the class of problems which can be exactly solved by a uniform quantum circuit family, where the coefficients of each unitary is computable by polynomial-time-bounded Turing machines (from the input string $1^n$) for each input size $n$, and that the layout of the circuit as a directed network can also be produced in polynomial time. By "exactly" solved, I mean that measuring the output bit yields $|0\rangle$ with certainty for NO instances, and $|1\rangle$ with certainty for YES instances.
Caveats:
Even restricting to unitary gates, this notion of $\mathsf{EQP}$ is different from that described by Bernstein and Vazirani using quantum Turing machines. The definition above allows a circuit family $\{ C_n \}$ to in principle have an infinite gate set — each individual circuit $C_n$ only uses a finite subset, of course — because the gates are in effect computed from the inputs. (A quantum Turing machine can simulate any finite gate set that you like, but can only simulate finite gate sets, because it only has a finite number of transitions.)
This model of computation trivializes any problems in $\mathsf P$, because the unitary could contain a single gate which hard-codes the solution to any problem in $\mathsf P$ (its coefficients are after all determined by a poly-time computation). So the specific time- or space-complexity of problems are not necessarily interesting for such circuits.
We can add to these caveats the observation that practical implementations of quantum computers will have noise anyway. This model of computation is interesting primarily for theoretical reasons, as one concerned with composing unitary transformations rather than feasible computation, and also as an exact version of $\mathsf{BQP}$. In particular, despite the caveats above, we have $\mathsf{P} \subseteq \mathsf{EQP} \subseteq \mathsf{BQP}$.
The reason for defining $\mathsf{EQP}$ in the way I do is so that DISCRETE-LOG can be put into $\mathsf{EQP}$. By [ Mosca+Zalka 2003 ], there is a polynomial-time algorithm to construct a unitary circuit which exactly solves instances of DISCRETE-LOG by producing exact versions of the QFT depending on the input modulus. I believe that we can then put DISCRETE-LOG into $\mathsf{EQP}$, as defined above, by embedding the elements of circuit-construction into the way that the gate coefficients are computed. (So the result DISCRETE-LOG $\in \mathsf{EQP}$ essentially holds by fiat, but relying on the construction of Mosca+Zalka.)
Suspending unitarity
Let $\mathsf{EQP_{\mathrm{GL}}}$ be the computational class that we get if we suspend the restriction that gates be unitary, and allow them to range over invertible transformations. Can we place this class (or even characterize it) in terms of other traditional non-deterministic classes $\mathbf C$?
One of my reasons for asking: if $\mathsf{BQP}_{\mathrm{GL}}$ is the class of problems efficiently solvable with bounded error, by uniform "non-unitary quantum" circuit families — where YES instances give an output of $|1\rangle$ with probability at least 2/3, and NO instances with probability at most 1/3 (after normalizing the state-vector) — then [Aaronson 2005] shows that $\mathsf{BQP}_{\mathrm{GL}} = \mathsf{PP}$. That is: suspending unitarity is in this case equivalent to allowing unbounded error.
Does a similar result, or any clear result, obtain for $\mathsf{EQP_{\mathrm{GL}}}$?