A Dichotomy for MIP* in the Presence of Unital Noise

Haigang Zhou; Minglong Qin; Penghui Yao; Yangjing Dong; Zhenyu Jiang

REVIEW

A Dichotomy for MIP* in the Presence of Unital Noise

Yangjing Dong, Zhenyu Jiang, Minglong Qin, Penghui Yao, Haigang Zhou

Quantum Physics · Submitted 30 Sep 2026

Pith's verdict: A complete dichotomy for fixed two-qubit noisy resources, with the NEXP side riding on one hard, correct-looking but verification-heavy lemma (Pauli folding almost-multiplicativity).

T0 · AI review

How this review was made: An AI referee (deepseek/deepseek-v4-flash) read the paper on October 1, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 1 major objection · 6 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv ID2609.39318 (version 2)

Pith ID4WHPZIYP, Pith's permanent record of this paper and its review

CitationHaigang Zhou, Minglong Qin, Penghui Yao, Yangjing Dong, Zhenyu Jiang. "A Dichotomy for MIP* in the Presence of Unital Noise." arXiv:2609.39318 (2026). https://pith.science/paper/4WHPZIYP

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

Read it. The dichotomy is real: for fixed two-qubit states with maximally mixed marginals, separable or rho_max<1 gives MIP^psi[poly,poly] = NEXP, and entangled with rho_max=1 gives RE. The notable claim: a dephased EPR pair keeps full MIP*=RE power. That alone is worth the paper.

What's new is real. They remove the constant-answer restriction from [DFN+25], getting D = poly(t) and k = poly(log t) — an exponential improvement over the earlier exp(poly(t)) copy bound — and they resolve the rho_max=1 boundary, which prior work left untouched. Two techniques deserve credit: the square-root low-degree approximation that preserves positivity without the per-outcome truncation-repair losses, and Pauli folding, dimension reduction for noncommutative products done with Mobius inversion and character multipliers rather than an invariance principle.

The soft spot is exactly where the stress-test lands. The poly-answer NEXP upper bound rides on Lemma 4.24 (almost-multiplicativity of Pauli folding), deferred to Appendix C. The needed bound C1*k^64/D has to be independent of n and polynomial in k; an n-dependence or an exponential-in-k constant would break the 2^poly(N) certificate size. I traced the proof structure: the first Mobius inversion factors phases over hash fibers with D^{-r(pi)}; the auxiliary polynomial has degree at most 4k per variable; Markov brothers gives per-rank terms ~(k^20/D)^r, so declaring D >= C0*k^64 has genuine slack. It looks right, but the chain is long and the constants are asserted, not machine-checked. That is normal for the subfield, but it is the part a referee must actually read. The paper tells you so itself — Section 1.3 flags Appendix C as the most challenging part.

The rho_max=1 branch is independent of that lemma; I checked the twirl fixed-point, F_{m,lambda} >= lambda^2, and the Hamming-code extraction — internally consistent. The NEXP lower bound comes from [DFN+25], a published J. ACM result with exactly these hypotheses; no circularity concern worth raising.

For quantum complexity readers, this is the natural completion of the line started by QY21 and DFN+25. Send it to a serious referee — the risk is verification burden, not an evident conceptual gap.

What would settle it

One concrete check: compute the exact squared multiplication error $\mathbb{E}_{h,r}\|\Phi_{h,r}(AB)-\Phi_{h,r}(A)\Phi_{h,r}(B)\|$_2^{2}$$ for small explicit instances, say $n=5$ qubits, degree $k=2$, and $D$ around $$C_0k^{{64}}$$, and test whether it is bounded by $C_{\mathrm{mul}}$k^{{64}}$$D^{{-1}}$\|A\|$_4^{2}$\|B\|$_4^{2}$$ with constants independent of $n$; if the error grew with $n$ or superpolynomially in $k$, the $\mathsf{NEXP}$ upper bound would collapse. Separately, apply the Hamming-partition plus bilateral Pauli-twirl conversion to a dephased EPR pair at small dimension $d=2^m$ and verify that the extracted exact EPR weight $F_{m,\$\lambda$}$ is at least $\$lambda^{2}$$ and independent of $m$; if some entangled $\rho_{\max}=1$ state failed to yield such a dimension-independent weight, the $\mathsf{RE}$ branch would fail.

Referee report

Significance

