Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.14785

Classical Communication Helps Single-Shot Quantum Compression

Omri Farber, Gilad Gour

quant-phmath-phSubmitted Oct 10, 2026• Announced Oct 13, 2026• 0 citations
arXivHTMLPDF

Abstract

Free classical communication can yield an unbounded single-shot saving in quantum compression, even though it leaves the asymptotic rate of an i.i.d. source unchanged. At every fixed error in $(0,1)$, we exhibit sources whose unassisted compression cost is arbitrarily large, yet a single qubit suffices with classical communication and no preshared entanglement. We establish this separation by determining the exact optimal source fidelity for compression through an $m$-dimensional noiseless quantum channel, with and without free classical communication, while preserving correlations with an inaccessible reference. Without classical assistance, the optimal fidelity is exactly the Ky Fan norm $\|ρ\|_{(m)}$, the sum of the $m$ largest eigenvalues of the source state. With classical assistance, we obtain an explicit spectral threshold formula and a protocol attaining it. Classical communication strictly improves fidelity whenever $m$ is smaller than the source rank. The corresponding compression costs are two smoothed versions of the log-rank entropy, also called max-entropy: trace-distance smoothing under local operations and quadratic smoothing under LOCC. For i.i.d. copies of a fixed source with positive entropy variance, however, the two costs have identical first-, second-, and third-order asymptotic terms. For nonlattice spectra, we determine the constant-order advantage: classical communication saves $\log_2(e)-1$ bits per block asymptotically, and the ratio of assisted to unassisted minimum communication dimensions converges to $2/e$.

AI Summary

The paper asks how free classical communication changes single-shot quantum compression without preshared entanglement, when reconstruction must preserve correlations with an inaccessible reference. Accuracy is measured by source fidelity, the square root of entanglement fidelity. It determines the optimal fidelity through an $m$-dimensional noiseless quantum channel exactly. With local encoding and decoding alone, the optimum is $\sum_{i=1}^m p_i$, where $p_i$ are the source eigenvalues in decreasing order. With LOCC, it is $\max_{0\leq\Lambda\leq I,\,\operatorname{tr}\Lambda^2\leq m}\operatorname{tr}(\rho\Lambda)$, with an explicit clipped spectral optimizer. Classical communication strictly improves fidelity whenever $m<\operatorname{rank}\rho$. The corresponding minimum dimensions are characterized by trace-distance-smoothed log-rank and a quadratic effect smoothing, respectively. At every fixed fidelity threshold $1-\epsilon\in(0,1)$, an explicit family of rank-$n^2+1$ sources requires dimension $n+1$ without assistance but only dimension two with classical communication. For i.i.d. copies of a fixed source with positive entropy variance, both costs share the first three asymptotic orders. For nonlattice log-spectra, the assisted-to-unassisted dimension ratio converges to $2/e$, saving $\log_2(e)-1\approx0.442695$ bits per block. Proofs combine channel converses, a reduction of LOCC implementations to rank-bounded Kraus operators, an explicit instrument attaining the previously studied quadratic optimum, and spectral asymptotics. The constant-order limit excludes lattice spectra; uniform spectra have a different limit. Minimum classical communication is not determined, and extensions to quantum side information remain open.

Little sign of AI-generated textAI use disclosed
the authors used GPT-6 Astra via Codex for substantial assistance in exploring, developing, and checking the i.i.d. asymptotic analysis leading to Theorem~\ref{thm:higher-order}, as well as in preparing the manuscript and organizing references.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
23 pages, no figures, comments are welcome

Related papers

One-Shot Entanglement-Assisted Quantum and Classical Communication

Nilanjana Datta, Min-Hsiu Hsieh

We study entanglement-assisted quantum and classical communication over a single use of a quantum channel, which itself can correspond to a finite number of uses of a channel with arbitrarily correlated noise. We obtain characterizations of the corresponding one-shot capacities by establishing upper and lower bounds on them in terms of the difference of two smoothed entropic quantities. In the case of a memoryless channel, the upper and lower bounds converge to the known single-letter formulas for the corresponding capacities, in the limit of asymptotically many uses of it. Our results imply that the difference of two smoothed entropic quantities characterizing the one-shot entanglement-assisted capacities serves as a one-shot analog of the mutual information, since it reduces to the mutual information, between the output of the channel and a system purifying its input, in the asymptotic, memoryless scenario.

