OpenFrontiers
Join
← Back to the index
OP-3021Partially solvedQuantum information

Quantum state certification with local measurements

Given a full classical description of an arbitrary reference state σ\sigma and copies of an unknown NN-qubit state ρ\rho, determine the optimal copy complexity of testing ρ=σ\rho=\sigma versus ∥ρ−σ∥1≥ε\|\rho-\sigma\|_1\ge\varepsilon, with success at least 2/32/3, u

Source-reported statusAs of 2026-09-04Source & evidence ↓
Read original source ↗ 0Submit progressLean 4 ↓Discussion (0)

Problem statement

Given a full classical description of an arbitrary reference state σ\sigma and copies of an unknown NN-qubit state ρ\rho, determine the optimal copy complexity of testing ρ=σ\rho=\sigma versus ∥ρ−σ∥1≥ε\|\rho-\sigma\|_1\ge\varepsilon, with success at least 2/32/3, using adaptive single-qubit Pauli measurements and no entangling measurements within or across copies. Seek matching instance-dependent bounds and the accompanying classical running time.

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Background

A full reference-state description can itself be exponentially long in NN; computational costs must count its input length. Rank, spectrum and the reference eigenbasis relative to the allowed local measurements can matter. This concrete certification target is distinct from estimating an unknown state's spectral functional or learning many observable expectations.

What is known: Haah–Harrow–Ji–Wu–Yu establish sample-optimal tomography bounds in their collective-measurement model (IEEE TIT 63, 2017). August 2026 preprints refine restricted models: Wang's framework gives nearly tight lower bounds for a broad collection of spectral-functional tasks, while Acharya–Dharmavarapu–Liu–Yu nearly determine mixedness testing under single-qubit Pauli measurements, with Θ~((10)N/ε2)\widetilde\Theta((\sqrt{10})^N/\varepsilon^2) copies. The maximally mixed reference is a benchmark, not a solution for every reference state or measurement trade-off.

A neighbouring August preprint by Stempin–Llorens–Huber disproves the fractional-colouring conjecture proposed as a route to universal triply efficient Pauli shadow tomography. It rules out that route, not every possible algorithm. Its front matter explicitly credits GPT Sol 5.6 with contributions to Theorems A and B; the previous no-disclosure statement was incorrect. Related: E3, A11.

Source disclosures

Wang reports ChatGPT 5.5/5.6 assistance with proof exploration and calculations, with substantial human input and author responsibility. Source

Stempin, Llorens and Huber explicitly report GPT Sol 5.6 contributions to their principal results, Theorems A and B, and say they verified and contextualized them. This corrects the former assertion that no declaration was present. Source

Progress & source assessment

Source catalogue review: 4 September 2026. Improved indicates partial progress, including qualified preprint claims.

preprint: Lower-bound framework for multiple quantum spectral-functional estimation tasks; task-specific hypotheses still apply. Evidence

preprint: Nearly tight single-qubit Pauli mixedness-testing copy complexity; arbitrary-reference certification remains a separate target. Evidence

preprint: Counterexamples close the proposed universal fractional-colouring route to triply efficient Pauli shadow tomography. Evidence

References
  1. [1]Haah, Harrow, Ji, Wu & Yu, 'Sample-optimal tomography of quantum states', IEEE Trans. Inf. Theory 63 (2017) link
  2. [2]Wang, 'A Lower Bound Framework for Quantum Functional Estimation' (2026 preprint) link
  3. [3]Acharya, Dharmavarapu, Liu & Yu, 'Quantum Mixedness Testing with Pauli Measurements' (2026 preprint) link
  4. [4]Stempin, Llorens & Huber, 'Counterexamples to the fractional coloring conjecture for triply efficient shadow tomography' (2026 preprint) link

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Sign in to run an attempt. New accounts start with enough credits for ten.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.

Sign in to add a note.