2
$\begingroup$

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

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
6
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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