Toward Instance-Optimal State Certification With Incoherent Measurements
Jul 2, 2022
Sprecher:innen
Sitan Chen
Sprecher:in · 0 Follower:innen
Ryan O'Donnell
Sprecher:in · 0 Follower:innen
Über
We revisit the basic problem of quantum state certification: given copies of unknown mixed state ρ∈ℂ^d×d and the description of a mixed state σ, decide whether σ=ρ or ‖σ−ρ‖_𝗍𝗋 ≥ ϵ. When σ is maximally mixed, this is mixedness testing, and it is known that Ω(d^Θ(1)/ϵ^2) copies are necessary, where the exact exponent depends on the type of measurements the learner can make [OW15, BCL20], and in many of these settings there is a matching upper bound [OW15, BOW19, BCL20]. Can one avoid this d^Θ(1) dependence for certain kinds of mixed states σ, e.g. ones which are approximately low rank? More ambitiously, does there exist a simple functional f : ℂ^d×d → ℝ_≥0 for which one can show that Θ(f(σ)/ϵ^2) copies are necessary and sufficient for state certification with respect to any σ? Such instance-optimal bounds are known in the context of classical distribution testing, e.g. [VV17]. Here we give the first bounds of this nature for the quantum setting, showing (up to log factors) 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 σ and the maximally mixed state. Surprisingly, our bound differs substantially from instance optimal bounds for the classical problem, demonstrating a qualitative difference between the two settings.We revisit the basic problem of quantum state certification: given copies of unknown mixed state ρ∈ℂ^d×d and the description of a mixed state σ, decide whether σ=ρ or ‖σ−ρ‖_𝗍𝗋 ≥ ϵ. When σ is maximally mixed, this is mixedness testing, and it is known that Ω(d^Θ(1)/ϵ^2) copies are necessary, where the exact exponent depends on the type of measurements the learner can make [OW15, BCL20], and in many of these settings there is a matching upper bound [OW15, BOW19, BCL20]. Can one avoid this d^Θ(1)…
Über COLT
The conference is held annually since 1988 and has become the leading conference on Learning theory by maintaining a highly selective process for submissions. It is committed in high-quality articles in all theoretical aspects of machine learning and related topics.
Gefällt euch das Format? Vertraut auf SlidesLive, um euer nächstes Event festzuhalten!
Professionelle Aufzeichnung und Livestreaming – weltweit.
Freigeben
Empfohlene Videos
Präsentationen, deren Thema, Kategorie oder Sprecher:in ähnlich sind
Provably Efficient Reinforcement Learning with Linear Function Approximation
Später ansehen
Chi Jin, …
Clustering with Queries under Semi-Random Noise
Später ansehen
New Projection-free Algorithms for Online Convex Optimization with Adaptive Regret Guarantees
Später ansehen
Ben Kretzu, …
Width is Less Important than Depth in ReLU Neural Networks
Später ansehen
Gal Vardi, …
Smooth Contextual Bandits: Bridging the Parametric and Non-differentiable Regret Regimes
Später ansehen
