Quantum Protocols for XOR Functions | Communication Complexity

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 Log Rank Conjecture*2 Rank lower bound*1 log2???? ?? ? ? 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. log? 1???? ?? *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 log2???? ?? ? ? log? 1???? ?? Quantum: rank lower bound *1 log2??????? ??? log? 1??????? ? :|?(?,?) ? (?,?)| ?????(? ) ?????? = min *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: ? --- Spectral norm. ? 0= Cauchy-Schwartz: ? 1 1= ? ? ? ?: ? ? 0 --- Fourier sparsity. 1/2for ?: 0,1? 1 ? 0

Log-rank Conj. For XOR functions Interesting connections to Fourier analysis: 1. ???? ?? = ? 0. ?(1) ? Log-rank Conj: ? ? log2 Thm.*1 ? ? 2?2/2log? 2 ? 0. 1 Thm.*1 ? ? ? ? ? ? = deg2(?): degree of ? as polynomial over ?2. Fact*2. ? log2 ? 1. 0. *1. Tsang, Wong, Xie, Zhang, FOCS, 2013. *2. Bernasconi and Codenotti. IEEE Transactions on Computers, 1999.

Quantum log ? 2. ? ? log??????? 1,?*1 ? 1,?= min ?1 ?: ? ? ? ? :|?(?,?) ? (?,?)| ?????(? ) This paper: ? ? ? 2?log ? Recall classical: ? ? 2?2/2log? 2 ? Confirms quantum Log-rank Conjecture for low-degree XOR functions. This talk: A simpler case ??? = O 2?log ? ??? = log ? ?????? = min 1,?, where ? = deg2(?). 1 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 ? 0 comes very naturally. 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 One more issue: Only Alice knows ?! Bob doesn t. It s unaffordable to send ?. Obs: ???? ?? ? + ?, ?. ? = ???? ? ? Measure{|+ ,| } Measure ? A random ? 0,1? and ?(? + ? + ?). Recall our target: ?(? + ?). What s the difference? The derivative: ?? ? = ? ? + ? ?(?). Good: deg2( ??) deg2(?) 1. Bad: ?? ? 0 (That s where the factor of 2? comes from.) 2. 0

Goal: compute ?(? + ?) where ?: 0,1? 1 0,1? ? ? ? ??? ? ? ? = |+ Add phase ??(?) ? ? ? ? + ? ? + ?:?,? ? Decoding + Fourier 0 + ?(? + ? + ?) 1 ? 2 One more issue: Only Alice knows ?! Bob doesn t. It s unaffordable to send ?. Obs: ???? ?? ? + ?, ?. ? = ???? ? ? ? Measure{|+ ,| } Measure ? A random ? 0,1? and ?(? + ? + ?). Recall our target: ?(? + ?). What s the difference? The derivative: ?? ? = ? ? + ? ?(?). Good: deg2( ??) deg2(?) 1. Bad: ?? ? 0 (That s where the factor of 2? comes from.) 2. 0

Goal: compute ?(? + ?) where ?: 0,1? 1 ? ? ? ??? ? ? ? = |+ Add phase ??(?) ? ? ? Decoding + Fourier 0 + ?(? + ? + ?) 1 ? 2 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 ? + ?. ? Measure{|+ ,| } Measure ? A random ? 0,1? and ?(? + ? + ?). Recall our target: ?(? + ?). What s the difference? The derivative: ?? ? = ? ? + ? ?(?). Good: deg2( ??) deg2(?) 1. Bad: ?? ? 0 (That s where the factor of 2? comes from.) 2. 0

Goal: compute ?(? + ?) where ?: 0,1? 1 ? ? ? ??? ? ? ? = |+ Add phase ??(?) ? ? ? Decoding + Fourier 0 + ?(? + ? + ?) 1 ? 2 ? Measure{|+ ,| } Measure ? A random ? 0,1? and ?(? + ? + ?). Compute ?2 ?? ? = ? ? + ? ?(?). At last, deg2?? = 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?

Thanks