Lower bound for the T count via unitary stabilizer nullity

• URL: http://arxiv.org/abs/2103.09999v2
• Date: Tue, 7 Mar 2023 23:34:22 GMT
• Title: Lower bound for the T count via unitary stabilizer nullity
• Authors: Jiaqing Jiang, Xin Wang
• Abstract summary: We introduce measures to quantify the nonstabilizerness of multiqubit quantum gates. We establish lower bounds on the $T$ count for fault-tolerant quantum computation.
• Score: 8.810275100251681
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce magic measures to quantify the nonstabilizerness of multiqubit quantum gates and establish lower bounds on the $T$ count for fault-tolerant quantum computation. First, we introduce the stabilizer nullity of multi-qubit unitary, which is based on the subgroup of the quotient Pauli group associated with the unitary. This unitary stabilizer nullity extends the state-stabilizer nullity by Beverland et al. to a dynamic version. In particular, we show this nonstabilizerness measure has desirable properties such as subadditivity under composition and additivity under tensor product. Second, we prove that a given unitary's stabilizer nullity is a lower bound for the $T$ count, utilizing the above properties in gate synthesis. Third, we compare the state- and the unitary-stabilizer nullity, proving that the lower bounds for the $T$ count obtained by the unitary-stabilizer nullity are never less than the state-stabilizer nullity. Moreover, we show an explicit $n$-qubit unitary family of unitary-stabilizer nullity $2n$, which implies that its $T$ count is at least $2n$. This gives an example where the bounds derived by the unitary-stabilizer nullity strictly outperform the state-stabilizer nullity by a factor of $2$. We finally showcase the advantages of unitary-stabilizer nullity in estimating the $T$ count of quantum gates with interests.

Related papers

• A nonstabilizerness monotone from stabilizerness asymmetry [0.0]
  We introduce a nonstabilizerness monotone which we name basis-minimised stabilizerness asymmetry (BMSA) For pure states, we show that the BMSA is a strong monotone for magic-state resource theory, while it can be extended to mixed states via the convex roof construction. We present numerical methods to compute the BMSA, highlighting its advantages and drawbacks compared to other nonstabilizerness measures in the context of pure many-body quantum states.
  arXiv  Detail & Related papers  (2024-11-08T18:26:40Z)
• 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)
• The wave function of stabilizer states and the Wehrl conjecture [0.0]
  We focus on quantum systems represented by a Hilbert space $L(A)$, where $A$ is a locally compact Abelian group that contains a compact open subgroup. We provide a complete and elegant solution to the problem of describing the stabilizer states in terms of their wave functions, an issue that arises in quantum information theory. We demonstrate that the stabilizer states are precisely the minimizers of the Wehrl entropy functional, thereby resolving the analog of the Wehrl conjecture for any such group.
  arXiv  Detail & Related papers  (2024-06-10T11:13:42Z)
• Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
  We consider clipped optimization problems with heavy-tailed noise with structured density. We show that it is possible to get faster rates of convergence than $mathcalO(K-(alpha - 1)/alpha)$, when the gradients have finite moments of order. We prove that the resulting estimates have negligible bias and controllable variance.
  arXiv  Detail & Related papers  (2023-11-07T17:39:17Z)
• 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)
• Stabilizer R\'enyi entropy [0.0]
  We introduce a novel measure for the quantum property of nonstabilizerness - commonly known as "magic" We show that this is a good measure of nonstabilizerness from the point of view of resource theory and show bounds with other known measures. We show that the nonstabilizerness is intimately connected to out-of-time-order correlation functions and that maximal levels of nonstabilizerness are necessary for quantum chaos.
  arXiv  Detail & Related papers  (2021-06-23T18:00:02Z)
• 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)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  We consider algorithm-independent lower bounds for the problem of black-box optimization of functions having a bounded norm. We provide a novel proof technique for deriving lower bounds on the regret, with benefits including simplicity, versatility, and an improved dependence on the error probability.
  arXiv  Detail & Related papers  (2020-08-20T03:48:14Z)
• Learning Stabilizing Controllers for Unstable Linear Quadratic Regulators from a Single Trajectory [85.29718245299341]
  We study linear controllers under quadratic costs model also known as linear quadratic regulators (LQR) We present two different semi-definite programs (SDP) which results in a controller that stabilizes all systems within an ellipsoid uncertainty set. We propose an efficient data dependent algorithm -- textsceXploration -- that with high probability quickly identifies a stabilizing controller.
  arXiv  Detail & Related papers  (2020-06-19T08:58:57Z)
• 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)
• Finite-time Identification of Stable Linear Systems: Optimality of the Least-Squares Estimator [79.3239137440876]
  We present a new finite-time analysis of the estimation error of the Ordinary Least Squares (OLS) estimator for stable linear time-invariant systems. We characterize the number of observed samples sufficient for the OLS estimator to be $(varepsilon,delta)$-PAC, i.e., to yield an estimation error less than $varepsilon$ with probability at least $1-delta$.
  arXiv  Detail & Related papers  (2020-03-17T20:59:17Z)

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.