# What is the average amount of gates needed to implement a random Clifford gate?

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$$?

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.
• 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" ? May 4 at 17:46
• 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. May 4 at 17:58
• @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. May 4 at 18:01
• 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" May 4 at 18:27