If correct, this result completely resolves the resource-power question for two-qubit states with maximally mixed marginals: maximal correlation together with entanglement fully determines whether the shared resource retains the full power of MIP* = RE or collapses to NEXP, with no intermediate regimes. A notable corollary is that dephased EPR pairs, which have rho_max = 1, achieve the full MIP* power, showing that perfect EPR pairs are not the only resource realizing RE. The two new techniques are of independent interest: a positivity-preserving low-degree approximation scheme that treats an entire POVM collectively via square-root factorizations, and a Pauli folding dimension-reduction map with an almost-multiplicativity estimate that is independent of the original qubit count. The paper deserves credit for shipping structured stepwise proofs with full appendices (Smoothing, Low-Degree Approximation, Dimension Reduction, Rounding, Succinct Certificates), explicit certificate-size bounds, and clearly headlineable falsifiable predictions.

Major objections (1)

[App. C, Lemma 4.24] The almost-multiplicativity estimate (C_1 k^64/D) prod ||A_j||_4^2 for the randomized Pauli-hashing map is the single load-bearing step for the poly-answer NEXP upper bound in Theorems 3.1, 3.4 and 3.6: the bound must be independent of the original qubit number n and polynomial in the degree k in order for D = poly(t) and k = poly(log t) to keep the certificate size poly(q,t)(3eD)^{O(k)} inside 2^{poly(N)}. I traced the two-stage Mobius-inversion structure and the auxiliary-polynomial argument and found the framework sound: the rank-r per-term contributions scale like (C k^{O(1)}/D)^r with v <= 2r <= 4k controlling the number of blocks, and the announced threshold D >= C_0 k^64 has genuine slack over what the Markov-brothers and coefficient-counting bounds appear to require. I therefore do not see a blocking error. I would nevertheless ask the authors to insert in Appendix C a short remark making the slack explicit (which inequalities force which power of k, and what the largest apparent exponent is before the final k^64 is imposed), because the k^64/D bound and its n-independence carry the entire poly-answer certificate argument, and making the constant accounting checkable would substantially lower the verification burden on readers.

Minor objections (6)

[Section 1 / Abstract] The sentence 'A basic example a dephased EPR pair, which retains quantum maximal correlation 1' is missing a verb ('is'); the same garbled phrasing appears twice.
[Author block] A stray '/'pilcrow' formatting artifact appears after the fourth author's affiliation; this looks like a LaTeX/WorldBank-style toolchain remnant and should be removed.
[Section 2.4, Definition 2.23] In the displayed formula for the truncation f^{<=k}, the text 'bf(chi)chi(k>=0)' appears to contain a stray 'k' after the character chi; the intended expression is presumably bf(chi)chi with the condition (k>=0) annotated alongside.
[Section 2.6, footnote 2] The parenthetical 'it does not infect the strategies' is informal; consider rewording to something like 'the transpose maps POVMs bijectively to POVMs, so this convention entails no loss of generality.'
[Reference [Ope26]] The citation to 'OpenAI. Quantum parallel repetition' in an unusual venue (Ten Advances in Mathematics and Theoretical Computer Science, 2026) is curious; since the authors state that Yuen's polynomial-decay theorem suffices, I suggest either removing this citation or clarifying its status (e.g., preprint), so that no reader mistakes it for a load-bearing source.
[Section 4.5.1, Eq. (54)] The count M(D,k) <= (3eD)^k of degree-at-most-k Pauli strings on D qubits is stated without proof; a one-line derivation (sum_{j=0}^k 3^j binom(D,j) <= (1+3)^D and compared against (3eD/k)^k / ... ) would make the 2^{poly(N)} certificate bound immediately verifiable.

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

For every fixed two-qubit state $\psi$ with maximally mixed marginals, the proof class $\mathsf{MIP}^{\psi}[\mathrm{poly},\mathrm{poly}]$ equals $\mathsf{NEXP}=\mathsf{MIP}$ when $\psi$ is separable or has quantum maximal…

The reading

This paper proves a complete dichotomy for the computational power of two-prover one-round quantum interactive proofs in which the provers share arbitrarily many copies of a fixed two-qubit state $\psi$ with maximally mixed marginals. For such a state, the class $\mathsf{MIP}^{\psi}[\mathrm{poly},\mathrm{poly}]$ is $\mathsf{NEXP}=\mathsf{MIP}$ when $\psi$ is separable or its quantum maximal correlation $\rho_{\max}(\psi)$ is below one, and it is $\mathsf{RE}$ when $\psi$ is entangled with $\rho_{\max}(\psi)=1$. The dichotomy says that, within this entire resource family, only the joint data of maximal correlation and entanglement matter: there are no intermediate possibilities, and polynomial-length answers add no power beyond constant-length answers in either branch. It also shows that perfect EPR pairs are not the only shared resource that realizes the full power $\mathsf{MIP}^*=\mathsf{RE}$, since entangled states with maximal correlation one, such as dephased EPR pairs, recover it.

