On the undecidability of quantum channel capacities

• URL: http://arxiv.org/abs/2601.22471v1
• Date: Fri, 30 Jan 2026 02:35:01 GMT
• Title: On the undecidability of quantum channel capacities
• Authors: Archishna Bhattacharyya, Arthur Mehta, Yuming Zhao,
• Abstract summary: We show that, for a general quantum channel, it is QMA-hard to compute its quantum capacity, and that the maximal-entanglement-assisted zero-error one-shot classical capacity is uncomputable.
• Score: 2.1088544691147435
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: An important distinction in our understanding of capacities of classical versus quantum channels is marked by the following question: is there an algorithm which can compute (or even efficiently compute) the capacity? While there is overwhelming evidence suggesting that quantum channel capacities may be uncomputable, a formal proof of any such statement is elusive. We initiate the study of the hardness of computing quantum channel capacities. We show that, for a general quantum channel, it is QMA-hard to compute its quantum capacity, and that the maximal-entanglement-assisted zero-error one-shot classical capacity is uncomputable.

Related papers

• The computational two-way quantum capacity [0.29555437538581053]
  Quantum channel capacities are fundamental to quantum information theory.<n>We show that the natural requirement of computational efficiency can radically alter the limits of quantum communication.
  arXiv  Detail & Related papers  (2026-01-21T19:04:07Z)
• Quantum-Classical Separation in Bounded-Resource Tasks Arising from Measurement Contextuality [107.84586711462556]
  We show that quantum contextuality enables certain tasks to be performed with success probabilities beyond classical limits.<n>Our work proposes novel ways to benchmark quantum processors using contextuality-based algorithms.
  arXiv  Detail & Related papers  (2025-12-01T23:54:32Z)
• On small perturbations of coherent information [7.078713722203906]
  Quantum capacity quantifies the amount of quantum information that can be transmitted by a quantum channel with an arbitrary small probability of error.<n>We develop perturbative methods for analyzing the behavior of coherent information of a quantum channel with respect to small perturbations of the input state.<n>We show how our criteria yield sufficient conditions for superadditivity of one-shot quantum capacity, and also for detecting a positive gap between one-shot private capacity and one-shot quantum capacity.
  arXiv  Detail & Related papers  (2025-07-22T18:02:27Z)
• General channel capacities from quantum channel-state duality [0.0]
  The quantum channel-state duality permits the characterization of a quantum process through a quantum state, referred to as a Choi state.<n>In this work, the fundamental theorems regarding quantum channel capacity are proven when Choi states are considered as sources.<n>It gives rise to novel opportunities for the comprehension of superadditivity phenomena and the discovery of new classes of quantum error-correction codes.
  arXiv  Detail & Related papers  (2025-04-02T06:58:25Z)
• Capacities of quantum Markovian noise for large times [8.302146576157497]
  Given a quantum Markovian noise model, we study the maximum dimension of a classical or quantum system that can be stored for arbitrarily large time.<n>We show that, unlike the fixed time setting, in the limit of infinite time, the classical and quantum capacities are characterized by efficiently computable properties of the peripheral spectrum of the quantum channel.
  arXiv  Detail & Related papers  (2024-07-31T19:02:50Z)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical. We show that tests of quantumness that follow a certain template, which captures recent proposals such as (Kalai et al., 2022) can in fact do much more. Namely, the same protocols can be used for certifying a qubit, a building-block that stands at the heart of applications such as certifiable randomness and classical delegation of quantum computation.
  arXiv  Detail & Related papers  (2023-03-02T14:18:17Z)
• Optimal Stochastic Resource Allocation for Distributed Quantum Computing [50.809738453571015]
  We propose a resource allocation scheme for distributed quantum computing (DQC) based on programming to minimize the total deployment cost for quantum resources. The evaluation demonstrates the effectiveness and ability of the proposed scheme to balance the utilization of quantum computers and on-demand quantum computers.
  arXiv  Detail & Related papers  (2022-09-16T02:37:32Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• An additive refinement of quantum channel capacities [0.0]
  Capacities of quantum channels are fundamental quantities in the theory of quantum information.<n>Asymptotic regularization is generically necessary making the study of capacities notoriously hard.<n>We prove additive quantities for quantum channel capacities that can be employed for quantum Shannon theorems.
  arXiv  Detail & Related papers  (2022-05-15T07:21:38Z)
• Efficient criteria of quantumness for a large system of qubits [58.720142291102135]
  We discuss the dimensionless combinations of basic parameters of large, partially quantum coherent systems. Based on analytical and numerical calculations, we suggest one such number for a system of qubits undergoing adiabatic evolution.
  arXiv  Detail & Related papers  (2021-08-30T23:50:05Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
  arXiv  Detail & Related papers  (2021-07-05T17:45:41Z)

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.