Exponents for Shared Randomness-Assisted Channel Simulation

• URL: http://arxiv.org/abs/2410.07051v1
• Date: Wed, 9 Oct 2024 16:45:58 GMT
• Title: Exponents for Shared Randomness-Assisted Channel Simulation
• Authors: Aadil Oufkir, Michael X. Cao, Hao-Chung Cheng, Mario Berta,
• Abstract summary: We determine the exact error and strong converse exponents of shared randomness-assisted channel simulation in worst case total-variation distance. Strikingly, and in stark contrast to channel coding, there are no critical rates, allowing a tight characterization for arbitrary rates below and above the simulation capacity.
• Score: 10.437113494732605
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We determine the exact error and strong converse exponents of shared randomness-assisted channel simulation in worst case total-variation distance. Namely, we find that these exponents can be written as simple optimizations over the R\'enyi channel mutual information. Strikingly, and in stark contrast to channel coding, there are no critical rates, allowing a tight characterization for arbitrary rates below and above the simulation capacity. We derive our results by asymptotically expanding the meta-converse for channel simulation [Cao {\it et al.}, IEEE Trans.~Inf.~Theory (2024)], which corresponds to non-signaling assisted codes. We prove this to be asymptotically tight by employing the approximation algorithms from [Berta {\it et al.}, Proc.~IEEE ISIT (2024)], which show how to round any non-signaling assisted strategy to a strategy that only uses shared randomness. Notably, this implies that any additional quantum entanglement-assistance does not change the error or the strong converse exponents.

Related papers

• One-shot Multiple Access Channel Simulation [9.271640666465364]
  We consider the problem of shared randomness-assisted multiple access channel (MAC) simulation for product inputs. We characterize the one-shot communication cost region via almost-matching inner and outer bounds in terms of the smooth max-information of the channel.
  arXiv  Detail & Related papers  (2024-10-22T17:18:38Z)
• Exponents for classical-quantum channel simulation in purified distance [5.598487000369366]
  We determine the exact error and strong converse exponent for entanglement-assisted classical-quantum channel simulation. We critically use various properties of the quantum fidelity, additional auxiliary channel techniques, approximations via Chebyshev inequalities, and entropic continuity bounds.
  arXiv  Detail & Related papers  (2024-10-14T17:45:41Z)
• Optimality of meta-converse for channel simulation [9.66763121039393]
  We study the effect of shared non-signaling correlations for the problem of simulating a channel using noiseless communication in the one-shot setting. For classical channels, we show how to round any non-signaling-assisted simulation strategy to a strategy that only uses shared randomness. For quantum channels, we round any non-signaling-assisted simulation strategy to a strategy that only uses shared entanglement.
  arXiv  Detail & Related papers  (2024-10-10T17:24:04Z)
• Error exponent of activated non-signaling assisted classical-quantum channel coding [12.221087476416056]
  We find that the optimal exponent--also called reliability function--is equal to the well-known sphere packing bound. Remarkably, there is no critical rate and our characterization remains tight for arbitrarily low rates below the capacity.
  arXiv  Detail & Related papers  (2024-10-01T21:26:17Z)
• Channel Simulation: Finite Blocklengths and Broadcast Channels [13.561997774592667]
  We study channel simulation under common randomness assistance in the finite-blocklength regime. We identify the smooth channel max-information as a linear program one-shot converse on the minimal simulation cost for fixed error tolerance.
  arXiv  Detail & Related papers  (2022-12-22T13:08:55Z)
• A Stochastic Newton Algorithm for Distributed Convex Optimization [62.20732134991661]
  We analyze a Newton algorithm for homogeneous distributed convex optimization, where each machine can calculate gradients of the same population objective. We show that our method can reduce the number, and frequency, of required communication rounds compared to existing methods without hurting performance.
  arXiv  Detail & Related papers  (2021-10-07T17:51:10Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sampling (AIS) and related algorithms are highly effective tools for marginal likelihood estimation. Differentiability is a desirable property as it would admit the possibility of optimizing marginal likelihood as an objective. We propose a differentiable algorithm by abandoning Metropolis-Hastings steps, which further unlocks mini-batch computation.
  arXiv  Detail & Related papers  (2021-07-21T17:10:14Z)
• Accurate methods for the analysis of strong-drive effects in parametric gates [94.70553167084388]
  We show how to efficiently extract gate parameters using exact numerics and a perturbative analytical approach. We identify optimal regimes of operation for different types of gates including $i$SWAP, controlled-Z, and CNOT.
  arXiv  Detail & Related papers  (2021-07-06T02:02:54Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  It is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth convex optimization have complexity bounds with dependence on confidence level. We propose novel stepsize rules for two methods with gradient clipping.
  arXiv  Detail & Related papers  (2021-06-10T17:54:21Z)
• Efficient classical simulation of random shallow 2D quantum circuits [104.50546079040298]
  Random quantum circuits are commonly viewed as hard to simulate classically. We show that approximate simulation of typical instances is almost as hard as exact simulation. We also conjecture that sufficiently shallow random circuits are efficiently simulable more generally.
  arXiv  Detail & Related papers  (2019-12-31T19:00:00Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  We propose a novel technique for analyzing adaptive sampling called the em Simulator. We prove the first instance-based lower bounds the top-k problem which incorporate the appropriate log-factors. Our new analysis inspires a simple and near-optimal for the best-arm and top-k identification, the first em practical of its kind for the latter problem.
  arXiv  Detail & Related papers  (2017-02-16T23:42:02Z)

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.