Explicit states with high $T$ count

It is well known, that the Clifford $$+T$$ gate set consisting of the gates $$\lbrace H, S, CNOT, T \rbrace$$ is universal for quantum computation, that is, for any n-qubit unitary $$U:\left( \mathbb{C}^2\right)^{\otimes n} \rightarrow \left( \mathbb{C}^2\right)^{\otimes n}$$ and for every $$\epsilon >0$$, there is a unitary $$V$$ composed of gates from the Clifford $$+T$$ gate set such that $$\|U |0\rangle ^{\otimes n} - V|0\rangle ^{\otimes n}\|<\epsilon$$

Let now $$\mathcal{C} = \lbrace V |0\rangle ^{\otimes n}: V \text{ composed from Clifford }+T \text{ gates}\rbrace$$ and define the $$T$$-count $$\tau(|c\rangle )$$ of an element $$|c\rangle \in \mathcal{C}$$ as the minimal number $$r$$ such that there is a quantum circuit $$V$$ composed of arbitrarily many Clifford gates and $$r$$ $$T$$-gates such that $$|c\rangle = V |0\rangle ^{\otimes n}$$.

The $$T$$-count can be arbitrarily large: Clearly, the universality of $$\mathcal{C}$$ implies that $$\mathcal{C}$$ is infinite. But since the Clifford group is (up to prefactors of the form $$e^{i\theta}, \theta \in [0,2\pi]$$) finite, we only reach (up to prefactors) a finite number of states with a finite number of $$T$$-gates.

Now my question: Do we know explicit families of states which have high $$T$$-count? An example for what I am looking for can be found on page 18 of this paper. There, the authors show - using the stabilizer nullity as a monotone - that for the controlled $$Z$$ gates with $$n-1$$ controls $$C^nZ$$, the state $$C^nZ |+\rangle ^{\otimes n}$$ has $$T$$-count $$\Omega(n)$$ (it is well known that $$C^nZ |+\rangle ^{\otimes n}\in \mathcal{C}$$, see e.g. Nielsen Chuang). Another example would probably be $$|T\rangle^{\otimes n}$$, where $$|T\rangle = T |+\rangle$$ (and all obvious variations of this).

I wonder if there are explicit examples where the $$T$$-count scales stronger with $$n$$. For example, I would be interested in seeing an explicit example of a family of states $$|\Psi_n\rangle \in \left( \mathbb{C}^2\right)^{\otimes n}$$ such that $$\tau (|\Psi_n\rangle) = \Omega(f(n))$$ where $$f$$ is maybe superlinear or even exponential.

(Maybe an interesting related observation: One will not be able to show something like this using the stabilizer nullity, since the stabilizer nullity is always bounded by the number of qubits!)

Alternatively: As the $$T$$-count can be arbitrarily large even for one qubit unitaries by the above argument, one can of course also ask the following (stronger) variant: Can we explicitly give a family $$|\Psi_n\rangle \in \mathbb{C}^2$$ such that $$\tau(\Psi_n) > \tau(\Psi_{n-1})$$ for all $$n\in \mathbb{N}$$?

I am quite new to this part of quantum information theory, any kind of insights are welcome - and also any kind of comment on my introductory thoughts.

• In the single qubit case, it is known that short approximating words always exist for the Clifford+T gate set, in the sense that there is always a sequence of gates $S$ of length $O(\log(1/\epsilon))$ which approximate any $2\times 2$ unitary $U$ up to error $\epsilon$ (where length is the number of gate set elements). So in particular this puts an upper bound on the number of $T$ gates in any approximation in terms of $\epsilon$. Jul 7 at 15:36

