7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$
    – Condo
    Jul 7, 2021 at 15:36

2 Answers 2

4
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ 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? $\endgroup$ Jul 2, 2021 at 9:49
  • $\begingroup$ @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 :) $\endgroup$ Jul 2, 2021 at 10:44
3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ Jul 5, 2021 at 9:07
  • $\begingroup$ @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. $\endgroup$ Jul 5, 2021 at 15:55

Your Answer

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

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