4
$\begingroup$

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 \begin{equation} |{\psi}\rangle = \sum_{j=1}^{r} c_j |φ_{j}\rangle. \end{equation} 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 \begin{equation} |||ψ\rangle − |φ\rangle||_{2} \leq \delta. \end{equation}

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ 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? $\endgroup$ Oct 18, 2021 at 15:58
  • 1
    $\begingroup$ What's a QROM read and how does it relate to stabilizer rank? Might you elaborate this into an answer? $\endgroup$
    – BlackHat18
    Oct 19, 2021 at 17:31

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.