What carries the argument

Two techniques carry the argument. First, a positivity-preserving low-degree approximation framework for quantum measurements: rather than truncating positive operators directly in the Pauli basis, the authors approximate the square roots of smoothed POVM elements $\sqrt{\mathcal{M}$_a^{{(u)}}$}$ by low-degree block operators $Q_a$, so that $Q_a^\dagger Q_a$ is positive by construction and the whole POVM is controlled by a single relative-entropy bound $\log t$ obtained from a complete strong data-processing inequality for the correlation channel. Second, a dimension-reduction method called Pauli folding: a randomized linear map $\Phi_{h,r}$ from operators on $n$ qubits to $D$ qubits, defined by hashing coordinates into $D$ buckets and multiplying each Pauli string by a random sign, which is approximately multiplicative on operators of Pauli degree at most $k$: the almost-multiplicativity theorem (Lemma 4.24) bounds $\mathbb{E}\|\Phi(AB)-\Phi(A)\Phi(B)\|$_2^{2}$ \leq C_{\mathrm{mul}}$k^{{64}}$$D^{{-1}}$\|A\|$_4^{2}$\|B\|$_4^{2}$$ with constants independent of $n$, proved by Möbius inversion on the partition lattice that keeps Fourier cancellations from coordinate collisions intact. These give $D=\mathrm{poly}(t)$ and $k=\mathrm{poly}(\log t)$, hence certificates of size $$2^{{\mathrm{poly}}$(N)}$, which is what yields the $\mathsf{NEXP}$ upper bound for polynomial-length answers.

Extended reading notes

Core claim

The central claim is Theorem 1.1. Let $\psi$ be a fixed two-qubit state with maximally mixed marginals, used by two noncommunicating provers who share arbitrarily many copies of $\psi$ and nothing else. If $\psi$ is separable or $\rho_{\max}(\psi)<1$, then $\mathsf{MIP}^{\psi}[\mathrm{poly},\mathrm{poly}]=\mathsf{NEXP}=\mathsf{MIP}$; if $\psi$ is entangled and $\rho_{\max}(\psi)=1$, then $\mathsf{MIP}^{\psi}[\mathrm{poly},\mathrm{poly}]=\mathsf{RE}$. The proof removes the constant-answer restriction of the prior work [DFN+25] and completes the remaining case, where maximal correlation one does not by itself decide the power because even a shared classical random bit has maximal correlation one. The decisive distinction at $\rho_{\max}=1$ is entanglement: the authors show that any entangled boundary state $\Psi_\$\lambda$$ contains an exact maximally entangled component of weight at least $\$lambda^{2}$$ in every finite dimension, extractable by a Hamming-partition relabeling followed by bilateral Pauli twirling, so that constant-answer EPR protocols for $\mathsf{RE}$ survive with a fixed transmission loss and can be amplified back to a constant completeness–soundness gap.

Load-bearing premise

The polynomial-answer $\mathsf{NEXP}$ upper bound rests on the almost-multiplicativity estimate of randomized Pauli hashing (Lemma 4.24), whose error bound $C_1 $k^{{64}}$ $D^{{-1}}$\prod_j\|A_j\|$_4^{2}$$ requires the hashing dimension $D\geq C_0 $k^{{64}}$$ to be independent of the original qubit count $n$ and polynomial in the degree $k$; if the true constants depended on $n$ or grew exponentially in $k$, the certificate would no longer be $$2^{{\mathrm{poly}}$(N)}$ and the upper bound would fail.

Editorial extensions

If this is right

