Clifford circuit approximation to a random Clifford circuit

Question

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?

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.