Unbounded quantum advantage in communication complexity measured by distinguishability
Communication complexity is a fundamental aspect of information science, concerned with the amount of communication required to solve a problem distributed among multiple parties. The standard quantification of one-way communication complexity relies on the minimal dimension of the communicated syst...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
American Physical Society
2024-12-01
|
| Series: | Physical Review Research |
| Online Access: | http://doi.org/10.1103/PhysRevResearch.6.043269 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850246978555871232 |
|---|---|
| author | Satyaki Manna Anubhav Chaturvedi Debashis Saha |
| author_facet | Satyaki Manna Anubhav Chaturvedi Debashis Saha |
| author_sort | Satyaki Manna |
| collection | DOAJ |
| description | Communication complexity is a fundamental aspect of information science, concerned with the amount of communication required to solve a problem distributed among multiple parties. The standard quantification of one-way communication complexity relies on the minimal dimension of the communicated systems. In this paper, we measure the communication complexity of a task by the minimal distinguishability required to accomplish it, while leaving the dimension of the communicated systems unconstrained. Distinguishability is defined as the maximum probability of correctly guessing the sender's input from the message, quantifying the message's distinctiveness relative to the sender's input. This measure becomes especially relevant when maintaining the confidentiality of the sender's input is essential. After establishing the generic framework, we focus on three relevant families of communication complexity tasks—the random access codes, equality problems defined by graphs, and the pair-distinguishability tasks. We derive general lower bounds on the minimal classical distinguishability as a function of the success metric of these tasks. We demonstrate that quantum communication outperforms classical communication presenting explicit protocols and utilizing semidefinite programming methods. In particular, we demonstrate unbounded quantum advantage for random access codes and Hadamard graph-based equality problems. Specifically, we show that the classical-to-quantum ratio of minimal distinguishability required to achieve the same success metric escalates polynomially and exponentially with the complexity of these tasks, reaching arbitrarily large values. |
| format | Article |
| id | doaj-art-389d889e35ff4b47bcca505c96f19b2e |
| institution | OA Journals |
| issn | 2643-1564 |
| language | English |
| publishDate | 2024-12-01 |
| publisher | American Physical Society |
| record_format | Article |
| series | Physical Review Research |
| spelling | doaj-art-389d889e35ff4b47bcca505c96f19b2e2025-08-20T01:59:04ZengAmerican Physical SocietyPhysical Review Research2643-15642024-12-016404326910.1103/PhysRevResearch.6.043269Unbounded quantum advantage in communication complexity measured by distinguishabilitySatyaki MannaAnubhav ChaturvediDebashis SahaCommunication complexity is a fundamental aspect of information science, concerned with the amount of communication required to solve a problem distributed among multiple parties. The standard quantification of one-way communication complexity relies on the minimal dimension of the communicated systems. In this paper, we measure the communication complexity of a task by the minimal distinguishability required to accomplish it, while leaving the dimension of the communicated systems unconstrained. Distinguishability is defined as the maximum probability of correctly guessing the sender's input from the message, quantifying the message's distinctiveness relative to the sender's input. This measure becomes especially relevant when maintaining the confidentiality of the sender's input is essential. After establishing the generic framework, we focus on three relevant families of communication complexity tasks—the random access codes, equality problems defined by graphs, and the pair-distinguishability tasks. We derive general lower bounds on the minimal classical distinguishability as a function of the success metric of these tasks. We demonstrate that quantum communication outperforms classical communication presenting explicit protocols and utilizing semidefinite programming methods. In particular, we demonstrate unbounded quantum advantage for random access codes and Hadamard graph-based equality problems. Specifically, we show that the classical-to-quantum ratio of minimal distinguishability required to achieve the same success metric escalates polynomially and exponentially with the complexity of these tasks, reaching arbitrarily large values.http://doi.org/10.1103/PhysRevResearch.6.043269 |
| spellingShingle | Satyaki Manna Anubhav Chaturvedi Debashis Saha Unbounded quantum advantage in communication complexity measured by distinguishability Physical Review Research |
| title | Unbounded quantum advantage in communication complexity measured by distinguishability |
| title_full | Unbounded quantum advantage in communication complexity measured by distinguishability |
| title_fullStr | Unbounded quantum advantage in communication complexity measured by distinguishability |
| title_full_unstemmed | Unbounded quantum advantage in communication complexity measured by distinguishability |
| title_short | Unbounded quantum advantage in communication complexity measured by distinguishability |
| title_sort | unbounded quantum advantage in communication complexity measured by distinguishability |
| url | http://doi.org/10.1103/PhysRevResearch.6.043269 |
| work_keys_str_mv | AT satyakimanna unboundedquantumadvantageincommunicationcomplexitymeasuredbydistinguishability AT anubhavchaturvedi unboundedquantumadvantageincommunicationcomplexitymeasuredbydistinguishability AT debashissaha unboundedquantumadvantageincommunicationcomplexitymeasuredbydistinguishability |