Maximum Separation of Quantum Communication Complexity With and Without Shared Entanglement

Atsuya Hasegawa; Augusto Modanese; Fran\c{c}ois Le Gall

arxiv: 2505.16457 · v3 · submitted 2025-05-22 · 🪐 quant-ph · cs.CC

Maximum Separation of Quantum Communication Complexity With and Without Shared Entanglement

Atsuya Hasegawa , Fran\c{c}ois Le Gall , Augusto Modanese This is my paper

Pith reviewed 2026-05-22 14:02 UTC · model grok-4.3

classification 🪐 quant-ph cs.CC

keywords quantum communication complexityshared entanglementnon-local gamesparallel repetitionrelation problemsNewman's theorem

0 comments

The pith

Relation problems can be solved with zero communication using entanglement but require linear communication without it.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper constructs relation problems of input size n that admit solutions requiring no communication whatsoever when the communicating parties share entanglement. The same problems, however, demand Omega(n) qubits of communication in the standard two-way quantum communication model that lacks any prior shared entanglement. The construction relies on taking parallel repetitions of non-local games that possess perfect quantum strategies yet lack perfect classical strategies, together with theorems that guarantee exponential decay under repetition. A sympathetic reader would care because the result establishes the strongest conceivable separation between the two quantum models and shows that shared entanglement can eliminate communication costs entirely in settings where substantial communication would otherwise be required.

Core claim

The central claim is that the parallel repetition of any non-local game possessing a perfect quantum strategy, no perfect classical strategy, and an exponential parallel repetition theorem produces a relation problem that can be solved with zero communication in the entanglement-assisted model yet requires Omega(n) communication in the model without shared entanglement, thereby achieving the maximum separation and refuting a quantum analog of Newman's theorem.

What carries the argument

Parallel repetition of non-local games that admit perfect quantum strategies, lack perfect classical strategies, and satisfy exponential-decay parallel repetition theorems.

If this is right

The separation between the two models reaches the largest possible gap of zero versus linear communication.
This supplies the first lower bound on quantum communication complexity without shared entanglement in the case where the entanglement-assisted complexity is exactly zero.
The result rules out any quantum analog of Newman's theorem that would bound the effect of shared resources.
The same construction applies to every non-local game meeting the stated conditions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

If many natural games satisfy the required conditions, then zero-communication entanglement-assisted protocols may exist for a broader class of tasks than currently known.
The problems could be used to benchmark the practical advantage of entanglement distribution in quantum networks.
Similar repetition-based lifts might separate other quantum resource models such as those with limited entanglement.

Load-bearing premise

The existence of non-local games that possess perfect quantum strategies, lack perfect classical strategies, and obey parallel repetition theorems with exponential decay.

What would settle it

A concrete non-local game satisfying the three conditions for which the derived relation problem nevertheless admits sublinear communication without shared entanglement.

Figures

Figures reproduced from arXiv: 2505.16457 by Atsuya Hasegawa, Augusto Modanese, Fran\c{c}ois Le Gall.

read the original abstract

We present relation problems whose input size is $n$ such that they can be solved with no communication for entanglement-assisted quantum communication models, but require $\Omega(n)$ qubit communication for $2$-way quantum communication models without prior shared entanglement. This is the maximum separation of quantum communication complexity with and without shared entanglement. To our knowledge, our result even shows the first lower bound on quantum communication complexity without shared entanglement when the upper bound of entanglement-assisted quantum communication models is zero. Our result refutes a quantum analog of Newman's theorem. The problem we consider is parallel repetition of any non-local game which has a perfect quantum strategy and no perfect classical strategy, and for which a parallel repetition theorem holds with exponential decay.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper constructs relation problems via parallel repetition to claim the maximum separation between entanglement-assisted zero-communication and Omega(n) without shared entanglement, but the lower bound needs checking on whether dynamic entanglement from messages is controlled.

read the letter

