What complexity issues are there in considering quantum algorithms with infinite gate-sets?

Question

Short Version

Suppose that you want to consider a model of quantum computation in which the gates used in the circuits may depend on the input size. Are there pitfalls to avoid when defining the circuits, to avoid obtaining unreasonable computational power from combining the coefficients themselves? Conversely: what limitations (aside from the conservative one of having a gate set of size $O(1)$ for the entire circuit family) yield a model whose complexity is still reasonable, and in particular does not disrupt too many of the things which we know hold for gate-sets of size $O(1)$?

Motivation and Details

The class $\def\EQP{\mathsf{EQP}}\EQP$ is the set of languages which can be decided with certainty by a polynomial-size uniform circuit family. Except — because of the fact that there is no exactly universal gate-set for quantum computation, the gates allowed may change from problem to problem. And it would seem that people remain unsure of whether to allow infinite gate-sets, so that the gates which are used in each circuit for a problem may depend on the input size.

It seems reasonable to me, in principle, to allow a unitary circuit family to use an infinite gate-set: for instance, a set in which the different gates used by the circuit on inputs of length $n$, grow as $O(n)$ rather than the scenario of $O(1)$ which is possible with (approximately) universal gate-sets. Gate-sets which scale as $O(n)$ are part of classical circuit complexity, after all. Furthermore, it's not clear to me that it should be necessary to allow a gate set of size larger than $O(n^2)$ — which would allow for a constant number of gate-sets having arity ranging from constant to the entire system. For many purposes, it may even be enough to have a gate-set of size $O(1)$ for each circuit size, but a different such set for each $n$ — so that one may describe the gate set used by the family as being $O(n)$ for the first $n$ circuit sizes.

However, allowing even a single distinct gate for each input size allows you to do strange things, even if you require that the coefficients of the gates be nicely behaved. For instance, you could allow as a gate a controlled-QFT gate $\Lambda\mathrm{QFT}$, acting on $2n$ qubits, which is defined on $\def\ket#1{|#1\rangle}\ket{m}\ket{x}$ for $m,x \in \{0,1\}^n$ by $$\begin{aligned} \Lambda\mathrm{QFT} \ket{m}\ket{x} &= \ket{m} \otimes \mathrm{QFT}_m\ket{x} \\[1ex]&= \begin{cases} \tfrac{1}{\sqrt m} \sum\limits_{k=0}^{m-1} \mathrm{e}^{2\pi i kx/m} \ket{m}\ket{k}, & \text{if $0 \leqslant x < m$}; \\[2ex] \qquad\ket{m}\ket{x}, &\text{otherwise}.\end{cases} \end{aligned}$$ This effectively allows you to simulate gates which not only depend on the input size, but on the input itself. In addition to being strange in itself, and making it potentially difficult to obtain a meaningful notion of complexity (how much work is being absorbed into the machine which describes the gates?), it would undo classic results in quantum computational complexity such as $\mathsf{EQP \subseteq LWPP}$ [Fortnow+Rogers-1999]. Admittedly, that result relies on a definition of $\EQP$ in terms of quantum Turing machines rather than circuits, so inherently depends on the gate-set of a circuit being finite; it would not be shocking to negate it, but negating it is a warning sign that we may be doing something unreasonable. It would still be nice to find a way to keep it intact.

There is a potentially more awkward problem, however, which I am less well-equipped to consider myself.

If we study $\EQP$ out of interest in theory of computation (as opposed to practical application, where $\mathsf{BQP}$ will be more relevant for the foreseeable future), it doesn't make sense to consider coefficients which are themselves only computable to finite precision. Instead we should probably consider coefficients which are expressed symbolically as algebraic numbers: that is, where each individual gate has coefficients drawn from some finite extension of $\mathbb Q$. This picture of quantum computation is preicsely what the classic results $\mathsf{BQP \subseteq PP}$, $\mathsf{EQP \subseteq LWPP}$, and $\mathsf{NQP = coC_=P}$ rely on, so I'm quite comfortable allowing the coefficients be specified abstractly and "symbolically", so that the only precision involved is the length of the representation of a polynomial of which a given coefficient is a root, or something similar.

