Quantum Advantage in Zero-Error Function Computation With Side Information

doi:10.1109/TIT.2025.3594298

Quantum Advantage in Zero-Error Function Computation With Side Information

2025-11-01

0

PRE

AI

DOI：10.1109/TIT.2025.3594298

Original

Original request for help

Save

Abstract

En 中文

We consider the problem of zero-error functioncomputation with side information. Alice and Bob have correlatedsourcesX,Ywith joint p.m.f. p(XY)(,). Bob wants to calculatef(X,Y) with zero error. Alice encodesm-length blocks (m >= 1)of her observations to Bob over error-free channels, which canbe classical or quantum. We consider two classical settings.(i) Alice communicates via a fixed length code (FLC), and(ii) Alice communicates via a variable length code (VLC). Inthe FLC scenario, the minimum communication rate dependson the asymptotic growth of the chromatic number of anappropriately definedm-instance confusion graphG((m)). In theVLC scenario, the corresponding rate is characterized by theasymptotics of the chromatic entropy of G((m)). In the quantumsetting, we only consider fixed length codes; the correspondingrate depends on the asymptotic growth of the orthogonal rankof the complement of G((m)). The behavior of the communicationrates depends critically on G((m)), which is shown to be sandwiched between G(Vm)(m-times strong product) andG boolean OR m(m-times ORproduct) respectively. Our work presents necessary and sufficientconditions on the function f(,) and joint p.m.f.p(XY)(,) such that G((m)) equals either G(m )or G(boolean OR m). Our work explores the multitudeof possible behaviors of the quantum and classical (FLC/VLC)rates in the single-instance case and the asymptotic (inm) casefor several classes of confusion graphs. We show that there existcon fusion graphs for which the quantum rate is exponentially smaller than the FLC and VLC rates. With respect to FLCs, weshow, e.g., that the quantum advantage may exist in the single-instance but disappear in the asymptotic rate. With respect to VLCs, we show that there are scenarios where the VLC rate canbe smaller than the quantum rate and vice versa.

Keywords:

Codes

Symbols

Image color analysis

Source coding

Quantum advantage

Training

Random variables

Indexes

Entropy

Data mining

Zero-error

function computation

chromatic number

orthogonal rank

quantum advantage

Quantum Advantage in Zero-Error Function Computation With Side Information

Abstract

Journal

Organization

Cited Papers