# Conditional lower bound on approximate stabilizer rank of magic states

I am currently reading about the approximate stabilizer rank and properties of the same.

I will quote the definitions from this paper.

The stabilizer rank of a quantum state $$|\psi\rangle$$ is the minimal $$r$$ such that $$$$|{\psi}\rangle = \sum_{j=1}^{r} c_j |φ_{j}\rangle.$$$$ for $$c_j \in \mathbb{C}$$ and stabilizer states $$|φ_j\rangle$$.

The $$\delta$$-approximate stabilizer rank of $$|ψ\rangle$$, denoted $$\chi_{\delta}(ψ)$$, is defined as the minimum of $$\chi(\psi)$$ over all states $$|φ\rangle$$ such that $$$$|||ψ\rangle − |φ\rangle||_{2} \leq \delta.$$$$

The paper I quoted gives a loose unconditional lower bound on approximate stabilizer rank. But, is there a known stronger conditional lower bound for the approximate stabiliser rank of an $$n$$-fold tensor product of any single qubit magic state?

There is such a conditional lower bound for the exact stabilizer rank, given by

Much stronger hardness assumptions than $$\text{P}=\text{NP}$$, such as the exponential time hypothesis, imply that $$\chi(H^{\otimes n}) = 2^{Ω(n)}.$$ [MT19, HNS20]

$$H$$ is a single qubit magic state, as defined in the paper. But I could not find anything for approximate stabilizer rank.

## 1 Answer

In a recent work Lovitz and Steffan (theorem 3.5) showed that for any non-stabilizer $$n$$-qubit state, there is a constant $$\delta>0$$, such that for every $$n\geq 2$$, $$\chi_\delta(\psi^{\otimes n})\geq \frac{\sqrt{n}}{2\log_2 n}.$$

• Don't you get a straight $\Omega(\sqrt{n})$ from the ability to apply QROM reads via gate teleportation, with a correction that's a QROM read of half the size, and the fact that QROM reads have a lower bound of $\Omega(\sqrt{n})$ T gates? Oct 18 '21 at 15:58
• What's a QROM read and how does it relate to stabilizer rank? Might you elaborate this into an answer? Oct 19 '21 at 17:31