Lower Bounds on Stabilizer Rank

• URL: http://arxiv.org/abs/2106.03214v2
• Date: Thu, 10 Feb 2022 08:54:39 GMT
• Title: Lower Bounds on Stabilizer Rank
• Authors: Shir Peleg, Amir Shpilka, Ben Lee Volk
• Abstract summary: We prove that for a sufficiently small constant $delta, the stabilizer rank of any state which is $$-close to those states is $Omega(sqrtn/log n)$. This is the first non-trivial lower bound for approximate stabilizer rank.
• Score: 3.265773263570237
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: The stabilizer rank of a quantum state $\psi$ is the minimal $r$ such that $\left| \psi \right \rangle = \sum_{j=1}^r c_j \left|\varphi_j \right\rangle$ for $c_j \in \mathbb{C}$ and stabilizer states $\varphi_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 $\Omega(n)$ on the stabilizer rank of such states, improving a previous lower bound of $\Omega(\sqrt{n})$ of Bravyi, Smith and Smolin (arXiv:1506.01396). Further, we prove that for a sufficiently small constant $\delta$, the stabilizer rank of any state which is $\delta$-close to those states is $\Omega(\sqrt{n}/\log n)$. 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 $\mathbb{F}_2^n$, 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.

Related papers

• A note on polynomial-time tolerant testing stabilizer states [6.458742319938316]
  We show an improved inverse theorem for the Gowers-$3$ of $n$-qubit quantum states $|psirangle. For every $gammageq 0$, if the $textsfGowers(|psi rangle,3)8 geq gamma then stabilizer fidelity of $|psirangle$ is at least $gammaC$ for some constant $C>1$.
  arXiv  Detail & Related papers  (2024-10-29T16:49:33Z)
• Stabilizer bootstrapping: A recipe for efficient agnostic tomography and magic estimation [16.499689832762765]
  We study the task of tomography: given copies of an unknown $n$-qubit state $rho$ which has fidelity $tau$ with some state in a given class $C$, find a state which has fidelity $ge tau - epsilon$ with $rho$. We give a new framework, stabilizer bootstrapping, for designing computationally efficient protocols for this task, and use this to get new agnostic tomography protocols for the following classes: stabilizer states and discrete product states.
  arXiv  Detail & Related papers  (2024-08-13T15:23:17Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)
• Quadratic Lower bounds on the Approximate Stabilizer Rank: A Probabilistic Approach [6.169364905804677]
  The approximate stabilizer rank of a quantum state is the minimum number of terms in any approximate decomposition of that state into stabilizer states. We improve the lower bound on the approximate rank to $tilde Omega(sqrt n)$ for a wide range of the approximation parameters.
  arXiv  Detail & Related papers  (2023-05-17T15:09:41Z)
• Improved Stabilizer Estimation via Bell Difference Sampling [0.43123403062068827]
  We study the complexity of learning quantum states in various models with respect to the stabilizer formalism. We prove that $Omega(n)$ $T$gates are necessary for any Clifford+$T$ circuit to prepare pseudorandom quantum states. We show that a modification of the above algorithm runs in time.
  arXiv  Detail & Related papers  (2023-04-27T01:58:28Z)
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
  "Statistical-computational gaps" occur in many statistical inference tasks. We consider a model for random order-3 decomposition where one component is slightly larger in norm than the rest. We show that tensor entries can accurately estimate the largest component when $ll n3/2$ but fail to do so when $rgg n3/2$.
  arXiv  Detail & Related papers  (2022-11-10T00:40:37Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  For every $delta>0,$ we construct CNF and formulas of size with approximate degree $Omega(n1-delta),$ essentially matching the trivial upper bound of $n. We show that for every $delta>0$, these models require $Omega(n1-delta)$, $Omega(n/4kk2)1-delta$, and $Omega(n/4kk2)1-delta$, respectively.
  arXiv  Detail & Related papers  (2022-09-04T10:01:39Z)
• Near-optimal fitting of ellipsoids to random points [68.12685213894112]
  A basic problem of fitting an ellipsoid to random points has connections to low-rank matrix decompositions, independent component analysis, and principal component analysis. We resolve this conjecture up to logarithmic factors by constructing a fitting ellipsoid for some $n = Omega(, d2/mathrmpolylog(d),)$. Our proof demonstrates feasibility of the least squares construction of Saunderson et al. using a convenient decomposition of a certain non-standard random matrix.
  arXiv  Detail & Related papers  (2022-08-19T18:00:34Z)
• Improved Graph Formalism for Quantum Circuit Simulation [77.34726150561087]
  We show how to efficiently simplify stabilizer states to canonical form. We characterize all linearly dependent triplets, revealing symmetries in the inner products. Using our novel controlled-Pauli $Z$ algorithm, we improve runtime for inner product computation from $O(n3)$ to $O(nd2)$ where $d$ is the maximum degree of the graph.
  arXiv  Detail & Related papers  (2021-09-20T05:56:25Z)
• Improved upper bounds on the stabilizer rank of magic states [0.0]
  improvement is obtained by establishing a new upper bound on the stabilizer rank of $m$ copies of the magic state $|Trangle=sqrt2-1(|0rangle+eipi/4|1rangle)$ in the limit of large $m$. We obtain a strong simulation algorithm for circuits consisting of Clifford gates and $m$ instances of any (fixed) single-qubit $Z$-rotation gate with runtime $textpoly(n,m) 2m/2$.
  arXiv  Detail & Related papers  (2021-06-14T20:20:51Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.