BQP^cc is not contained in MA^cc

Dmytro Gavinsky

REVIEW

BQP^cc is not contained in MA^cc

Dmytro Gavinsky

Computational Complexity · Submitted 17 Oct 2026 · 2 references

Pith's verdict: The BQP^cc ⊄ MA^cc separation is natural and the proof clean, but the entire lower bound rests on an unverified lemma from an unpublished same-author preprint.

T0 · AI review

How this review was made: An AI referee (deepseek/deepseek-v4-flash) read the paper on October 20, 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 →

· 2 major objections · 4 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv ID2610.24742 (version 1)

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

CitationDmytro Gavinsky. "BQP^cc is not contained in MA^cc." arXiv:2610.24742 (2026). https://pith.science/paper/SKWUP4CD

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

Dear colleague,

This paper claims to separate BQP^cc from MA^cc by taking the complement of a function (Cheat-Shape) from the author's earlier work. The quantum upper bound is already in [1]; the new contribution is the Merlin–Arthur lower bound, which uses Klauck's rectangle-size technique in a clean, short argument. If the crucial inequality holds, the result is correct and closes a natural open problem.

But the entire lower bound is conditional on Lemma 7.2 of [1], which asserts the existence of distributions Λ₀, Λ₁ with a specific rectangle inequality (A_n = n^{O(1)}, ε_n = 2^{-Ω(√n)}). The paper does not prove this lemma, does not sketch it, and does not even describe the distributions. [1] is listed as an unpublished full version (arXiv:2608.18784, 2026) – same author. The present manuscript cannot be evaluated independently; a referee would have to read [1] and check that the lemma is correctly stated and proved. The paper does not acknowledge this dependency as a limitation, which is a weakness.

So what we have is a two-page note that reduces a separation question to a single combinatorial claim in a non-independent unpublished source. The argument from that claim forward is sound. The significance of the separation is real (though within the subfield). The novelty is the observation about the complement, which is modest but legitimate.

Who this is for: researchers in communication complexity who care about the quantum-versus-classical landscape. They would need to verify the lemma in [1] before trusting the result. I wouldn't cite it in my own work until the lemma is either published in a refereed venue or reproduced here.

Recommendation: send to peer review, but the referee must be asked to verify Lemma 7.2 of [1] (or the authors should be required to include a self-contained proof). The result is worth taking seriously, but it's not ready for acceptance as-is.

Referee report

Major objections (2)

[§2 (full text, Lemma 7.2 citation)] The lower bound argument (Theorem 3.1) depends entirely on Lemma 7.2 from the unpublished preprint [1] (arXiv:2608.18784, 2026). The paper provides no proof, sketch, or independent verification of this lemma. The existence of distributions Λ0,n, Λ1,n satisfying inequality (2) with A_n = n^{O(1)} and ε_n = 2^{-Ω(√n)} is not established here. Until this lemma is either proved within the paper or published in a peer-reviewed source, the main result remains conditional. The paper does not acknowledge this dependence as a limitation.
[§3 (Theorem 3.1, parameter translation)] The relationship between the parameter n and the input length N_n is given as n ≤ N_n ∈ O(n^3 log^2 n). The lower bound is stated in terms of N_n^{1/12} / log^{1/6} N_n, but the derivation from c ∈ Ω(n^{1/4}) to this expression is not spelled out. The text merely says 'The length bound in (1) implies the result.' This step should be made explicit to verify the stated bounds.

Minor objections (4)

[§1 (Introduction)] The total function Cheat-Shape_n is not defined in this paper; the reader must consult [1] for its definition. For a short note this may be acceptable, but a brief informal description would improve readability.
[§2 (Notation)] The definition of a 'bipartite language' as L ⊆ ⋃_{N≥1} ({0,1}^N × {0,1}^N) could be clarified: the union over N suggests that inputs of different lengths are not mixed, but the domain is not explicitly the disjoint union. This is minor but could be made precise.
[§3 (Proof of Theorem 3.1)] The amplification step assumes the same proof is used in independent repetitions. This is standard for public-coin MA protocols, but a brief justification would help the reader confirm that the reused proof does not compromise soundness.
[§3 (Proof of Theorem 3.1)] The text states 'assuming without loss of generality that A_n ≥ 2'. It would be helpful to note that A_n ≥ 1 always, and if 1 ≤ A_n < 2 the amplification can be adjusted trivially by using a larger constant.

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

The paper

The paper claims

BQP^cc is not contained in MA^cc, as shown by a function with poly-log quantum communication but polynomial Merlin-Arthur cost.

The reading

