# Clifford circuit approximation to a random Clifford circuit

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?

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.