{"id":"arxiv/2606.19545","url":"https://arxiv.org/abs/2606.19545","tags":["quant-ph"],"score":0,"title":"Complexity of detecting large coefficients in the Pauli basis","domain":"quant-ph","source":"arxiv","authors":["Santiago Cifuentes"],"reviews":0,"subject":"quant-ph","summary":"We study the problem of deciding, given a mechanism to prepare a quantum state $ρ$ and a value $\\varepsilon > 0$, whether there is some non-identity Pauli matrix $P$ such that $|Tr(P ρ)| \\geq \\varepsilon$. 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ρ)|\\leq \\varepsilon/2$. The problem is in $QCMA$, and we prove that if it…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-06-17","reactions":{}}