<p>Here is a proof that $R(W_n) \in \Omega(\sqrt[4]{n})$.</p>

<p>Given a $W_n$ state, it is possible to create $\lg n$ T states with Clifford operations and a single additional T gate. Basically:</p>

<ol>
<li>Xor together all the qubit's whose binary index has an odd number of 1s, apply a T gate to that xor'd value, then unxor.</li>
<li>Apply an S gate to every qubit whose binary index has a number of 1s that's 2 or 3 more than a multiple of 4.</li>
<li>Apply a Z gate to every qubit whose binary index has a number of 1s that's 4, 5, 6, or 7 more than a multiple of 8.</li>
<li>Compress the unary $W_n$ state down into a binary register.</li>
</ol>

<p>Here's an <a href="http://algassert.com/quirk#circuit=%7B%22cols%22%3A%5B%5B%22H%22%5D%2C%5B%22%E2%97%A6%22%2C%22X%22%5D%2C%5B1%2C%22Swap%22%2C%22Swap%22%5D%2C%5B%22~e6am%22%2C1%2C%22~e6am%22%5D%2C%5B1%2C%22Swap%22%2C1%2C1%2C%22Swap%22%5D%2C%5B1%2C1%2C1%2C%22Swap%22%2C1%2C1%2C%22Swap%22%5D%2C%5B%22~e6am%22%2C1%2C%22~e6am%22%2C1%2C%22~e6am%22%2C1%2C%22~e6am%22%5D%2C%5B1%2C%22Z%22%2C%22Z%22%2C1%2C%22Z%22%2C1%2C1%2C%22%E2%8A%96%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C1%2C1%2C%22Z%5E%C2%BC%22%5D%2C%5B1%2C%22Z%22%2C%22Z%22%2C1%2C%22Z%22%2C1%2C1%2C%22%E2%8A%96%22%5D%2C%5B1%2C1%2C1%2C%22Z%5E%C2%BD%22%2C1%2C%22Z%5E%C2%BD%22%2C%22Z%5E%C2%BD%22%2C%22Z%5E%C2%BD%22%5D%2C%5B%22%5E%3DA4%22%2C1%2C1%2C1%2C%22inputA4%22%5D%2C%5B1%2C1%2C1%2C1%2C%22%E2%8A%96%22%2C%22Z%22%2C%22Z%22%2C%22Z%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C%22H%22%2C%22H%22%2C%22H%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C%22Measure%22%2C%22Measure%22%2C%22Measure%22%5D%2C%5B1%2C%22Z%22%2C1%2C1%2C%22%E2%80%A2%22%2C%22%E2%80%A2%22%5D%2C%5B1%2C1%2C%22Z%22%2C1%2C%22%E2%80%A2%22%2C1%2C%22%E2%80%A2%22%5D%2C%5B1%2C1%2C1%2C%22Z%22%2C%22%E2%80%A2%22%2C1%2C1%2C%22%E2%80%A2%22%5D%2C%5B%22%5E%3DA2%22%2C1%2C%22inputA2%22%5D%2C%5B1%2C1%2C%22%E2%8A%96%22%2C%22Z%22%5D%2C%5B1%2C1%2C1%2C%22H%22%5D%2C%5B1%2C1%2C1%2C%22Measure%22%5D%2C%5B1%2C%22Z%22%2C%22%E2%80%A2%22%2C%22%E2%80%A2%22%5D%2C%5B%22%5E%3DA1%22%2C%22inputA1%22%2C1%2C%22%3C%3C2%22%5D%2C%5B%22%3E%3E4%22%5D%2C%5B%22Amps1%22%2C%22Amps1%22%2C%22Amps1%22%5D%5D%2C%22gates%22%3A%5B%7B%22id%22%3A%22~e6am%22%2C%22name%22%3A%22Spr%22%2C%22circuit%22%3A%7B%22cols%22%3A%5B%5B%22%E2%80%A2%22%2C%22H%22%5D%2C%5B%22X%22%2C%22%E2%80%A2%22%5D%5D%7D%7D%5D%7D" rel="nofollow noreferrer">example circuit turning $W_8$ into 3 $|T\rangle$ states</a>:</p>

