Explicit states with high $T$ count

Question

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.

Answer 1

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

Answer 2

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