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,196
  • 7
  • 31
treks2448
  • 71
  • 1

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
  • 3,169
  • 2
  • 10
  • 36
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,725
  • 6
  • 22