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:2305.18748 · Quantum Information and Computation

Optimal lower bound for lossless quantum block encoding

George Androulakis, Rabins Wosti

Published Nov 1, 2024• 0 citations
arXivHTMLPDF

Abstract

Consider a general quantum stochastic source that emits at discrete time steps quantum pure states which are chosen from a finite alphabet according to some probability distribution which may depend on the whole history. Also, fix two positive integers $m$ and $l$. We encode any tensor product of $m$ many states emitted by the quantum stochastic source by breaking the tensor product into $m$ many blocks where each block has length $l$, and considering sequences of $m$ many isometries so that each isometry encodes one of these blocks into the Fock space, followed by the concatenation of their images. We only consider certain sequences of such isometries that we call \lq\lq special block codes\rq\rq\ in order to ensure that the string of encoded states is uniquely decodable. We compute the minimum average codeword length of these encodings which depends on the quantum source and the integers $m$, $l$, among all possible special block codes. Our result extends the result of [Bellomo, Bosyk, Holik and Zozor, Scientific Reports 7.1 (2017): 14765] where the minimum was computed for one block, i.e.\ for $m=1$. Lastly, we give a simplified non-adaptive compression technique based on constrained special block codes for general quantum stochastic sources. For quantum stationary sources in particular, we show that the minimum average codeword length per symbol computed over all constrained special block codes is equal to the von-Neumann entropy rate of the source for an asymptotically long block size.

DOI
10.26421/qic24.13-14-3

Related papers

Optimal Lower Bound of the Average Indeterminate Length Lossless Quantum Block Encoding

George Androulakis, Rabins Wosti

Consider a general quantum stochastic source that emits at discrete time steps quantum pure states which are chosen from a finite alphabet according to some probability distribution which may depend on the whole history. Also, fix two positive integers$m$and l. We encode any tensor product of ml many states emitted by the given quantum source by breaking it into$m$many blocks where each block has length l, and considering sequences of$m$many isometries so that each isometry encodes one of these blocks into the Fock space, followed by the concatenation of their images. We only consider certain sequences of such isometries that we call “special block codes” in order to ensure that the string of encoded states is uniquely decodable. We compute the minimum average codeword length of these encodings which depends on the quantum source and the integers m, l, among all possible special block codes. Our result extends the result of [Bellomo, Bosyk, Holik and Zozor, Scientific Reports 7.1 (2017): 14765] where the minimum was computed for one block, i.e. for m = 1.

IEEE International Symposium on Information Theory (ISIT)•Jul 7, 2024•0 citations

New Approaches on Source Coding for Quantum Stochastic Sources and Implementation of Quantum Fanout Gate

Rabins Wosti

The accurate computation of advanced quantum algorithms like Shor’s integer factorization, quantum phase estimation (QPE), and the quantum Fourier transform (QFT) requires quantum circuits of considerable size and depth. It is difficult to achieve reliable computation with deep quantum circuits due to the limited coherence times of the current noisy quantum devices. The quantum fanout gate is known to be a powerful primitive for reducing the depth of many quantum circuits (Høyer and Špalek 2003; Gottesman and Chuang 1999). Shallow or constant-depth quantum circuits are desirable for both near-term and fault-tolerant quantum computations as they reduce noise and allow faster execution of quantum algorithms, potentially skirting the effects of short coherence times. In this work, we show new approaches towards implementation of quantum fanout gate. In particular, we show that by analogue time-evolving the quantum systems according to two well-studied Hamiltonians, namely, quantum Ising and quantum Heisenberg models, we can implement the quantum fanout operator using constantly many layers of digital quantum gates. Important foundations to the area of quantum encoding were provided by Schumacher who proved the quantum analog of Shannon’s noiseless coding theorem for an independent and identically distributed (i.i.d.) quantum source, (Schumacher 1995). In this work, we show a lossless, variable-length block encoding scheme of quantum information emitted from a completely general stochastic quantum source, and it is encoded into the Fock space. While doing so, we extend the notion of uniquely decodable (or completely lossless) quantum codes to be used for quantum block data compression. As our main result, for a fixed mlmany pure states emitted by a given quantum stochastic source, we derive the optimal lower bound of the average codeword length over a subset of uniquely decodable quantum codes called “special block codes,” which are applied to encode the pure states of m many blocks each of block size l. Additionally, we show that for quantum stationary sources in particular, the optimal lower bound of the average codeword length per symbol computed over a subset of special block codes called “constrained special block codes” equals the von Neumann entropy rate of the source for an asymptotically long block size.