arXiv:1105.3321•IEEE Transactions on Information Theory•Nov 21, 2012•55 citations

Classical Communication Cost of a Bipartite Quantum Channel Assisted by Non-Signaling Correlations

Chengkai Zhu, Xuanqiang Zhao, Xin Wang

Understanding the classical communication cost of simulating a quantum channel is a fundamental problem in quantum information theory, which becomes even more intriguing when considering the role of non-locality in quantum information processing. This paper investigates the bidirectional classical communication cost of simulating a bipartite quantum channel assisted by non-signalling correlations, which are permitted across the spatial dimension between the two parties. By introducing non-signalling superchannels, we present lower and upper bounds on the one-shot $ε$-error one-way classical communication cost of a bipartite channel via its smooth max-relative entropy of one-way classical communication, and establish that the asymptotic exact cost is given by its max-relative entropy of one-way classical communication. For the bidirectional scenario, we derive semidefinite programming (SDP) formulations for the one-shot exact bidirectional classical communication cost via non-signalling bipartite superchannels. We further introduce a channel's bipartite conditional min-entropy as an efficiently computable lower bound on the asymptotic cost of bidirectional classical communication. Our results in both one-shot and asymptotic settings provide lower bounds on the entanglement-assisted simulation cost in scenarios where entanglement is available to the two parties. Moreover, we propose a seesaw-based algorithm to compute an upper bound on the minimum simulation error via local operations and shared entanglement, which provides valuable insights into the relationship between non-signalling bipartite superchannels and more physically realizable protocols. Numerical experiments demonstrate the effectiveness of our bounds in estimating communication costs for various quantum channels, showing that our bounds can be tight in different scenarios.

arXiv:2408.02506•IEEE Transactions on Information Theory•May 9, 2025•1 citation

Trading quantum for classical resources in quantum data compression

Patrick M. Hayden, Richard Jozsa, Andreas Winter

We study the visible compression of a source E={|φi〉,pi} of pure quantum signal states or, more formally, the minimal resources per signal required to represent arbitrarily long strings of signals with arbitrarily high fidelity, when the compressor is given the identity of the input state sequence as classical information. According to the quantum source coding theorem, the optimal quantum rate is the von Neumann entropy S(E) qubits per signal. We develop a refinement of this theorem in order to analyze the situation in which the states are coded into classical and quantum bits that are quantified separately. This leads to a trade-off curve Q*(R), where Q*(R) qubits per signal is the optimal quantum rate for a given classical rate of R bits per signal. Our main result is an explicit characterization of this trade-off function by a simple formula in terms of only single-signal, perfect fidelity encodings of the source. We give a thorough discussion of many further mathematical properties of our formula, including an analysis of its behavior for group covariant sources and a generalization to sources with continuously parametrized states. We also show that our result leads to a number of corollaries characterizing the trade-off between information gain and state disturbance for quantum sources. In addition, we indicate how our techniques also provide a solution to the so-called remote state preparation problem. Finally, we develop a probability-free version of our main result which may be interpreted as an answer to the question: “How many classical bits does a qubit cost?” This theorem provides a type of dual to Holevo’s theorem, insofar as the latter characterizes the cost of coding classical bits into qubits.

arXiv:quant-ph/0204038•Journal of Mathematical Physics•Sep 1, 2002•41 citations

Quantum Compression and Quantum Learning via Information Theory

Shima Bab Hadiashar

