PaperlayerView exact revision on arXiv

Source-linked AI summary

Exponential Quantum Advantage in Numbers-on-Forehead Communication

Haoyu Wang, Pei Wu, Guangxu Yang

arXiv:2609.40273v2cs.CCquant-ph

TL;DR

The paper asks whether quantum communication can retain an advantage in the general interactive three-party NOF model. It introduces the Interleaved Unitary Product problem and a regularity-based argument for randomized lower bounds. The resulting partial Boolean function has logarithmic quantum communication and polynomial randomized communication requirements.

  • Problem

    Discrepancy-based lower bounds for interactive NOF also lower-bound quantum communication, leaving them unable to establish a quantum-versus-randomized separation.

    Source: §1.3 · p. 4

  • Method

    The paper introduces the Interleaved Unitary Product problem and adapts regularity decomposition to cylinder intersections for a randomized NOF lower bound.

    Source: §1 · p. 2, §4.1 · p. 10

  • Results

    O(log n) quantum communication and Ω((n/log n)^1/32) randomized communication are required for IUP.

    Source: §1.1 · p. 3, §1.3 · p. 5

  • Takeaways & Limitations

    The bounds establish an exponential separation for a partial Boolean function in three-party NOF, with one clean qubit on the quantum side.

    Source: §1 · p. 2, §1.1 · p. 3

Abstract

from arXiv · show

We give the first exponential quantum advantage in the general interactive three-party Numbers-on-Forehead (NOF) model for a decision problem. Previous separations hold only for restricted protocols like one-way communication for a relation. We construct an explicit partial Boolean function, the Interleaved Unitary Product problem, that requires only $O(\log n)$ NOF quantum communication but $\widetilde{\Omega}(n^{1/32})$ randomized communication. This function builds on the two-party unitary product problem of Arunachalam, Girish, and Lifshitz (TQC 2024). The main technical obstacle is that discrepancy, the standard lower-bound method for NOF, also lower-bounds quantum communication. We instead develop a regularity-based argument for randomized NOF lower bounds, building on the approach of Kelley, Lovett, and Meka and adapting the regularity decomposition of Abboud, Fischer, Kelley, Lovett, and Meka (STOC 2024) to cylinder intersections. Combined with matrix-product estimates of Arunachalam, Girish, and Lifshitz, this yields our randomized lower bound.

1 Introduction

The introduction asks whether quantum messages can outperform classical ones when players have overlapping input access, and presents three-party NOF as a setting for that question. It introduces the Interleaved Unitary Product problem and outlines a regularity-based approach to the randomized lower bound.

1 Introduction

  • Three-party NOF gives each player all input parts except one, creating overlapping views that motivate studying quantum advantage beyond two-party settings.The paper also frames initial-state purity as a complementary question and notes a prior two-party separation in the one-clean-qubit model.Source: §1 · p. 2

1.1 Our contributions

  • IUP adapts the two-party unitary product problem [AGL23] into a three-party NOF problem whose inputs are grouped across matrices in an interleaved product.The input matrices are promised to be approximately unitary, and the task distinguishes cases according to the normalized real trace of their product.Source: §1.1 · pp. 2–3
  • The IUP problem uses O(log n) quantum communication, while every randomized protocol requires Ω((n/log n)^1/32).The paper combines these bounds to establish an exponential separation for a partial Boolean function, with one clean qubit on the quantum side.Source: §1.1 · p. 3, §1.3 · p. 5

1.2 Related work

  • Earlier separations considered relational problems or restricted classical interaction; this work establishes a separation for a partial Boolean function with unrestricted three-player interaction.The cited prior directions include simultaneous NOF [GP08] and later simultaneous and one-way NOF constructions [YZ25b] [YZ26].Source: §1.2 · p. 3

1.3 Technical Overview

  • Discrepancy and generalized discrepancy cannot separate the models because they also lower-bound quantum communication.The paper instead adapts a regularity decomposition to cylinder intersections and combines it with matrix-product estimates to prove a corruption bound.Source: §1.3 · p. 4
  • The lower-bound argument decomposes cylinder intersections into sparse and pseudorandom pieces, then bounds the pieces separately before deriving the communication bound.The overview sets d = Θ(m^1/16) and concludes t = Ω(m^1/16) = Ω((n/log n)^1/32).Source: §1.3 · pp. 4–5

2 Preliminaries

The preliminaries set the three-party NOF model and define the IUP decision function through a promised gap in a normalized matrix-product trace. They also specify the one-clean-qubit communication formalism and the encoding of bit-string inputs as matrices.

