$\sf BQP$ and general $\mathrm{SU}(2^n)$ gates

Question

In his lecture on quantum computing, Scott Aaronson describes polynomial-size quantum circuits,

Now, once we fix a universal set (any universal set) of quantum gates, we'll be interested in those circuits consisting of at most p(n) gates from our set, where p is a polynomial, and n is the number of bits of the problem instance we want to solve. We call these the polynomial-size quantum circuits.

and then using this goes on to give a practical definition of $\sf BQP$:

$\sf BQP$ is the class of languages $L\subseteq\{0, 1\}^*$ for which there exists a uniform family of polynomial-size quantum circuits, $\{C_n\}$, such that for all $x\in\{0, 1\}^n$:

• If $x\in L$ then $C_n$ accepts input $|x\rangle|0\cdots0\rangle$ with probability at least 2/3.
• If $x\notin L$ then $C_n$ accepts input $|x\rangle|0\cdots0\rangle$ with probability at most 1/3.

Now, take $G$ to be any standard universal gate set (e.g. the Clifford+$\rm T$ set), and let $L$ be a language that can be computed on $n$ qubits only by using (polynomially many copies of) some general $SU(2^n)$ gate $\rm U$, whose decomposition requires exponentially (in $n$) many gates from the set $G$. Seemingly $L\notin\sf BQP$ as the circuit implementing $\rm U$ is not a polynomial circuit.

Then, let $G'=G\cup\{\rm U\}$. Clearly, $G'$ is still a universal gate set. However, computing $L$ requires polynomially many gates from $G'$, which would indicate $L\in\sf BQP$.

This seems like a contradiction. Or more profoundly, the definition of $\sf BQP$ seems to depend on the choice of the gate set. What exactly is going wrong here? And is $L$ an element of $\sf BQP$ or not?

Answer 1

I think the issue here is that you've got to be careful with families of circuits. If you're picking a single fixed gate from $SU(2^k)$ for some $k$, then that doesn't necessarily help you with $L$ for $n>k$.

On the other hand, if you implicitly assumed that you had the circuit from $SU(2^n)$ for all $n$, then you're in contradiction with the definition of the universal set (or should be; the notion isn't defined very carefully): that the set be finite (or, at least, that's the easiest clarification, even if it's not quite true. You could still allow an infinite set of gates if it's, for example, single qubit gates depending on a continuous parameter).