Hey colleague, the one or two things to know are that the authors build relation problems from parallel repetitions of non-local games that have perfect quantum strategies but no perfect classical ones, and they claim this gives zero communication with shared entanglement but requires Omega(n) qubits in the 2-way quantum model without prior entanglement. If the details hold, it would be the strongest separation and refute a quantum analog of Newman's theorem. They also position it as the first lower bound in the regime where the entanglement-assisted upper bound is zero. What the paper does well is apply standard parallel repetition theorems with exponential decay to lift the zero-communication property from the entangled case to the repeated relation on n bits. The construction stays general rather than depending on one specific game, which keeps the argument clean and reusable. It draws on existing tools without obvious circularity or invented parameters. The soft spot is in the lower bound for protocols that actually communicate. A 2-way quantum protocol without prior entanglement can still exchange qubits and thereby generate some shared entanglement during the run. The parallel repetition bound is typically stated for independent or non-communicating plays, so the proof has to show why small total communication does not let the parties boost their success probability enough to solve the relation with o(n) qubits. The abstract does not spell out this control step, and the stress-test concern lands here: if the argument only invokes the no-communication or classical bound without handling on-the-fly entanglement, the linear lower bound may not follow directly. This is the load-bearing part and will need careful verification in the full proofs. This work is for specialists in quantum communication complexity and non-local games. A reader who already knows the parallel repetition literature would get the most out of checking how the lower bound is derived. It deserves a serious referee because the claim is sharp, the method is direct, and the potential gap is technical rather than foundational. I would send it to peer review.

Referee Report

2 major / 2 minor

Summary. The paper constructs relation problems of input size n that admit zero-communication solutions in the entanglement-assisted quantum communication model but require Ω(n) qubit communication in the two-way quantum model without prior shared entanglement. The construction relies on parallel repetition of any non-local game possessing a perfect quantum strategy, no perfect classical strategy, and an exponential-decay parallel-repetition theorem; the resulting relation is solved with independent quantum strategies on each copy (zero communication) while any entanglement-free two-way protocol is claimed to need linear communication. The result is presented as the maximum separation between the two models and as a refutation of a quantum analogue of Newman's theorem.

Significance. If the central claims are correct, the work establishes the strongest conceivable separation between quantum communication complexity with and without shared entanglement and supplies the first explicit lower bound for the no-entanglement model when the entanglement-assisted upper bound is zero. By reducing the separation to the existence of suitable non-local games and invoking existing parallel-repetition theorems, the argument is modular and falsifiable; it also supplies concrete, parameter-free examples once a concrete game (e.g., the magic-square game) is substituted.

major comments (2)

[Proof of the lower bound (around the invocation of the parallel-repetition theorem)] The load-bearing step is the claim that any o(n)-qubit two-way quantum protocol without prior entanglement cannot solve the repeated relation with positive probability. Because the protocol may generate entanglement through the exchanged qubits, it is not immediate that its success probability is bounded by the no-communication value of the repeated game. The manuscript must therefore supply an explicit reduction showing that any such protocol can be turned into a no-communication strategy for the underlying non-local game G^k whose winning probability still decays exponentially; without this reduction the Ω(n) lower bound does not follow from the parallel-repetition theorem alone.
[Definition of the relation problem] The abstract states that the relation is defined on n = Θ(k) input bits. The precise relation between the number of repetitions k, the input size n, and the communication lower bound must be stated explicitly, including the constant factors hidden by the Θ notation, so that the claimed linear dependence is verifiable.

minor comments (2)

[Introduction] The statement that the result 'even shows the first lower bound … when the upper bound … is zero' should be accompanied by a brief comparison with prior separations (e.g., those based on the CHSH game or other Bell inequalities) to clarify the novelty.
[Preliminaries] Notation for the communication models (EA vs. Q vs. Q*) should be introduced once and used consistently; the current text occasionally switches between 'entanglement-assisted quantum communication' and 'quantum communication with shared entanglement' without explicit cross-reference.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address the two major comments below and will revise the manuscript to incorporate clarifications and an explicit reduction as requested. These changes will strengthen the presentation without altering the core claims.

read point-by-point responses

