7

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?

Condo
  • 2,008
  • 6
  • 31
treks2448
  • 71
  • 1
  • 1
    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 – Quantum Mechanic Dec 09 '21 at 14:46
  • 2
    @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. – Condo Dec 09 '21 at 16:48
  • This may be helpful: https://quantumcomputing.stackexchange.com/questions/11861/how-to-approximate-rx-ry-and-rz-gates – Martin Vesely Dec 10 '21 at 09:05
  • @Condo is it true that all classical algorithms have finite length? That seems restrictive – Quantum Mechanic Dec 10 '21 at 15:47
  • @QuantumMechanic I think it depends on your definition of algorithm. My point is that given a gate $g$ and a finite gate set $S$ the Turing machine that enumerates over all gate combinations $\hat{g}$ from the gate set and accepts if $\hat{g}=g$ is not guaranteed to halt in a finite number of steps. – Condo Dec 10 '21 at 16:10
  • 1
    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. – Condo Dec 10 '21 at 16:32

2 Answers2

4

I think there exist and the problem can be understood in an easier way. The problem is actually how to implement an arbitrary unitary gate, which has already been written into the book of Nielsen and Chuang(in chap 4.5, universal quantum gates). The content I mentioned in the link will tell you how to construct an arbitrary unitary gate with some fundamental gates, just resemble how a classical computer can work with only some basic logical gates like OR, NOT, AND. And there also exist some other algorithms like Solovay-Kitaev's algorithm to decompose a SU(2) unitary into some fundamental gates.

narip
  • 2,964
  • 2
  • 9
  • 32
  • 3
    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. – Condo Dec 09 '21 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. – Condo Dec 09 '21 at 19:52
  • 1
    @Condo As far as I can see in the question, there's no restriction preventing the use of arbitrary single qubit gates. These certainly exist at a physical level. – DaftWullie Dec 10 '21 at 07:12
  • @DaftWullie My apologies, I did not intend to imply that one cannot synthesize arbitrary single-qubit rotations, I believe that this is possible. Rather, my point is that starting from a fixed finite set of rotations, there is no method outlined in N&C to reduce an arbitrary rotation into a product of the fixed set of rotations. – Condo Dec 10 '21 at 14:39
  • 1
    @Condo Sure, I see that. But my question is what's the relevance of restricting to a finite gate set in the context of the question? – DaftWullie Dec 10 '21 at 14:52
  • @DaftWullie that is a valid point! I guess I got caught up in the idea that we want to compile circuits from a certain gate set, which is practical from a software standpoint. I agree, that I have overlooked the fact that one could always try and synthesize the exact single-qubit rotations required in say the CS decomposition of a unitary. – Condo Dec 10 '21 at 16:21
4

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.

Nikita Nemkov
  • 1,605
  • 5
  • 18