Let $\Psi \in (\mathbb{C}^2)^{\otimes n}$ be a $n$-qubit quantum state. In the computational basis, we can write $\Psi$ as $$\Psi = \sum_{(i_1, \dots, i_n) \in \mathbb{F}_2^n} \Psi_{i_1, \dots, i_n} |i_1 \dots i_n \rangle $$ where $\mathbb{F}_2 = \lbrace 0,1 \rbrace$ is the field with two elements. For a natural number $p$, we say that $\Psi$ has a length-$p$ exponentially increasing coefficient sequence if there are $x_1, \dots , x_p \in \mathbb{F}_2^n$ such that $\Psi_{x_1} \neq 0$ and for all $i = 1, \dots , p-1$, $$2\cdot|\Psi_{x_i}| \leq |\Psi_{x_{i+1}}|$$

Write $l(\Psi)$ for the largest $p$ such that $\Psi$ has a length-$p$ exponentially increasing coefficient sequence.

For example, the unnormalised state $\psi = |000\rangle + |001\rangle + 3\cdot |010\rangle + 9 \cdot |100 \rangle$ has $l(\psi) = 3$.

Recall that the $T$-count, denoted $\tau(\Psi)$, of a state $\Psi$ is the minimum number of $T$-gates needed in a circuit that creates $\Psi$ from $|0\rangle$ using Clifford $+T$ gates, arbitrarily many ancilla qubits, and post-selective Pauli measurements on those ancillas. I want to construct a set of states with small $T$-count and a large exponentially-increasing sequence.

It is not difficult to construct a set of states $\Psi_n \in (\mathbb{C}^2)^{\otimes n}$ with $\frac{l(\Psi_n)}{\tau(\Psi_n)}=\Omega(1)$. For example, the state $|H\rangle ^{\otimes n}$, where $|H \rangle= |0\rangle+ (\sqrt{2}-1)|1\rangle$, has $\tau(|H \rangle)=n$ and $l(|H\rangle)=\Omega(n)$.

Question: Can we find a sequence of states $\Psi_n \in (\mathbb{C}^2)^{\otimes n}$ such that the quotient $\frac{l(\Psi_n)}{\tau(\Psi_n)}$ grows with $n$? Ideally, we would like it to grow superlogarithmically in $n$.


Note that a circuit composed only of Clifford gates will output a state whose non-zero coordinates all have the same absolute value, so the $T$ gates are somehow "responsible" for creating the exponentially increasing sequence.

Here is another example of a sequence of states for which the quotient is constant in $n$. Recall that we can implement the multi-controlled $X$ gate $C^nNOT$ using $\mathcal{O}(n)$ many $T$ gates (and actually also $\Omega(n)$ many, see proposition 4.1 of this paper). Note that we can do the following trick (which I took from this paper): Start with the three qubit state $|000\rangle^{\otimes 3}$ and apply $H \otimes H \otimes \text{id}$. Then, apply a multi-controlled NOT gate where the first two qubits are the controls. This will leave our whole system (up to normalisation) in state $$\sum_{x_1, x_2, x_3 \in \mathbb{F}_2} |x_1 x_2 \rangle |x_1 \cdot x_2 \rangle$$ If we now measure the first two qubits in $|+\rangle, |-\rangle$ basis and apply $X$ on the last qubit, we get $|0\rangle + 3 \cdot |1 \rangle $ up to normalisation.

With that, we can build quantum circuits $\mathcal{C}_n$ with $2n$ ancilla qubits which look like this here for $n = 3$:

enter image description here

The measurements stand for measurements in $|+\rangle, |-\rangle$ basis post selecting outcome $|+\rangle$. Ignoring the ancillas, the following will happen on the three qubits in the three steps applying the multi controlled NOT gates: $$ |000\rangle \mapsto |000\rangle + 3 |100\rangle \mapsto |000\rangle + 3 |100\rangle + 9 |110\rangle \mapsto |000\rangle + 3 |100\rangle + 9 |110\rangle + 27 |111\rangle$$

It's clear that this construction generalises: On $n$ qubits we can create a state $\Psi_n$ with an exponentially increasing coefficient sequence of size $ n + 1$ using $2n$ ancilla qubits and $n$ multi controlled NOT gates with 3 controls, giving a $T$-count $\mathcal{O}(n)$, that is, we again have $\frac{l(\Psi_n)}{\tau(n)} = \Omega(1)$.

I would be happy to hear if someone has an idea of other tricks which are similar to the multi controlled NOT gate which I can use to build up circuits creating these exponentially increasing sequences as output.

  • $\begingroup$ Could you write down python code that takes a list of computational basis amplitudes and computes the length you're talking about? It's not clear to me exactly what sorts of gaps are allowed. Is it basically that you can discard anything from the start of the list, and the end of the list, but only zeroes can be discarded from the middle? And you need to be left with a long list of exponentially growing values? Or can I also discard arbitrary values from the middle? $\endgroup$ Jul 13, 2021 at 15:44
  • $\begingroup$ @CraigGidney You are just looking for a subset of the set of computational basis amplitudes that can be ordered into an exponentially increasing sequence. So the state $4 |{000}\rangle+1 |{001}\rangle + 2 |{100}\rangle$ would have an exponentially increasing sequence of length 3. $\endgroup$
    – Ben
    Jul 13, 2021 at 22:18

1 Answer 1


Suppose you have a chain of length $n$. Then the smallest amplitude in that chain is no larger than $2^{-n}$. But this implies the operations you are applying have a maximum error term $\epsilon$ that is smaller than that, since otherwise they would overwhelm that amplitude. And approximating arbitrary rotations to within $\epsilon$ requires $\Omega(\lg(1/\epsilon))$ T gates. This suggests the T cost of such a state has to be at least $\Omega(n)$, unless you can find a series of easily-approximated rotations whose structure allows you to avoid the bound on arbitrary rotations.

For example, suppose you start with $n$ qubits $q_0, ..., q_{n-1}$ each in the $|0\rangle$ state. You define $P(d) = R_y(2 \arcsin(\sqrt{1/(d+1)}))$. Then you apply the operation $P(2^{2^k})$ to qubit $q_k$ for each $k$ from $0$ to $k-1$. The system state is now proportional to $\sum_{v=0}^{2^n-1} 2^{v} |v\rangle$... but some of those operations had ridiculously tiny angles. You'd need a linear number of T gates to approximate them well enough to distinguish them from zero. So you don't get below linear with that idea.

I'm not sure how to take this vague "precision seems too high" idea and turn it into a proper proof, but at the very least it's an interesting obstacle you have to bypass for a solution.

Of course in practice this is all totally irrelevant. Amplitudes that are $2^{2^{10}}$ times smaller than other amplitudes in the system are never ever going to matter observationally. So in practice you'd just approximate the whole thing ridiculously well by doing the first 10 rotations, skip the rest, and call it done.


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.