5
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ 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 $\endgroup$
    – Quantum Mechanic
    Dec 9, 2021 at 14:46
  • 2
    $\begingroup$ @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. $\endgroup$
    – Condo
    Dec 9, 2021 at 16:48
  • $\begingroup$ This may be helpful: quantumcomputing.stackexchange.com/questions/11861/… $\endgroup$
    – Martin Vesely
    Dec 10, 2021 at 9:05
  • $\begingroup$ @Condo is it true that all classical algorithms have finite length? That seems restrictive $\endgroup$
    – Quantum Mechanic
    Dec 10, 2021 at 15:47
  • 1
    $\begingroup$ 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. $\endgroup$
    – Condo
    Dec 10, 2021 at 16:32

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • 3
    $\begingroup$ 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. $\endgroup$
    – Condo
    Dec 9, 2021 at 16:32
  • $\begingroup$ 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. $\endgroup$
    – Condo
    Dec 9, 2021 at 19:52
  • 1
    $\begingroup$ @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. $\endgroup$
    – DaftWullie
    Dec 10, 2021 at 7:12
  • $\begingroup$ @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. $\endgroup$
    – Condo
    Dec 10, 2021 at 14:39
  • 1
    $\begingroup$ @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? $\endgroup$
    – DaftWullie
    Dec 10, 2021 at 14:52
3
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.