Formal Definition of a Quantum Circuit

Question

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?

Answer 1

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$^[1].

And the second concern is covered by Solovay–Kitaev theorem. This theorem implies that any universal set of gates can simulate any other universal set efficiently – that is, with at most a polynomial increase in the number of gates^[2]. So, BQP class will be the same regardless of the chosen universal gate set.

• [1] John Watrous lecture notes - Lecture 22 [PDF]
• [2] Scott Aaronson lecture notes - Lecture 10 [PDF]