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?

Reason for asking

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.


1 Answer 1


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).

  • $\begingroup$ 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. $\endgroup$
    – Lior
    Nov 18, 2022 at 13:44

Your Answer

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

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