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)?
2
-
1$\begingroup$ This may help arxiv.org/abs/quant-ph/9503016 $\endgroup$– Martin VeselyJun 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$– JSdJJun 23, 2022 at 9:43
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
1
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.
-
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
$\begingroup$
$\endgroup$
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
