Q14: Is the EPR∗ problem in BPP?

The conjecture

For fixed $b\in[-1,1]$ , let $\begin{aligned}K_b={}&(b+1)\lvert\psi^+\rangle\langle\psi^+\rvert\\&+(b-1)\lvert\phi^-\rangle\langle\phi^-\rvert.\end{aligned}$ Is deciding the ground-energy promise problem for $H=\sum_e w_e(K_b)_e$ , with positive polynomially bounded weights and inverse-polynomial promise gap, in $\mathsf{BPP}$ ? This is the $\mathrm{EPR}^{*}$ tractability conjecture of Marwaha–Sud.

Scope & assumptions

$\mathsf{BQP}$ containment is established via Rayudu–Takahashi’s Lee–Yang theorem, building on Wong–Bravyi–Gosset–Liu. The open conjecture here is $\mathsf{BPP}$ containment. Use one shared $b$ within an instance. The theorem does not assert a zero-field spectral gap.

Why this is interesting

The $\mathsf{BQP}$ upper bound leaves a concrete classical-versus-quantum question on the same side of the complexity transition.

Explicit variants

Exchange-symmetric classification
For a fixed two-qubit interaction $h$ satisfying $[h,\operatorname{SWAP}]=0$ , classify the promise problem for positive weighted sums of copies of $h$ . Allow splitting and mixing within the triplet block, and state whether local fields and geometric restrictions are included. Determine which aspects of singlet/triplet ordering and degeneracy govern $\mathsf{QMA}$ , $\mathsf{StoqMA}$ , $\mathsf{QCMA}$ , or tractable regimes. Local eigenvalue ordering alone is a proposed organizing principle, not a complete classification.

A place to start

Study the simplest $\mathrm{EPR}^{*}$ instances and identify what a proposed classical sampler must control.

Related work

These works provide context and established results. They need not be the origin of this exact formulation.

Discuss this question

Continue on GitHub Propose a research question

Reading is public. Posting requires a GitHub account. You can also write to Kunal.