Complexity of detecting large coefficients in the Pauli basis

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 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 ρ 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.