The problem is this: completely aside from whether or not you can hide non-trivial polynomial amounts of computation in the computation of the coefficients, I worry that the linear combinations of these algebraic coefficients, arising from the matrix multiplication itself, might itself hide non-trivial amounts of work by simulating a Blum-Shub-Smale machine. I'm not very familiar with the issues involved in that, so I wonder whether allowing infinite gate-sets might be a bit of a minefield.

Question #1. What theoretical problems (as opposed to practical problems, i.e. let us not concern ourselves any more with experimental implementation than we would with the polynomial hierarchy) does one have to worry about — for bounded error as well as for exact quantum computation — if one considers infinite gate-sets allowing the simulation of complicated arithmetic over the reals?

Question #2. What are the sufficient conditions for an infinite gate set to be "benign", from a standpoint of computational complexity?

Answer 1

To answer my own question: for the purposes of exact computation, there's no need to worry about having too much computational power from linear combinations of algebraic numbers.

Details

On representations of algebraic numbers.

If the coefficients of all of the gates in a unitary circuit $U_n$ belong to a field extension $\mathbb E{:}\mathbb Q$ of finite dimension, we can represent elements of $\mathbb E$ as rational vectors of polynomial dimension by construction. Sums of these numbers are performed component-wise, and products by fixed elements of $\mathbb E$ are linear transformations of those vectors. So we may reduce the representation of this model of computation to one over the rational numbers, albeit with the property of unitarity (or for vectors, having unit $\ell_2$-norm) not being directly represented in the linear transformations.

Bounding the complexity of exact quantum computation with infinite gate sets.

For a decision problem represented as a function $P: \{0,1\}^n \to \{0,1\}$, using classic results involving uncomputation, we can suppose that the unitary circuit computes a function $$ U_n |x\rangle|0^m\rangle|0\rangle = |x\rangle|0^m\rangle|P(x)\rangle $$ for some number $\def\poly{\mathrm{poly}}m \in O(\poly(n))$ of ancillas. Being a standard basis vector, this obviously has only rational coefficients, so in the vectors representing the elements of the field $\mathbb E$ we only need to compute the component of rational contributions.

If — furthermore — the coefficients of all gates in $U_n$ can be expressed in the form $\tfrac{1}{m} \alpha$, where $m$ can be computed in polynomial time from $n$ and where $\alpha$ is a sum of algebraic integers, the standard proof that $\mathsf{EQP \subseteq LWPP}$ goes through with only simple modifications. Note that this appears to rule out the $\Lambda\mathrm{QFT}$ operator described above, for which we would have $m^2 = {(2^n)!}/{(2^{n-1})!}$, which is monstrously large.

Bounding the complexity of bounded-error quantum computation with infinite gate sets

Bounded error quantum computation with symbolically specified coefficients is slightly more worrying on the face of it, as it appears to allow unit-cost comparison of algebraic numbers with 1/3 or 2/3. Of course, the same is true for circuit families constructed from a finite gate-set; only in that case the comparisons are being made between algebraic numbers from a field-extension $\mathbb E{:}\mathbb Q$ which is of constant degree, rather than degree $D \in O(\poly(n))$ growing with the input size as in our setting.

It is clear that being able to make these comparisons allows us to save at most a polynomial amount of work, as any one coefficient of $\mathbb E$ is a $\poly(n)$-sized sum of numbers $a_j$, each of which can be computed to precision $\varepsilon$ in time $O(\poly \log(a_j) \poly \log(1/\varepsilon))$; and for deciding problems in $\mathsf{BQP}$, it suffices to consider $\varepsilon \in O(1/\poly(n))$. So any complexity which is subsumed into evaluating whether the norm-square of a coefficient is large or small will not affect any results concerning complexity classes, and actually only amounts to computing $\poly(n)$ algebraic integers numbers up to $\log(n)$ bits of precision and adding them.