<p><a href="https://i.sstatic.net/GN5Ew.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/GN5Ew.png" alt="W_8 to 3 T"></a></p>

<p>I also tested <a href="http://algassert.com/quirk#circuit=%7B%22cols%22%3A%5B%5B%22H%22%5D%2C%5B%22%E2%97%A6%22%2C%22X%22%5D%2C%5B1%2C%22Swap%22%2C%22Swap%22%5D%2C%5B%22~e6am%22%2C1%2C%22~e6am%22%5D%2C%5B1%2C%22Swap%22%2C1%2C1%2C%22Swap%22%5D%2C%5B1%2C1%2C1%2C%22Swap%22%2C1%2C1%2C%22Swap%22%5D%2C%5B%22~e6am%22%2C1%2C%22~e6am%22%2C1%2C%22~e6am%22%2C1%2C%22~e6am%22%5D%2C%5B1%2C%22Swap%22%2C1%2C1%2C1%2C1%2C1%2C1%2C%22Swap%22%5D%2C%5B1%2C1%2C1%2C%22Swap%22%2C1%2C1%2C1%2C1%2C1%2C1%2C%22Swap%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C%22Swap%22%2C1%2C1%2C1%2C1%2C1%2C1%2C%22Swap%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C1%2C1%2C%22Swap%22%2C1%2C1%2C1%2C1%2C1%2C1%2C%22Swap%22%5D%2C%5B%22~e6am%22%2C1%2C%22~e6am%22%2C1%2C%22~e6am%22%2C1%2C%22~e6am%22%2C1%2C%22~e6am%22%2C1%2C%22~e6am%22%2C1%2C%22~e6am%22%2C1%2C%22~e6am%22%5D%2C%5B%22%E2%80%A6%22%5D%2C%5B1%2C%22Z%22%2C%22Z%22%2C1%2C%22Z%22%2C1%2C1%2C%22Z%22%2C%22Z%22%2C1%2C1%2C%22Z%22%2C1%2C%22Z%22%2C%22%E2%8A%96%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C1%2C1%2C1%2C1%2C1%2C1%2C1%2C1%2C1%2C%22Z%5E%C2%BC%22%5D%2C%5B1%2C%22Z%22%2C%22Z%22%2C1%2C%22Z%22%2C1%2C1%2C%22Z%22%2C%22Z%22%2C1%2C1%2C%22Z%22%2C1%2C%22Z%22%2C%22%E2%8A%96%22%5D%2C%5B1%2C1%2C1%2C%22Z%5E%C2%BD%22%2C1%2C%22Z%5E%C2%BD%22%2C%22Z%5E%C2%BD%22%2C%22Z%5E%C2%BD%22%2C1%2C%22Z%5E%C2%BD%22%2C%22Z%5E%C2%BD%22%2C%22Z%5E%C2%BD%22%2C%22Z%5E%C2%BD%22%2C%22Z%5E%C2%BD%22%2C%22Z%5E%C2%BD%22%2C%22Z%22%5D%2C%5B%22%5E%3DA8%22%2C1%2C1%2C1%2C1%2C1%2C1%2C1%2C%22inputA8%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C1%2C1%2C1%2C%22%E2%8A%96%22%2C%22Z%22%2C%22Z%22%2C%22Z%22%2C%22Z%22%2C%22Z%22%2C%22Z%22%2C%22Z%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C1%2C1%2C1%2C1%2C%22H%22%2C%22H%22%2C%22H%22%2C%22H%22%2C%22H%22%2C%22H%22%2C%22H%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C1%2C1%2C1%2C1%2C%22Measure%22%2C%22Measure%22%2C%22Measure%22%2C%22Measure%22%2C%22Measure%22%2C%22Measure%22%2C%22Measure%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C1%2C1%2C%22%E2%80%A2%22%2C%22Z%22%2C1%2C1%2C1%2C1%2C1%2C1%2C%22%E2%80%A2%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C1%2C%22%E2%80%A2%22%2C1%2C%22Z%22%2C1%2C1%2C1%2C1%2C1%2C%22%E2%80%A2%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C%22%E2%80%A2%22%2C1%2C1%2C%22Z%22%2C1%2C1%2C1%2C1%2C%22%E2%80%A2%22%5D%2C%5B1%2C1%2C1%2C1%2C%22%E2%80%A2%22%2C1%2C1%2C1%2C%22Z%22%2C1%2C1%2C1%2C%22%E2%80%A2%22%5D%2C%5B1%2C1%2C1%2C%22%E2%80%A2%22%2C1%2C1%2C1%2C1%2C%22Z%22%2C1%2C1%2C%22%E2%80%A2%22%5D%2C%5B1%2C1%2C%22%E2%80%A2%22%2C1%2C1%2C1%2C1%2C1%2C%22Z%22%2C1%2C%22%E2%80%A2%22%5D%2C%5B1%2C%22%E2%80%A2%22%2C1%2C1%2C1%2C1%2C1%2C1%2C%22Z%22%2C%22%E2%80%A2%22%5D%2C%5B%22%5E%3DA4%22%2C1%2C1%2C1%2C%22inputA4%22%5D%2C%5B1%2C1%2C1%2C1%2C%22%E2%8A%96%22%2C%22Z%22%2C%22Z%22%2C%22Z%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C%22H%22%2C%22H%22%2C%22H%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C%22Measure%22%2C%22Measure%22%2C%22Measure%22%5D%2C%5B1%2C1%2C1%2C%22%E2%80%A2%22%2C%22Z%22%2C1%2C1%2C%22%E2%80%A2%22%5D%2C%5B1%2C1%2C%22%E2%80%A2%22%2C1%2C%22Z%22%2C1%2C%22%E2%80%A2%22%5D%2C%5B1%2C%22%E2%80%A2%22%2C1%2C1%2C%22Z%22%2C%22%E2%80%A2%22%5D%2C%5B%22%5E%3DA2%22%2C1%2C%22inputA2%22%5D%2C%5B1%2C1%2C%22%E2%8A%96%22%2C%22Z%22%5D%2C%5B1%2C1%2C1%2C%22H%22%5D%2C%5B1%2C1%2C1%2C%22Measure%22%5D%2C%5B1%2C%22%E2%80%A2%22%2C%22Z%22%2C%22%E2%80%A2%22%5D%2C%5B%22%5E%3DA1%22%2C%22inputA1%22%2C1%2C%22%3C%3C2%22%5D%2C%5B1%2C1%2C1%2C1%2C%22%3C%3C5%22%5D%2C%5B%22%3E%3E5%22%5D%2C%5B%22Amps1%22%2C%22Amps1%22%2C%22Amps1%22%2C%22Amps1%22%5D%5D%2C%22gates%22%3A%5B%7B%22id%22%3A%22~e6am%22%2C%22name%22%3A%22Spr%22%2C%22circuit%22%3A%7B%22cols%22%3A%5B%5B%22%E2%80%A2%22%2C%22H%22%5D%2C%5B%22X%22%2C%22%E2%80%A2%22%5D%5D%7D%7D%5D%7D" rel="nofollow noreferrer">turning $W_{16}$ into 4 $|T\rangle$ states</a>.</p>