Referee: [Proof of the lower bound (around the invocation of the parallel-repetition theorem)] The load-bearing step is the claim that any o(n)-qubit two-way quantum protocol without prior entanglement cannot solve the repeated relation with positive probability. Because the protocol may generate entanglement through the exchanged qubits, it is not immediate that its success probability is bounded by the no-communication value of the repeated game. The manuscript must therefore supply an explicit reduction showing that any such protocol can be turned into a no-communication strategy for the underlying non-local game G^k whose winning probability still decays exponentially; without this reduction the Ω(n) lower bound does not follow from the parallel-repetition theorem alone.

Authors: We agree that an explicit reduction is required for rigor. The manuscript relies on the observation that a two-way protocol without prior entanglement induces, via its local operations and message exchanges, a strategy for the k-fold game whose success probability cannot exceed the exponentially decaying bound given by the parallel-repetition theorem. To make this fully rigorous, the revised version will include a dedicated lemma that formally extracts a no-communication strategy for G^k from any o(k)-qubit two-way protocol: the communicating parties' local unitaries and the fixed communication transcript are used to define effective local measurements whose joint winning probability is bounded by the no-communication value of the repeated game. This establishes the claimed Ω(n) lower bound directly from the parallel-repetition theorem. revision: yes
Referee: [Definition of the relation problem] The abstract states that the relation is defined on n = Θ(k) input bits. The precise relation between the number of repetitions k, the input size n, and the communication lower bound must be stated explicitly, including the constant factors hidden by the Θ notation, so that the claimed linear dependence is verifiable.

Authors: We thank the referee for noting the need for explicit parameters. Let m denote the input size of the base game G. The k-fold relation is defined on inputs of total length n = k · m. The entanglement-assisted quantum communication complexity is zero (independent strategies on each copy), while any two-way protocol without prior entanglement requires Ω(k) qubits of communication by the reduction above. Hence the lower bound is Ω(k) = Ω(n) with leading constant 1/m. The revised manuscript will state this relation explicitly in the abstract, introduction, and main theorem, replacing the Θ notation with the precise linear dependence n = Θ(k). revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation applies external theorems

full rationale

The paper defines a relation problem via parallel repetition of any non-local game G that admits a perfect quantum strategy (value 1), has classical value <1, and satisfies an exponential-decay parallel repetition theorem. It then invokes the zero-communication upper bound from the perfect quantum strategy on each copy and claims an Omega(n) qubit lower bound for entanglement-free 2-way quantum protocols. These ingredients are drawn from prior independent literature on non-local games and parallel repetition; the paper does not define G in terms of its own output, fit parameters to a subset of its own data, or rely on a uniqueness theorem or ansatz imported solely from the authors' earlier work. No equation or construction reduces to its own inputs by definition. The derivation is therefore self-contained against external benchmarks and receives the default non-circularity finding.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the existence of suitable non-local games and the applicability of parallel repetition theorems with exponential decay; these are standard but non-trivial assumptions from quantum information theory.

axioms (2)

domain assumption Existence of non-local games with a perfect quantum strategy but no perfect classical strategy.
Base case for constructing the relation problems via parallel repetition.
domain assumption Parallel repetition theorem holds with exponential decay for the chosen games.
Required to ensure the communication lower bound scales linearly with the number of repetitions n.

pith-pipeline@v0.9.0 · 5652 in / 1371 out tokens · 47696 ms · 2026-05-22T14:02:16.216851+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AbsoluteFloorClosure.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

The problem we consider is parallel repetition of any non-local game which has a perfect quantum strategy and no perfect classical strategy, and for which a parallel repetition theorem holds with exponential decay.

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Multi-Prover Interactive Proof Systems with Leakage
quant-ph 2026-05 unverdicted novelty 8.0

Two-prover one-round MIP protocols for NEXP and MIP* protocols for RE remain sound against any polynomial bits of leakage between provers.
Multi-Prover Interactive Proof Systems with Leakage
quant-ph 2026-05 unverdicted novelty 8.0

Multi-prover interactive proof systems for NEXP and RE can be made robust against polynomial bits of leakage between provers via parallel repetition and PCP conversions.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages · cited by 1 Pith paper · 3 internal anchors

[1]

Trade-Offs Between Entanglement and Communication

[AG23] Srinivasan Arunachalam and Uma Girish. Trade-Offs Between Entanglement and Communication. In38th Computational Complexity Conference (CCC 2023), volume 264 ofLIPIcs, pages 25:1–25:23,