For fixed two-qubit resources with maximally mixed marginals, the computational power of two-prover one-round proofs takes exactly two values, $\mathsf{NEXP}$ or $\mathsf{RE}$, with no intermediate possibilities, determined jointly by quantum maximal correlation and entanglement.
Perfect EPR pairs are not the only resource that realizes $\mathsf{MIP}^*=\mathsf{RE}$; every entangled two-qubit state with maximally mixed marginals and $\rho_{\max}=1$, including dephased EPR pairs, does so.
Allowing polynomial-length answers adds no power beyond constant-length answers in either branch: $\mathsf{MIP}^{\psi}[\mathrm{poly},O(1)]=\mathsf{MIP}^{\psi}[\mathrm{poly},\mathrm{poly}]$ for all covered $\psi$.
The dimension reduction via Pauli folding gives $D=\mathrm{poly}(t)$ and $k=\mathrm{poly}(\log t)$, an exponential improvement over prior bounds, suggesting a general route toward dimension reduction for structured families of quantum operators.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The dichotomy raises the question whether quantum maximal correlation together with entanglement is the right invariant for computational power of fixed quantum resources more broadly; testing resources beyond two qubits, or with more than two provers, would delimit how far the classification extends.
The dimension-independent lower bound $\lambda^2$ on the extracted EPR component suggests that every entangled $\rho_{\max}=1$ boundary state contains a hidden perfect EPR core that a fixed local procedure draws out; this may connect to entanglement-purification and resource-theoretic questions with bounded local operations.
Because the almost-multiplicativity of Pauli folding holds without positivity or Hermiticity assumptions, a natural testable extension is whether the same mechanism gives quantum dimension reduction for structured operator families beyond POVM blocks, and where its limits sit relative to the known obstruction to dimension reduction for arbitrary quantum states.

Original abstract

We study two-prover one-round quantum interactive proofs in which the provers share arbitrarily many copies of a noisy EPR pair. Prior work showed that if the shared state $\psi$ has quantum maximal correlation $\rho_{\max}(\psi) < 1$, then $\mathrm{MIP}^{\psi}[\mathrm{poly}, O(1)] = \mathrm{MIP} = \mathrm{NEXP}$, while noiseless EPR pairs give $\mathrm{MIP}^{\mathrm{EPR}}[\mathrm{poly}, O(1)] = \mathrm{RE}$. That result leaves two cases open: answers of polynomial length, and noise that keeps $\rho_{\max}(\psi) = 1$, which unital noise can do. We settle both for unital noise. Equivalently, let $\psi$ be any two-qubit state with maximally mixed marginals. We show that $$\mathsf{MIP}^{\psi}[\mathrm{poly},\mathrm{poly}] =\mathsf{MIP} =\mathsf{NEXP},~\text{if $\psi$ is separable or $\rho_{\max}(\psi)<1$};$$ $$\mathsf{MIP}^{\psi}[\mathrm{poly},\mathrm{poly}] =\mathsf{RE}, \text{if $\psi$ is entangled and $\rho_{\max}(\psi)=1$.}$$ Beyond this complexity-theoretic dichotomy, our proof introduces two techniques of potential independent interest. The first technique approximates quantum measurements by positive low-degree operators. We prove that the square roots of the measurement elements, after applying the smoothing operation, can be approximated by low-degree operators, with error controlled in the Schatten 4-norm. This further gives a positive low-degree approximation with small normalization error. Second, we introduce Pauli folding, a randomized dimension-reduction method for low-degree quantum operators. For fixed accuracy, the number of qubits after folding is polynomial in the Pauli degree and the number of outcomes and does not depend on $n$. Moreover, Pauli folding preserves Hilbert-Schmidt inner products in expectation and is approximately multiplicative. This is an exponential improvement over the dimension reductions via invariance principles in all previous works.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-10-01: 1 request, 8,741 input tokens.

What the abstract itself states, as probabilities: claims first 0.11 · states limitation 0.20 · human participants 0.01 · controlled comparison 0.10 · randomized assignment 0.07 · states quantitative result 0.36 · compares with prior results 0.96 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

