Pith. sign in

REVIEW 1 major objections 2 minor 20 references

Reviewed by Pith at T0; open to challenge.

T0 means a machine referee read the full paper against a public rubric. The mark states how deep the mechanical check went, never who wrote it. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.3

Deciding if a quantum state has a large non-identity Pauli coefficient is in QCMA but not in BQP unless NP ⊆ BQP.

2026-06-26 20:24 UTC pith:TRPIMC7N

load-bearing objection The paper reduces min-weight codeword to Pauli coefficient detection and shows the decision problem is not in BQP unless NP ⊆ BQP, with the reduction claimed to work for pure states at constant ε. the 1 major comments →

arxiv 2606.19545 v1 pith:TRPIMC7N submitted 2026-06-17 quant-ph

Complexity of detecting large coefficients in the Pauli basis

Santiago Cifuentes This is my paper
classification quant-ph
keywords quantum complexityPauli basisstate tomographyQCMABQPNPminimum weight codepromise problem
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines the computational complexity of determining whether a quantum state prepared by a circuit has a large overlap with any non-identity Pauli operator, or whether all such overlaps are small. It places the decision problem in QCMA and proves that membership in BQP would imply NP is contained in BQP. The hardness result applies even when the state is pure, with no qubits traced out, and when the threshold ε is a fixed constant. This shows that no efficient quantum procedure exists for locating the largest Pauli coefficients under the assumption that NP is not in BQP.

Core claim

We study the problem of deciding, given a mechanism to prepare a quantum state ρ and a value ε > 0, whether there is some non-identity Pauli matrix P such that |Tr(P ρ)| ≥ ε. We consider that the state ρ is described as the result of tracing out some of the qubits of a pure state prepared by a circuit C, and we assume the promise that either there is a Pauli matrix satisfying the stated condition or, instead, that for all non-identity Pauli matrices P it is the case that |Tr(Pρ)|≤ ε/2. The problem is in QCMA, and we prove that if it belongs to BQP then NP ⊆ BQP. The result is obtained through a reduction from the minimum-weight code problem, and it holds even when ρ is assumed to be a pure s

What carries the argument

Reduction from the minimum-weight code problem to the Pauli coefficient detection problem that preserves the promise gap for pure states and constant ε.

Load-bearing premise

The reduction from the minimum-weight code problem to the Pauli coefficient detection problem is correct and preserves the promise gap even for pure states prepared by circuits with no tracing out and constant ε.

What would settle it

A BQP algorithm solving the Pauli coefficient detection problem on circuit-prepared states would yield a BQP algorithm for the minimum-weight code problem.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • No efficient quantum tomographic procedures exist to find the largest coefficients of a quantum state in the Pauli basis under the hypothesis NP notsubseteq BQP.
  • The hardness persists even when the state is pure with no qubits traced out.
  • The result applies when ε is a fixed constant rather than vanishing with system size.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Quantum procedures for learning the Pauli expansion of states may need to incorporate classical verification steps rather than operating in BQP alone.
  • The link to coding theory problems raises the possibility of similar conditional hardness for learning tasks in other operator bases.
  • State certification protocols relying on finding dominant Pauli terms would inherit this complexity barrier.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

1 major / 2 minor

Summary. The manuscript defines the problem of deciding, given a circuit preparing a (possibly mixed) state ρ and ε>0, whether some non-identity Pauli P satisfies |Tr(Pρ)|≥ε, under the promise that either such a P exists or all non-identity Paulis satisfy |Tr(Pρ)|≤ε/2. It places the problem in QCMA and shows that membership in BQP would imply NP⊆BQP, via a Karp reduction from the minimum-weight codeword problem. The hardness holds even when ρ is pure (no tracing) and ε is a fixed constant.

Significance. If the reduction is correct, the result supplies a complexity-theoretic barrier to efficient quantum procedures for identifying large Pauli coefficients, even in the pure-state constant-ε regime, thereby answering an open question in the negative under the standard assumption NP⊈BQP. The explicit extension to pure states prepared by circuits without post-selection or tracing is a concrete strengthening.

major comments (1)
  1. [Reduction from minimum-weight codeword problem] Reduction (the construction that maps a code instance to a circuit C preparing ρ): the argument must explicitly verify that the output circuit produces a pure state (no qubits traced out), that low-weight codewords map to some non-identity P with |Tr(Pρ)|≥ε for constant ε independent of dimension, and that the no-case enforces |Tr(Pρ)|≤ε/2 for every non-identity P. These three properties are load-bearing for the strengthened pure-state constant-ε claim; the abstract asserts them but the explicit mapping and gap analysis require inspection.
