Asymptotic Compression of Interactive Quantum Communication using Type-Constrained de Finetti Reduction

• URL: http://arxiv.org/abs/2606.24746v1
• Date: Tue, 23 Jun 2026 16:09:31 GMT
• Title: Asymptotic Compression of Interactive Quantum Communication using Type-Constrained de Finetti Reduction
• Abstract summary: We apply our constrained de Finetti reduction to the compression of quantum interactive communication protocols with classical inputs.<n>We prove that the prior-free quantum information cost equals the worst-case input amortized quantum communication cost.
• Score: 1.4932780345357946
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: For many information processing tasks, de Finetti-style theorems can often simplify the analysis in worst-case input scenarios for which the task exhibits some permutation-invariance symmetry, as they can allow for a reduction from an analysis on worst-case inputs to that of i.i.d. inputs. If further information is available on the inputs, it might be advantageous to reflect this information in the de Finetti reduction. In our work, we focus on a form of such constraint, based on the type of the input. This allows us to obtain a conceptually simple proof of a new de Finetti reduction for classical probability distributions, derived from elementary properties from the method of types. We apply our constrained de Finetti reduction to the compression of quantum interactive communication protocols with classical inputs, and prove that the prior-free quantum information cost equals the worst-case input amortized quantum communication cost.

Related papers

• Limits of Classical correlations and Quantum advantages under (Anti-)Distinguishability constraints in Multipartite Communication [0.0]
  We show that quantum strategies without any shared entanglement can outperform the classical ones.<n>Explicit quantum protocols are studied that violate these inequalities.<n>We prove that when each sender has a binary input, the quantum advantage grows with the number of senders.
  arXiv  Detail & Related papers  (2025-06-09T12:38:58Z)
• Quantum Information-Theoretical Size Bounds for Conjunctive Queries with Functional Dependencies [5.430093460802071]
  We establish a connection between earlier work on estimating size bounds for conjunctive queries with classical information theory and quantum information theory.<n>We propose replacing the classical Shannon entropy with the quantum R'enyi entropy.<n>Although this is a promising modification, optimization with respect to the quantum states instead of classical distributions creates a new set of challenges.
  arXiv  Detail & Related papers  (2025-06-09T08:46:56Z)
• Resolvability of classical-quantum channels [54.825573549226924]
  We study the resolvability of classical-quantum channels in two settings, for the channel output generated from the worst input, and form the fixed independent and identically distributed (i.i.d.) input. For the fixed-input setting, while the direct part follows from the known quantum soft covering result, we exploit the recent alternative quantum Sanov theorem to solve the strong converse.
  arXiv  Detail & Related papers  (2024-10-22T05:18:43Z)
• Unveiling the Statistical Foundations of Chain-of-Thought Prompting Methods [59.779795063072655]
  Chain-of-Thought (CoT) prompting and its variants have gained popularity as effective methods for solving multi-step reasoning problems. We analyze CoT prompting from a statistical estimation perspective, providing a comprehensive characterization of its sample complexity.
  arXiv  Detail & Related papers  (2024-08-25T04:07:18Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Quantization for decentralized learning under subspace constraints [61.59416703323886]
  We consider decentralized optimization problems where agents have individual cost functions to minimize subject to subspace constraints. We propose and study an adaptive decentralized strategy where the agents employ differential randomized quantizers to compress their estimates. The analysis shows that, under some general conditions on the quantization noise, the strategy is stable both in terms of mean-square error and average bit rate.
  arXiv  Detail & Related papers  (2022-09-16T09:38:38Z)
• Moderate deviation expansion for fully quantum tasks [20.30365614522286]
  The moderate deviation regime is concerned with the finite block length trade-off between communication cost and error for information processing tasks. We find exact characterisations of these trade-offs for a variety of fully quantum communication tasks.
  arXiv  Detail & Related papers  (2021-12-14T05:15:22Z)
• Fault-tolerant Coding for Quantum Communication [71.206200318454]
  encode and decode circuits to reliably send messages over many uses of a noisy channel. For every quantum channel $T$ and every $eps>0$ there exists a threshold $p(epsilon,T)$ for the gate error probability below which rates larger than $C-epsilon$ are fault-tolerantly achievable. Our results are relevant in communication over large distances, and also on-chip, where distant parts of a quantum computer might need to communicate under higher levels of noise.
  arXiv  Detail & Related papers  (2020-09-15T15:10:50Z)
• The Variational Bandwidth Bottleneck: Stochastic Evaluation on an Information Budget [164.65771897804404]
  In many applications, it is desirable to extract only the relevant information from complex input data. The information bottleneck method formalizes this as an information-theoretic optimization problem. We propose the variational bandwidth bottleneck, which decides for each example on the estimated value of the privileged information.
  arXiv  Detail & Related papers  (2020-04-24T18:29:31Z)
• Using Quantum Metrological Bounds in Quantum Error Correction: A Simple Proof of the Approximate Eastin-Knill Theorem [77.34726150561087]
  We present a proof of the approximate Eastin-Knill theorem, which connects the quality of a quantum error-correcting code with its ability to achieve a universal set of logical gates. Our derivation employs powerful bounds on the quantum Fisher information in generic quantum metrological protocols.
  arXiv  Detail & Related papers  (2020-04-24T17:58:10Z)
• From Information Theory Puzzles in Deletion Channels to Deniability in Quantum Cryptography [0.0]
  We first conjecture on the basis of experimental data that the entropy of the posterior is minimized by the constant strings. We then establish a connection between covert communication and deniability to propose DC-QKE. We present an efficient coercion-resistant and quantum-secure voting scheme, based on fully homomorphic encryption.
  arXiv  Detail & Related papers  (2020-03-25T22:20:47Z)

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.