Optimality of meta-converse for channel simulation

• URL: http://arxiv.org/abs/2410.08140v1
• Date: Thu, 10 Oct 2024 17:24:04 GMT
• Title: Optimality of meta-converse for channel simulation
• Authors: Aadil Oufkir, Omar Fawzi, Mario Berta,
• Abstract summary: 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.
• Score: 9.66763121039393
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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--which corresponds to the natural linear programming meta-converse for channel simulation--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. Our main result is for classical and classical-quantum channels, for which we employ ideas from approximation algorithms to give a guarantee on the ratio of success probabilities of at least $(1-\mathrm{e}^{-1})$. We further show this ratio to be optimal for the purely classical case. It can be improved to $(1-t^{-1})$ using $O(\ln \ln(t))$ additional bits of communication.

Related papers

• 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)
• Exponents for Shared Randomness-Assisted Channel Simulation [10.437113494732605]
  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.
  arXiv  Detail & Related papers  (2024-10-09T16:45:58Z)
• Distributed Extra-gradient with Optimal Complexity and Communication Guarantees [60.571030754252824]
  We consider monotone variational inequality (VI) problems in multi-GPU settings where multiple processors/workers/clients have access to local dual vectors. Extra-gradient, which is a de facto algorithm for monotone VI problems, has not been designed to be communication-efficient. We propose a quantized generalized extra-gradient (Q-GenX), which is an unbiased and adaptive compression method tailored to solve VIs.
  arXiv  Detail & Related papers  (2023-08-17T21:15:04Z)
• Stochastic Approach For Simulating Quantum Noise Using Tensor Networks [0.8258451067861933]
  We show that our simulation error is relatively low, even for large numbers of qubits. By using the slicing technique, we can simulate up to 100 qubitOA circuits with high depth using supercomputers.
  arXiv  Detail & Related papers  (2022-10-28T03:44:59Z)
• Exploiting Temporal Structures of Cyclostationary Signals for Data-Driven Single-Channel Source Separation [98.95383921866096]
  We study the problem of single-channel source separation (SCSS) We focus on cyclostationary signals, which are particularly suitable in a variety of application domains. We propose a deep learning approach using a U-Net architecture, which is competitive with the minimum MSE estimator.
  arXiv  Detail & Related papers  (2022-08-22T14:04:56Z)
• The minimal communication cost for simulating entangled qubits [0.0]
  We analyze the amount of classical communication required to reproduce the statistics of local projective measurements on a general pair of entangled qubits. We construct a protocol that perfectly simulates local projective measurements on all entangled qubit pairs by communicating one classical trit.
  arXiv  Detail & Related papers  (2022-07-25T18:25:49Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
  We show how to apply the quantum approximate optimization algorithm (RQAOA) to MAX-$k$-CUT, the problem of finding an approximate $k$-vertex coloring of a graph. We construct an efficient classical simulation algorithm which simulates level-$1$ QAOA and level-$1$ RQAOA for arbitrary graphs.
  arXiv  Detail & Related papers  (2020-11-26T18:22:21Z)
• Plug-And-Play Learned Gaussian-mixture Approximate Message Passing [71.74028918819046]
  We propose a plug-and-play compressed sensing (CS) recovery algorithm suitable for any i.i.d. source prior. Our algorithm builds upon Borgerding's learned AMP (LAMP), yet significantly improves it by adopting a universal denoising function within the algorithm. Numerical evaluation shows that the L-GM-AMP algorithm achieves state-of-the-art performance without any knowledge of the source prior.
  arXiv  Detail & Related papers  (2020-11-18T16:40:45Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  We study the learnability of halfspaces in the presence of Tsybakov noise. We give an algorithm that achieves misclassification error $epsilon$ with respect to the true halfspace.
  arXiv  Detail & Related papers  (2020-06-11T14:25:02Z)
• Capacity Approaching Coding for Low Noise Interactive Quantum Communication, Part I: Large Alphabets [15.078027648304115]
  We consider the problem of implementing two-party interactive quantum communication over noisy channels. For a noiseless qudit channel over a $mathrmpoly(n)$ size alphabet, our main result is a simulation method that fails with probability less than $2-Theta(nepsilon)$ We conjecture that it is optimal up to a constant factor in the $sqrtepsilon$ term.
  arXiv  Detail & Related papers  (2020-01-09T02:48:43Z)

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.