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

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

• Are you allowing this set $S_u$ contain parameterized gates, e.g. $R_x(\theta)$ for any choice of $\theta$? Or do you restrict it to a finite/discrete set of gates? Feb 10 at 16:51
• Let's say that $S_u$ can contain any kind of gates (including parameterized gates) acting at most on 2 qubits. So even controlled-$U(\theta, \phi, \lambda)$ is allowed for any $\theta$, $\phi$, $\lambda$ value Feb 10 at 18:06
• So the set of with a single universal 2 qubit (with any number of parameters) unitary gate will be a valid set? Feb 10 at 21:45
• Yes.. But it should be a gate defined in the Qiskit library (or any other software), otherwise the transpilation would not be practically feasible Feb 10 at 21:51

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.

• Thank you for the answer! It is very helpful and I put my upvote. Of course you are right: if I include any parametrized gate even with one single parameter $\theta \in \mathbb{R}$, then I would already have an uncountable infinite set. However, my problem is more "empirical": I edited my original question trying to be more clear and specific Feb 11 at 14:39

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

• I'm not sure I got what you mean... I would say that, in order to transpile to minimal depth a circuit containing controlled-$R_Z(\theta)$ gates, I just need to pass basis_gates=['crz'] to the Qiskit transpile function (it will work for any $\theta$). What I want is the minimal set basis_gates able to transpile any circuit to minimal depth (for example, the set containing the 'u' gate only, would do the job if the given circuit contained one-qubit gates only..) Feb 13 at 14:45
• so are you counting ['crz'] as 1 gate in your enumeration of the size of the basis set? Feb 13 at 15:25
• Yes I am! I know it is actually an infinite set because $\theta$ is a continuous parameter but, in the context of quantum simulation, the application of a controlled-$R_Z(\theta)$ operation on a quantum statevector is actually implemented as a multiplication by a single (parameterized) unitary matrix Feb 13 at 15:48
• So how are you dividing up what counts as 1 "gate"? Is it just "number of calls required in qiskit"? Feb 13 at 15:54
• Yes, Qiskit or any other software having a "finite" set of already implemented gates to pick from. Probably I should have been more clean about this in my question and maybe this is why the question sounds as not-well posed.. Sorry about that Feb 13 at 16:02

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.

• Thanks for your help! So, I guess that there is no way to build such a "minimal" universal set of gates, given any quantum circuit.. Right? Feb 13 at 17:25
• No “easy” way I don’t think. You could always build a huge $n$-input $n$-output gate for your particular circuit. But I don’t think that’s what you want. Feb 13 at 17:43