### Communication complexity of XOR functions

```Effcient quantum protocols for
XOR functions
Shengyu Zhang
The Chinese University of Hong Kong
Communication complexity

(, )
• Two parties, Alice and Bob, jointly compute a
function  on input (, ).
–  known only to Alice and  only to Bob.
• Communication complexity*1: how many bits are
needed to be exchanged?
*1. A. Yao. STOC, 1979.
Computation modes
• Deterministic: Players run determ. protocol. ---()
small error probability allowed. --- ()
• Quantum: Players send quantum messages.
– Share resource? (Superscript.)
• ∗ (): share entanglement.
• (): share nothing
– Error? (Subscript)
•  (): bounded-error.
•  (): zero-error, fixed length.
Lower bounds
• Not only interesting on its own, but also important
because of numerous applications.
– to prove lower bounds.
• Question: How to lower bound communication

complexity itself?
↓
• Communication matrix
≝  ,
, :
→
(, )
4
Log-rank conjecture
• Rank lower
bound*1
Log Rank Conjecture*2
log 2   ≤   ≤ log
1

• Conj: The rank lower bound is polynomially tight.
• combinatorial measure ⇔ linear algebra measure.
• Equivalent to a bunch of other conjectures.
– related to graph theory*2; nonnegative rank*3, Boolean
roots of polynomials*4, quantum sampling complexity*5.
*1. Melhorn, Schmidt. STOC, 1982.
*2. Lovász, Saks. FOCS, 1988.
*3. Lovász. Book Chapter, 1990.
*4. Valiant. Info. Proc. Lett., 2004.
*5. Ambainis, Schulman, Ta-Shma, Vazirani,
Wigderson, SICOMP 2003.
5
Log-rank conjecture: quantum version
Log Rank Conjecture
• Rank lower bound
log 2   ≤   ≤ log
1

• Quantum: rank lower bound *1
log 2   ≤   ≤ log
–   =
min ′
′ :|(,)− (,)|≤
1

(′ )
*1. Buhrman, de Wolf. CCC, 2001.
6
Log-rank conjecture for XOR functions
• Since Log-rank conjecture appears too hard in
its full generality,…
• let’s try some special class of functions.
• XOR functions: ( ⊕ ).
---  =  ∘⊕
– The linear composition of  and .
– Include important functions such as Equality,
Hamming Distance, Gap Hamming Distance.
• Interesting connections to Fourier analysis of
functions on 0,1  .
Digression: Fourier analysis
• ∀: 0,1

→ ℝ can be written as
= ∈ 0,1
–   = −1 ⋅ , and characters are orthogonal
–   :  ∈ 0,1  : Fourier coefficients of
– Parseval: If   = +1, −1 , then    2 = 1.
• Two important measures:
–
–
1
0
=

--- Spectral norm.
= :   ≠ 0
• Cauchy-Schwartz:
1
--- Fourier sparsity.
≤
1/2
0
for : 0,1

→ ±1
Log-rank Conj. For XOR functions
• Interesting connections to Fourier analysis:
• 1.  ∘⊕ =
.
0
• Log-rank Conj:   ∘⊕ ≤
•
Thm.*1
∘⊕ ≤ 2
2 /2
(1)
log 2

log −2
• Thm.*1   ∘⊕ ≤
1
.
0
1
.
–  = deg 2 (): degree of  as polynomial over 2 .
– Fact*2.  ≤ log 2  0 .
*1. Tsang, Wong, Xie, Zhang, FOCS, 2013.
*2. Bernasconi and Codenotti. IEEE Transactions on Computers, 1999.
Quantum
• 2.   ∘⊕ ≥ Ω log  ∘⊕
–

1,
=
min
: − ∞ ≤
–   =

≥ Ω log
1,
*1
1
min ′
′ :|(,)− (,)|≤
(′ )
• This paper:   ∘⊕ ≤  2 log
2
1,
, where  = deg 2 ().
– Recall classical:   ∘⊕ ≤ 2 /2 log −2  1
– Confirms quantum Log-rank Conjecture for low-degree XOR
functions.
• This talk: A simpler case   ∘⊕ = O 2 log
–   ∘⊕ = Ω log
0
0
.
. *2
*1. Lee and Shraibman. Foundations and Trends in Theoretical Computer Science, 2009.
*2. Buhrman and de Wolf. CCC, 2001.
• Much simpler.
• log
comes
very
naturally.
0
• Inherently quantum.
– Not from quantizing any classical protocol.
Goal: compute ( + )
where : 0,1  → ±1
0 + 1
2
⊗  =

∈
′ =
′

∈
→
+
∈
Fourier:  →
+   ()
∈
=

++
0 + ( +  + ) 1

2

()

|〉
Goal: compute ( + )
where : 0,1  → ±1
= |+〉

′
∈
Decoding + Fourier
0 + ( +  + ) 1

2
Measure{|+〉, |−〉}

Measure
A random  ∈ 0,1  and ( +  + ).
Recall our target: ( + ). What’s the difference?
The derivative: Δ   =   +  ().
Good: deg 2 (Δ ) ≤ deg 2 () − 1.
2
Bad: Δ  0 ≤  0 .
(That’s where the factor of 2 comes from.)
• One more issue: Only Alice
knows ! Bob doesn’t.
• It’s unaffordable to send .
• Obs:  Δ  ⊆  + , ∀.
•  =
Goal: compute ( + )
where : 0,1  → ±1
0,1
= |+〉

′
+
≝  + : ,  ∈
Decoding + Fourier
∈
0 + ( +  + ) 1

2
Measure{|+〉, |−〉}

Measure
A random  ∈ 0,1  and ( +  + ).
Recall our target: ( + ). What’s the difference?
The derivative: Δ   =   +  ().
Good: deg 2 (Δ ) ≤ deg 2 () − 1.
2
Bad: Δ  0 ≤  0 .
(That’s where the factor of 2 comes from.)
• One more issue: Only Alice
knows ! Bob doesn’t.
• It’s unaffordable to send .
• Obs:  Δ  ⊆  + , ∀.
•  =
Goal: compute ( + )
where : 0,1  → ±1
= |+〉

′
∈
Decoding + Fourier
0 + ( +  + ) 1

2
Measure{|+〉, |−〉}

Measure
A random  ∈ 0,1  and ( +  + ).
Recall our target: ( + ). What’s the difference?
The derivative: Δ   =   +  ().
Good: deg 2 (Δ ) ≤ deg 2 () − 1.
2
Bad: Δ  0 ≤  0 .
(That’s where the factor of 2 comes from.)
• One more issue: Only Alice
knows ! Bob doesn’t.
• It’s unaffordable to send .
• Obs:  Δ  ⊆  + , ∀.
•  =
• Thus in round 2, Alice and Bob
can just encode the entire
+ .
Goal: compute ( + )
where : 0,1  → ±1
= |+〉

′
∈
Decoding + Fourier
0 + ( +  + ) 1
2

Measure{|+〉, |−〉}

Measure
A random  ∈ 0,1  and ( +  + ).
Compute 2 ≝ Δ   =   +  ().
At last, deg 2  = 0, a constant function.
Cost: log  + log 2 + log 4 + ⋯ + log 2−1  ≤ 2 log ||.
Used trivial bound:  ≤

Open problems
• Get rid of the factor 2 !