Getting exponential sequence of coefficients with not so many $T$-gates

Question

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

Ideas

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$:

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.

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.