Given a random Clifford state on $L$ qubits (defined as an infinite depth Clifford circuit acting on the zero state), what depth Clifford circuit is required to approximate this state to a given accuracy $\epsilon$.

I am essentially looking for a Kitaev Solovay theorem restricted to Clifford circuits. For a Haar random unitary on $L$ qubits, it is know that the required circuit depth to approximate it to a given accuracy scales as $2^L$. Is this also the case for random Clifford unitary gates on $L$ qubits?


1 Answer 1


Clifford operations are discrete. They can't approximate arbitrary states. The state may not be close to a state reachable by Clifford operations.

There are $O(L^2)$ distinct $L$-qubit states reachable by Clifford operations. By a circuit counting argument (there's only so many ways to place two-qubits gates, and you need to be able to make all the states), you can prove most circuits need to have depth $\Omega(L / \log L)$ (assuming you have $O(L)$ ancilla qubits).

All Clifford operations (and therefore all reachable states) on $L$ qubits can be compiled into an $O(L)$ depth circuit, even if you're limited to nearest neighbor interactions on a line: https://arxiv.org/abs/1705.09176 .

So for states reachable with Cliffords the answer is either $L$, or $L / \log L$, or something in between. For other states it depends how much error you'll tolerate, since you can't make it arbitrarily small.


Your Answer

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