Given a Clifford gate acting on $n$ qubits is implemented using its generators, what is the average number of gates needed to implement a random Clifford gate as a function of $n$?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
It's $O(n^2)$ operations from various constructive decompositions (such as in "Hadamard-free circuits expose the structure of the Clifford group ").
You can prove from information theoretic bounds that there has to be at least $\Omega(n^2/ \lg n)$ gates in the worst case, because otherwise there wouldn't be enough distinct possible circuits to give a different one to each different operation. And the majority of the circuits have to be this large or else again they won't fit.
-
$\begingroup$ Thanks for the answer Craig, I really appreciate it. Can you please provide a reference for your second point: "You can prove from information theoretic bounds that there has to be at least $\Omega(n^2/ \lg n)$ gates in the worst case... And the majority of the circuits have to be this large or else again they won't fit" ? $\endgroup$ May 4 at 17:46
-
$\begingroup$ Also, I am a bit confused as to how your two points don't contradict each other... At first you say it is $O(n^2)$, but then say it is $\Omega(n^2/ \lg n)$. That means the lower bound is higher than the upper bound. $\endgroup$ May 4 at 17:58
-
$\begingroup$ @QuantumGuy123 I don't have a reference, it's just based on the size of the Clifford group for $n$ qubits and how many different $n$-qubit circuits you can make with $m$ gates. I don't know what you're talking about with the lower bound being higher than the upper bound. n^2/lg n is less than n^2. $\endgroup$ May 4 at 18:01
-
$\begingroup$ oh true. for some reason I was reading the division as multiplication...! just getting over a bout of COVID rn. Seems I still have a bit of brain fog. $\endgroup$ May 4 at 18:24
-
$\begingroup$ I would've written your answer as "there has to be at least $\Omega(n^2/ \lg n)$ gates in the best case" instead of "there has to be at least $\Omega(n^2/ \lg n)$ gates in the worst case" $\endgroup$ May 4 at 18:27