Liu and Winter (http://arxiv.org/abs/2010.13817) have shown that any "reasonable" magic monotone is asymptotically bounded by $$n$$. Moreover, Haar-random pure states cluster around that value (deviation is exponentially suppressed in $$n$$).

By a standard argument (as in Beverland et al.), $$\Omega(n)$$ magic implies that we need $$\Omega(n)$$ copies of the $$T$$ gate to prepare the state. More precisely, if $$f$$ is a sub-additive magic monotone and assume that $$|c\rangle$$ can be prepared with $$t$$ $$T$$ gates. $$\Omega(n) = f(|c\rangle) \leq f(|T\rangle^{\otimes t}) \leq tf(|T\rangle).$$ Here, $$|T\rangle$$ is the magic state associated to $$T$$. Hence, $$t=\Omega(n)$$. In conclusion: any family of Haar random states will do with high probability.

Interstingly, these typical states with high magic are useless for quantum computation - in the same sense as highly entangled states are useless, too (https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.102.190501)

EDIT: I have just seen that you ask for superlinear scaling. Well, this is unclear but results from the construction of unitary designs (http://arxiv.org/abs/2002.09524) and complexity theory (http://arxiv.org/abs/1912.04297, https://arxiv.org/abs/2106.05305) suggest that a polynomial number should be sufficient (maybe even linear).

• Thanks for the answer, it's already very helpful! One question: Can you maybe explain what you mean with "...suggest that a polynomial number should be sufficient"? Isn't my argument right that even for the one qubit case, for all $k\in \mathbb{N}$, there are states in what I call $\mathcal{C}$ with T-count greater than $k$? So in particular, any scaling with number of qubits should be possible, right? Jul 2 at 9:49
• @FritzHefter Ok, I see that my statement is confusing. The exact T count can be arbitarily large, but this is also somewhat not very surprising / interesting. Almost every unitary needs super-polynomial (infinite?) circuit depth and the same holds for dense covers such as the group generated by Clifford + T. It is more interesting (and difficult) to consider approximate synthesis and ask how many T gates you need to implement the unitary up to some error. My comment is more in this direction, but also very hand-waivy :) Jul 2 at 10:44

I wonder if there are explicit examples where the T-count scales stronger with n. [...] maybe superlinear or even exponential.

Here's an existence proof of an $$n$$ qubit magic state with a T count of $$\Theta(2^{n/4})$$, based on caching QROM reads. It takes $$\Theta(2^{n/4})$$ T gates to prepare the cached-QROM state, and also you can consume the cached-QROM state to save $$\Theta(2^{n/4})$$ T gates on the cost of performing a QROM read.

A QROM circuit looks up classical data indexed by a quantum address register. It applies the transformation $$\sum_k |k\rangle \rightarrow |k,\text{DATA}[k]\rangle$$ where $$k$$ is the address and $$\text{DATA}$$ is the classical data. You can show by circuit counting arguments that the family of QROM circuits where $$|k\rangle$$ is $$a$$ qubits long, and $$\text{DATA}$$ has entries that are $$m$$ bits long, has circuits with a T count of $$\Theta(\sqrt{2^a m})$$. I say $$\Theta$$ instead of $$\Omega$$ because there are known constructions that achieve this asymptotic T count.

Suppose that when you cash out the asymptotic bounds into actual bounds, that the constant factor behind the asymptotic notation is $$c$$. Caution: in the rest of this argument I'll be assuming that the T count is exactly $$c \sqrt{2^a m}$$. Of course the T count is going to bounce around a bit relative to that line, e.g. from rounding effects or certain special sizes like powers of 2 being unusually easy, but ultimately this is irrelevant to the underlying idea behind the argument.

Anyways. Let $$a=m=n/2$$, and let $$\text{HARD_DATA}$$ be the read-only data table that results in the QROM circuit with the worst cost. Let

$$Q = \text{QROM}_{a,m,\text{HARD_DATA}}$$

be that worst case QROM operation. For sufficiently large $$n$$, it costs at least $$T \geq c \sqrt{2^a m} = c \sqrt{2^{n/2} n/2}$$.

Now suppose that I give you the magic state

$$|M\rangle = Q |+\rangle^{\otimes a} |0\rangle^{\otimes m}$$

You can use that magic state to perform $$Q$$ via gate teleportation. The gate teleportation will require a probabilistic fixup, but you can show that the fixup is always a QROM circuit from the family $$\text{QROM}_{a-1,m,*}$$ (for the same reason that the corrections to teleporting through a $$C^nZ$$ gate is made up of $$C^{n-1}Z$$ gates). By assumption we can upper bound the T cost of the gate teleportation, not counting the production of the magic state, to be at most $$T^\prime \leq d \sqrt{2^{n/2-1} n/2} = \frac{c}{\sqrt{2}} \sqrt{2^{n/2} (n/2)}$$.

The cost of preparing $$|M\rangle$$ has to be at least $$T - T^\prime$$. Otherwise we could apply $$Q$$ cheaper than we assumed possible by preparing $$|M\rangle$$ and teleporting through it.

$$T - T^\prime \geq c \sqrt{2^{n/2} n/2} - \frac{c}{\sqrt{2}} \sqrt{2^{n/2} (n/2)} = \left(1 - \frac{1}{\sqrt{2}}\right) c \sqrt{2^{n/2} n/2}$$

Note that $$1 - \frac{1}{\sqrt{2}} \approx 0.29 > 0$$. So the T cost of preparing $$|M\rangle$$ (and the T savings from having an $$|M\rangle$$) is at least $$0.29 c \sqrt{2^{n/2} n/2} \in \Omega\left(\sqrt{2^{n/2} n/2}\right) \subset \Omega(2^{n/4})$$.

• Thanks for your answer! I must admit that I never heard of QROM circuits before. How I understand it: From the theory of QROM circuits we know there are circuits on a+m qubits with T-Count exponential in a (can you give me a reference where I can read about counting arguments?) Then you say that you can use $\mathcal{Q} |+>^a |0>^m$ to apply the circuit with a bounded number of $T$-gates (Is this the same idea as applying a $T$ gate by using only stabilizer operations and $T|+>$ as a resource state? I don't really get how you derive the upper bound on $T'$, could you maybe say more about that? Jul 5 at 9:07
• @FritzHefter I think the paper I linked for the QROM construction also has a proof of the lower bound. Theirs might even apply for approximations, instead of only exact circuits. Jul 5 at 15:55