An obvious solution to making sure that no complexity is hidden in the construction of the gate is to make the gate have cost greater than $1$ to use, associated to the complexity of the coefficients.

For consistency with the case of finite gate sets, we suppose that the cost of applying any gate from a gate-set of size $O(1)$ is only a constant; and so that results on complexity are robust, we want the cost of applying a gate

1. not to compound the cost of transforming many amplitudes in parallel (so that the cost of performing a single-qubit gate does not depend on whether you consider it to "act" on many qubits when you take the tensor product with the identity), and

2. to be independent of what other gates are used in the circuits (we don't assess the cost of any gate depending on whether the circuit uses more exotic gates as well).

We may therefore suppose that the cost of performing arithmetic on the amplitudes does not compound with the number of amplitudes being transformed in parallel, and that a rational linear combination (with coefficients $a_j$) of rational numbers $x_j$ may be performed effectively at a cost depending only on the complexity of specifying the coefficients $a_j$ themselves.

• Extension degree cost. For a given gate $G$, one might assign to $G$ a cost which depends on the degree $d$ of an minimum extension $\mathbb G{:}\mathbb Q$ of a field $\mathbb G \subseteq \mathbb E$ which contains the gate elements. For a "typical" field extension of $\mathbb Q$ by radicals (i.e. by the $n^{\mathrm{th}}$ roots of numbers), multiplication of an element of $\mathbb E$ by a coefficient in $\mathbb G$ would be represented as a $D \times D$ linear transformation over $\mathbb Q$, which decomposes as a tensor product of a $d \times d$ matrix with a $D/d \times D/d$ identity operation — that is: it is analogous to performing a $d \times d$ matrix to several amplitudes in parallel — it seems reasonable to me to impose a cost for $G$ which is proportional to $d^2$.

• Precision cost. To avoid ignoring any complexity associated with arithmetic involving any one of the coefficients (e.g. algebraic extensions of the form $\mathbb Q[1/{\sqrt N}]$, which is a degree two extension but where $N$ may be huge), we may take the further step of considering the coefficients of the minimal polynomial for each element of $G$ (which for ${1}/{\sqrt N}$ would be $Nx^2 - 1$). We then assign a "coefficient cost" to $G$ of $\ell = \max \log_2(|c| + 1)$, where $c$ is any one coefficient of a minimal polynomial for an element of $G$, and the maximum is taken over all such coefficients.

• Arity cost. Finally, to avoid many single-qubit gates being performed with unit cost for arbitrarily many qubits, we impose on gates $G$ with arity $k$ and which do not factor as $G' \otimes \mathbf 1$ over any bipartition a cost proportional to $k$.

We may then assign to any $k$-qubit gate $G$ the cost $d^2\ell k$, essentially accounting for any work being performed by recombination of the coefficients. In the case of the extension $\mathbb E{:}\mathbb Q$ having finite degree, all gates would then have cost $O(1)$, reducing to the usual asymptotic analysis of computations with finite gate sets. This seems to me to be a perfectly fair way to assign costs to constructions of exotic gates.

The Bottom Line

If you allow gates which depend on the input size $n$, but

• require that all gates for a given input size have coefficients which are expressible as a sum of terms $\tfrac{1}{m} \alpha$ for $\alpha$ an algebraic integer and $m$ a fixed integer computible in time $O(\poly(n))$, and

• assign to each gate $G$ a cost $d^2 \ell k$, where $d$ in effect is the degree of the extension of $\mathbb Q$ required by $G$, $\ell$ effectively measures the precision required by the extension, and $k$ is the number of qubits on which $G$ acts,

then you recover a theory of quantum computation in which all of the classic complexity results seem to hold (save the equivalence of uniform circuit families to quantum Turing machines), essentially no complexity is being hidden in the choice of gates, and which reduces to the standard theory for constant-sized gate sets. As a result, it should be safe to define $\EQP$ in terms of such a gate model — and also $\mathsf{BQP}$, though the existence of an approximately universal gate-set makes this unnecessary.