minor comments (2)
  1. Clarify the precise promise-gap parameters (ε vs ε/2) in the problem statement and ensure they remain constant throughout the reduction analysis.
  2. Add a short paragraph contrasting the new pure-state result with the earlier mixed-state version to highlight what changes in the construction.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and for pinpointing the need for more explicit verification in the reduction. We address the major comment below and will revise the manuscript to strengthen the exposition of the pure-state constant-ε properties.

read point-by-point responses

  1. Referee: [Reduction from minimum-weight codeword problem] Reduction (the construction that maps a code instance to a circuit C preparing ρ): the argument must explicitly verify that the output circuit produces a pure state (no qubits traced out), that low-weight codewords map to some non-identity P with |Tr(Pρ)|≥ε for constant ε independent of dimension, and that the no-case enforces |Tr(Pρ)|≤ε/2 for every non-identity P. These three properties are load-bearing for the strengthened pure-state constant-ε claim; the abstract asserts them but the explicit mapping and gap analysis require inspection.

    Authors: We agree that the reduction requires a clearer, self-contained verification of these three properties to support the pure-state constant-ε claim. The construction encodes the code instance into a circuit on n qubits that prepares a pure state |ψ⟩ (no tracing occurs). Low-weight codewords are mapped to a non-identity Pauli P via a fixed-angle rotation on the corresponding support, yielding |Tr(Pρ)| ≥ ε with ε = 1/4 independent of n. In the no-case, the minimum-weight promise ensures |Tr(Pρ)| ≤ ε/2 for all non-identity P. We will add an explicit lemma (with a short proof) that isolates and verifies each of these three facts, without altering the reduction itself. revision: yes

Circularity Check

0 steps flagged

No circularity: hardness via external reduction from min-weight codeword problem

full rationale

The derivation establishes membership in QCMA and conditional NP-hardness for the Pauli detection problem by a direct Karp-style reduction from the classical minimum-weight codeword problem. This external NP-complete problem supplies the hardness independently of the quantum detection task; the abstract states the reduction works even for pure states (no tracing) and constant ε. No self-definitional equations, fitted parameters renamed as predictions, or load-bearing self-citations appear. The central claim does not reduce to its own inputs by construction and remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on standard complexity-theoretic assumptions and a reduction; no free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (2)
  • standard math The minimum-weight code problem is NP-hard
    The reduction is from this known problem; the abstract invokes it as the source of hardness.
  • domain assumption Quantum circuit model and trace-out operations are correctly formalized
    The state preparation model is standard in quantum complexity.

pith-pipeline@v0.9.1-grok · 5738 in / 1350 out tokens · 25382 ms · 2026-06-26T20:24:25.625990+00:00 · methodology

0 comments
read the original abstract

We study the problem of deciding, given a mechanism to prepare a quantum state $\rho$ and a value $\varepsilon > 0$, whether there is some non-identity Pauli matrix $P$ such that $|Tr(P \rho)| \geq \varepsilon$. We consider that the state $\rho$ is described as the result of tracing out some of the qubits of a pure state prepared by a circuit $C$, and we assume the promise that either there is a Pauli matrix satisfying the stated condition or, instead, that for all non-identity Pauli matrices $P$ it is the case that $|Tr(P\rho)|\leq \varepsilon/2$. The problem is in $QCMA$, and we prove that if it belongs to $BQP$ then $NP \subseteq BQP$. The result is obtained through a reduction from the minimum-weight code problem, and it holds even when $\rho$ is assumed to be a pure state (i.e. when no qubits are discarded) and $\varepsilon$ is constant. This resolves an open question regarding the existence of efficient tomographic procedures to find the largest coefficients of a quantum state in the Pauli basis: namely, they do not exist under the standard hypothesis $NP \nsubseteq BQP$.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

