Quantum Mixedness Testing with Pauli Measurements

• URL: http://arxiv.org/abs/2608.18839v1
• Date: Wed, 19 Aug 2026 11:58:16 GMT
• Title: Quantum Mixedness Testing with Pauli Measurements
• Abstract summary: Given $n$ copies of an $N$-qubit state $$, determine whether $= mathbbI_d/d$ or $|-mathbbI_d/d|_1 geq varepsilon$ with high probability, where $d = 2N$.<n>We provide a nearly complete picture of single-qubit mixedness tesing by showing $n = widetildeleft(sqrt10N/varepsilon2right)$
• Score: 35.1480951977013
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider a fundamental problem of \emph{mixedness testing}: Given $n$ copies of an $N$-qubit state $ρ$, determine whether $ρ= \mathbb{I}_d/d$ or $\|ρ-\mathbb{I}_d/d\|_1 \geq \varepsilon$ with high probability, where $d = 2^N$. In particular, we focus on performing this task in the practical setting of single-qubit measurements, where measurements are prepared independently on each qubit. We provide a nearly complete picture of single-qubit mixedness tesing by showing $n = \widetildeΘ\left(\sqrt{10}^N/\varepsilon^2\right)$. To establish our lower bound, we introduce a new measurement-dependent lower bound framework for adaptive single-copy state certification. For the upper bound, we present a randomized Pauli basis measurement protocol, which relies on a new primitive for computationally efficient uniformity testing of correlation-concentrated distributions on the Boolean hypercube.

Related papers

• Robust quantum state certification and uncertainty principles for total influence [5.7531205491708945]
  We show that nonadaptive single-qubit Pauli measurements suffice to test whether an unknown $n$-qubit state $$ is $varepsilon$-close to or $O(varepsilon)$-far from an ideal target state $|rangle$.<n>The test uses $O(varepsilon-2log (1/)$ copies of $$ to achieve confidence $1-$, which is information-theoretically optimal even among protocols with arbitrary joint measurements.
  arXiv  Detail & Related papers  (2026-07-29T17:53:23Z)
• Optimal Quantum State Testing Even with Limited Entanglement [13.84229509611525]
  We consider the fundamental task of quantum state certification: given copies of an unknown quantum state $$, test whether it matches some target state $$ or is $$-far from it.<n>Our main result is a smooth copy complexity upper bound for state certification as a function of $t$, which achieves a near-optimal rate at $t = d2$.<n>We extend our techniques to develop new algorithms for the related tasks of mixedness testing and purity estimation, and show tradeoffs achieving the optimal rates for these problems at $t = d2$ as well.
  arXiv  Detail & Related papers  (2026-04-08T18:01:51Z)
• The Power of Two Bases: Robust and copy-optimal certification of nearly all quantum states with few-qubit measurements [5.266360532660872]
  We present robust certification protocols based on few-qubit measurements.<n>Our tests are based on a new uncertainty principle for conditional fidelities.
  arXiv  Detail & Related papers  (2026-02-12T06:08:04Z)
• Pauli Measurements Are Near-Optimal for Single-Qubit Tomography [34.83118849281207]
  We show that at least $Omegaleft(frac10NsqrtN varepsilon2right)$ copies are required to learn an $N$-qubit state $rhoinmathbbCdtimes d,d=2N$ to within $varepsilon$ trace distance.
  arXiv  Detail & Related papers  (2025-07-29T16:50:19Z)
• Pauli measurements are not optimal for single-copy tomography [34.83118849281207]
  We prove a stronger upper bound of $O(frac10Nepsilon2)$ and a lower bound of $Omega(frac9.118Nepsilon2)$.<n>This demonstrates the first known separation between Pauli measurements and structured POVMs.
  arXiv  Detail & Related papers  (2025-02-25T13:03:45Z)
• Testing the Feasibility of Linear Programs with Bandit Feedback [53.40256244941895]
  We develop a test based on low-regret algorithms and a nonasymptotic law of iterated logarithms. We prove that this test is reliable, and adapts to the signal level,' $Gamma,$ of any instance. We complement this by a minimax lower bound $(Omegad/Gamma2)$ for sample costs of reliable tests.
  arXiv  Detail & Related papers  (2024-06-21T20:56:35Z)
• Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
  We introduce an observation-matrix-based framework for fully asynchronous online Federated Learning with adversaries. Our main result is that the proposed algorithm almost surely converges to the desired mean $mu.$ We derive this convergence using a novel differential-inclusion-based two-timescale analysis.
  arXiv  Detail & Related papers  (2023-04-04T04:32:29Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  This work considers the sample complexity of obtaining an $varepsilon$-optimal policy in an average reward Markov Decision Process (AMDP) We prove an upper bound of $widetilde O(H varepsilon-3 ln frac1delta)$ samples per state-action pair, where $H := sp(h*)$ is the span of bias of any optimal policy, $varepsilon$ is the accuracy and $delta$ is the failure probability.
  arXiv  Detail & Related papers  (2022-12-01T15:57:58Z)
• Tight Bounds for Quantum State Certification with Incoherent Measurements [18.566266990940374]
  When $sigma$ is the maximally mixed state $frac1d I_d$, this is known as mixedness testing. We focus on algorithms which use incoherent measurements, i.e. which only measure one copy of $rho$ at a time.
  arXiv  Detail & Related papers  (2022-04-14T17:59:31Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  We prove a Lipschitzness lower bound $Omega(sqrtn/p)$ of robustness of interpolating neural network parameters on arbitrary distributions. We then show the potential benefit of overparametrization for smooth data when $n=mathrmpoly(d)$. We disprove the potential existence of an $O(1)$-Lipschitz robust interpolating function when $n=exp(omega(d))$.
  arXiv  Detail & Related papers  (2022-02-23T16:10:23Z)
• 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)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  Asynchronous Q-learning aims to learn the optimal action-value function (or Q-function) of a Markov decision process (MDP) We show that the number of samples needed to yield an entrywise $varepsilon$-accurate estimate of the Q-function is at most on the order of $frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$ up to some logarithmic factor.
  arXiv  Detail & Related papers  (2020-06-04T17:51:00Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  We output a distribution from $mathcalQ$ whose total variation distance to $p$ is comparable to the best such distribution. We show that the constraint of local differential privacy incurs an exponential increase in cost. Our algorithms result in exponential improvements on the round complexity of previous methods.
  arXiv  Detail & Related papers  (2020-02-21T18:30:48Z)

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.