1
$\begingroup$

What are the algorithms that allow to decompose any given multi qubit Clifford unitary into elementary Clifford operations (e.g. Pauli+CNOT, with no T gate)?

$\endgroup$
2
  • 1
    $\begingroup$ This may help arxiv.org/abs/quant-ph/9503016 $\endgroup$ Jun 21, 2022 at 20:48
  • $\begingroup$ BTW, note that Pauli+CNOT do not create the entire Clifford group, you need also e.g. $\sqrt{Z}$ or $H$ for this. $\endgroup$
    – JSdJ
    Jun 23, 2022 at 9:43

3 Answers 3

3
$\begingroup$

I don't know if there is a formal way to decompose a n-qubits Clifford operation with gates from {H,X,Y,Z,CNOT}, but I know a paper that uses Monte Carlo Three Search for this purpose: Automated Quantum Circuit Design with Nested Monte Carlo Tree Search

Since it can be seen as a combinatorial problem, deep Reinforcement Learning can be a way to get a decomposition of your unitary operation (the agent begins with an empty circuit and at each step he puts a gate on the circuit until he reaches the target or maximal depth allowed). I have worked on this problem during an internship and it seems quite promising.

$\endgroup$
1
$\begingroup$

There is only one method (the KAK decomposition) that is provably minimal in the number of 2-qubit gates, and it's for 2 qubit unitaries. I've found these 2 papers useful on that topic:

Methods for unitaries of more than 2 qubits are not provably minimal in the number of 2-qubit gates unfortunately. I know this is a partial answer, but I hope you find it useful.

$\endgroup$
1
  • 3
    $\begingroup$ This method is for general unitaries. It's way more complicated than needed for just Clifford gates. Also it's only for 2 qubit gates but the question is about larger gates. $\endgroup$ Jun 22, 2022 at 7:35
1
$\begingroup$

In a paper by Aaronson and Gottesman, there is a construction that uses $O(n^2/log(n))$ Clifford gates to synthesize any n-qubit Clifford circuit, and it runs in poly(n) time. See the construction in the proof of theorem 8 of https://arxiv.org/abs/quant-ph/0406196

$\endgroup$

Your Answer

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

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