This thesis consists of two parts: quantum compression and quantum learning theory. A common theme between these problems is that we study them through the lens of information theory. \n \nWe first study the task of visible compression of an ensemble of quantum states with entanglement assistance in the one-shot setting. The protocols achieving the best compression use many more qubits of shared entanglement than the number of qubits in the states in the ensemble. Other compression protocols, with potentially higher communication cost, have entanglement cost bounded by the number of qubits in the given states. This motivates the question as to whether entanglement is truly necessary for compression, and if so, how much of it is needed. We show that an ensemble given by Jain, Radhakrishnan, and Sen (ICALP'03) cannot be compressed by more than a constant number of qubits without shared entanglement, while in the presence of shared entanglement, the communication cost of compression can be arbitrarily smaller than the entanglement cost. \n \nNext, we study the task of quantum state redistribution, the most general version of compression of quantum states. We design a protocol for this task with communication cost in terms of a measure of distance from quantum Markov chains. More precisely, the distance is defined in terms of quantum max-relative entropy and quantum hypothesis testing entropy. Our result is the first to connect quantum state redistribution and Markov chains and gives an operational interpretation for a possible one-shot analogue of quantum conditional mutual information. The communication cost of our protocol is lower than all previously known ones and asymptotically achieves the well-known rate of quantum conditional mutual information. \n \nIn the last part, we focus on quantum algorithms for learning Boolean functions using quantum examples. We consider two commonly studied models of learning, namely, quantum PAC learning and quantum agnostic learning. We reproduce the optimal lower bounds by Arunachalam and de Wolf (JMLR’18) for the sample complexity of either of these models using information theory and spectral analysis. Our proofs are simpler than the previous ones and the techniques can be possibly extended to similar scenarios.

•Dec 21, 2020•1 citation

One-Shot Lossy Quantum Data Compression

Nilanjana Datta, Joseph M. Renes, Renato Renner +1 more

We provide a framework for one-shot quantum rate distortion coding, in which the goal is to determine the minimum number of qubits required to compress quantum information as a function of the probability that the distortion incurred upon decompression exceeds some specified level. We obtain a one-shot characterization of the minimum qubit compression size for an entanglement-assisted quantum rate-distortion code in terms of the smooth max-information, a quantity previously employed in the one-shot quantum reverse Shannon theorem. Next, we show how this characterization converges to the known expression for the entanglement-assisted quantum rate distortion function for asymptotically many copies of a memoryless quantum information source. Finally, we give a tight, finite blocklength characterization for the entanglement-assisted minimum qubit compression size of a memoryless isotropic qubit source subject to an average symbolwise distortion constraint.

arXiv:1304.2336•IEEE Transactions on Information Theory•Sep 26, 2013•45 citations

Processing correlated quantum systems in the one-shot setting

Ian George

The novel ways in which correlations may be encoded non-locally in quantum mechanics have led to the promise of new technologies. This, in turn, has led to the first attempts at the development of quantum networks. Nonetheless, our understanding of quantum correlations and the limits of how we may process them over a quantum network remains nascent. This thesis studies the limits of processing quantum correlations between spatially separated parties in various settings and the mathematical tools necessary to determine such limits. To do so, this thesis studies three general problems in quantum network theory. The first problem is the minimum resources to prepare a quantum correlation between non-communicative receivers, which may be viewed as a star network. This study is separated into three pieces. The first piece is a near-tight one-shot quantum generalization of a problem introduced by Wyner, distributed source simulation. Establishing our one-shot bounds builds on recent work on soft-covering without smoothing and relies on establishing a variety of properties for one-shot entropic quantities, as well as improving our understanding of the smooth entropy framework in quantum network information theory. As distributed source simulation cannot be achieved to arbitrary error for sufficiently entangled states, the second piece characterizes the minimal error of converting one entangled state to another using zero communication. This relies on establishing new properties of the fidelity measure. The third piece establishes an entanglement-assisted version of the distributed source simulation task that can be achieved to arbitrary error for arbitrary quantum systems. This result builds on recent work on multipartite state splitting and establishing new properties of one-shot multipartite max mutual information quantities. The second problem is the extraction of perfect classical correlation from a multipartite quantum source where the receivers do not communicate. This may be seen as the reverse process of distributed source simulation. We establish that this is asymptotically possible in quantum mechanics for the first time and establish the asymptotic rate for classical-quantum states. The technical barrier in establishing the asymptotic rate is establishing a limit on how much noiseless correlation can be extracted without communication. Our major technical contribution is establishing such a limit by generalizing a technical lemma of Gács and Körner to classical-quantum states. The final problem is distributed state discrimination of quantum product states. This is motivated by its relevance to both understanding non-locality in quantum mechanics and developing quantum cryptographic schemes. Our study again breaks into three key pieces. First, we study the framework of local operations and simultaneous classical or quantum communication (LOSCC and LOSQC respectively) for product states, which is relevant to quantum cryptography. We establish the first separation between quantum and classical communication in the simultaneous communication model using only product state inputs. We also establish a new uncertainty relation that implies error bounds for discriminating product states using LOSQC. Second, we study state discrimination under local operations and classical communication (LOCC). We develop a new framework for zero-error state discrimination under LOCC. Our framework provides a simple proof of orthogonal product states that cannot be distinguished using LOCC--- a property introduced by Bennett et al. Finally, we study the thermodynamics of zero-error distributed state discrimination in the framework of Faist et al. This allows us to resolve an open problem from the aforementioned paper of Bennett et al.

•Oct 2, 2024•0 citations
Free classical communication can yield an unbounded single-shot saving in quantum compression, even though it leaves the asymptotic rate of an i.i.d. source unchanged. At every fixed error in (0,1)(0,1)(0,1), we exhibit sources whose unassisted compression cost is arbitrarily large, yet a single qubit suffices with classical communication and no preshared entanglement. We establish this separation by determining the exact optimal source fidelity for compression through an mmm-dimensional noiseless quantum channel, with and without free classical communication, while preserving correlations with an inaccessible reference. Without classical assistance, the optimal fidelity is exactly the Ky Fan norm ∥ρ∥(m)\|ρ\|_{(m)}∥ρ∥(m)​, the sum of the mmm largest eigenvalues of the source state. With classical assistance, we obtain an explicit spectral threshold formula and a protocol attaining it. Classical communication strictly improves fidelity whenever mmm is smaller than the source rank. The corresponding compression costs are two smoothed versions of the log-rank entropy, also called max-entropy: trace-distance smoothing under local operations and quadratic smoothing under LOCC. For i.i.d. copies of a fixed source with positive entropy variance, however, the two costs have identical first-, second-, and third-order asymptotic terms. For nonlattice spectra, we determine the constant-order advantage: classical communication saves log⁡2(e)−1\log_2(e)-1log2​(e)−1 bits per block asymptotically, and the ratio of assisted to unassisted minimum communication dimensions converges to 2/e2/e2/e.
The paper asks how free classical communication changes single-shot quantum compression without preshared entanglement, when reconstruction must preserve correlations with an inaccessible reference. Accuracy is measured by source fidelity, the square root of entanglement fidelity.
It determines the optimal fidelity through an mmm-dimensional noiseless quantum channel exactly. With local encoding and decoding alone, the optimum is ∑i=1mpi\sum_{i=1}^m p_i∑i=1m​pi​, where pip_ipi​ are the source eigenvalues in decreasing order. With LOCC, it is max⁡0≤Λ≤I, tr⁡Λ2≤mtr⁡(ρΛ)\max_{0\leq\Lambda\leq I,\,\operatorname{tr}\Lambda^2\leq m}\operatorname{tr}(\rho\Lambda)max0≤Λ≤I,trΛ2≤m​tr(ρΛ), with an explicit clipped spectral optimizer. Classical communication strictly improves fidelity whenever m<rank⁡ρm<\operatorname{rank}\rhom<rankρ. The corresponding minimum dimensions are characterized by trace-distance-smoothed log-rank and a quadratic effect smoothing, respectively.
At every fixed fidelity threshold 1−ϵ∈(0,1)1-\epsilon\in(0,1)1−ϵ∈(0,1), an explicit family of rank-n2+1n^2+1n2+1 sources requires dimension n+1n+1n+1 without assistance but only dimension two with classical communication. For i.i.d. copies of a fixed source with positive entropy variance, both costs share the first three asymptotic orders. For nonlattice log-spectra, the assisted-to-unassisted dimension ratio converges to 2/e2/e2/e, saving log⁡2(e)−1≈0.442695\log_2(e)-1\approx0.442695log2​(e)−1≈0.442695 bits per block.
Proofs combine channel converses, a reduction of LOCC implementations to rank-bounded Kraus operators, an explicit instrument attaining the previously studied quadratic optimum, and spectral asymptotics. The constant-order limit excludes lattice spectra; uniform spectra have a different limit. Minimum classical communication is not determined, and extensions to quantum side information remain open.
We study entanglement-assisted quantum and classical communication over a single use of a quantum channel, which itself can correspond to a finite number of uses of a channel with arbitrarily correlated noise. We obtain characterizations of the corresponding one-shot capacities by establishing upper and lower bounds on them in terms of the difference of two smoothed entropic quantities. In the case of a memoryless channel, the upper and lower bounds converge to the known single-letter formulas for the corresponding capacities, in the limit of asymptotically many uses of it. Our results imply that the difference of two smoothed entropic quantities characterizing the one-shot entanglement-assisted capacities serves as a one-shot analog of the mutual information, since it reduces to the mutual information, between the output of the channel and a system purifying its input, in the asymptotic, memoryless scenario.
Understanding the classical communication cost of simulating a quantum channel is a fundamental problem in quantum information theory, which becomes even more intriguing when considering the role of non-locality in quantum information processing. This paper investigates the bidirectional classical communication cost of simulating a bipartite quantum channel assisted by non-signalling correlations, which are permitted across the spatial dimension between the two parties. By introducing non-signalling superchannels, we present lower and upper bounds on the one-shot εεε-error one-way classical communication cost of a bipartite channel via its smooth max-relative entropy of one-way classical communication, and establish that the asymptotic exact cost is given by its max-relative entropy of one-way classical communication. For the bidirectional scenario, we derive semidefinite programming (SDP) formulations for the one-shot exact bidirectional classical communication cost via non-signalling bipartite superchannels. We further introduce a channel's bipartite conditional min-entropy as an efficiently computable lower bound on the asymptotic cost of bidirectional classical communication. Our results in both one-shot and asymptotic settings provide lower bounds on the entanglement-assisted simulation cost in scenarios where entanglement is available to the two parties. Moreover, we propose a seesaw-based algorithm to compute an upper bound on the minimum simulation error via local operations and shared entanglement, which provides valuable insights into the relationship between non-signalling bipartite superchannels and more physically realizable protocols. Numerical experiments demonstrate the effectiveness of our bounds in estimating communication costs for various quantum channels, showing that our bounds can be tight in different scenarios.
We study the visible compression of a source E={|φi〉,pi} of pure quantum signal states or, more formally, the minimal resources per signal required to represent arbitrarily long strings of signals with arbitrarily high fidelity, when the compressor is given the identity of the input state sequence as classical information. According to the quantum source coding theorem, the optimal quantum rate is the von Neumann entropy S(E) qubits per signal. We develop a refinement of this theorem in order to analyze the situation in which the states are coded into classical and quantum bits that are quantified separately. This leads to a trade-off curve Q*(R), where Q*(R) qubits per signal is the optimal quantum rate for a given classical rate of R bits per signal. Our main result is an explicit characterization of this trade-off function by a simple formula in terms of only single-signal, perfect fidelity encodings of the source. We give a thorough discussion of many further mathematical properties of our formula, including an analysis of its behavior for group covariant sources and a generalization to sources with continuously parametrized states. We also show that our result leads to a number of corollaries characterizing the trade-off between information gain and state disturbance for quantum sources. In addition, we indicate how our techniques also provide a solution to the so-called remote state preparation problem. Finally, we develop a probability-free version of our main result which may be interpreted as an answer to the question: “How many classical bits does a qubit cost?” This theorem provides a type of dual to Holevo’s theorem, insofar as the latter characterizes the cost of coding classical bits into qubits.
This thesis consists of two parts: quantum compression and quantum learning theory. A common theme between these problems is that we study them through the lens of information theory. \n \nWe first study the task of visible compression of an ensemble of quantum states with entanglement assistance in the one-shot setting. The protocols achieving the best compression use many more qubits of shared entanglement than the number of qubits in the states in the ensemble. Other compression protocols, with potentially higher communication cost, have entanglement cost bounded by the number of qubits in the given states. This motivates the question as to whether entanglement is truly necessary for compression, and if so, how much of it is needed. We show that an ensemble given by Jain, Radhakrishnan, and Sen (ICALP'03) cannot be compressed by more than a constant number of qubits without shared entanglement, while in the presence of shared entanglement, the communication cost of compression can be arbitrarily smaller than the entanglement cost. \n \nNext, we study the task of quantum state redistribution, the most general version of compression of quantum states. We design a protocol for this task with communication cost in terms of a measure of distance from quantum Markov chains. More precisely, the distance is defined in terms of quantum max-relative entropy and quantum hypothesis testing entropy. Our result is the first to connect quantum state redistribution and Markov chains and gives an operational interpretation for a possible one-shot analogue of quantum conditional mutual information. The communication cost of our protocol is lower than all previously known ones and asymptotically achieves the well-known rate of quantum conditional mutual information. \n \nIn the last part, we focus on quantum algorithms for learning Boolean functions using quantum examples. We consider two commonly studied models of learning, namely, quantum PAC learning and quantum agnostic learning. We reproduce the optimal lower bounds by Arunachalam and de Wolf (JMLR’18) for the sample complexity of either of these models using information theory and spectral analysis. Our proofs are simpler than the previous ones and the techniques can be possibly extended to similar scenarios.
We provide a framework for one-shot quantum rate distortion coding, in which the goal is to determine the minimum number of qubits required to compress quantum information as a function of the probability that the distortion incurred upon decompression exceeds some specified level. We obtain a one-shot characterization of the minimum qubit compression size for an entanglement-assisted quantum rate-distortion code in terms of the smooth max-information, a quantity previously employed in the one-shot quantum reverse Shannon theorem. Next, we show how this characterization converges to the known expression for the entanglement-assisted quantum rate distortion function for asymptotically many copies of a memoryless quantum information source. Finally, we give a tight, finite blocklength characterization for the entanglement-assisted minimum qubit compression size of a memoryless isotropic qubit source subject to an average symbolwise distortion constraint.
The novel ways in which correlations may be encoded non-locally in quantum mechanics have led to the promise of new technologies. This, in turn, has led to the first attempts at the development of quantum networks. Nonetheless, our understanding of quantum correlations and the limits of how we may process them over a quantum network remains nascent. This thesis studies the limits of processing quantum correlations between spatially separated parties in various settings and the mathematical tools necessary to determine such limits. To do so, this thesis studies three general problems in quantum network theory. The first problem is the minimum resources to prepare a quantum correlation between non-communicative receivers, which may be viewed as a star network. This study is separated into three pieces. The first piece is a near-tight one-shot quantum generalization of a problem introduced by Wyner, distributed source simulation. Establishing our one-shot bounds builds on recent work on soft-covering without smoothing and relies on establishing a variety of properties for one-shot entropic quantities, as well as improving our understanding of the smooth entropy framework in quantum network information theory. As distributed source simulation cannot be achieved to arbitrary error for sufficiently entangled states, the second piece characterizes the minimal error of converting one entangled state to another using zero communication. This relies on establishing new properties of the fidelity measure. The third piece establishes an entanglement-assisted version of the distributed source simulation task that can be achieved to arbitrary error for arbitrary quantum systems. This result builds on recent work on multipartite state splitting and establishing new properties of one-shot multipartite max mutual information quantities. The second problem is the extraction of perfect classical correlation from a multipartite quantum source where the receivers do not communicate. This may be seen as the reverse process of distributed source simulation. We establish that this is asymptotically possible in quantum mechanics for the first time and establish the asymptotic rate for classical-quantum states. The technical barrier in establishing the asymptotic rate is establishing a limit on how much noiseless correlation can be extracted without communication. Our major technical contribution is establishing such a limit by generalizing a technical lemma of Gács and Körner to classical-quantum states. The final problem is distributed state discrimination of quantum product states. This is motivated by its relevance to both understanding non-locality in quantum mechanics and developing quantum cryptographic schemes. Our study again breaks into three key pieces. First, we study the framework of local operations and simultaneous classical or quantum communication (LOSCC and LOSQC respectively) for product states, which is relevant to quantum cryptography. We establish the first separation between quantum and classical communication in the simultaneous communication model using only product state inputs. We also establish a new uncertainty relation that implies error bounds for discriminating product states using LOSQC. Second, we study state discrimination under local operations and classical communication (LOCC). We develop a new framework for zero-error state discrimination under LOCC. Our framework provides a simple proof of orthogonal product states that cannot be distinguished using LOCC--- a property introduced by Bennett et al. Finally, we study the thermodynamics of zero-error distributed state discrimination in the framework of Faist et al. This allows us to resolve an open problem from the aforementioned paper of Bennett et al.