2 Preliminaries

  • The paper uses standard Euclidean, Frobenius, and operator norms, and defines uniform sampling notation for finite sets.It also uses Haar probability measure on SU(m) and its product measures.Source: §2 · p. 5
  • In the three-party NOF model, each player sees the other two inputs; protocols may use public randomness and unrestricted blackboard interaction.Communication cost is the worst-case total bits or qubits, and protocols have error at most 1/3 on promised inputs unless stated otherwise.Source: §2 · p. 5
  • The input encoding decodes bit-string blocks into complex numbers and arranges them row by row into m × m matrices, with m = Θ(n/log n).The decoded inputs are grouped as X = (A1, C1, A2, C2), Y = (B1, D1, B2, D2), and Z = (E1, E2).Source: §2 · p. 5
  • IUP maps inputs to 0 when Re Tr(W)/m ≤ 0.1 and to 1 when Re Tr(W)/m ≥ 0.9, leaving other cases outside the promise.The players decode their views into matrices and determine the value only when the function is not ∗.Source: §2 · p. 6
  • In the one-clean-qubit model, the initial state has one pure qubit and a maximally mixed workspace; players apply input-dependent unitaries and exchange qubits without extra quantum memory.The protocol uses no prior entanglement and ends with a fixed projective measurement.Source: §2 · p. 6

3 Quantum protocol

The protocol estimates the trace gap by applying controlled matrix operations to a sampled register and measuring the result. With O(log n) quantum communication, it also works in the more restrictive NIH model, yielding an exponential separation from randomized NOF protocols when paired with the lower bound.

3 Quantum protocol

  • The protocol replaces each input matrix by its polar factor, a change that preserves the trace gap under the stated matrix promise.For σ = 10^-4, the normalized trace changes by less than 0.002.Source: §3 · pp. 6–7
  • A uniformly sampled index selects a diagonal entry, and the players apply controlled operations in the order of the interleaved product before measurement.The conditional measurement probabilities depend on the real part of that sampled entry; its average equals Re Tr(W)/m.Source: §3 · p. 7
  • The protocol uses 100 independent sampled trials and applies Chebyshev’s inequality to analyze their outcomes.Each trial has variance at most 1.Source: §3 · p. 7
  • Each iteration uses nine message transmissions of 1 + ⌈log2 m⌉ qubits, yielding total communication O(log n) for m = Θ(n/log n).Source: §3 · p. 7
  • O(log n) quantum communication suffices for the IUP protocol, and the same upper bound holds in the more restrictive NIH model.Together with the randomized NOF lower bound, the NIH protocol establishes an exponential separation between the models.Source: §3 · pp. 7–8

4 Randomized lower bound

The section proves an 8((n/log n)^1/32) randomized communication lower bound for IUP by establishing a corruption bound for cylinder intersections under two input distributions. It adapts regularity decomposition to handle regular and sparse intersections, using bounds on 0 and 1 for the regular case and p=2 grid-norm estimates for the sparse case.

4.1 Corruption bound via regularity decomposition

  • The corruption-bound proof adapts regularity decomposition to cylinder intersections, splitting them into sparse and pseudorandom parts and bounding the parts separately.It first establishes the bound for finite-type intersections and extends it to measurable ones by approximation; the decomposition builds on Kelley, Lovett, and Meka [KLM24] and Abboud, Fischer, Kelley, Lovett, and Meka [AFK+24].Source: §4.1 · pp. 10, 12

4.1.1 Corruption bound on regular cylinder intersections.

  • For regular cylinder-intersection terms, grid-norm bounds and a moment bound control their µ1 mass and provide a matching lower bound on µ0 mass.The grid-norm estimate is derived from Arunachalam, Girish, and Lifshitz [AGL23, Lemma 5.2], while the regularity-based moment bound draws on Kelley, Lovett, and Meka [KLM24, Lemma 4.8].Source: §4.1.1 · pp. 12–13
  • For regular cylinder intersections, regularity and grid-norm estimates yield the corruption parameter α = 4λ².The proof lower-bounds μ0 and upper-bounds μ1 before comparing the two bounds.Source: §4.1.1 · p. 14

4.1.2 Corruption bound on sparse cylinder intersections.

  • For sparse intersections, the proof uses the p=2 Boolean grid-norm bound and the fact that some cylinder density is at most 2^-εd.For Boolean functions, U(2, 2) is at most the square root of the density.Source: §4.1.2 · p. 14

AI Declaration

The authors used AI across approach development, proof work, and manuscript support, while retaining responsibility for the final mathematical claims and proofs.

Approach development

  • AI suggested using the ABCD problem as a building block, and the authors formalized the Interleaved Unitary Product problem after trials and manual screening.The reported discussions also concerned using prior work to construct a three-party function along the lifting route.Source: AI Declaration · p. 15

Proof development

  • AI helped adapt a regularity decomposition to cylinder intersections and developed the grid-norm bound, regular and sparse estimates, and resulting corruption bound.The authors proposed applying a structure-versus-pseudorandomness framework to the analysis.Source: AI Declaration · p. 15

Writing and responsibility

  • The authors wrote the first draft, while AI tools were later used to polish language and presentation.The authors state that they reviewed and finalized all mathematical claims and proofs and take responsibility for correctness, exposition, and attribution.Source: AI Declaration · p. 15

Checking and other support

  • AI helped check proofs and simplify them, and also assisted with literature searches and language polishing.It did not identify consequential errors in proofs developed along the successful route.Source: AI Declaration · p. 15

