Please note: This seminar will take place in DC 1304 and online.
Arkadev Chattopadhyay, Professor
School of Technology and Computer Science, Tata Institute of Fundamental Research
A major research theme in communication complexity has been understanding when can quantum protocols be exponentially more efficient than classical protocols.
Two natural classes of functions permeate the field of communication complexity. The first one, known as AND functions, consist of functions of the form f_n o AND_2, where f_n is an arbitrary n-bit Boolean function and AND_2 is just the 2-bit AND function. Two very well-known members of this class are Set-Disjointness and Inner-Product. The other class, known as XOR functions, is obtained by using the 2-bit XOR as the inner function, instead of AND. Equality is an XOR function that is the canonical example of a function where randomness provides an exponential advantage over determinism.
Until recently, the question whether quantum protocols offered truly significant advantage over their classical counterparts, even for any AND/XOR function remained open. In this work, we show that there cannot be any super-polynomial quantum advantage for AND functions, ignoring polylog(n) factors. Our results build on the recent work by some of the co-authors on structural characterizations of non-sparse Boolean functions. Very recently, and after our work was published, Gavinsky has uploaded a paper which exhibits an exponential quantum advantage, in contrast, for a total XOR function.
Joint work with Sreejata Bhattacharya, Farzan Byramji, Yogesh Dahiya and Shachar Lovett.
To attend this seminar in person, please go to DC 1304. You can also attend virtually on Zoom.