Lower Bounds on Stabilizer Rank
Lower Bounds on Stabilizer Rank
复制标题
稳定器等级下限
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Ben lee Volk
中科院分区：
文献类型：
--
作者：
Shir Peleg;Amir Shpilka;Ben lee Volk
量子态 ψ 的稳定器等级是最小 r，使得 |ψ⟩=Σj=1rcj|φj⟩ 对于 cj∈C 和稳定器状态 φj。量子电路的几种经典模拟方法的运行时间是由单量子位魔态的n次张量幂的稳定器等级决定的。我们证明了此类状态的稳定器等级上的Ω(n)下界，改进了Bravyi、Smith和Smolin之前的Ω(n)下界\cite{BSS16}。此外，我们证明，对于足够小的常数 δ，任何与这些状态 δ 接近的状态的稳定器等级都是 Ω(n/logn)。这是近似稳定器等级的第一个重要下界。我们的技术依赖于将稳定器状态表示为 F2n 仿射子空间上的二次函数，并且我们使用布尔函数和复杂性理论分析的工具。第一个结果的证明涉及对二次多项式的方向导数的仔细分析，而第二个结果的证明使用 Razborov-Smolensky 低次多项式近似和针对多数函数的相关界限。
The stabilizer rank of a quantum state ψ is the minimal r such that |ψ⟩=∑j=1rcj|φj⟩ for cj∈C 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 \cite{BSS16}. Further, we prove that for a sufficiently small constant δ, the stabilizer rank of any state which is δ-close to those states is Ω(n/logn). 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 F2n, 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.
影响因子：
6.4
作者：
Bravyi, Sergey;Browne, Dan;Howard, Mark
通讯作者：
Howard, Mark
Oracle BQP 和 PH 分离
DOI：
10.1145/3313276.3316315
发表时间：
2019
期刊：
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019
影响因子：
--
作者：
Raz, Ran;Tal, Avishay
通讯作者：
Tal, Avishay