How powerful is exact "quantum" computing if you suspend unitarity?

Question

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}}}$?

Answer 1

Short answer. It turns out that suspending the requirement of unitary transformations, and requiring each operation to be invertible, gives rise to exact gap-definable classes. The specific classes in question are $\mathsf{LWPP}$ and a 'new' subclass $\mathsf{LPWPP}$, both of which sit between $\mathsf{SPP}$ and $\mathsf{C_=P}$. These classes have fairly technical definitions, which are briefly described below; though these definitions can now be substituted, in principle, with ones in terms of non-unitary "quantum-like" algorithms.

The counting class $\mathsf{SPP}$ contains GRAPH ISOMORPHISM. It also contains the entire class $\mathsf{UP}$, so we would not expect exact unitary quantum algorithms to be as powerful as the non-unitary classes (as we could otherwise show $\mathsf{NP \subseteq BQP}$).

Longer answer.

• In my question, I proposed redefining $\mathsf{EQP}$ to allow for problems which are solvable by uniform circuit families which use gates which are efficiently computable, but not necessarily drawn from a finite gate-set. I'm no longer so certain that it is a good idea to redefine $\mathsf{EQP}$ in this way, though I do believe such circuit families are worthwhile to study. We may call this class something like $\mathsf{UnitaryP_{\mathbb C}}$ instead.

  It is possible to show that $\mathsf{UnitaryP_{\mathbb C} \subseteq LWPP}$, which until recently was the best known bound for $\mathsf{EQP}$. The class $\mathsf{LWPP}$ more-or-less corresponds to problems for which there is a randomised algorithm, where NO instances produce an outcome of 1 with probability exactly 0.5, and YES instances produce an outcome of 1 with some probability which can be efficiently and exactly computed in rational form, which is greater than (but possibly exponentially close to) 0.5. The technical definition of $\mathsf{LWPP}$ is presented in terms of nondeterministic Turing machines, but is no more illuminating.

  If we define $\mathsf{GLP}_{\mathbb C}$ to be the invertible-gate equivalent of $\mathsf{UnitaryP_{\mathbb C}}$, so that it is the set of problems which are exactly solvable by invertible circuit families with efficiently computable gate coefficients, then $\mathsf{GLP_{\mathbb C} = LWPP}$.

• If we restrict to finite gate-sets, it is possible to show that unitary circuit families may be simulated in a subset of $\mathsf{LWPP}$, which we might call $\mathsf{LPWPP}$. (Using the description of $\mathsf{LWPP}$ above, this corresponds to randomised algorithms where the probability of obtaining an output of 1 for YES instances is exactly $m^{t(x)} / 2^{p(|x|)}$, for some polynomial $p$, some integer $m$, and some efficiently computable polynomial $t$.)

  If we define $\mathsf{EQP_{\mathrm{GL}}}$ to be the invertible-gate equivalent of $\mathsf{EQP}$ as it is normally defined, we may show that $\mathsf{EQP_{\mathrm{GL}} \subseteq LPWPP}$.

A correction regarding DISCRETE LOG.

The results above rely on standard techniques to represent algebraic coefficients, in a way which is independent of the input (but which may depend on input size). In the description of the original question, I claimed that [ Mosca+Zalka 2003 ] show that DISCRETE LOG is exactly solvable by a gate-set with efficiently computable coefficients. The truth appears to be more complicated. If one cares about exact solvability, then I consider exact representation of the coefficients to be important: but Mosca and Zalka do not provide a way of doing this in an input-dependent way. So it is not obvious that DISCRETE LOG is in fact in $\mathsf{EQP}$ or in the new class $\mathsf{UnitaryP_{\mathbb C}}$.

Reference.

• de Beaudrap, On exact counting and quasi-quantum complexity, [arXiv:1509.07789].