Complexity of detecting large coefficients in the Pauli basis

Technical Summary: Complexity of Detecting Large Coefficients in the Pauli Basis

Problem Definition
This paper addresses the computational problem of determining whether a quantum state $\rho$, prepared by a succinct quantum circuit $C$, possesses a "large" coefficient in the Pauli basis. Formally, given a state preparation circuit $C$ and a threshold $\epsilon > 0$, the task is to decide if there exists a non-identity Pauli matrix $P \in \mathcal{P}_n \setminus \{I^{\otimes n}\}$ such that $|\text{Tr}(P\rho)| \ge \epsilon$. The problem is framed as a promise problem: the algorithm must return "Yes" if such a $P$ exists, and "No" if for all non-identity $P$, $|\text{Tr}(P\rho)| \le \epsilon/2$. The state $\rho$ is defined as the partial trace of a pure state generated by $C$, though the paper also considers the case where $\rho$ is pure (no qubits discarded).

Methodology
The core methodology involves a complexity-theoretic reduction from the $\lambda$-Gap Minimum-Weight Codeword ($\lambda$-GapMWC) problem, a known hard problem for classical linear codes.

1. Reduction Construction: The authors construct a mapping from an instance $(G, t)$ of $\lambda$-GapMWC (where $G$ is a generator matrix and $t$ is a threshold) to an instance of the Large Pauli Coefficient (LPC) problem.

   • They define a random variable $V$ by uniformly sampling columns from a padded version of $G$.
   • They construct a density matrix $\rho_{G,t}$ as the expectation of $|V\rangle\langle V|$ over $k$ independent copies of $V$, effectively creating a diagonal state in the computational basis.
   • Using Lemma 3.2, they establish a direct algebraic link between the Hamming weight of codewords $xG$ and the expectation values of diagonal Pauli operators $Z^x$ on $\rho_{G,t}$:
     $$\text{Tr}(Z^x \rho_{G,t}) = \left(1 - \frac{2\text{wt}(xG)}{N}\right)^k$$
   • By carefully choosing the parameters $N$ (padding size) and $k$ (number of samples), they ensure that if a codeword with weight $\le t$ exists, the corresponding Pauli expectation exceeds $\epsilon$, whereas if all codewords have weight $> \lambda t$, all expectations remain below $\epsilon/2$.

2. Extension to Pure States: To address the case where $\rho$ must be a pure state, the authors employ a "hiding" technique. They utilize a unitary operator $U$ (guaranteed to exist by Lemma 3.3 and 3.4 via concentration of measure arguments) that suppresses the expectation values of non-identity Pauli operators acting on an auxiliary "sample register." This allows the reduction to embed the mixed-state logic into a pure state $|\Psi_{G,t}\rangle$ without introducing spurious large coefficients.

3. Complexity Analysis:

   • Membership: The paper demonstrates that LPC is in QCMA. A classical witness consists of the description of the Pauli matrix $P$. A quantum verifier can estimate $\text{Tr}(P\rho)$ using repeated Pauli measurements. If $\epsilon$ is inverse-polynomial in the circuit size, this verification runs in polynomial time.
   • Hardness: The reduction from $\lambda$-GapMWC to LPC is performed in deterministic polynomial time. Since $\lambda$-GapMWC is hard for NP (specifically, solving it in BQP implies $\text{NP} \subseteq \text{BQP}$), the hardness transfers to LPC.

Key Contributions and Results

• QCMA Membership: The problem is shown to be in QCMA, confirming that a classical description of the Pauli operator suffices for verification.
• NP-Hardness under BQP: The primary result is that if LPC were in BQP (solvable by a polynomial-time quantum algorithm), then NP $\subseteq$ BQP. This implies that, under the standard assumption that $\text{NP} \not\subseteq \text{BQP}$, no efficient quantum algorithm exists to detect large Pauli coefficients for general states.
• Pure State Hardness: The hardness result holds even when the input state is restricted to be pure, resolving the question of whether discarding qubits (mixed states) is the source of the difficulty.
• BQP-Hardness: The paper further proves that LPC is BQP-hard. This suggests that the problem is likely not in NP (unless $\text{BQP} \subseteq \text{NP}$), indicating that a purely classical witness characterization is unlikely.
• Constant Threshold: The hardness holds even when $\epsilon$ is a constant independent of the input size, ruling out the possibility that the difficulty arises solely from requiring high-precision detection.

Significance and Claims
The paper claims to resolve an open question regarding the existence of efficient tomographic procedures for finding the largest coefficients of a quantum state in the Pauli basis. The results indicate that such efficient procedures do not exist under standard complexity assumptions.

The authors note that while they establish membership in QCMA and hardness for NP (and BQP-hardness), they do not prove a tight bound (e.g., QCMA-completeness). However, they argue that the results are sufficient to clarify the landscape: algorithms intended to find large Pauli coefficients with polynomial resources must rely on additional structural assumptions about the state, such as Pauli sparsity, stabilizer-like behavior, low rank, locality, or low entanglement. Without such constraints, the general problem remains computationally intractable.