Skip to content
OpenContext

← All problems

Problem 3: Sample complexity

Consider a bipartite state ρAB\rho^{AB} with known local dimension dd, measured by uncharacterized local devices, so that the statistics are

p(ab∣xy)=Tr⁡ ⁣[(Ma∣xA⊗Mb∣yB) ρAB].p(ab|xy) = \operatorname{Tr}\!\left[(M^A_{a|x}\otimes M^B_{b|y})\,\rho^{AB}\right].

Let NC\mathcal{NC} be the polytope of statistics admitting a local ontological model whose response functions preserve the operational identities among each party's measurement effects, and let Etr(ρ):=min⁡σ∈Sep12∥ρ−σ∥1E_{\mathrm{tr}}(\rho):=\min_{\sigma\in\mathrm{Sep}}\frac12\|\rho-\sigma\|_1, where Sep\mathrm{Sep} is the set of separable states. Assume independent, identically prepared target copies, stationary and memoryless devices, the tomographic completeness needed to infer the local identities, and measurement families rich enough to certify every state with Etr(ρAB)≥γE_{\mathrm{tr}}(\rho^{AB})\geq\gamma in the exact-data limit.

What is the minimum total number of target copies required for a protocol returning either certify\mathsf{certify} or inconclusive\mathsf{inconclusive} to satisfy

Pr⁡(certify)≤δif p∈NC,Pr⁡(certify)≥1−δif Etr(ρAB)≥γ,\begin{aligned} \Pr(\mathsf{certify})&\leq\delta &&\text{if } p\in\mathcal{NC},\\ \Pr(\mathsf{certify})&\geq1-\delta &&\text{if } E_{\mathrm{tr}}(\rho^{AB})\geq\gamma, \end{aligned}

when the operational identities defining NC\mathcal{NC} must be inferred from the same finite experimental data? How does this number scale with dd, γ\gamma, δ\delta, and the number of distinct local effects, counting all copies used to infer the identities?

Status
open since 3 Oct 2026
Updated
3 Oct 2026
Posed by
Yujie Zhang, 3 Oct 2026

Background

Compared to the Bell and Kochen–Specker literature, experimental investigations of generalized contextuality remain relatively limited, with only a handful of experiments reported [, , , , , , 7, 8, 9]. Generalized contextuality tests can address loopholes arising in Kochen–Specker tests [10, , , ], and can be made robust [, , , , ]. Yet, despite our increasing ability to control high-dimensional systems, much of the development around testing generalized contextuality remains concerned with low-dimensional examples, and it is not entirely clear how these tests scale.

A first difficulty is establishing the operational equivalences that enter the definition of generalized noncontextuality. Some form of tomography is required for this purpose [10, ]. If one wishes to remain agnostic about the underlying theory, in the instrumentalist sense of operational probabilistic theories, this can be done within the framework of generalized probabilistic theories (GPTs) through theory-agnostic tomography, demonstrated experimentally for a photon's polarization degree of freedom [] and for a three-level photonic system [], or through other standard self-consistent tomography [] within the framework of quantum theory.

A second difficulty concerns how to assess the output of self-consistent tomography. Even with tomographically complete, exact statistics, state and effect representations are determined only up to compatible gauge transformations. A reconstruction-based sample-complexity analysis therefore needs an accuracy criterion that accounts for this freedom, for example by minimizing a distance over gauges, which may introduce a computationally demanding optimization. An alternative is to benchmark tomography together with the subsequent noncontextuality test through a gauge-independent certification task.

Self-consistent entanglement certification provides one such task [7, 21]. Every separable state produces statistics in the polytope NC\mathcal{NC} of the statement, so p∉NCp\notin\mathcal{NC} certifies entanglement, and both the operational identities and this verdict are independent of the tomographic gauge. Compared with standard tomography using calibrated measurements, an additional difficulty is that finite data introduce uncertainty not only in the probabilities but also in the estimate of NC\mathcal{NC} itself, through the inferred operational identities; the certification test must account for both sources of uncertainty.

When the exact identities are supplied independently, suitable local projective measurement families give an optimal target-copy cost of Θd(γ−2log⁡(1/δ))\Theta_d(\gamma^{-2}\log(1/\delta)) at fixed dd [21]. The additional cost of inferring those identities, while accounting for their statistical uncertainty, is what the problem asks for.

Relevance

