# Does there exists an algorithm to construct a quantum circuit given an arbitrary unitary?

Suppose there exists an algorithm that takes as input an arbitrary unitary matrix and produces as output a quantum circuit representing that matrix. Then in theory that algorithm could construct any quantum circuit. This would be quite useful.

Furthermore, since any computable algorithm may be implemented as a quantum circuit, the hypothetical circuit constructing algorithm could in principle construct any such algorithm as a quantum circuit. This seems similar, though not identical, to the idea of Turing completeness.

Intuitively it seems bizarre that such an algorithm could exist. However, I am not able to think of something that disproves this. Has such an algorithm's existence been proven/disproven?

• Why would it be bizarre that such an algorithm could exist? There's an algorithm to compute any classical computation using dominoes; surely quantum circuits can't be that much more bizarre Dec 9, 2021 at 14:46
• @QuantumMechanic it's not obvious because the set of quantum gates is the projective unitary group $PU(n)$ and essentially the question is: given a finite set of generators for $PU(n)$ give an algorithm that decomposes an arbitrary $U\in PU(n)$ into a word in the generators. Even $SU(2)$ is an infinite group, so it's not at all like the classical case where everything is finite. Dec 9, 2021 at 16:48
• This may be helpful: quantumcomputing.stackexchange.com/questions/11861/… Dec 10, 2021 at 9:05
• @Condo is it true that all classical algorithms have finite length? That seems restrictive Dec 10, 2021 at 15:47
• Sorry everyone, I have conflated the idea of synthesizing a gate out of CNOTs and single-qubit rotations and the idea of reducing any unitary into the generators of a given gate set. The former is possible and outlined in N&C, while the latter is much more difficult. Dec 10, 2021 at 16:32

• The Solovay-Kitaev algorithm is an approximation algorithm, it does not provide an exact implementation of a unitary $U$, rather it provides a close approximation $\tilde{U}$. The advantage is that this approximation has short length (with respect to the gate set) and therefore $\tilde{U}$ doesn't require an exponential amount of resources to implement. Dec 9, 2021 at 16:32
• The method outlined in Neilsen and Chuang using Gray codes outlines a way to decompose an arbitrary $n$-qubit gate into single-qubit gates and CNOTs it doesn't provide an algorithm for exactly synthesizing single-qubit rotations. Dec 9, 2021 at 19:52
There is an algorithm that goes by the name of Quantum Shannon Decomposition see the paper which allows to decompose any unitary into CNOTs and single-qubit gates. For an $$n$$-qubit unitary it produces roughly $$\frac12 4^n$$ CNOT gates which is only 2x more than the theoretical lower bound (see a related question Minimum number of 2 qubit gates to build any unitary). The algorithm is not trivial but also not very complicated and in many respects is similar to standard matrix decompositions (like cosine-sine decompositoin) applied recursively.