New techniques for bounding stabilizer rank

• URL: http://arxiv.org/abs/2110.07781v2
• Date: Wed, 13 Apr 2022 19:26:44 GMT
• Title: New techniques for bounding stabilizer rank
• Authors: Benjamin Lovitz and Vincent Steffan
• Abstract summary: We present number-theoretic and algebraic-geometric techniques for bounding the stabilizer rank of quantum states. We show an explicit sequence of product states with exponential stabilizer rank but approximate stabilizer rank, and to provide alternate (and simplified) proofs of the best-known lower bounds on stabilizer rank and approximate stabilizer rank.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this work, we present number-theoretic and algebraic-geometric techniques for bounding the stabilizer rank of quantum states. First, we refine a number-theoretic theorem of Moulton to exhibit an explicit sequence of product states with exponential stabilizer rank but constant approximate stabilizer rank, and to provide alternate (and simplified) proofs of the best-known asymptotic lower bounds on stabilizer rank and approximate stabilizer rank, up to a log factor. Second, we find the first non-trivial examples of quantum states with multiplicative stabilizer rank under the tensor product. Third, we introduce and study the generic stabilizer rank using algebraic-geometric techniques.

Related papers

• Hessian stability and convergence rates for entropic and Sinkhorn potentials via semiconcavity [4.604003661048267]
  This is the first work addressing this second-order quantitative stability estimate in general unbounded settings. We deduce exponential convergence rates for gradient and Hessian of Sinkhorns along Sinkhorn's algorithm.
  arXiv  Detail & Related papers  (2025-04-15T12:34:09Z)
• Stabilizer Ranks, Barnes Wall Lattices and Magic Monotones [0.0]
  Kliuchnikov and Sch"onnenbeck showed a connection between the Barnes Wall lattices, stabilizer states and Clifford operations. We show the first quantitative lower bound on stabilizer fidelity as a function of stabilizer ranks.
  arXiv  Detail & Related papers  (2025-03-06T05:20:55Z)
• Improved bounds for testing low stabilizer complexity states [6.169364905804677]
  We improve the state-of-the-art parameters for the tolerant testing of stabilizer states. We also study the problem of testing low stabilizer rank states.
  arXiv  Detail & Related papers  (2024-10-31T17:56:57Z)
• Bases for optimising stabiliser decompositions of quantum states [14.947570152519281]
  We introduce and study the vector space of linear dependencies of $n$-qubit stabiliser states. We construct elegant bases of linear dependencies of constant size three. We use them to explicitly compute the stabiliser extent of states of more qubits than is feasible with existing techniques.
  arXiv  Detail & Related papers  (2023-11-29T06:30:05Z)
• Ito Diffusion Approximation of Universal Ito Chains for Sampling, Optimization and Boosting [64.0722630873758]
  We consider rather general and broad class of Markov chains, Ito chains, that look like Euler-Maryama discretization of some Differential Equation. We prove the bound in $W_2$-distance between the laws of our Ito chain and differential equation.
  arXiv  Detail & Related papers  (2023-10-09T18:38:56Z)
• 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)
• Numerov and phase-integral methods for charmonium [0.0]
  This paper applies the Numerov and phase-integral methods to the stationary Schrodinger equation that studies bound states of charm anti-charm quarks. The latter is an analytic method that provides, in principle, even exact solutions of the stationary Schrodinger equation.
  arXiv  Detail & Related papers  (2022-04-03T14:25:51Z)
• Tight Exponential Analysis for Smoothing the Max-Relative Entropy and for Quantum Privacy Amplification [56.61325554836984]
  The max-relative entropy together with its smoothed version is a basic tool in quantum information theory. We derive the exact exponent for the decay of the small modification of the quantum state in smoothing the max-relative entropy based on purified distance.
  arXiv  Detail & Related papers  (2021-11-01T16:35:41Z)
• 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)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  We present an analysis of the ExtraGradient (SEG) method with constant step size, and present variations of the method that yield favorable convergence. We prove that when augmented with averaging, SEG provably converges to the Nash equilibrium, and such a rate is provably accelerated by incorporating a scheduled restarting procedure.
  arXiv  Detail & Related papers  (2021-06-30T17:51:36Z)
• Lower Bounds on Stabilizer Rank [3.265773263570237]
  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.
  arXiv  Detail & Related papers  (2021-06-06T19:27:51Z)
• Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent [55.85456985750134]
  We introduce a new stability measure called on-average model stability, for which we develop novel bounds controlled by the risks of SGD iterates. This yields generalization bounds depending on the behavior of the best model, and leads to the first-ever-known fast bounds in the low-noise setting. To our best knowledge, this gives the firstever-known stability and generalization for SGD with even non-differentiable loss functions.
  arXiv  Detail & Related papers  (2020-06-15T06:30:19Z)
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration [115.1954841020189]
  We study the inequality and non-asymptotic properties of approximation procedures with Polyak-Ruppert averaging. We prove a central limit theorem (CLT) for the averaged iterates with fixed step size and number of iterations going to infinity.
  arXiv  Detail & Related papers  (2020-04-09T17:54:18Z)

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.