English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

The approximate stabilizer rank of a quantum state is the minimum number ofterms in any approximate decomposition of that state into stabilizer states.Bravyi and Gosset showed that the approximate stabilizer rank of a so-called"magic" state like $|T\rangle^{\otimes n}$, up to polynomial factors, is anupper bound on the number of classical operations required to simulate anarbitrary quantum circuit with Clifford gates and $n$ number of $T$ gates. As aresult, an exponential lower bound on this quantity seems inevitable. Despitethis intuition, several attempts using various techniques could not lead to abetter than a linear lower bound on the "exact" rank of ${|T\rangle}^{\otimesn}$, meaning the minimal size of a decomposition that exactly produces thestate. For the "approximate" rank, which is more realistically related to thecost of simulating quantum circuits, no lower bound better than $\tilde\Omega(\sqrt n)$ has been known. In this paper, we improve the lower bound onthe approximate rank to $\tilde \Omega (n^2)$ for a wide range of theapproximation parameters. An immediate corollary of our result is the existenceof polynomial time computable functions which require a super-linear number ofterms in any decomposition into exponentials of quadratic forms over$\mathbb{F}_2$, resolving a question in [Wil18]. Our approach is based on astrong lower bound on the approximate rank of a quantum state sampled from theHaar measure, a step-by-step analysis of the approximate rank of a magic-stateteleportation protocol to sample from the Haar measure, and a result abouttrading Clifford operations with $T$ gates by [LKS18].

Quadratic Lower bounds on the Approximate Stabilizer Rank: A Probabilistic Approach