The computational two-way quantum capacity
- URL: http://arxiv.org/abs/2601.15393v1
- Date: Wed, 21 Jan 2026 19:04:07 GMT
- Title: The computational two-way quantum capacity
- Authors: Johannes Jakob Meyer, Jacopo Rizzo, Asad Raza, Lorenzo Leone, Sofiene Jerbi, Jens Eisert,
- Abstract summary: 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.
- Score: 0.29555437538581053
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum channel capacities are fundamental to quantum information theory. Their definition, however, does not limit the computational resources of sender and receiver. In this work, we initiate the study of computational quantum capacities. These quantify how much information can be reliably transmitted when imposing the natural requirement that en- and decoding have to be computationally efficient. We focus on the computational two-way quantum capacity and showcase that it is closely related to the computational distillable entanglement of the Choi state of the channel. This connection allows us to show a stark computational capacity separation. Under standard cryptographic assumptions, there exists a quantum channel of polynomial complexity whose computational two-way quantum capacity vanishes while its unbounded counterpart is nearly maximal. More so, we show that there exists a sharp transition in computational quantum capacity from nearly maximal to zero when the channel complexity leaves the polynomial realm. Our results demonstrate that the natural requirement of computational efficiency can radically alter the limits of quantum communication.
Related papers
- Quantum-Channel Matrix Optimization for Holevo Bound Enhancement [87.57725685513088]
We propose a unified projected gradient ascent algorithm to optimize the quantum channel given a fixed input ensemble.<n> Simulation results demonstrate that the proposed quantum channel optimization yields higher Holevo bounds than input ensemble optimization.
arXiv Detail & Related papers (2026-02-19T04:15:03Z) - On the undecidability of quantum channel capacities [2.1088544691147435]
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.
arXiv Detail & Related papers (2026-01-30T02:35:01Z) - 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) - Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [62.46800898243033]
Recent progress in quantum learning theory prompts a question: can linear properties of a large-qubit circuit be efficiently learned from measurement data generated by varying classical inputs?<n>We prove that the sample complexity scaling linearly in $d$ is required to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d.<n>We propose a kernel-based method leveraging classical shadows and truncated trigonometric expansions, enabling a controllable trade-off between prediction accuracy and computational overhead.
arXiv Detail & Related papers (2024-08-22T08:21:28Z) - The curse of random quantum data [62.24825255497622]
We quantify the performances of quantum machine learning in the landscape of quantum data.
We find that the training efficiency and generalization capabilities in quantum machine learning will be exponentially suppressed with the increase in qubits.
Our findings apply to both the quantum kernel method and the large-width limit of quantum neural networks.
arXiv Detail & Related papers (2024-08-19T12:18:07Z) - Computable and noncomputable in the quantum domain: statements and conjectures [0.70224924046445]
We consider an approach to the question of describing a class of problems whose solution can be accelerated by a quantum computer.
The unitary operation that transforms the initial quantum state into the desired one must be decomposable into a sequence of one- and two-qubit gates.
arXiv Detail & Related papers (2024-03-25T15:47:35Z) - Oblivious Quantum Computation and Delegated Multiparty Quantum
Computation [61.12008553173672]
We propose a new concept, oblivious computation quantum computation, where secrecy of the input qubits and the program to identify the quantum gates are required.
Exploiting quantum teleportation, we propose a two-server protocol for this task.
Also, we discuss delegated multiparty quantum computation, in which, several users ask multiparty quantum computation to server(s) only using classical communications.
arXiv Detail & Related papers (2022-11-02T09:01:33Z) - 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) - Quantum reservoir computation utilising scale-free networks [0.0]
We introduce a new reservoir computational model for pattern recognition showing a quantum advantage utilizing scale-free networks.
The simplicity in our approach illustrates the computational power in quantum complexity as well as provide new applications for such processors.
arXiv Detail & Related papers (2021-08-27T06:28:08Z) - 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.