Report

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. ---() • Randomized: Players have access to random bits; 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. About quantum protocol • Much simpler. • log comes very naturally. 0 • Inherently quantum. – Not from quantizing any classical protocol. Goal: compute ( + ) where : 0,1 → ±1 0 + 1 2 ⊗ = Add phase () ∈ ′ = ′ ∈ → + ∈ Fourier: → + () ∈ = ++ 0 + ( + + ) 1 2 () |〉 Goal: compute ( + ) where : 0,1 → ±1 = |+〉 ′ ∈ Add phase () 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.) Add phase () • One more issue: Only Alice knows ! Bob doesn’t. • It’s unaffordable to send . • Obs: Δ ⊆ + , ∀. • = Goal: compute ( + ) where : 0,1 → ±1 = |+〉 ′ ∈ Add phase () 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 = |+〉 ′ ∈ Add phase () 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 ! • What can we say about additive structure of supp for Boolean functions ? Say, + ≤ 1.5 ?