•Oct 1, 2025•0 citations

On Lossless Quantum Data Compression With a Classical Helper

Rudolf Ahlswede, N. Cai

After K. Bostro/spl uml/m and T. Felbinger observed that lossless quantum data compression does not exist unless decoders know the lengths of codewords, they introduced a classical noiseless channel to inform the decoder of a quantum source about the lengths of codewords. In this paper we analyze their codes and present: 1) a sufficient and necessary condition for the existence of such codes for given lists of lengths of codes; 2) a characterization of the optimal compression rate for their codes. However our main contribution is a more efficient way to use the classical channel. We propose a more general coding scheme. It turned out that the optimal compression can always be achieved by a code obtained by this scheme. A von Neumann entropy lower bound to rates of our codes and a necessary and sufficient condition to achieve the bound are obtained. The gap between this lower bound and the compression rates is also well analyzed. For a special family of quantum sources we provide a sharper lower bound in terms of Shannon entropy. Finally, we propose some problems for further research.

IEEE Transactions on Information Theory•Jun 1, 2004•10 citations

Optimality in quantum data compression using dynamical entropy

George Androulakis, Duncan Wright

In this article we study lossless compression of strings of pure quantum states of indeterminate-length quantum codes which were introduced by Schumacher and Westmoreland. Past work has assumed that the strings of quantum data are prepared to be encoded in an independent and identically distributed way. We discuss the notion of quantum stochastic ensembles, allowing us to consider strings of quantum states prepared in a general way. For any quantum stochastic ensemble we define an associated quantum dynamical system and prove that the optimal average codeword length via lossless coding is equal to the quantum dynamical entropy of the associated quantum dynamical system.

arXiv:1904.05402•Physical Review A•Sep 3, 2019•2 citations

Aspects of Quantum Information Compression for Pure States

Richard Jozsa

Consider a source of pure quantum states with density matrix ρ and von Neumann entropy S . It is known that the quantum information of the source may be faithfully compressed to 5 qubits/signal (asymptotically for long sequences) and that this limit is optimal if we demand high fidelity for long strings of signals. The usual method for achieving this compression, based on the typical subspace of the source, requires knowledge of the density matrix. We describe a new “universal” compression scheme which does not even require knowledge of ρ. More precisely, suppose that the source is known to have von Neumann entropy less than some given bound S 0 but is otherwise completely unspecified. Our method will faithfully compress the quantum information of any such source to S 0 qubits/signal. It is known that S is always less than or equal to the Shannon entropy H of the prior distribution of the source. According to Shannon’s theorem, H provides the limit for compression of classical signals, so one may ask the question: what is the physical origin of the extra compression available in the quantum case compared to the classical case (where the prior probabilities are the same)? One may suggest that this effect is a consequence of possible non-orthogonality of signal states. However we demonstrate that it is possible to make each pair of signal states of a source more parallel (keeping the prior probabilities the same) while increasing the von Neumann entropy. This casts doubt on the conventional wisdom that overlap of quantum states is a measure of their (non-)distinguishability. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Kluwer Academic Publishers eBooks•Dec 19, 2005•1 citation

Universal compression of ergodic quantum sources

Alexei Kaltchenko, E-H Yang