work page 2023
[2]

A simple demonstration of Bell's theorem involving two observers and no probabilities or inequalities

[Ara02] PK Aravind. A simple demonstration of Bell’s theorem involving two observers and no probabilities or inequalities.arXiv preprint quant-ph/0206070,

work page internal anchor Pith review Pith/arXiv arXiv
[3]

Extending and Characterizing Quantum Magic Games

[Ark12] Alex Arkhipov. Extending and characterizing quantum magic games.arXiv preprint arXiv:1209.3819,

work page internal anchor Pith review Pith/arXiv arXiv
[4]

Quantum pseudo-telepathy.Foun- dations of Physics, 35(11):1877–1907,

[BBT05] Gilles Brassard, Anne Broadbent, and Alain Tapp. Quantum pseudo-telepathy.Foun- dations of Physics, 35(11):1877–1907,

work page 1907
[5]

Quantum vs

[BCW98] Harry Buhrman, Richard Cleve, and Avi Wigderson. Quantum vs. classical commu- nication and computation. InProceedings of the 30th annual ACM symposium on Theory of computing (STOC 1998), pages 63–68,

work page 1998
[6]

On the power of geometrically-local classical and quantum circuits.arXiv preprint arXiv:2310.01540,

[BJ23] Kishor Bharti and Rahul Jain. On the power of geometrically-local classical and quantum circuits.arXiv preprint arXiv:2310.01540,

work page arXiv
[7]

Consequences and limits of nonlocal strategies

[CHTW04] Richard Cleve, Peter Hoyer, Benjamin Toner, and John Watrous. Consequences and limits of nonlocal strategies. InProceedings. 19th IEEE Annual Conference on Computational Complexity (CCC 2004), pages 236–249. IEEE,

work page 2004
[8]

Characterization of binary constraint system games

[CM14] Richard Cleve and Rajat Mittal. Characterization of binary constraint system games. InAutomata, Languages, and Programming: 41st International Colloquium (ICALP 2014), pages 320–331. Springer,

work page 2014
[9]

Quantum computing: Lecture notes.arXiv preprint arXiv:1907.09415, 2019

[dW19] Ronald de Wolf. Quantum computing: Lecture notes.arXiv preprint arXiv:1907.09415,

work page arXiv 1907
[10]

On the role of shared entanglement.arXiv preprint quant- ph/0604052,

[Gav06] Dmytro Gavinsky. On the role of shared entanglement.arXiv preprint quant- ph/0604052,

work page arXiv
[11]

Classical interaction cannot replace quantum nonlocality.arXiv preprint arXiv:0901.0956,

[Gav09] Dmytro Gavinsky. Classical interaction cannot replace quantum nonlocality.arXiv preprint arXiv:0901.0956,

work page arXiv
[12]

Quantum communication advantage in TFNP.arXiv preprint arXiv:2411.03296,

[GGJL24] Mika Göös, Tom Gur, Siddhartha Jain, and Jiawei Li. Quantum communication advantage in TFNP.arXiv preprint arXiv:2411.03296,

work page arXiv
[13]

Bounded-error quantum state identification and exponential separations in communication complexity

13 [GKRdW06] Dmitry Gavinsky, Julia Kempe, Oded Regev, and Ronald de Wolf. Bounded-error quantum state identification and exponential separations in communication complexity. InProceedings of the 38th annual ACM symposium on Theory of Computing (STOC 2006), pages 594–603,

work page 2006
[14]

A direct product theorem for quantum communication complexity with applications to device-independent cryptography.arXiv preprint arXiv:2106.04299,

[JK21] Rahul Jain and Srijita Kundu. A direct product theorem for quantum communication complexity with applications to device-independent cryptography.arXiv preprint arXiv:2106.04299,

work page arXiv
[15]

Direct product theorems for classical communication complexity via subdistribution bounds

[JKN08] Rahul Jain, Hartmut Klauck, and Ashwin Nayak. Direct product theorems for classical communication complexity via subdistribution bounds. InProceedings of the 40th annual ACM symposium on Theory of computing (STOC 2008), pages 599–608,