<p>We can produce $\lg n$ T states from a $W_n$ state and a single $T$ state. It must always be the case that an output's robustness of magic is less than or equal than the input's. Therefore:</p>

<p>$$R(W_n) \cdot R(T) \geq R(W_n \otimes T) \geq R(T^{\otimes \lg n})$$</p>

<p>In the paper <a href="https://arxiv.org/abs/1609.07488" rel="nofollow noreferrer">"Application of a resource theory for magic states to fault-tolerant quantum computing"</a> it is proven (see page 3) that:</p>

<p>$$R(T^{\otimes k}) \in \Omega(1.2^k)$$</p>

<p>Meaning $R(W_n) \cdot R(T)$ is greater than or equal to something asymptotically lowerbounded by $1.2^{\lg n}$. Since $R(T)$ is a constant, we can ignore it and deduce:</p>

<p>$$\begin{align}
R(W_n) &amp;\in Ω(1.2^{\lg n})
       \\&amp;= Ω(n^{\lg 1.2})
       \\&amp;\subset Ω(n^{0.263})
       \\&amp;\subset Ω(\sqrt[4]{n})
\end{align}$$</p>

<p>Therefore $R(W_n)$ is asymptotically somewhere between $\sqrt[4]{n}$ (by synthesizing into Ts) and $n$ (via the decomposition I showed in the question).</p>

