Unbounded Quantum Advantage in One-Way Strong Communication Complexity
of a Distributed Clique Labelling Relation
- URL: http://arxiv.org/abs/2305.10372v2
- Date: Wed, 26 Jul 2023 18:02:06 GMT
- Title: Unbounded Quantum Advantage in One-Way Strong Communication Complexity
of a Distributed Clique Labelling Relation
- Authors: Sumit Rout, Nitica Sakharwade, Some Sankar Bhattacharya, Ravishankar
Ramanathan, Pawe{\l} Horodecki
- Abstract summary: We investigate the one-way zero-error classical and quantum communication complexities for a class of relations induced by a distributed clique labelling problem.
We show that for the specific class of relations considered here when the players do not share any resources, there is no quantum advantage in the CCR task for any graph.
We highlight some applications of this task to semi-device-independent dimension witnessing as well as to the detection of Mutually Unbiased Bases.
- Score: 0.19090202146054183
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate the one-way zero-error classical and quantum communication
complexities for a class of relations induced by a distributed clique labelling
problem. We consider two variants: 1) the receiver outputs an answer satisfying
the relation - the traditional communication complexity of relations (CCR) and
2) the receiver has non-zero probabilities of outputting every valid answer
satisfying the relation (equivalently, the relation can be fully
reconstructed), that we denote the strong communication complexity of the
relation (S-CCR). We prove that for the specific class of relations considered
here when the players do not share any resources, there is no quantum advantage
in the CCR task for any graph. On the other hand, we show that there exist,
classes of graphs for which the separation between one-way classical and
quantum communication in the S-CCR task grow with the order of the graph $m$,
specifically, the quantum complexity is $O(1)$ while the classical complexity
is $\Omega(\log m)$. Secondly, we prove a lower bound (that is linear in the
number of cliques) on the amount of shared randomness necessary to overcome the
separation in the scenario of fixed restricted communication and connect this
to the existence of Orthogonal Arrays. Finally, we highlight some applications
of this task to semi-device-independent dimension witnessing as well as to the
detection of Mutually Unbiased Bases.
Related papers
- KPZ scaling from the Krylov space [83.88591755871734]
Recently, a superdiffusion exhibiting the Kardar-Parisi-Zhang scaling in late-time correlators and autocorrelators has been reported.
Inspired by these results, we explore the KPZ scaling in correlation functions using their realization in the Krylov operator basis.
arXiv Detail & Related papers (2024-06-04T20:57:59Z) - The Complexity of Being Entangled [0.0]
Nielsen's approach to quantum state complexity relates the minimal number of quantum gates required to prepare a state to the length of geodesics computed with a certain norm on the manifold of unitary transformations.
For a bipartite system, we investigate binding complexity, which corresponds to norms in which gates acting on a single subsystem are free of cost.
arXiv Detail & Related papers (2023-11-07T19:00:02Z) - Bounds on oblivious multiparty quantum communication complexity [0.0]
We show, for a wide class of functions, how to prove strong lower bounds on their oblivious quantum $k$-party communication complexity.
In particular, we obtain an optimal $Omega(ksqrtn)$ lower bound on the oblivious quantum $k$-party communication complexity of the $n$-bit Set-Disjointness function.
arXiv Detail & Related papers (2022-10-27T13:09:51Z) - Pipelined correlated minimum weight perfect matching of the surface code [56.01788646782563]
We describe a pipeline approach to decoding the surface code using minimum weight perfect matching.
An independent no-communication parallelizable processing stage reweights the graph according to likely correlations.
A later general stage finishes the matching.
We validate the new algorithm on the fully fault-tolerant toric, unrotated, and rotated surface codes.
arXiv Detail & Related papers (2022-05-19T19:58:02Z) - Permutation Compressors for Provably Faster Distributed Nonconvex
Optimization [68.8204255655161]
We show that the MARINA method of Gorbunov et al (2021) can be considered as a state-of-the-art method in terms of theoretical communication complexity.
Theory of MARINA to support the theory of potentially em correlated compressors, extends to the method beyond the classical independent compressors setting.
arXiv Detail & Related papers (2021-10-07T09:38:15Z) - Experimental violations of Leggett-Garg's inequalities on a quantum
computer [77.34726150561087]
We experimentally observe the violations of Leggett-Garg-Bell's inequalities on single and multi-qubit systems.
Our analysis highlights the limits of nowadays quantum platforms, showing that the above-mentioned correlation functions deviate from theoretical prediction as the number of qubits and the depth of the circuit grow.
arXiv Detail & Related papers (2021-09-06T14:35:15Z) - Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
Efficient distributed computing offers a scalable strategy for solving resource-demanding tasks.
Quantum resources are well-suited to this task, offering clear strategies that can outperform classical counterparts.
We prove that a new class of communication complexity tasks can be associated to Bell-like inequalities.
arXiv Detail & Related papers (2021-06-11T18:00:09Z) - Quantum Communication Complexity of Distribution Testing [114.31181206328276]
Two players each receive $t$ samples from one distribution over $[n]$.
The goal is to decide whether their two distributions are equal, or are $epsilon$-far apart.
We show that the quantum communication complexity of this problem is $tildeO$(tepsilon2))$ qubits when distributions have low $l$-norm.
arXiv Detail & Related papers (2020-06-26T09:05:58Z) - Solution to the Quantum Symmetric Simple Exclusion Process : the
Continuous Case [0.0]
We present a solution for the invariant probability measure of the one dimensional Q-SSEP in the infinite size limit.
We incidentally point out a possible interpretation of the Q-SSEP correlation functions via a surprising conneatorics and the associahedron polytopes.
arXiv Detail & Related papers (2020-06-22T13:20:40Z) - Tight Limits on Nonlocality from Nontrivial Communication Complexity;
a.k.a. Reliable Computation with Asymmetric Gate Noise [19.970633213740363]
It has long been known that the existence of certain superquantum nonlocal correlations would cause communication complexity to collapse.
We show that communication complexity collapses in any physical theory whose maximal winning probability exceeds the quantum value.
We provide evidence that the 0.91 result is the best possible using a large class of proof strategies.
arXiv Detail & Related papers (2018-09-25T22:39:03Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.