work page 2008
[16]

Optimal Direct Sum and Privacy Trade-off Results for Quantum and Classical Communication Complexity

[JSR08] Rahul Jain, Pranab Sen, and Jaikumar Radhakrishnan. Optimal direct sum and privacy trade-off results for quantum and classical communication complexity.arXiv preprint arXiv:0807.1267,

work page internal anchor Pith review Pith/arXiv arXiv
[17]

Classical and quantum partition bound and detector inefficiency

[LLR12] Sophie Laplante, Virginie Lerays, and Jérémie Roland. Classical and quantum partition bound and detector inefficiency. InInternational Colloquium on Automata, Languages, and Programming (ICALP 2012), pages 617–628. Springer,

work page 2012
[18]

Parallel repetition of two prover games (invited survey)

[Raz10] Ran Raz. Parallel repetition of two prover games (invited survey). In2010 IEEE 25th Annual Conference on Computational Complexity (CCC 2010), pages 3–6. IEEE,

work page 2010
[19]

Tensor norms and the classical communication complexity of nonlocal quantum measurement

[Shi05] Yaoyun Shi. Tensor norms and the classical communication complexity of nonlocal quantum measurement. InProceedings of the 37th annual ACM symposium on Theory of computing (STOC 2005), pages 460–467,

work page 2005
[20]

Some complexity questions related to distributive computing (preliminary report)

[Yao79] Andrew Chi-Chih Yao. Some complexity questions related to distributive computing (preliminary report). InProceedings of the eleventh annual ACM symposium on Theory of computing (STOC 1979), pages 209–213,

work page 1979
[21]

Quantum circuit complexity

[Yao93] Andrew Chi-Chih Yao. Quantum circuit complexity. InProceedings of 1993 IEEE 34th Annual Foundations of Computer Science (FOCS 1993), pages 352–361. IEEE,

work page 1993

[1] [1]

Trade-Offs Between Entanglement and Communication

[AG23] Srinivasan Arunachalam and Uma Girish. Trade-Offs Between Entanglement and Communication. In38th Computational Complexity Conference (CCC 2023), volume 264 ofLIPIcs, pages 25:1–25:23,

work page 2023

[2] [2]

A simple demonstration of Bell's theorem involving two observers and no probabilities or inequalities

[Ara02] PK Aravind. A simple demonstration of Bell’s theorem involving two observers and no probabilities or inequalities.arXiv preprint quant-ph/0206070,

work page internal anchor Pith review Pith/arXiv arXiv

[3] [3]

Extending and Characterizing Quantum Magic Games

[Ark12] Alex Arkhipov. Extending and characterizing quantum magic games.arXiv preprint arXiv:1209.3819,

work page internal anchor Pith review Pith/arXiv arXiv

[4] [4]

Quantum pseudo-telepathy.Foun- dations of Physics, 35(11):1877–1907,

[BBT05] Gilles Brassard, Anne Broadbent, and Alain Tapp. Quantum pseudo-telepathy.Foun- dations of Physics, 35(11):1877–1907,

work page 1907

[5] [5]

Quantum vs

[BCW98] Harry Buhrman, Richard Cleve, and Avi Wigderson. Quantum vs. classical commu- nication and computation. InProceedings of the 30th annual ACM symposium on Theory of computing (STOC 1998), pages 63–68,

work page 1998

[6] [6]

On the power of geometrically-local classical and quantum circuits.arXiv preprint arXiv:2310.01540,

[BJ23] Kishor Bharti and Rahul Jain. On the power of geometrically-local classical and quantum circuits.arXiv preprint arXiv:2310.01540,

work page arXiv

[7] [7]

Consequences and limits of nonlocal strategies

[CHTW04] Richard Cleve, Peter Hoyer, Benjamin Toner, and John Watrous. Consequences and limits of nonlocal strategies. InProceedings. 19th IEEE Annual Conference on Computational Complexity (CCC 2004), pages 236–249. IEEE,

work page 2004

[8] [8]

Characterization of binary constraint system games

