Quadratic Lower bounds on the Approximate Stabilizer Rank: A Probabilistic Approach

• URL: http://arxiv.org/abs/2305.10277v4
• Date: Fri, 29 Mar 2024 23:55:52 GMT
• Title: Quadratic Lower bounds on the Approximate Stabilizer Rank: A Probabilistic Approach
• Authors: Saeed Mehraban, Mehrdad Tahmasbi,
• Abstract summary: 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.
• Score: 6.169364905804677
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The approximate stabilizer rank of a quantum state is the minimum number of terms in any approximate decomposition of that state into stabilizer states. Bravyi and Gosset showed that the approximate stabilizer rank of a so-called "magic" state like $|T\rangle^{\otimes n}$, up to polynomial factors, is an upper bound on the number of classical operations required to simulate an arbitrary quantum circuit with Clifford gates and $n$ number of $T$ gates. As a result, an exponential lower bound on this quantity seems inevitable. Despite this intuition, several attempts using various techniques could not lead to a better than a linear lower bound on the "exact" rank of ${|T\rangle}^{\otimes n}$, meaning the minimal size of a decomposition that exactly produces the state. For the "approximate" rank, which is more realistically related to the cost of simulating quantum circuits, no lower bound better than $\tilde \Omega(\sqrt n)$ has been known. In this paper, we improve the lower bound on the approximate rank to $\tilde \Omega (n^2)$ for a wide range of the approximation parameters. An immediate corollary of our result is the existence of polynomial time computable functions which require a super-linear number of terms in any decomposition into exponentials of quadratic forms over $\mathbb{F}_2$, resolving a question in [Wil18]. Our approach is based on a strong lower bound on the approximate rank of a quantum state sampled from the Haar measure, a step-by-step analysis of the approximate rank of a magic-state teleportation protocol to sample from the Haar measure, and a result about trading Clifford operations with $T$ gates by [LKS18].

Related papers

• 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)
• Pseudoentanglement Ain't Cheap [0.43123403062068827]
  We show that any pseudoentangled state ensemble with a gap of $t$ bits of entropy requires $Omega(t)$ non-Clifford gates to prepare. This is tight up to polylogarithmic factors if linear-time-secure pseudorandom functions exist.
  arXiv  Detail & Related papers  (2024-03-29T19:39:59Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  We study the Shortest Path (SSP) problem with a linear mixture transition kernel. An agent repeatedly interacts with a environment and seeks to reach certain goal state while minimizing the cumulative cost. Existing works often assume a strictly positive lower bound of the iteration cost function or an upper bound of the expected length for the optimal policy.
  arXiv  Detail & Related papers  (2024-02-14T07:52:00Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
  In this paper we consider finding an approximate second-order stationary point (SOSP) that minimizes a twice different subject general non conic optimization. In particular, we propose a Newton-CG based-augmentedconjugate method for finding an approximate SOSP.
  arXiv  Detail & Related papers  (2023-01-10T20:43:29Z)
• Quantum Lower Bounds for Finding Stationary Points of Nonconvex Functions [8.495749905129278]
  Despite progress in classical lower bounds for non optimization, these bounds are still widely open. Omegabig(frac-1+ppp)$ regarding the first setting. Omegano()$ regarding the second setting. Omega()$ if gradient function is meand smooth. Omega()$ if gradient function is meand smooth. Omega()$ if gradient function is meand smooth. Omega()$ if gradient function is meand smooth.
  arXiv  Detail & Related papers  (2022-12-07T19:02:36Z)
• Average-case Speedup for Product Formulas [69.68937033275746]
  Product formulas, or Trotterization, are the oldest and still remain an appealing method to simulate quantum systems. We prove that the Trotter error exhibits a qualitatively better scaling for the vast majority of input states. Our results open doors to the study of quantum algorithms in the average case.
  arXiv  Detail & Related papers  (2021-11-09T18:49:48Z)
• 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)
• 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)
• Improved Strong Simulation of Universal Quantum Circuits [0.0]
  We find a scaling reduction in the stabilizer rank of the twelve-qubit tensored $T$ gate magic state. This lowers its bound to $2sim 0.463 t$ for multi-Pauli measurements on $t$ magic states. This constructively produces the most efficient strong simulation of the Clifford+$T$ gateset.
  arXiv  Detail & Related papers  (2020-12-21T23:13:20Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

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.