CC BY-SA 3.0
2018-03-01T04:45:25.590Z
2018-03-01T05:08:35.910Z
2018-03-01T05:08:35.910Z
Craig Gidney
<p><strong>Question</strong></p>

<p>What is the asymptotic robustness-of-magic of a $W$ state over $n$ qubits. Is it $\Theta(n)$? $\Omega(\sqrt{n})$? $O\left(\frac{n}{\lg n} \right)$?</p>

<p><strong>Background</strong></p>

<p>$W$ states are entangled states where exactly one qubit is ON and every qubit has an equal chance of being ON if measured. For example, $W_3 = \frac{1}{\sqrt{3}} \left( |100\rangle + |010\rangle + |001\rangle \right)$.</p>

<p>In the paper <a href="https://arxiv.org/abs/1609.07488" rel="nofollow noreferrer">"Application of a resource theory for magic states to fault-tolerant quantum computing"</a>, Howard and Campbell associate a quantum state $\rho$ with a cost $R(\rho)$ called "robustness of magic" and defined as:</p>

<p>$$R(\rho) = \min_x \sum_i |x_i|; \rho = \sum_i x_i \sigma_i $$</p>

<p>Where each $\sigma_i$ is a state that can be prepared by a stabilizer circuit (i.e. using only H, S, CNOT, and measurement gates). In other words, you try to find a weighted combination of stabilizer states that produce your desired state, and the cost you minimize while doing so is the sum of the weights' magnitudes. The minimum such cost is the robustness of magic of the state.</p>

<p><strong>What I've Tried</strong></p>

<p>The best-scoring decomposition I've found, for the $n$-qubit $W$ state, is:</p>

<p>$$s_{j,k} = X_j \cdot \text{CNOT}_{j\rightarrow k} \cdot H_j \cdot |0\rangle$$</p>

<p>$$S_{j,k} = s_{j,k} \cdot s_{j,k}^\dagger$$</p>

<p>$$W_n = \left(\sum_{j=0}^{n-1} \sum_{k=j+1}^{n-1} \frac{1}{n} S_{j,k} \right) + \left(\sum_{j=0}^{n-1} \frac{2-n}{n}|j\rangle \langle j| \right)$$</p>

<p>Which achieves a cost of $\frac{1}{n} \cdot \frac{n(n-1)}{2} + \frac{n-2}{n}\cdot n = \frac{3}{2}n-\frac{5}{2}$.</p>

<p>The best circuit construction I know for producing a large W state has a T-count that also scales like $\Theta(n)$. For example, here is an example construction that shows how to create a $W_n$ state using $2n-4$ T gates if $n$ is a power of 2:</p>

<p><a href="https://i.sstatic.net/u6s2e.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/u6s2e.png" alt="preparing a W_8 state"></a></p>

<p>Note that, if you want to compare the $2n-4$ T-count to the $\frac{3}{2}n - \frac{5}{2}$ potential-robustness-of-magic of the best-I-found decomposition, you must account for the fact that a $|T\rangle$ state's robustness-of-magic is $\sqrt{2}$ (not $1$).</p>