A Regularity decomposition for cylinder intersections

The section adapts a regularity decomposition for two Boolean matrices to cylinder intersections, preserving their product while splitting them into sparse or regular pieces. The resulting outputs have controlled size and number.

Adaptation to cylinder intersections

GoodCube and recursion

AB-decomposition bounds

  • The AB-decomposition returns k tuples with a bound on their combined domain size and on k, as stated in Lemma A.2.The proof bounds total returned-domain size and number of outputs separately.Source: A Regularity decomposition for… · pp. 20–21

Regularity decomposition

  • Each output is sparse in at least one matrix, with density at most 2^-d, or both matrices are (ϵ, d)-regular and satisfy ϵ-min-degree.The cylinder-intersection result inherits the classification through the finite-type construction and norm monotonicity.Source: A Regularity decomposition for… · pp. 20, 22

Product preservation

  • The decomposition preserves the product F(y, z)G(x, z) at every triple, and multiplying by H(x, y) recovers the cylinder intersection.The component terms are Boolean and pairwise disjoint wherever they equal 1.Source: A Regularity decomposition for… · p. 22

B The grid norm bound

The section establishes a grid-norm bound by applying matrix-product estimates to the two products in W = PE1QE2. Weighted estimates remove a density condition and support the application to both products.

Grid-norm bound

  • The estimate of Arunachalam, Girish, and Lifshitz [AGL23] is applied to the two matrix products in W = PE1QE2 to obtain the grid-norm bound.Their cited estimate bounds how much the constraint ABCD = Im can increase an average of u(A, C)w(B, D).Source: B The grid norm bound · p. 23

Theorem B.1 assumptions

  • The cited product estimate assumes independent Haar matrices in SU(m) and functions with averages at least e^-κ√m.The theorem specifies a universal constant κ > 0.Source: B The grid norm bound · p. 23

Weighted product estimates

  • Weighted product estimates remove the density condition by bounding small averages directly, then apply the resulting estimate twice for both matrix products.The proof starts with Boolean functions and extends the inequality to functions in [0, 1].Source: B The grid norm bound · p. 23

B.1 Proof of Theorem 4.10

The proof analyzes samples under μ1 by conditioning on L and applying product-measure bounds to conditional moments. It combines these bounds with grid norms to establish the stated estimate for every d ≥ 2.

Sampling and distributions

  • Conditioned on L, Z is independent of (X, Y), while L and Z are each unconditionally distributed as ν⊗2.The proof uses the corresponding product Haar marginals to control functions of the sampled factors and views.Source: §B.1 · p. 24

Step 1: Conditional mean bound

  • The first moment step applies Lemma B.2(1) to bound conditional means of u(Z) when r(L) exceeds 2λ0E[u].It defines r(L) = E[u(Z) | L] and applies the lemma to the alternating factors in PE1QE2 = Im.Source: §B.1 · p. 24

Step 2: Product moments

  • The moment argument takes independent conditional samples of Z and uses Lemma B.2(2) to replace dependent averages of products of f and g with independent averages.The resulting second moments are bounded using grid norms and the conditional-moment bound.Source: §B.1 · p. 24

Step 3: Final bound

  • For p ≥ 1/λ the main term is at least 1; otherwise the grid-norm estimate yields the stated bound for every d ≥ 2.In the latter case, the proof bounds the conditional expectation norm by p^(1/(2d)) < λ^(-1/(2d)) and chooses κ to obtain the claimed exponential form.Source: §B.1 · p. 25

C Additional Proofs

These additional proofs establish distributional properties of the unitary-product inputs, control rounding and approximation errors, and derive a probability statement for the rounded function. They also construct finite-type approximations using equal-measure partitions.

Claim 4.5

  • If ∥U†U − Im∥op ≤ σ < 1, then U is invertible.The proof uses this condition in establishing a property of U's polar factor.Source: C Additional Proofs · p. 25

Claim 4.1

  • The views (X, Y), (X, Z), and (Y, Z) contain 8, 6, and 6 distinct matrices, respectively, and each has the same product Haar distribution as under μ0.Under μ1, the first nine factors are independent Haar matrices and the tenth is determined by their product.Source: C Additional Proofs · pp. 25–26

Claim 4.2

  • The rounded product has normalized real trace above 0.9 on the stated inputs, so Fn(R(X, Y, Z)) = 1.The proof bounds rounding's change to the normalized trace by less than 10^-3.Source: C Additional Proofs · p. 26

Probability estimate

  • The proof derives a probability estimate for Fn = 0 from a continuous-input estimate and the fact that Fn ≠ 0 includes inputs outside the promise.It first bounds the continuous-input event and accounts for rounding in transferring the estimate.Source: C Additional Proofs · p. 26

Finite-type approximation

  • Finite partitions make f′, g′, and h′ constant on cell products, with each approximation error at most 1/(6r).The construction then refines these to equal-measure partitions and makes the resulting functions finite-type.Source: C Additional Proofs · pp. 26–27
Loading 2609.40273v2…