# types of states that can be created with a given number of entangling gates

I want to know if it is possible to say something in general about the "richness" or "complexity" of quantum states that can be created using a given number of entangling 2-qubit gates.

For example, using $$n$$ CNOTs, we can create an $$n$$ qubit GHZ state, and furthermore that we can't create it using less than $$n$$ such gates.

Trying to extend this logic, are there states that can only be created, for example, using no less than $$O(n^2)$$ 2-qubit entangling gates, and that are "more complex" than GHZ state by some suitable metric? In partcular, a metric that represents whether these states can represent for example a ground state of an interacting many body system, or something else that is of interest to compute?

The motivation for asking this question is because I am interested in understanding how many qubits and entangling gates are needed to perform a useful quantum simulation. In this paper, fig. 1, they look at spin chains simulation that scales approximately as $$n^2$$ - I wanted to know how generic this is and if there is an underlying principle.

The question seems to ask for:

• A quantum state that requires $$O(n^2)$$ entangling gates to prepare, starting from some canonical state (say the all-0's ket)
• Wherein the state so-prepared is "of interest" to prepare with a quantum computer.

Considering initially the generalized GHZ/cat state $$\frac{1}{\sqrt n}(|00\cdots 0\rangle+|11\cdots 1\rangle)$$. As stated this can be prepared from the all-0's ket $$|00\cdots 0\rangle$$ with a Hadamard gate and $$O(n)$$ CNOT gates. Note, however, that the Hadamard and CNOT gates are from the Clifford gate set. By the Gottesman-Knill theorem, there likely will not be any computational speedup with a quantum computer preparing such states.

Consider also the generalized W state - $$\frac{1}{\sqrt{n}}(|0\cdots 01\rangle + |0\cdots 010\cdots 0\rangle + |10\ldots 0\rangle)$$. A circuit to prepare this state from the canonical all-0's ket does use non-Clifford gates such as arbitrary rotation gates. An initial circuit as described here naively uses $$O(n^2)$$ such gates. However, as explained in an answer from Craig Gidney, it appears that this can be reduced to $$O(n)$$ CSWAP gates. Nonetheless the CSWAP gate is not in the Clifford gate set, which seems to suggest that the generalized W state is "more complex" to prepare than preparation of the generalized GHZ state.

We can take this analysis a bit further and ask for a simple class of generalized states on $$n$$ qubits that (1) requires $$O(n^2)$$ gates to prepare, starting from some canonical state, wherein (2) these gates are not from the Clifford gate set? The GHZ state fails on both accounts, while the W state appears to fail only on the first requirement.

A slight variation of the W state may suffice - for example, the W state is in a superposition of "one-hot" basis states; perhaps a generalized "two-hot" state requires more than $$O(n)$$ non-Clifford gates (as there are $$\frac n 2(n-1)$$ such basis vectors).

• thanks! The two-hot W state is an interesting example. Perhaps the question will be clearer if I write more explicitly what is my motivation for it - I edited the question to reflect it.
– Lior
Nov 18, 2022 at 13:44