文章基本信息

标题：Lower Bounds on Stabilizer Rank
本地全文：下载
作者：Shir Peleg ; Amir Shpilka ; Ben Lee Volk 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2021
卷号：21
语种：English
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：The stabilizer rank of a quantum state is the minimal r such that =rj=1cjj for cjC and stabilizer states j. The running time of several classical simulation methods for quantum circuits is determined by the stabilizer rank of the n-th tensor power of single-qubit magic states. We prove a lower bound of (n) on the stabilizer rank of such states, improving a previous lower bound of (n) of Bravyi, Smith and Smolin [BSS16]. Further, we prove that for a sufficiently small constant , the stabilizer rank of any state which is -close to those states is (nlogn) . This is the first non-trivial lower bound for approximate stabilizer rank. Our techniques rely on the representation of stabilizer states as quadratic functions over affine subspaces of Fn2, and we use tools from analysis of boolean functions and complexity theory. The proof of the first result involves a careful analysis of directional derivatives of quadratic polynomials, whereas the proof of the second result uses Razborov-Smolensky low degree polynomial approximations and correlation bounds against the majority function.
关键词：quantum computing;simulation of quantum circuits;stabilizer rank