The complexity class $BQP$ is defined like so:
A language $L \subseteq \{0, 1\}^*$ is in $BQP$ if there exists a family of "polynomial time uniform quantum circuits" $\{Q_n | n \in \mathbb{N} \}$ that input $n$ qubits and output $1$ bit that outputs the correct answer (either "yes" or "no") with a probability of at least $\frac{2}{3}$
more formal definition from wikipedia
My question is this:
What "base matrices" are we choosing to form these quantum circuits.
If we just allow any $2^N \times 2^N$ matrix, then all decidable problems are in BQP, because the unitary matrices form a group.
And picking a random universal gate set seems arbitrary.
For example, it is possible that some gates can be implemented in polynomial time in some gate sets, and exponential time in other gate sets.
Let $X$ be the universal gate set of Hadamard and Toffoli. Let's say that a gate $G$ is exponential to compute with this set. If we make a new universal gate set of $X \cup \{G\}$, $G$ is now computable in constant time.
If not, what universal gate set did we set as standard, and why was it chosen?