Alladi Ramakrishnan Hall

Role of Symmetry in Quantum Query and Communication Complexity

Manaswi Paraashar

Department of Computer Science, University of Copenhagen.

Join Zoom Meeting
zoom.us/j/99598370034

Meeting ID: 995 9837 0034
Passcode: 941422

Quantum computing is currently one of the most active areas of research, mainly due to its ability to outperform classical computing for certain computational tasks. We will look at quantum computing through the lenses of two central and closely-related models of computation: query complexity and communication complexity. The majority of provable advantages of quantum computing over classical computing are found within these models, which makes them crucial. In this talk, I will discuss quantum query and communication complexity, with a focus on the role of symmetry.

Along the way I will give a brief overview of some of my results and current research interests. I will describe the problem of quantum query-to-communication simulation. It is a well-known fact that classical query algorithms for an n-bit Boolean function can be simulated to give communication protocols of a related communication problem with only a constant overhead. Buhrman, Cleve and Wigderson (STOC'98) showed that this query-to-communication simulation can also be performed in the quantum world, however, with an O(log n) overhead. Whether this overhead is necessary was a long-standing open problem. We resolve this open problem, with symmetry associated with Boolean functions playing a central role. We will also explore how symmetry affects the relationship between complexity measures of Boolean functions and can be exploited in designing quantum algorithms for computing over noisy data.

This talk is based on an ongoing work and the following papers:
- Quantum Query-To-Communication Simulation Needs a Logarithmic Overhead. Sourav Chakraborty, Arkadev Chattopadhyay, Nikhil S. Mande and Manaswi Paraashar. QIP 2020 and CCC 2020.

- Symmetry and Quantum Query-to-Communication Simulation. Sourav Chakraborty, Arkadev Chattopadhyay, Peter Hoyer, Nikhil S. Mande, Manaswi Paraashar and Ronald de Wolf. STACS 2022.

- Separations Between Combinatorial Measures for Transitive Functions. Sourav Chakraborty, Chandrima Kayal and Manaswi Paraashar. ICALP 2022.
- Randomized and quantum query complexities of finding a king in a tournament. Nikhil S. Mande, Manaswi Paraashar and Nitin Saurabh. FSTTCS 2023.

- Local Correction of Linear Functions over the Boolean Cube. Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar, Srikanth Srinivasan and Madhu Sudan. STOC 2024.

- On the communication complexity of finding a king. Nikhil Mande, Manaswi Paraashar, Swagato Sanyal and Nitin Saurabh. Manuscript. 2024.