Tolerant Testing of Stabilizer States with Mixed State Inputs

• URL: http://arxiv.org/abs/2411.08765v1
• Date: Wed, 13 Nov 2024 16:51:03 GMT
• Title: Tolerant Testing of Stabilizer States with Mixed State Inputs
• Authors: Vishnu Iyer, Daniel Liang,
• Abstract summary: In particular, we give the first such algorithm that accepts mixed state inputs. Our algorithm distinguishes the two cases with sample complexity $textpoly (1/varepsilon)$ and time complexity $cdot textpoly (1/varepsilon)$.
• Score: 0.4604003661048266
• License:
• Abstract: We study the problem of tolerant testing of stabilizer states. In particular, we give the first such algorithm that accepts mixed state inputs. Formally, given a mixed state $\rho$ that either has fidelity at least $\varepsilon_1$ with some stabilizer pure state or fidelity at most $\varepsilon_2$ with all such states, where $\varepsilon_2 \leq \varepsilon_1^{O(1)}$, our algorithm distinguishes the two cases with sample complexity $\text{poly}(1/\varepsilon_1)$ and time complexity $O(n \cdot \text{poly}(1/\varepsilon_1))$.

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)
• Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits [55.957560311008926]
  We propose a piecewise stationary linear bandit (PSLB) model where the quality of an arm is measured by its return averaged over all contexts. PS$varepsilon$BAI$+$ is guaranteed to identify an $varepsilon$-optimal arm with probability $ge 1-delta$ and with a minimal number of samples.
  arXiv  Detail & Related papers  (2024-10-10T06:15:42Z)
• Polynomial-time tolerant testing stabilizer states [4.65004369765875]
  An algorithm is given copies of an unknown $n$-qubit quantum state $|psirangle promised $(i)$ $|psirangle$. We show that for every $varepsilon_1>0$ and $varepsilonleq varepsilon_C$, there is a $textsfpoly that decides which is the case. Our proof includes a new definition of Gowers norm for quantum states, an inverse theorem for the Gowers-$3$ norm of quantum states and new bounds on stabilizer covering for
  arXiv  Detail & Related papers  (2024-08-12T16:56:33Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  We show that any efficient SQ algorithm for the problem requires sample complexity at least $Omega(d1/2/(maxp, epsilon)2)$. Our lower bound suggests that this quadratic dependence on $1/epsilon$ is inherent for efficient algorithms.
  arXiv  Detail & Related papers  (2023-07-13T18:59:28Z)
• 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)
• The Price of Tolerance in Distribution Testing [31.10049510641336]
  We show the sample complexity to be [fracsqrtnvarepsilon2 + fracnlog n cdotmaxleftfracvarepsilon2, providing a smooth tradeoff between the two previously known cases. We also provide a similar characterization for the problem of tolerant equivalence testing, where both $p$ and $q$ are unknown.
  arXiv  Detail & Related papers  (2021-06-25T03:59:42Z)
• Quantum certification of state set and unitary channel [2.3889084213601346]
  We study efficient quantum certification algorithms for quantum state set and unitary quantum channel. We present an algorithm that uses $O(varepsilon-4ln |mathcalP|)$ copies of an unknown state to distinguish whether the unknown state is contained in or $varepsilon$-far from a finite set.
  arXiv  Detail & Related papers  (2021-03-04T05:17:49Z)
• Improved Sample Complexity for Incremental Autonomous Exploration in MDPs [132.88757893161699]
  We learn the set of $epsilon$-optimal goal-conditioned policies attaining all states that are incrementally reachable within $L$ steps. DisCo is the first algorithm that can return an $epsilon/c_min$-optimal policy for any cost-sensitive shortest-path problem.
  arXiv  Detail & Related papers  (2020-12-29T14:06:09Z)
• 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)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  Given an MDP with $S$ states, $A$ actions, the discount factor $gamma in (0,1)$, and an approximation threshold $epsilon > 0$, we provide a model-free algorithm to learn an $epsilon$-optimal policy. For small enough $epsilon$, we show an improved algorithm with sample complexity.
  arXiv  Detail & Related papers  (2020-06-06T13:34:41Z)
• Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm [100.11971836788437]
  We study the fixed-support Wasserstein barycenter problem (FS-WBP) We develop a provably fast textitdeterministic variant of the celebrated iterative Bregman projection (IBP) algorithm, named textscFastIBP.
  arXiv  Detail & Related papers  (2020-02-12T03:40:52Z)

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.