What is the minimal set of gates to transpile any quantum circuit to minimal depth?

Question

Suppose I am given a universal set of quantum gates $S_u$ (e.g. the single-qubit rotation gate $U$ and the controlled-not gate $CX$). This is known to be universal, so any quantum circuit can be decomposed in a sequence of operations $\in S_u$. However, this process of compiling/transpiling the circuit can in general raise the depth of the original circuit.

So here is my question: is it possible to extend the set $S_u$ in order to transpile any kind of quantum circuit to its corresponding minimal-depth version? Of course, adding more and more gates to the set will possibly reduce the circuit depth but what I want is the "minimal" $S_u^*$, so that adding more gates to it will not reduce the depth anymore.

EDIT:
To be more clear about what I really need to do, consider the following example: suppose we are given the circuit $SWAP_{0,1}$ (single gate, depth=1) and the universal set of gates $S_u = \left\{U, CX\right\}$. Of course, we know that any quantum circuit can be transpiled by a proper sequence of gates $\in S_u$. However, $SWAP_{0,1}$ would be transformed into $CX_{0,1} \cdot CX_{1,0} \cdot CX_{0,1}$, which is a depth=3 circuit. So, in this trivial case, I can extend my set to $S_u = \left\{U, CX, SWAP\right\}$ in order to be sure that transpiling the circuit will lead again to depth=1.

In general, what I want is an extended (but "minimal") universal set $S_u^*$ that I can use to transpile any given quantum circuit without making it deeper (or better, making it as shallow as possible).

Answer 1

Given any arbitrary one-qubit gate you can only approximately decompose it into a product of gates from a finite universal basis gate set $\mathcal{S}$.

In other words, if the basis gate set $\mathcal{S}$ is finite, then you can't exactly decompose any arbitrary gate.

The depth of the circuit will grow depending on the desired error of approximation. The results from the Solovay-Kitaev theorem state that for an arbitrary single-qubit gate it is possible to produce a sequence of $O(\log^{c}(1/\epsilon))$ quantum gates which is guaranteed to approximate the desired quantum gate to an accuracy within $\epsilon > 0$. The standard basis set is usually Clifford + T, in particular, we can get away with the universal gate set made out of only 4 gates, $\mathcal{S} = \{S, T, H, CNOT\}$.

Clearly, if you include any one-qubit parametrized gate like $U(\theta, \phi, \gamma)$ into $\mathcal{S}$, then the universal set $\mathcal{S}$ is not finite anymore. It is not even countable. This is because the parameters $\theta, \phi, \gamma \in \mathbb{R}$ take on uncountably many values. So your set $\mathcal{S}$ becomes uncountably infinite. On the other hand, you can extend $\mathcal{S}$ by adding gates like $Z$ or a finite sequence $\{RZ(\theta_i)\}_{i=1}^m$. That would make $\mathcal{S}$ larger, but give an opportunity to shorten the approximating sequence. The tradeoff would be a computational burden. Most importantly, in general, it will not drastically improve the asymptotic behaviour of sequence length.

Of course, if your particular circuit consists of specific gates, then you can by hand create a finite generator set $G$ which will generate all the gates in your particular circuit. However, such a generator will not be able to exactly decompose any other arbitrary gate which was not part of your original circuit.

Answer 2

I'm still not sure that this question is well posed. Imagine I have some set of gates that I can implement in a single step (this may be a finite set, but the argument still follows if it's a continuous set). But also imagine that there exists a two-qubit gate which is not in that set. Then there can always be a circuit that calls for that two-qubit gate. So, either you build it out of your existing gates (which requires at least two gates by definition), or you add that gate to your set. Continue in this way, and your set $S$ is just the set of all two-qubit gates.

---

By way of an example, think of the Quantum Fourier Transform. This contains gates controlled-$R_Z(\theta)$ for values of $\theta$ down to $2\pi/2^k$ for some $k$ (that increases as you increase the number of qubits you're acting on). Each of these gates for all $k$ must be added to your set $S$.

Answer 3

This is analogous to the classical problem of determining which gates from a standard cell library should best be used to realize a particular boolean function. The short answer is that it's problem-specific but even with a more formal definition the problem is (probably) NP-complete.

One of the first things that a computer engineer learns is that the NAND gate (or the NOR gate) alone is sufficient to realize any particular boolean function. These gates require four (CMOS) transistors - two PFET's and two NFET's. The NOT gate is simply achieved by shorting the two inputs of the NAND gate together - but our computer engineer would be unlikely to choose a four-transistor NAND gate when she wants a simple NOT gate, as a NOT gate only needs two CMOS transistors (one pullup and one pulldown).

Even more, our computer engineer might see that her circuit uses a lot of AND-OR-INVERT (AOI) gates. She would be unlikely to build these AOI gates out of NANDs, NORs, and inverters as this costs 10 transistors; instead, she could simplify the same gate with only 6 transistors. So it might make sense to have the AOI gate in her library as well.

Deciding which kinds of gates to add into her library will be highly dependent on the specific boolean function she wishes to realize. For example if the boolean function is monotonic, then she might not need any NOT gates at all. But picking out the specific set of gates to choose, and minimizing thereafter, are well-known NP-complete problems.

Quantum mechanically, we have a similar problem, with a significant difference being that there is a continuum of gates to choose from - but this is resolved with appeal to comments about polynomial precision.