Certifying entanglement dimensionality by random Pauli sampling

• URL: http://arxiv.org/abs/2601.11040v1
• Date: Fri, 16 Jan 2026 07:12:38 GMT
• Title: Certifying entanglement dimensionality by random Pauli sampling
• Authors: Changhao Yi,
• Abstract summary: We introduce a Pauli-measurement-based algorithm to certify the Schmidt number of $n$-qubit pure states.<n>Our protocol achieves an average-case sample complexity of $caO(mathrmpoly(n)2)$, a substantial improvement over the $caO(2n )$ worst-case bound.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce a Pauli-measurement-based algorithm to certify the Schmidt number of $n$-qubit pure states. Our protocol achieves an average-case sample complexity of $\caO(\mathrm{poly}(n)χ^2)$, a substantial improvement over the $\caO(2^n χ)$ worst-case bound. By utilizing local pseudorandom unitaries, we ensure the worst case can be transformed into the average-case with high probability. This work establishes a scalable approach to high-dimensional entanglement certification and introduces a proof framework for random Pauli sampling.

Related papers

• Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterization [85.91302339486673]
  We study robust Markov decision processes (RMDPs) with general policy parameterization under s-rectangular and non-rectangular uncertainty sets.<n>We prove novel Lipschitz and Lipschitz-smoothness properties for general policy parameterizations that extends to infinite state spaces.<n>We design a projected gradient descent algorithm for s-rectangular uncertainty and a Frank-Wolfe algorithm for non-rectangular uncertainty.
  arXiv  Detail & Related papers  (2026-02-11T21:44:20Z)
• Provably Efficient Sample Complexity for Robust CMDP [7.060086147428817]
  We study the problem of learning policies that maximize cumulative reward while satisfying safety constraints.<n>We focus on robust constrained Markov decision processes (RCMDPs), where the agent must maximize reward while ensuring cumulative utility exceeds a threshold.<n>We propose a novel Robust constrained Value iteration (RCVI) algorithm with a sample complexity of $mathcaltildeO(|S||A|H5/2)$ achieving at most $$ violations.
  arXiv  Detail & Related papers  (2025-11-10T04:40:37Z)
• Oracle-based Uniform Sampling from Convex Bodies [2.087898608419977]
  We propose new Markov chain Monte Carlo algorithms to sample a uniform distribution on a convex body $K$.<n>Our algorithms are based on the Alternating Sampling Framework/proximal sampler, which uses Gibbs sampling on an augmented distribution.
  arXiv  Detail & Related papers  (2025-10-03T13:21:05Z)
• A Variance-Reduced Cubic-Regularized Newton for Policy Optimization [6.52142708235708]
  Existing second-order methods often suffer from suboptimal sample complexity or unrealistic assumptions about importance sampling.<n>To overcome these limitations, we propose VR-CR-PN, a variance-regularized Newton-reduced estimator.<n>As an additional contribution, we introduce a novel horizon for the expected return function, allowing the algorithm to achieve a uniform sample complexity.
  arXiv  Detail & Related papers  (2025-07-14T10:04:02Z)
• Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learning [50.81240969750462]
  We present first finite-sample analysis of policy evaluation in robust average Markov Decision Processes (PMDs)<n>We show that the robust Bellman operator is a contraction under a carefully constructed semi-norm, and developing a framework with controlled bias.<n>Our method achieves the order-optimal sample complexity of $tildemathcalO(epsilon-2)$ for robust policy evaluation and robust average reward estimation.
  arXiv  Detail & Related papers  (2025-02-24T03:55:09Z)
• Exponential improvements to the average-case hardness of BosonSampling [0.4515414068394328]
  We show that additive-error estimates to output probabilities of random BosonSampling experiments are $#P$-hard for any $delta>0$.<n>We also show, for the first time, a hardness of average-case classical sampling result for BosonSampling.
  arXiv  Detail & Related papers  (2024-11-07T09:41:45Z)
• Efficient distributed inner product estimation via Pauli sampling [0.04104921880358479]
  Cross-platform verification is the task of comparing the output states produced by different physical platforms.<n>We propose a novel protocol for this task based on Pauli sampling.
  arXiv  Detail & Related papers  (2024-05-10T15:40:18Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
  This paper investigates group distributionally robust optimization (GDRO) with the goal of learning a model that performs well over $m$ different distributions. To reduce the number of samples in each round from $m$ to 1, we cast GDRO as a two-player game, where one player conducts and the other executes an online algorithm for non-oblivious multi-armed bandits. In the second scenario, we propose to optimize the average top-$k$ risk instead of the maximum risk, thereby mitigating the impact of distributions.
  arXiv  Detail & Related papers  (2023-02-18T09:24:15Z)
• Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path [106.37656068276902]
  We study the sample complexity of learning an $epsilon$-optimal policy in the Shortest Path (SSP) problem. We derive complexity bounds when the learner has access to a generative model. We show that there exists a worst-case SSP instance with $S$ states, $A$ actions, minimum cost $c_min$, and maximum expected cost of the optimal policy over all states $B_star$.
  arXiv  Detail & Related papers  (2022-10-10T18:34:32Z)
• Nearly Optimal Latent State Decoding in Block MDPs [74.51224067640717]
  In episodic Block MDPs, the decision maker has access to rich observations or contexts generated from a small number of latent states. We are first interested in estimating the latent state decoding function based on data generated under a fixed behavior policy. We then study the problem of learning near-optimal policies in the reward-free framework.
  arXiv  Detail & Related papers  (2022-08-17T18:49:53Z)
• The Sample Complexity of Robust Covariance Testing [56.98280399449707]
  We are given i.i.d. samples from a distribution of the form $Z = (1-epsilon) X + epsilon B$, where $X$ is a zero-mean and unknown covariance Gaussian $mathcalN(0, Sigma)$. In the absence of contamination, prior work gave a simple tester for this hypothesis testing task that uses $O(d)$ samples. We prove a sample complexity lower bound of $Omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma
  arXiv  Detail & Related papers  (2020-12-31T18:24:41Z)
• Coherent randomized benchmarking [68.8204255655161]
  We show that superpositions of different random sequences rather than independent samples are used. We show that this leads to a uniform and simple protocol with significant advantages with respect to gates that can be benchmarked.
  arXiv  Detail & Related papers  (2020-10-26T18:00:34Z)

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.