Tata Institute of Fundamental Research
Quantum versus Randomized Communication Complexity, with Efficient Players
STCS Seminar
Speaker:
Uma Girish (Princeton University
United States)
Organiser:
Jaikumar Radhakrishnan
Date:
Friday, 7 Feb 2020, 11:30 to 12:30
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Abstract: We study a new type of separation between quantum and classical communication complexity, a separation which is obtained using quantum protocols where all parties are efficient, in the sense that they can be implemented by small quantum circuits with oracle access to their inputs. More precisely, we give an explicit partial Boolean function that can be computed in the quantum-simultaneous-with-entanglement model of communication, however, every interactive randomized protocol is of exponentially larger cost. Furthermore, all the parties in the quantum protocol can be implemented by quantum circuits of small size with blackbox access to the inputs. Our result qualitatively matches the strongest known separation between quantum and classical communication complexity and is obtained using a quantum protocol where all parties are efficient. Our proof technique is new in the context of communication complexity and is based on techniques from the recent oracle separation of BQP and PH.
This is a joint work with Ran Raz and Avishay Tal.
| Speaker: | Uma Girish (Princeton University United States) |
| Organiser: | Jaikumar Radhakrishnan |
| Date: | Friday, 7 Feb 2020, 11:30 to 12:30 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Abstract: We study a new type of separation between quantum and classical communication complexity, a separation which is obtained using quantum protocols where all parties are efficient, in the sense that they can be implemented by small quantum circuits with oracle access to their inputs. More precisely, we give an explicit partial Boolean function that can be computed in the quantum-simultaneous-with-entanglement model of communication, however, every interactive randomized protocol is of exponentially larger cost. Furthermore, all the parties in the quantum protocol can be implemented by quantum circuits of small size with blackbox access to the inputs. Our result qualitatively matches the strongest known separation between quantum and classical communication complexity and is obtained using a quantum protocol where all parties are efficient. Our proof technique is new in the context of communication complexity and is based on techniques from the recent oracle separation of BQP and PH.
This is a joint work with Ran Raz and Avishay Tal.
This is a joint work with Ran Raz and Avishay Tal.