This paper proves that the quantum communication complexity class BQP^cc strictly contains the Merlin-Arthur communication class MA^cc. The author exhibits a family of total functions, the complement of Cheat-Shape, whose quantum communication protocol costs only O($log^{3}$ N) qubits, yet any classical Merlin-Arthur protocol requires Ω($N^{{1/12}}$/$log^{{1/6}}$ N) bits of communication plus proof. This is the first separation showing that quantum protocols can beat classical ones even when the two parties share a short classical proof before interacting.

What carries the argument

The lower bound relies on a rectangle inequality (Lemma 7.2 from [1]): there exist distributions Λ_{0,n} (on 0-inputs) and Λ_{1,n} (on 1-inputs) such that for every rectangle R, Λ_{0,n}(R) ≤ A_n Λ_{1,n}(R) + ε_n with A_n = $n^{{O(1)}}$ and ε_n = $2^{{-Ω(√n)}}$. Klauck's technique [2] then translates any Merlin–Arthur protocol for G_n into a contradiction unless the communication plus proof length is large.

Extended reading notes

Core claim

The paper shows that the function family G_n = 1 - Cheat-Shape_n has quantum communication complexity O($log^{3}$ N_n) and Merlin–Arthur communication complexity Ω($N_n^{{1/12}}$ / $log^{{1/6}}$ N_n). Since G_n ∈ BQP^cc but G_n ∉ MA^cc, it follows that BQP^cc ⊈ MA^cc.

Load-bearing premise

Lemma 7.2 from the unpublished preprint [1] asserts the existence of distributions Λ_{0,n} and Λ_{1,n} satisfying the rectangle inequality Λ_{0,n}(R) ≤ A_n Λ_{1,n}(R) + ε_n for all rectangles R, with A_n = $n^{{O(1)}}$ and ε_n = $2^{{-Ω(√ n)}}$.

Editorial extensions

If this is right

This separation is unconditional (modulo the truth of Lemma 7.2) and explicitly exhibits a total function that witnesses it.
It shows that quantum communication cannot be efficiently simulated by classical interaction even when the parties receive a short proof, placing a concrete lower bound on the power of MA communication.
The result suggests that other natural total functions may exhibit similar separations between quantum and classical-with-proof communication.
The proof method (distribution over inputs + rectangle bound) may be extended to separate BQP^cc from other classical classes, such as AM^cc.

Reading between the lines

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

If Lemma 7.2 of [1] is verified in a peer-reviewed venue, the separation is rigorous and establishes BQP^cc ⊈ MA^cc unconditionally, resolving a longstanding open question in communication complexity.
The construction (complement of Cheat-Shape) is simple and might be adapted to prove that quantum communication is not contained in the analogue of the polynomial hierarchy in the communication setting.
The fact that the lower bound is polynomial (N^{1/12}) rather than exponential suggests that the separation is tight up to polynomial factors, and a sharper analysis could improve the exponent.
The dependence on an unpublished preprint means the result is conditional; a self-contained proof of the needed distributional inequality would strengthen the paper.

Original abstract

We exhibit a bipartite language with a poly-logarithmic quantum communication protocol and polynomial Merlin-Arthur communication complexity.

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-20: 1 request, 1,580 input tokens.

What the abstract itself states, as probabilities: claims first 0.06 · states limitation 0.15 · human participants 0.02 · controlled comparison 0.03 · randomized assignment 0.02 · states quantitative result 0.86 · compares with prior results 0.29 · 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.

We exhibit a bipartite language with a poly-logarithmic quantum communication protocol and polynomial Merlin-Arthur communication complexity.

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	We exhibit a bipartite language with a poly-logarithmic quantum communication protocol and polynomial Merlin-Arthur communication complexity.	result 0.77	0.92	0.80	asserted 1.00

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

References

Works cited (2)

[1]

Dmytro Gavinsky. On the quantum communication complexity of total functions. Full version of arXiv:2608.18784, 2026

View on Pith Pith review arXiv 2026
[2]

Hartmut Klauck. Rectangle size bounds and threshold covers in communication complexity. InPro- ceedings of the 18th IEEE Conference on Computational Complexity (CCC), pages 118–134, 2003. doi:10.1109/CCC.2003.1214415; extended version arXiv:cs/0208006. 2

View on Pith Pith review arXiv 2003

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.

[1] [1]

Dmytro Gavinsky. On the quantum communication complexity of total functions. Full version of arXiv:2608.18784, 2026

View on Pith Pith review arXiv 2026

[2] [2]

Hartmut Klauck. Rectangle size bounds and threshold covers in communication complexity. InPro- ceedings of the 18th IEEE Conference on Computational Complexity (CCC), pages 118–134, 2003. doi:10.1109/CCC.2003.1214415; extended version arXiv:cs/0208006. 2

View on Pith Pith review arXiv 2003