A recent work studied quantum two-prover one-round proof systems $\mathsf{MIP}^{\psi}[\text{poly},O(1)]$. It showed that when $\psi$ is a noisy EPR state with quantum maximal correlation $\rho_{\max}(\psi)<1$, the resulting complexity class is equivalent to $\mathsf{NEXP}=\mathsf{MIP}$. In contrast, $\mathsf{MIP}^{\text{EPR}}[\text{poly},O(1)]=\mathsf{RE}$. Not all noise, however, decreases quantum maximal correlation. A basic example is dephasing noise: a dephased EPR pair retain quantum maximal correlation $1$. In this work, we remove the constant-answer restriction and establish a complete dichotomy for $\mathsf{MIP}^{\psi}[\text{poly},\text{poly}]$, where the provers share arbitrarily many copies of EPR pairs subject to unital noise. Equivalently, let $\psi$ be a fixed two-qubit state with maximally mixed marginals. We prove that \[\mathsf{MIP}^{\psi}[\text{poly},\text{poly}]=\mathsf{MIP} =\mathsf{NEXP},~\text{if $\psi$ is separable or $\rho_{\max}(\psi)<1$};\]\[\mathsf{MIP}^{\psi}[\text{poly},\text{poly}]=\mathsf{MIP}^{\psi}[\text{poly},O(1)]=\mathsf{RE},\text{if $\psi$ is entangled and $\rho_{\max}(\psi)=1$.}\] Beyond the complexity classification, our proof develops two techniques that may be useful more broadly in quantum information and quantum complexity. First, we introduce a positivity-preserving low-degree approximation framework for quantum measurements: instead of truncating positive operators directly in the Pauli basis, we approximate suitable square-root factorizations, simultaneously achieving low Pauli degree, positivity, and global control over an entire POVM. Second, we develop a new dimension-reduction method, called Pauli folding, for low-degree positive operators. Its key ingredient is an almost-multiplicativity theorem for randomized Pauli hashing, which allows noncommutative products, positivity, and normalization to survive compression with controlled error.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	A recent work studied quantum two-prover one-round proof systems $\mathsf{MIP}^{\psi}[\text{poly},O(1)]$.	background 1.00	0.04	0.02	asserted 0.99
s1	It showed that when $\psi$ is a noisy EPR state with quantum maximal correlation $\rho_{\max}(\psi)<1$, the resulting complexity class is equivalent to $\mathsf{NEXP}=\mathsf{MIP}$.	background 0.98	0.04	0.05	asserted 1.00
s2	In contrast, $\mathsf{MIP}^{\text{EPR}}[\text{poly},O(1)]=\mathsf{RE}$.	background 0.95	0.10	0.05	asserted 1.00
s3	Not all noise, however, decreases quantum maximal correlation.	background 0.68	0.12	0.03	asserted 1.00
s4	A basic example is dephasing noise: a dephased EPR pair retain quantum maximal correlation $1$.	background 0.95	0.10	0.02	asserted 1.00
s5	In this work, we remove the constant-answer restriction and establish a complete dichotomy for $\mathsf{MIP}^{\psi}[\text{poly},\text{poly}]$, where the provers share arbitrarily many copies of EPR pairs subject to unital noise.	contribution 1.00	0.95	0.19	asserted 1.00
s6	Equivalently, let $\psi$ be a fixed two-qubit state with maximally mixed marginals.	contribution 0.41	0.26	0.03	asserted 0.94
s7	We prove that \[\mathsf{MIP}^{\psi}[\text{poly},\text{poly}]=\mathsf{MIP} =\mathsf{NEXP},~\text{if $\psi$ is separable or $\rho_{\max}(\psi)<1$};\]\[\mathsf{MIP}^{\psi}[\text{poly},\text{poly}]=\mathsf{MIP}^{\psi}[\text{poly},O(1)]=\mathsf{RE},\text{if $\psi$ is entangled and $\rho_{\max}(\psi)=1$.}\] Beyond the complexity classification, our proof develops two techniques that may be useful more broadly in quantum information and quantum complexity.	result 0.98	0.96	0.97	asserted 1.00
s8	First, we introduce a positivity-preserving low-degree approximation framework for quantum measurements: instead of truncating positive operators directly in the Pauli basis, we approximate suitable square-root factorizations, simultaneously achieving low Pauli degree, positivity, and global control over an entire POVM.	method 0.71	0.95	0.02	asserted 1.00
s9	Second, we develop a new dimension-reduction method, called Pauli folding, for low-degree positive operators.	method 0.63	0.96	0.02	asserted 1.00
s10	Its key ingredient is an almost-multiplicativity theorem for randomized Pauli hashing, which allows noncommutative products, positivity, and normalization to survive compression with controlled error.	method 0.91	0.91	0.02	asserted 0.99

What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

Figures

**Figure 1.** Roadmap for the proof of Theorem 1.1 3.2 ρmax < 1 Implies NEXP Theorem 3.1 (Finite-copy approximation). There are absolute constants C, γ > 0 such that the following holds. Let ψ ∈ M2 ⊗ M2 be a fixed state with maximally mixed marginals ψA = ψB = 1/2 and ρmax(ψ) < 1. There exists a constant αψ ∈ [0, 1), depending only on ψ, with the following property. Let G = (X , Y, A, B, pG, V ) be a finite entangled game, set t := max{|A|, |B|}, and let 0 < 33

**Figure 2.** Proof overview for Lemma 4.24. The first M

Figures reproduced from arXiv:2609.39318 by the authors.

References

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.