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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.19545
curl -X POST /api/v1/records/arxiv/2606.19545/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.19545/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'