Strengthening the connection between generalized contextuality and experimentation is a major goal, since any application ultimately rests on it, and experiments remain few compared to the Bell and Kochen–Specker literature. Generalized contextuality tests can address the loopholes of Kochen–Specker tests and can be made robust to noise, but they have mostly been developed for low-dimensional examples, and it is not clear how they scale. How complex it is to implement such a test has accordingly been receiving attention, and it is tied to the tomography that any test needs to establish its operational equivalences [10, ]. Self-consistent entanglement certification [7, 21] turns this into a well-posed question: it sidesteps the gauge freedom of self-consistent tomography, and the cost is already known when the identities are supplied independently, leaving the cost of inferring them open.

The problem traces to Goal III, Useful applications, through its witnessing theme: devising tests that are tighter, cheaper to implement and robust, scaling them to high-dimensional systems, and carrying out the corresponding experiments.

Significance

Resolving the problem would clarify the experimental resources needed for a concrete application of generalized noncontextuality, entanglement certification with uncharacterized local devices, counting the cost of establishing the operational identities and not only of estimating the probabilities. The scaling with dd and with the number of distinct local effects would say how such tests extend from the low-dimensional examples studied so far to larger systems, which is the scaling question the witnessing theme of Goal III raises, and comparing it with the Θd(γ−2log⁡(1/δ))\Theta_d(\gamma^{-2}\log(1/\delta)) cost when the identities are supplied would isolate the price of self-consistency. This bears directly on the goal of making the failure of classicality, as captured by generalized noncontextuality, a certified resource witnessed in experiments.

Self-consistent tomographyEntanglement certificationSample complexityExperimental tests

Permanent link:open-context.jan-bulling.com/contribution/3

References

  1. M. D. Mazurek, M. F. Pusey, R. Kunjwal, K. J. Resch and R. W. Spekkens, An experimental test of noncontextuality without unphysical idealizations, Nat. Commun. 7, 11780 (2016)
  2. M. D. Mazurek, M. F. Pusey, K. J. Resch and R. W. Spekkens, Experimentally bounding deviations from quantum theory in the landscape of generalized probabilistic theories, PRX Quantum 2, 020302 (2021)
  3. T. Giordani, R. Wagner, C. Esposito, A. Camillini, F. Hoch, G. Carvacho, C. Pentangelo, F. Ceccarelli, S. Piacentini, A. Crespi, N. Spagnolo, R. Osellame, E. F. Galvão and F. Sciarrino, Experimental certification of contextuality, coherence, and dimension in a programmable universal photonic processor, Sci. Adv. 9, eadj4249 (2023)
  4. R. W. Spekkens, D. H. Buzacott, A. J. Keehn, B. Toner and G. J. Pryde, Preparation contextuality powers parity-oblivious multiplexing, Phys. Rev. Lett. 102, 010401 (2009)
  5. X. Zhan, E. G. Cavalcanti, J. Li, Z. Bian, Y. Zhang, H. M. Wiseman and P. Xue, Experimental generalized contextuality with single-photon qubits, Optica 4, 966 (2017)
  6. A. Zhang, H. Xu, J. Xie, H. Zhang, B. J. Smith, M. S. Kim and L. Zhang, Experimental test of contextuality in quantum and classical systems, Phys. Rev. Lett. 122, 080401 (2019)
  7. Y. Zhang, J. Spodek, D. Schmid, C. Reid, L. J. Morrison, T. Jennewein, K. J. Resch and R. W. Spekkens, A new paradigm for entanglement certification using noncontextuality inequalities (2026) arXiv:2507.01122
  8. J. M. M. Gama, G. T. C. Cruz, M. Khoshbin, L. Catani, J. A. O. Huguenin and W. F. Balthazar, Experimental investigation of nonclassicality in the simplest scenario via the degrees of freedom of light (2026) arXiv:2601.16952
  9. V. P. Rossi, E. Polino, B. Polacchi, V. Cimini, D. Schmid, J. H. Selby, G. Corrielli, A. Crespi, R. Osellame, F. Sciarrino and A. B. Sainz, Theory-agnostic nonclassicality certification in an integrated photonic circuit (2026) arXiv:2609.18671
  10. M. F. Pusey, L. del Rio and B. Meyer, Contextuality without access to a tomographically complete set (2019) arXiv:1904.08699

Progress and history

  1. 3 Oct 2026
    PosedEntry created from Problem III of the companion paper.

Contributions

No contributions recorded yet.

Contribute to this problem

You need to be signed in. Every contribution is reviewed by a moderator before it appears, and is credited to the people you name.

Discussion

Sign in to join the discussion.

  • Rafael Wagner · 18 Nov 2026

    What does "sample complexity" means in this description?