Instance-Optimal Quantum State Certification with Entangled Measurements

• URL: http://arxiv.org/abs/2507.06010v1
• Date: Tue, 08 Jul 2025 14:15:46 GMT
• Title: Instance-Optimal Quantum State Certification with Entangled Measurements
• Authors: Ryan O'Donnell, Chirag Wadhwa,
• Abstract summary: We prove nearly instance-optimal bounds for quantum state certification when the tester can perform fully entangled measurements.<n>We prove our lower bounds using a novel quantum analogue of the Ingster-Suslina method, which is likely to be of independent interest.
• Score: 1.8416014644193066
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the task of quantum state certification: given a description of a hypothesis state $\sigma$ and multiple copies of an unknown state $\rho$, a tester aims to determine whether the two states are equal or $\epsilon$-far in trace distance. It is known that $\Theta(d/\epsilon^2)$ copies of $\rho$ are necessary and sufficient for this task, assuming the tester can make entangled measurements over all copies [CHW07,OW15,BOW19]. However, these bounds are for a worst-case $\sigma$, and it is not known what the optimal copy complexity is for this problem on an instance-by-instance basis. While such instance-optimal bounds have previously been shown for quantum state certification when the tester is limited to measurements unentangled across copies [CLO22,CLHL22], they remained open when testers are unrestricted in the kind of measurements they can perform. We address this open question by proving nearly instance-optimal bounds for quantum state certification when the tester can perform fully entangled measurements. Analogously to the unentangled setting, we show that the optimal copy complexity for certifying $\sigma$ is given by the worst-case complexity times the fidelity between $\sigma$ and the maximally mixed state. We prove our lower bounds using a novel quantum analogue of the Ingster-Suslina method, which is likely to be of independent interest. This method also allows us to recover the $\Omega(d/\epsilon^2)$ lower bound for mixedness testing [OW15], i.e., certification of the maximally mixed state, with a surprisingly simple proof.

Related papers

• Coherence in Property Testing: Quantum-Classical Collapses and Separations [42.44394412033434]
  We show that no tester can distinguish subset states of size $2n/8$ from $2n/4$ with probability better than $2-Theta(n)$.<n>We also show connections to disentangler and quantum-to-quantum transformation lower bounds.
  arXiv  Detail & Related papers  (2024-11-06T19:52:15Z)
• Certifying classes of $d$-outcome measurements with quantum steering [49.1574468325115]
  We provide a construction of a family of steering inequalities tailored to large classes of $d$-outcomes projective measurements. We prove that the maximal quantum violation of those inequalities can be used for certification of those measurements and the maximally entangled state of two qudits.
  arXiv  Detail & Related papers  (2024-10-27T15:32:53Z)
• 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)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• The role of shared randomness in quantum state certification with unentangled measurements [36.19846254657676]
  We study quantum state certification using unentangled quantum measurements. $Theta(d2/varepsilon2)$ copies are necessary and sufficient for state certification. We develop a unified lower bound framework for both fixed and randomized measurements.
  arXiv  Detail & Related papers  (2024-01-17T23:44:52Z)
• Validation tests of GBS quantum computers give evidence for quantum advantage with a decoherent target [62.997667081978825]
  We use positive-P phase-space simulations of grouped count probabilities as a fingerprint for verifying multi-mode data. We show how one can disprove faked data, and apply this to a classical count algorithm.
  arXiv  Detail & Related papers  (2022-11-07T12:00:45Z)
• 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)
• Distributed quantum inner product estimation [14.222887950206658]
  A benchmarking task known as cross-platform verification has been proposed that aims to estimate the fidelity of states prepared on two quantum computers. No quantum communication can be performed between the two physical platforms due to hardware constraints. We show that the sample complexity must be at least $Omega(max1/varepsilon2,sqrtd/varepsilon)$, even in the strongest setting.
  arXiv  Detail & Related papers  (2021-11-05T05:35:03Z)
• Toward Instance-Optimal State Certification With Incoherent Measurements [17.107198714549515]
  Given copies of unknown mixed state $rhoinmathbbCdtimes d$, decide whether $sigma = rho$ or $|sigma - rho|_mathsftr ge epsilon$. We show that the copy complexity for state certification using nonadaptive incoherent measurements is essentially given by the copy complexity for mixedness testing times the fidelity between $sigma$ and the maximally mixed state.
  arXiv  Detail & Related papers  (2021-02-25T18:59:11Z)
• 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)
• Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
  We study the problem of testing discrete distributions with a focus on the high probability regime. We provide the first algorithms for closeness and independence testing that are sample-optimal, within constant factors.
  arXiv  Detail & Related papers  (2020-09-14T16:09:17Z)
• Entanglement is Necessary for Optimal Quantum Property Testing [15.58122727889318]
  We show that with independent measurements, $Omega(d4/3/epsilon2)$ is necessary, even if the measurements are chosen adaptively. We develop several new techniques, including a chain-rule style proof of Paninski's lower bound for classical uniformity testing.
  arXiv  Detail & Related papers  (2020-04-16T18:28:39Z)

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.