<p>Now, obviously, trying to find better and better decompositions is a reasonable way to upper-bound the robustness of magic... but this strategy will never create a lower-bound. What kinds of strategies <em>do</em> work for making lower bounds on this kind of problem?</p>

<quantum-information><asymptotics>
Computing 'Robustness of Magic' of $n$-bit W states
Craig Gidney
# Computing 'Robustness of Magic' of $n$-bit W states

(Asked by: username_0 on 2018-02-25)

**Question**

What is the asymptotic robustness-of-magic of a $W$ state over $n$ qubits. Is it $\Theta(n)$? $\Omega(\sqrt{n})$? $O\left(\frac{n}{\lg n} \right)$?

**Background**

$W$ states are entangled states where exactly one qubit is ON and every qubit has an equal chance of being ON if measured. For example, $W\_3 = \frac{1}{\sqrt{3}} \left( |100\rangle + |010\rangle + |001\rangle \right)$.

In the paper ["Application of a resource theory for magic states to fault-tolerant quantum computing"](https://arxiv.org/abs/1609.07488), Howard and Campbell associate a quantum state $\rho$ with a cost $R(\rho)$ called "robustness of magic" and defined as:

$$R(\rho) = \min\_x \sum\_i |x\_i|; \rho = \sum\_i x\_i \sigma\_i $$

Where each $\sigma\_i$ is a state that can be prepared by a stabilizer circuit (i.e. using only H, S, CNOT, and measurement gates). In other words, you try to find a weighted combination of stabilizer states that produce your desired state, and the cost you minimize while doing so is the sum of the weights' magnitudes. The minimum such cost is the robustness of magic of the state.

**What I've Tried**

The best-scoring decomposition I've found, for the $n$-qubit $W$ state, is:

$$s\_{j,k} = X\_j \cdot \text{CNOT}\_{j\rightarrow k} \cdot H\_j \cdot |0\rangle$$

$$S\_{j,k} = s\_{j,k} \cdot s\_{j,k}^\dagger$$

$$W\_n = \left(\sum\_{j=0}^{n-1} \sum\_{k=j+1}^{n-1} \frac{1}{n} S\_{j,k} \right) + \left(\sum\_{j=0}^{n-1} \frac{2-n}{n}|j\rangle \langle j| \right)$$

Which achieves a cost of $\frac{1}{n} \cdot \frac{n(n-1)}{2} + \frac{n-2}{n}\cdot n = \frac{3}{2}n-\frac{5}{2}$.

The best circuit construction I know for producing a large W state has a T-count that also scales like $\Theta(n)$. For example, here is an example construction that shows how to create a $W\_n$ state using $2n-4$ T gates if $n$ is a power of 2:

[![preparing a W_8 state](https://i.sstatic.net/u6s2e.png)](https://i.sstatic.net/u6s2e.png)

Note that, if you want to compare the $2n-4$ T-count to the $\frac{3}{2}n - \frac{5}{2}$ potential-robustness-of-magic of the best-I-found decomposition, you must account for the fact that a $|T\rangle$ state's robustness-of-magic is $\sqrt{2}$ (not $1$).

Now, obviously, trying to find better and better decompositions is a reasonable way to upper-bound the robustness of magic... but this strategy will never create a lower-bound. What kinds of strategies *do* work for making lower bounds on this kind of problem?

**Tags:** quantum-information, asymptotics


---

## 1 answers

### Answer by username_0 on 2018-03-01. Score: 2 | Accepted answer

Here is a proof that $R(W\_n) \in \Omega(\sqrt[4]{n})$.

Given a $W\_n$ state, it is possible to create $\lg n$ T states with Clifford operations and a single additional T gate. Basically:

1. Xor together all the qubit's whose binary index has an odd number of 1s, apply a T gate to that xor'd value, then unxor.
2. Apply an S gate to every qubit whose binary index has a number of 1s that's 2 or 3 more than a multiple of 4.
3. Apply a Z gate to every qubit whose binary index has a number of 1s that's 4, 5, 6, or 7 more than a multiple of 8.
4. Compress the unary $W\_n$ state down into a binary register.

Here's an [example circuit turning $W\_8$ into 3 $|T\rangle$ states](http://algassert.com/quirk#circuit=%7B%22cols%22%3A%5B%5B%22H%22%5D%2C%5B%22%E2%97%A6%22%2C%22X%22%5D%2C%5B1%2C%22Swap%22%2C%22Swap%22%5D%2C%5B%22~e6am%22%2C1%2C%22~e6am%22%5D%2C%5B1%2C%22Swap%22%2C1%2C1%2C%22Swap%22%5D%2C%5B1%2C1%2C1%2C%22Swap%22%2C1%2C1%2C%22Swap%22%5D%2C%5B%22~e6am%22%2C1%2C%22~e6am%22%2C1%2C%22~e6am%22%2C1%2C%22~e6am%22%5D%2C%5B1%2C%22Z%22%2C%22Z%22%2C1%2C%22Z%22%2C1%2C1%2C%22%E2%8A%96%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C1%2C1%2C%22Z%5E%C2%BC%22%5D%2C%5B1%2C%22Z%22%2C%22Z%22%2C1%2C%22Z%22%2C1%2C1%2C%22%E2%8A%96%22%5D%2C%5B1%2C1%2C1%2C%22Z%5E%C2%BD%22%2C1%2C%22Z%5E%C2%BD%22%2C%22Z%5E%C2%BD%22%2C%22Z%5E%C2%BD%22%5D%2C%5B%22%5E%3DA4%22%2C1%2C1%2C1%2C%22inputA4%22%5D%2C%5B1%2C1%2C1%2C1%2C%22%E2%8A%96%22%2C%22Z%22%2C%22Z%22%2C%22Z%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C%22H%22%2C%22H%22%2C%22H%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C%22Measure%22%2C%22Measure%22%2C%22Measure%22%5D%2C%5B1%2C%22Z%22%2C1%2C1%2C%22%E2%80%A2%22%2C%22%E2%80%A2%22%5D%2C%5B1%2C1%2C%22Z%22%2C1%2C%22%E2%80%A2%22%2C1%2C%22%E2%80%A2%22%5D%2C%5B1%2C1%2C1%2C%22Z%22%2C%22%E2%80%A2%22%2C1%2C1%2C%22%E2%80%A2%22%5D%2C%5B%22%5E%3DA2%22%2C1%2C%22inputA2%22%5D%2C%5B1%2C1%2C%22%E2%8A%96%22%2C%22Z%22%5D%2C%5B1%2C1%2C1%2C%22H%22%5D%2C%5B1%2C1%2C1%2C%22Measure%22%5D%2C%5B1%2C%22Z%22%2C%22%E2%80%A2%22%2C%22%E2%80%A2%22%5D%2C%5B%22%5E%3DA1%22%2C%22inputA1%22%2C1%2C%22%3C%3C2%22%5D%2C%5B%22%3E%3E4%22%5D%2C%5B%22Amps1%22%2C%22Amps1%22%2C%22Amps1%22%5D%5D%2C%22gates%22%3A%5B%7B%22id%22%3A%22~e6am%22%2C%22name%22%3A%22Spr%22%2C%22circuit%22%3A%7B%22cols%22%3A%5B%5B%22%E2%80%A2%22%2C%22H%22%5D%2C%5B%22X%22%2C%22%E2%80%A2%22%5D%5D%7D%7D%5D%7D):

[![W_8 to 3 T](https://i.sstatic.net/GN5Ew.png)](https://i.sstatic.net/GN5Ew.png)

I also tested [turning $W\_{16}$ into 4 $|T\rangle$ states](http://algassert.com/quirk#circuit=%7B%22cols%22%3A%5B%5B%22H%22%5D%2C%5B%22%E2%97%A6%22%2C%22X%22%5D%2C%5B1%2C%22Swap%22%2C%22Swap%22%5D%2C%5B%22~e6am%22%2C1%2C%22~e6am%22%5D%2C%5B1%2C%22Swap%22%2C1%2C1%2C%22Swap%22%5D%2C%5B1%2C1%2C1%2C%22Swap%22%2C1%2C1%2C%22Swap%22%5D%2C%5B%22~e6am%22%2C1%2C%22~e6am%22%2C1%2C%22~e6am%22%2C1%2C%22~e6am%22%5D%2C%5B1%2C%22Swap%22%2C1%2C1%2C1%2C1%2C1%2C1%2C%22Swap%22%5D%2C%5B1%2C1%2C1%2C%22Swap%22%2C1%2C1%2C1%2C1%2C1%2C1%2C%22Swap%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C%22Swap%22%2C1%2C1%2C1%2C1%2C1%2C1%2C%22Swap%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C1%2C1%2C%22Swap%22%2C1%2C1%2C1%2C1%2C1%2C1%2C%22Swap%22%5D%2C%5B%22~e6am%22%2C1%2C%22~e6am%22%2C1%2C%22~e6am%22%2C1%2C%22~e6am%22%2C1%2C%22~e6am%22%2C1%2C%22~e6am%22%2C1%2C%22~e6am%22%2C1%2C%22~e6am%22%5D%2C%5B%22%E2%80%A6%22%5D%2C%5B1%2C%22Z%22%2C%22Z%22%2C1%2C%22Z%22%2C1%2C1%2C%22Z%22%2C%22Z%22%2C1%2C1%2C%22Z%22%2C1%2C%22Z%22%2C%22%E2%8A%96%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C1%2C1%2C1%2C1%2C1%2C1%2C1%2C1%2C1%2C%22Z%5E%C2%BC%22%5D%2C%5B1%2C%22Z%22%2C%22Z%22%2C1%2C%22Z%22%2C1%2C1%2C%22Z%22%2C%22Z%22%2C1%2C1%2C%22Z%22%2C1%2C%22Z%22%2C%22%E2%8A%96%22%5D%2C%5B1%2C1%2C1%2C%22Z%5E%C2%BD%22%2C1%2C%22Z%5E%C2%BD%22%2C%22Z%5E%C2%BD%22%2C%22Z%5E%C2%BD%22%2C1%2C%22Z%5E%C2%BD%22%2C%22Z%5E%C2%BD%22%2C%22Z%5E%C2%BD%22%2C%22Z%5E%C2%BD%22%2C%22Z%5E%C2%BD%22%2C%22Z%5E%C2%BD%22%2C%22Z%22%5D%2C%5B%22%5E%3DA8%22%2C1%2C1%2C1%2C1%2C1%2C1%2C1%2C%22inputA8%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C1%2C1%2C1%2C%22%E2%8A%96%22%2C%22Z%22%2C%22Z%22%2C%22Z%22%2C%22Z%22%2C%22Z%22%2C%22Z%22%2C%22Z%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C1%2C1%2C1%2C1%2C%22H%22%2C%22H%22%2C%22H%22%2C%22H%22%2C%22H%22%2C%22H%22%2C%22H%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C1%2C1%2C1%2C1%2C%22Measure%22%2C%22Measure%22%2C%22Measure%22%2C%22Measure%22%2C%22Measure%22%2C%22Measure%22%2C%22Measure%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C1%2C1%2C%22%E2%80%A2%22%2C%22Z%22%2C1%2C1%2C1%2C1%2C1%2C1%2C%22%E2%80%A2%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C1%2C%22%E2%80%A2%22%2C1%2C%22Z%22%2C1%2C1%2C1%2C1%2C1%2C%22%E2%80%A2%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C%22%E2%80%A2%22%2C1%2C1%2C%22Z%22%2C1%2C1%2C1%2C1%2C%22%E2%80%A2%22%5D%2C%5B1%2C1%2C1%2C1%2C%22%E2%80%A2%22%2C1%2C1%2C1%2C%22Z%22%2C1%2C1%2C1%2C%22%E2%80%A2%22%5D%2C%5B1%2C1%2C1%2C%22%E2%80%A2%22%2C1%2C1%2C1%2C1%2C%22Z%22%2C1%2C1%2C%22%E2%80%A2%22%5D%2C%5B1%2C1%2C%22%E2%80%A2%22%2C1%2C1%2C1%2C1%2C1%2C%22Z%22%2C1%2C%22%E2%80%A2%22%5D%2C%5B1%2C%22%E2%80%A2%22%2C1%2C1%2C1%2C1%2C1%2C1%2C%22Z%22%2C%22%E2%80%A2%22%5D%2C%5B%22%5E%3DA4%22%2C1%2C1%2C1%2C%22inputA4%22%5D%2C%5B1%2C1%2C1%2C1%2C%22%E2%8A%96%22%2C%22Z%22%2C%22Z%22%2C%22Z%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C%22H%22%2C%22H%22%2C%22H%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C%22Measure%22%2C%22Measure%22%2C%22Measure%22%5D%2C%5B1%2C1%2C1%2C%22%E2%80%A2%22%2C%22Z%22%2C1%2C1%2C%22%E2%80%A2%22%5D%2C%5B1%2C1%2C%22%E2%80%A2%22%2C1%2C%22Z%22%2C1%2C%22%E2%80%A2%22%5D%2C%5B1%2C%22%E2%80%A2%22%2C1%2C1%2C%22Z%22%2C%22%E2%80%A2%22%5D%2C%5B%22%5E%3DA2%22%2C1%2C%22inputA2%22%5D%2C%5B1%2C1%2C%22%E2%8A%96%22%2C%22Z%22%5D%2C%5B1%2C1%2C1%2C%22H%22%5D%2C%5B1%2C1%2C1%2C%22Measure%22%5D%2C%5B1%2C%22%E2%80%A2%22%2C%22Z%22%2C%22%E2%80%A2%22%5D%2C%5B%22%5E%3DA1%22%2C%22inputA1%22%2C1%2C%22%3C%3C2%22%5D%2C%5B1%2C1%2C1%2C1%2C%22%3C%3C5%22%5D%2C%5B%22%3E%3E5%22%5D%2C%5B%22Amps1%22%2C%22Amps1%22%2C%22Amps1%22%2C%22Amps1%22%5D%5D%2C%22gates%22%3A%5B%7B%22id%22%3A%22~e6am%22%2C%22name%22%3A%22Spr%22%2C%22circuit%22%3A%7B%22cols%22%3A%5B%5B%22%E2%80%A2%22%2C%22H%22%5D%2C%5B%22X%22%2C%22%E2%80%A2%22%5D%5D%7D%7D%5D%7D).

We can produce $\lg n$ T states from a $W\_n$ state and a single $T$ state. It must always be the case that an output's robustness of magic is less than or equal than the input's. Therefore:

$$R(W\_n) \cdot R(T) \geq R(W\_n \otimes T) \geq R(T^{\otimes \lg n})$$

In the paper ["Application of a resource theory for magic states to fault-tolerant quantum computing"](https://arxiv.org/abs/1609.07488) it is proven (see page 3) that:

$$R(T^{\otimes k}) \in \Omega(1.2^k)$$

Meaning $R(W\_n) \cdot R(T)$ is greater than or equal to something asymptotically lowerbounded by $1.2^{\lg n}$. Since $R(T)$ is a constant, we can ignore it and deduce:

$$\begin{align}
R(W\_n) &\in Ω(1.2^{\lg n})
\\&= Ω(n^{\lg 1.2})
\\&\subset Ω(n^{0.263})
\\&\subset Ω(\sqrt[4]{n})
\end{align}$$

Therefore $R(W\_n)$ is asymptotically somewhere between $\sqrt[4]{n}$ (by synthesizing into Ts) and $n$ (via the decomposition I showed in the question).


---

