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?


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.