[CM14] Richard Cleve and Rajat Mittal. Characterization of binary constraint system games. InAutomata, Languages, and Programming: 41st International Colloquium (ICALP 2014), pages 320–331. Springer,

work page 2014

[9] [9]

Quantum computing: Lecture notes.arXiv preprint arXiv:1907.09415, 2019

[dW19] Ronald de Wolf. Quantum computing: Lecture notes.arXiv preprint arXiv:1907.09415,

work page arXiv 1907

[10] [10]

On the role of shared entanglement.arXiv preprint quant- ph/0604052,

[Gav06] Dmytro Gavinsky. On the role of shared entanglement.arXiv preprint quant- ph/0604052,

work page arXiv

[11] [11]

Classical interaction cannot replace quantum nonlocality.arXiv preprint arXiv:0901.0956,

[Gav09] Dmytro Gavinsky. Classical interaction cannot replace quantum nonlocality.arXiv preprint arXiv:0901.0956,

work page arXiv

[12] [12]

Quantum communication advantage in TFNP.arXiv preprint arXiv:2411.03296,

[GGJL24] Mika Göös, Tom Gur, Siddhartha Jain, and Jiawei Li. Quantum communication advantage in TFNP.arXiv preprint arXiv:2411.03296,

work page arXiv

[13] [13]

Bounded-error quantum state identification and exponential separations in communication complexity

13 [GKRdW06] Dmitry Gavinsky, Julia Kempe, Oded Regev, and Ronald de Wolf. Bounded-error quantum state identification and exponential separations in communication complexity. InProceedings of the 38th annual ACM symposium on Theory of Computing (STOC 2006), pages 594–603,

work page 2006

[14] [14]

A direct product theorem for quantum communication complexity with applications to device-independent cryptography.arXiv preprint arXiv:2106.04299,

[JK21] Rahul Jain and Srijita Kundu. A direct product theorem for quantum communication complexity with applications to device-independent cryptography.arXiv preprint arXiv:2106.04299,

work page arXiv

[15] [15]

Direct product theorems for classical communication complexity via subdistribution bounds

[JKN08] Rahul Jain, Hartmut Klauck, and Ashwin Nayak. Direct product theorems for classical communication complexity via subdistribution bounds. InProceedings of the 40th annual ACM symposium on Theory of computing (STOC 2008), pages 599–608,

work page 2008

[16] [16]

Optimal Direct Sum and Privacy Trade-off Results for Quantum and Classical Communication Complexity

[JSR08] Rahul Jain, Pranab Sen, and Jaikumar Radhakrishnan. Optimal direct sum and privacy trade-off results for quantum and classical communication complexity.arXiv preprint arXiv:0807.1267,

work page internal anchor Pith review Pith/arXiv arXiv

[17] [17]

Classical and quantum partition bound and detector inefficiency

[LLR12] Sophie Laplante, Virginie Lerays, and Jérémie Roland. Classical and quantum partition bound and detector inefficiency. InInternational Colloquium on Automata, Languages, and Programming (ICALP 2012), pages 617–628. Springer,

work page 2012

[18] [18]

Parallel repetition of two prover games (invited survey)

[Raz10] Ran Raz. Parallel repetition of two prover games (invited survey). In2010 IEEE 25th Annual Conference on Computational Complexity (CCC 2010), pages 3–6. IEEE,

work page 2010

[19] [19]

Tensor norms and the classical communication complexity of nonlocal quantum measurement

[Shi05] Yaoyun Shi. Tensor norms and the classical communication complexity of nonlocal quantum measurement. InProceedings of the 37th annual ACM symposium on Theory of computing (STOC 2005), pages 460–467,

work page 2005

[20] [20]

Some complexity questions related to distributive computing (preliminary report)

[Yao79] Andrew Chi-Chih Yao. Some complexity questions related to distributive computing (preliminary report). InProceedings of the eleventh annual ACM symposium on Theory of computing (STOC 1979), pages 209–213,

work page 1979

[21] [21]

Quantum circuit complexity

[Yao93] Andrew Chi-Chih Yao. Quantum circuit complexity. InProceedings of 1993 IEEE 34th Annual Foundations of Computer Science (FOCS 1993), pages 352–361. IEEE,

work page 1993