For a real number r>0, let F(r) be the family of all stationary ergodic quantum sources with von Neumann entropy rates less than r. We prove that, for any r>0, there exists a blind, source-independent block compression scheme which compresses every source from F(r) to rn qubits per input block length~n with arbitrarily high fidelity for all large n.}As our second result, we show that the stationarity and the ergodicity of a quantum source \rho_m_{m=1}^{\infty} are preserved by any trace-preserving completely positive linear map of the tensor product form {\cal E}^{\otimes m}, where a copy of {\cal E} acts locally on each spin lattice site. We also establish ergodicity criteria for so called classically-correlated quantum sources.

arXiv:quant-ph/0302174•Quantum Information and Computation•Jul 1, 2003•19 citations
Consider a general quantum stochastic source that emits at discrete time steps quantum pure states which are chosen from a finite alphabet according to some probability distribution which may depend on the whole history. Also, fix two positive integers mmm and lll. We encode any tensor product of mmm many states emitted by the quantum stochastic source by breaking the tensor product into mmm many blocks where each block has length lll, and considering sequences of mmm many isometries so that each isometry encodes one of these blocks into the Fock space, followed by the concatenation of their images. We only consider certain sequences of such isometries that we call \lq\lq special block codes\rq\rq\ in order to ensure that the string of encoded states is uniquely decodable. We compute the minimum average codeword length of these encodings which depends on the quantum source and the integers mmm, lll, among all possible special block codes. Our result extends the result of [Bellomo, Bosyk, Holik and Zozor, Scientific Reports 7.1 (2017): 14765] where the minimum was computed for one block, i.e.\ for m=1m=1m=1. Lastly, we give a simplified non-adaptive compression technique based on constrained special block codes for general quantum stochastic sources. For quantum stationary sources in particular, we show that the minimum average codeword length per symbol computed over all constrained special block codes is equal to the von-Neumann entropy rate of the source for an asymptotically long block size.
Consider a general quantum stochastic source that emits at discrete time steps quantum pure states which are chosen from a finite alphabet according to some probability distribution which may depend on the whole history. Also, fix two positive integersmmmand l. We encode any tensor product of ml many states emitted by the given quantum source by breaking it intommmmany blocks where each block has length l, and considering sequences ofmmmmany isometries so that each isometry encodes one of these blocks into the Fock space, followed by the concatenation of their images. We only consider certain sequences of such isometries that we call “special block codes” in order to ensure that the string of encoded states is uniquely decodable. We compute the minimum average codeword length of these encodings which depends on the quantum source and the integers m, l, among all possible special block codes. Our result extends the result of [Bellomo, Bosyk, Holik and Zozor, Scientific Reports 7.1 (2017): 14765] where the minimum was computed for one block, i.e. for m = 1.
The accurate computation of advanced quantum algorithms like Shor’s integer factorization, quantum phase estimation (QPE), and the quantum Fourier transform (QFT) requires quantum circuits of considerable size and depth. It is difficult to achieve reliable computation with deep quantum circuits due to the limited coherence times of the current noisy quantum devices. The quantum fanout gate is known to be a powerful primitive for reducing the depth of many quantum circuits (Høyer and Špalek 2003; Gottesman and Chuang 1999). Shallow or constant-depth quantum circuits are desirable for both near-term and fault-tolerant quantum computations as they reduce noise and allow faster execution of quantum algorithms, potentially skirting the effects of short coherence times. In this work, we show new approaches towards implementation of quantum fanout gate. In particular, we show that by analogue time-evolving the quantum systems according to two well-studied Hamiltonians, namely, quantum Ising and quantum Heisenberg models, we can implement the quantum fanout operator using constantly many layers of digital quantum gates. Important foundations to the area of quantum encoding were provided by Schumacher who proved the quantum analog of Shannon’s noiseless coding theorem for an independent and identically distributed (i.i.d.) quantum source, (Schumacher 1995). In this work, we show a lossless, variable-length block encoding scheme of quantum information emitted from a completely general stochastic quantum source, and it is encoded into the Fock space. While doing so, we extend the notion of uniquely decodable (or completely lossless) quantum codes to be used for quantum block data compression. As our main result, for a fixed mlmany pure states emitted by a given quantum stochastic source, we derive the optimal lower bound of the average codeword length over a subset of uniquely decodable quantum codes called “special block codes,” which are applied to encode the pure states of m many blocks each of block size l. Additionally, we show that for quantum stationary sources in particular, the optimal lower bound of the average codeword length per symbol computed over a subset of special block codes called “constrained special block codes” equals the von Neumann entropy rate of the source for an asymptotically long block size.
After K. Bostro/spl uml/m and T. Felbinger observed that lossless quantum data compression does not exist unless decoders know the lengths of codewords, they introduced a classical noiseless channel to inform the decoder of a quantum source about the lengths of codewords. In this paper we analyze their codes and present: 1) a sufficient and necessary condition for the existence of such codes for given lists of lengths of codes; 2) a characterization of the optimal compression rate for their codes. However our main contribution is a more efficient way to use the classical channel. We propose a more general coding scheme. It turned out that the optimal compression can always be achieved by a code obtained by this scheme. A von Neumann entropy lower bound to rates of our codes and a necessary and sufficient condition to achieve the bound are obtained. The gap between this lower bound and the compression rates is also well analyzed. For a special family of quantum sources we provide a sharper lower bound in terms of Shannon entropy. Finally, we propose some problems for further research.
In this article we study lossless compression of strings of pure quantum states of indeterminate-length quantum codes which were introduced by Schumacher and Westmoreland. Past work has assumed that the strings of quantum data are prepared to be encoded in an independent and identically distributed way. We discuss the notion of quantum stochastic ensembles, allowing us to consider strings of quantum states prepared in a general way. For any quantum stochastic ensemble we define an associated quantum dynamical system and prove that the optimal average codeword length via lossless coding is equal to the quantum dynamical entropy of the associated quantum dynamical system.
Consider a source of pure quantum states with density matrix ρ and von Neumann entropy S . It is known that the quantum information of the source may be faithfully compressed to 5 qubits/signal (asymptotically for long sequences) and that this limit is optimal if we demand high fidelity for long strings of signals. The usual method for achieving this compression, based on the typical subspace of the source, requires knowledge of the density matrix. We describe a new “universal” compression scheme which does not even require knowledge of ρ. More precisely, suppose that the source is known to have von Neumann entropy less than some given bound S 0 but is otherwise completely unspecified. Our method will faithfully compress the quantum information of any such source to S 0 qubits/signal. It is known that S is always less than or equal to the Shannon entropy H of the prior distribution of the source. According to Shannon’s theorem, H provides the limit for compression of classical signals, so one may ask the question: what is the physical origin of the extra compression available in the quantum case compared to the classical case (where the prior probabilities are the same)? One may suggest that this effect is a consequence of possible non-orthogonality of signal states. However we demonstrate that it is possible to make each pair of signal states of a source more parallel (keeping the prior probabilities the same) while increasing the von Neumann entropy. This casts doubt on the conventional wisdom that overlap of quantum states is a measure of their (non-)distinguishability. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
For a real number r>0, let F(r) be the family of all stationary ergodic quantum sources with von Neumann entropy rates less than r. We prove that, for any r>0, there exists a blind, source-independent block compression scheme which compresses every source from F(r) to rn qubits per input block length~n with arbitrarily high fidelity for all large n.}As our second result, we show that the stationarity and the ergodicity of a quantum source \rho_m_{m=1}^{\infty} are preserved by any trace-preserving completely positive linear map of the tensor product form {\cal E}^{\otimes m}, where a copy of {\cal E} acts locally on each spin lattice site. We also establish ergodicity criteria for so called classically-correlated quantum sources.