# Formal Definition of a Quantum Circuit

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?

The first concern (allowing any $$2^N \times 2^N$$ matrix) is covered by the uniformity condition in the definition. Uniformity means that there exists a deterministic polynomial-time algorithm that, on input $$n$$, outputs a classical description of $$Q_n$$.