Computing 'Robustness of Magic' of $n$-bit W states

Question

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", 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:

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?

Answer 1

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:

I also tested turning $W_{16}$ into 4 $|T\rangle$ states.

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