20 extracted references · 2 canonical work pages · 2 internal anchors

  1. [1]

    Shadow tomography of quantum states

    Scott Aaronson. Shadow tomography of quantum states. InProceedings of the 50th annual ACM SIGACT symposium on theory of computing, pages 325–338, 2018

    2018

  2. [2]

    A simple deterministic reduction for the gap minimum distance of code problem.IEEE Transactions on Information Theory, 60(10):6636–6645, 2014

    Per Austrin and Subhash Khot. A simple deterministic reduction for the gap minimum distance of code problem.IEEE Transactions on Information Theory, 60(10):6636–6645, 2014

    2014

  3. [3]

    Selective and efficient estimation of parameters for quantum process tomography.Physical review letters, 100(19):190403, 2008

    Ariel Bendersky, Fernando Pastawski, and Juan Pablo Paz. Selective and efficient estimation of parameters for quantum process tomography.Physical review letters, 100(19):190403, 2008

    2008

  4. [4]

    Selective and efficient quantum state tomography and its application to quantum process tomography.Physical Review A—Atomic, Molecular, and Optical Physics, 87(1):012122, 2013

    Ariel Bendersky and Juan Pablo Paz. Selective and efficient quantum state tomography and its application to quantum process tomography.Physical Review A—Atomic, Molecular, and Optical Physics, 87(1):012122, 2013

    2013

  5. [5]

    General theory of measurement with two copies of a quantum state.Physical review letters, 103(4):040404, 2009

    Ariel Bendersky, Juan Pablo Paz, and Marcelo Terra Cunha. General theory of measurement with two copies of a quantum state.Physical review letters, 103(4):040404, 2009

    2009

  6. [6]

    A deterministic reduction for the gap minimum distance problem

    Qi Cheng and Daqing Wan. A deterministic reduction for the gap minimum distance problem. InProceedings of the forty-first annual ACM symposium on Theory of computing, pages 33–38, 2009

    2009

  7. [7]

    Measuring the largest coefficients of a quantum state

    Nicol´ as Ciancaglini, Santiago Cifuentes, Guido Bellomo, Santiago Figueira, and Ariel Bendersky. Measuring the largest coefficients of a quantum state.arXiv preprint arXiv:2605.00341, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  8. [8]

    Efficient quantum state tomography.Nature communications, 1(1):149, 2010

    Marcus Cramer, Martin B Plenio, Steven T Flammia, Rolando Somma, David Gross, Stephen D Bartlett, Olivier Landon-Cardinal, David Poulin, and Yi-Kai Liu. Efficient quantum state tomography.Nature communications, 1(1):149, 2010

    2010

  9. [9]

    Hardness of approximating the minimum distance of a linear code.IEEE Transactions on Information Theory, 49(1):22–37, 2003

    Ilya Dumer, Daniele Micciancio, and Madhu Sudan. Hardness of approximating the minimum distance of a linear code.IEEE Transactions on Information Theory, 49(1):22–37, 2003

    2003

  10. [10]

    Efficient learning of quantum states prepared with few non-clifford gates.Quantum, 9:1907, 2025

    Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang. Efficient learning of quantum states prepared with few non-clifford gates.Quantum, 9:1907, 2025

    1907

  11. [11]

    Quantum state tomography via compressed sensing.Physical review letters, 105(15):150401, 2010

    David Gross, Yi-Kai Liu, Steven T Flammia, Stephen Becker, and Jens Eisert. Quantum state tomography via compressed sensing.Physical review letters, 105(15):150401, 2010

    2010

  12. [12]

    Bell sampling from quantum circuits.Physical Review Letters, 133(2):020601, 2024

    Dominik Hangleiter and Michael J Gullans. Bell sampling from quantum circuits.Physical Review Letters, 133(2):020601, 2024. 14

    2024

  13. [13]

    Aspects of generic entanglement

    Patrick Hayden, Debbie W Leung, and Andreas Winter. Aspects of generic entanglement. Communications in mathematical physics, 265(1):95–117, 2006

    2006

  14. [14]

    Efficient distributed inner-product estimation via pauli sampling.PRX Quantum, 6(3):030354, 2025

    Marcel Hinsche, Marios Ioannou, Sofiene Jerbi, Lorenzo Leone, Jens Eisert, and Jose Carrasco. Efficient distributed inner-product estimation via pauli sampling.PRX Quantum, 6(3):030354, 2025

    2025

  15. [15]

    Predicting many properties of a quantum system from very few measurements.Nature Physics, 16(10):1050–1057, 2020

    Hsin-Yuan Huang, Richard Kueng, and John Preskill. Predicting many properties of a quantum system from very few measurements.Nature Physics, 16(10):1050–1057, 2020

    2020

  16. [16]

    Efficient estimation of pauli observables by derandomization.Physical review letters, 127(3):030503, 2021

    Hsin-Yuan Huang, Richard Kueng, and John Preskill. Efficient estimation of pauli observables by derandomization.Physical review letters, 127(3):030503, 2021

    2021

  17. [17]

    Number 89

    Michel Ledoux.The concentration of measure phenomenon. Number 89. American Mathematical Soc., 2001

    2001

  18. [18]

    Learning t-doped stabilizer states

    Lorenzo Leone, Salvatore FE Oliviero, and Alioscia Hamma. Learning t-doped stabilizer states. Quantum, 8:1361, 2024

    2024

  19. [19]

    Learning stabilizer states by Bell sampling

    Ashley Montanaro. Learning stabilizer states by bell sampling.arXiv preprint arXiv:1707.04012, 2017

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  20. [20]

    The intractability of computing the minimum distance of a code.IEEE Transactions on Information Theory, 43(6):1757–1766, 1997

    Alexander Vardy. The intractability of computing the minimum distance of a code.IEEE Transactions on Information Theory, 43(6):1757–1766, 1997. 15

    1997