arXiv:2610.08757
Complexity of self-consistent entanglement certification
Yujie Zhang
Abstract
In recent work Phys. Rev. X 16, 031057 (2026), we proposed a self-consistent approach to entanglement certification based on generalized noncontextuality. It requires no prior characterization of the measurement devices and, given access to all local measurements, can certify every entangled state in a Bell circuit. Here, we study the complexity of this protocol in a finite experiment. At fixed local dimension $d$, we show that the optimal number of distinct local effects needed to reach a trace-distance \textit{entanglement resolution} $γ$ is $Θ_d(γ^{-(d-1)})$. This scaling is necessary even when the measurements are tailored to the target state. Independent Haar-random projective measurements instead require $Θ_d(γ^{-(d-1)}\log(1/γ))$ effects. Finally, we show that, once the exact operational identities are known, $Θ_d(γ^{-2}\log(1/δ))$ copies of the target state are necessary and sufficient for certification with error probability at most $δ$. Determining the optimal sample complexity when those identities must instead be inferred from the same finite target-state data remains open.
AI Summary
The paper asks how finite measurement resources limit a previously proposed entanglement-certification protocol based on generalized noncontextuality. The protocol uses a Bell circuit without prior measurement calibration, testing statistics against models that preserve all local operational identities. With all local measurements available, it can certify every entangled state. At fixed local dimension $d$, the paper proves that the optimal number of distinct local effects per party, counted up to positive rescaling, needed to certify every state at trace distance at least $\gamma$ from the separable set is $\Theta_d(\gamma^{-(d-1)})$. No finite measurement family is universal. The lower bound also applies to worst-case targets when measurements can be tailored to the state. Independent Haar-random projective measurements require $\Theta_d(\gamma^{-(d-1)}\log(1/\gamma))$ effects instead. The central step relates the largest uncertified entanglement to the effects’ pure-state covering infidelity $\epsilon$, proving $\epsilon/[16d(d+1)]\leq\gamma^{\rm tr}\leq2d\epsilon$ for sufficiently small $\epsilon$. Local depolarization establishes the upper bound; measurement-independent Werner states establish the lower bound. Pure-state covering estimates then give the effect counts. If exact operational identities are supplied independently, the optimal target-copy complexity is $\Theta_d(\gamma^{-2}\log(1/\delta))$ for error probability $\delta$. The upper bound samples only $d^4$ product probabilities; quantum hypothesis testing gives the lower bound even for collective measurements. This excludes the cost of learning identities. Sample complexity when identities are inferred from the same finite target data remains open, as do optimal dimension dependence and computational-complexity comparisons with other separability approximations.
The optimal effect complexity and the Haar-random complexity were subsequently established through interactions with OpenAI Codex (using models 5.6 and later 6).
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- Preliminary version for upcoming talks