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:0804.0022

Quantum Bit Strings and Prefix-Free Hilbert Spaces

Markus P. Müller, Caroline Rogers

Published Mar 31, 2008• 5 citations
arXivHTMLPDF

Abstract

We give a mathematical framework for manipulating indeterminate-length quantum bit strings. In particular, we define prefixes, fragments, tensor products and concatenation of such strings of qubits, and study their properties and relationships. The results are then used to define prefix-free Hilbert spaces in a more general way than in previous work, without assuming the existence of a basis of length eigenstates. We prove a quantum analogue of the Kraft inequality, illustrate the results with some examples and discuss the relevance of prefix-free Hilbert spaces for lossless compression.

DOI
10.48550/arxiv.0804.0022

Related papers

Lossless quantum prefix compression for communication channels that are always open

Markus P. Müller, Caroline Rogers, Rajagopal Nagarajan

We describe a method for lossless quantum compression if the output of the information source is not known. We compute the best possible compression rate, minimizing the expected base length of the output quantum bit string (the base length of a quantum string is the maximal length in the superposition). This complements work by Schumacher and Westmoreland who calculated the corresponding rate for minimizing the output's average length. Our compressed code words are prefix-free indeterminate-length quantum bit strings which can be concatenated in the case of multiple sources. Therefore, we generalize the known theory of prefix-free quantum codes to the case where strings have indeterminate length. Moreover, we describe a communication model which allows the lossless transmission of the compressed code words. The benefit of compression is then the reduction of transmission errors in the presence of noise.

arXiv:0808.2003•Physical Review A•Jan 6, 2009•7 citations

Indeterminate-length quantum coding

Benjamin W. Schumacher, Michael D. Westmoreland

The quantum analogues of classical variable-length codes are indeterminate-length quantum codes, in which code words may exist in superpositions of different lengths. This paper explores some of their properties. The length observable for such codes is governed by a quantum version of the Kraft--McMillan inequality. Indeterminate-length quantum codes also provide an alternate approach to quantum data compression.

arXiv:quant-ph/0011014•Physical Review A•Sep 10, 2001•35 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

Quantum Kolmogorov Complexity and the Quantum Turing Machine

Markus P. Müller

The purpose of this thesis is to give a formal definition of quantum Kolmogorov complexity (QC), and rigorous mathematical proofs of its basic properties. The definition used here is similar to that by Berthiaume, van Dam, and Laplante. It defines the QC of some indeterminate-length qubit string ρas the minimum base length of any quantum input which makes a quantum Turing machine (QTM) halt and output ρ, up to some error tolerance. First, we prove that there is a QTM which is universal in the sense of input base length. Furthermore, we show several general properties of QTMs, including a result on mutually orthogonal ``halting spaces'', and a way to transform every almost-halting input into a deterministically-halting input by adding at most a constant number of qubits. Afterwards, we apply these results to QC. In particular, we show that QC is invariant, incompressible, agrees with classical Kolmogorov complexity for classical strings, and is closely related to von Neumann entropy for ergodic quantum information sources.

arXiv:0712.4377•Dec 28, 2007•14 citations

Hilbert Space Theory and Its Implementation in Quantum Computing Systems

Mehmet Keçeci

Hilbert spaces provide the fundamental mathematical framework for describing quantum mechanical systems. Their structure, characterized by an inner product and completeness, allows for the representation of quantum states as vectors and physical observables as self-adjoint operators. Key quantum phenomena such as superposition and entanglement find natural expression within this formalism. Superposition, where a quantum system can exist in multiple states simultaneously, is represented by linear combinations of basis vectors in the Hilbert space. Entanglement, a non-classical correlation between quantum systems, is described by non-separable state vectors in a tensor product of Hilbert spaces. These concepts are pivotal in quantum computing, where the unit of information, the qubit, is a two-level quantum system whose state is a vector in a two-dimensional complex Hilbert space (ℂ²). Quantum gates, which perform operations on qubits, are represented by unitary operators acting on these state vectors. The power of quantum computation, particularly in algorithms like Shor's or Grover's, stems from the ability to exploit superposition and entanglement, processes intrinsically described within the Hilbert space framework. Thus, a thorough understanding of Hilbert spaces is indispensable for grasping the principles of quantum mechanics and for advancing the field of quantum information and computation [1, 7]. The transition from classical bits to quantum qubits, and from classical logic gates to quantum unitary operations, is entirely predicated on the mathematical properties endowed by Hilbert spaces.

•Aug 8, 2025•1 citation

Quantum Entanglement-Based Data Compression via Phase Space Mapping

Jincheng Zhang

This paper proposes a novel data compression technique leveraging the unique properties of quantum entanglement. The core idea involves encoding data into the correlated phase space of entangled qubits, achieving lossless compression. The algorithm utilizes controlled phase manipulation for both encoding and decoding, capitalizing on the inherent correlations between entangled particles. Unlike traditional entropy-based compression methods, this approach directly exploits quantum mechanical phenomena. We demonstrate a theoretical framework and outline a compression algorithm with the potential for significant improvements in compression ratios. The key mathematical representation of the compression process is defined as follows: Let $x = (x_1, x_2, ..., x_N)$ be the original data sequence, where each $x_i$ is a binary value (0 or 1). The compression algorithm maps this sequence to an entangled state $(|\psi_1\rangle, |\psi_2\rangle, ..., |\psi_N\rangle)$, where $|\psi_i\rangle$ represents the state of the *i*-th qubit in the entangled pair. The compression ratio *R* is defined as: $R = \frac{N}{N_{encoded}}$ where *N* is the length of the original data sequence and *Nencoded* is the number of qubits used to represent the data. The encoding process is described by: $|\psi_i\rangle = \alpha_i |0\rangle + \beta_i |1\rangle$ where $\alpha_i$ and $\beta_i$ are complex amplitudes determined by the data bit $x_i$. The decoding process reverses this operation, reconstructing the original data from the measured state of the qubits. The fidelity of the reconstruction is crucial, and the algorithm incorporates techniques to minimize errors due to measurement noise. The overall compression algorithm can be summarized as follows:

•Sep 6, 2026•0 citations
We give a mathematical framework for manipulating indeterminate-length quantum bit strings. In particular, we define prefixes, fragments, tensor products and concatenation of such strings of qubits, and study their properties and relationships. The results are then used to define prefix-free Hilbert spaces in a more general way than in previous work, without assuming the existence of a basis of length eigenstates. We prove a quantum analogue of the Kraft inequality, illustrate the results with some examples and discuss the relevance of prefix-free Hilbert spaces for lossless compression.
We describe a method for lossless quantum compression if the output of the information source is not known. We compute the best possible compression rate, minimizing the expected base length of the output quantum bit string (the base length of a quantum string is the maximal length in the superposition). This complements work by Schumacher and Westmoreland who calculated the corresponding rate for minimizing the output's average length. Our compressed code words are prefix-free indeterminate-length quantum bit strings which can be concatenated in the case of multiple sources. Therefore, we generalize the known theory of prefix-free quantum codes to the case where strings have indeterminate length. Moreover, we describe a communication model which allows the lossless transmission of the compressed code words. The benefit of compression is then the reduction of transmission errors in the presence of noise.
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.
The purpose of this thesis is to give a formal definition of quantum Kolmogorov complexity (QC), and rigorous mathematical proofs of its basic properties. The definition used here is similar to that by Berthiaume, van Dam, and Laplante. It defines the QC of some indeterminate-length qubit string ρas the minimum base length of any quantum input which makes a quantum Turing machine (QTM) halt and output ρ, up to some error tolerance. First, we prove that there is a QTM which is universal in the sense of input base length. Furthermore, we show several general properties of QTMs, including a result on mutually orthogonal ``halting spaces'', and a way to transform every almost-halting input into a deterministically-halting input by adding at most a constant number of qubits. Afterwards, we apply these results to QC. In particular, we show that QC is invariant, incompressible, agrees with classical Kolmogorov complexity for classical strings, and is closely related to von Neumann entropy for ergodic quantum information sources.
Hilbert spaces provide the fundamental mathematical framework for describing quantum mechanical systems. Their structure, characterized by an inner product and completeness, allows for the representation of quantum states as vectors and physical observables as self-adjoint operators. Key quantum phenomena such as superposition and entanglement find natural expression within this formalism. Superposition, where a quantum system can exist in multiple states simultaneously, is represented by linear combinations of basis vectors in the Hilbert space. Entanglement, a non-classical correlation between quantum systems, is described by non-separable state vectors in a tensor product of Hilbert spaces. These concepts are pivotal in quantum computing, where the unit of information, the qubit, is a two-level quantum system whose state is a vector in a two-dimensional complex Hilbert space (ℂ²). Quantum gates, which perform operations on qubits, are represented by unitary operators acting on these state vectors. The power of quantum computation, particularly in algorithms like Shor's or Grover's, stems from the ability to exploit superposition and entanglement, processes intrinsically described within the Hilbert space framework. Thus, a thorough understanding of Hilbert spaces is indispensable for grasping the principles of quantum mechanics and for advancing the field of quantum information and computation [1, 7]. The transition from classical bits to quantum qubits, and from classical logic gates to quantum unitary operations, is entirely predicated on the mathematical properties endowed by Hilbert spaces.
This paper proposes a novel data compression technique leveraging the unique properties of quantum entanglement. The core idea involves encoding data into the correlated phase space of entangled qubits, achieving lossless compression. The algorithm utilizes controlled phase manipulation for both encoding and decoding, capitalizing on the inherent correlations between entangled particles. Unlike traditional entropy-based compression methods, this approach directly exploits quantum mechanical phenomena. We demonstrate a theoretical framework and outline a compression algorithm with the potential for significant improvements in compression ratios. The key mathematical representation of the compression process is defined as follows: Let x=(x1,x2,...,xN)x = (x_1, x_2, ..., x_N)x=(x1​,x2​,...,xN​) be the original data sequence, where each xix_ixi​ is a binary value (0 or 1). The compression algorithm maps this sequence to an entangled state (∣ψ1⟩,∣ψ2⟩,...,∣ψN⟩)(|\psi_1\rangle, |\psi_2\rangle, ..., |\psi_N\rangle)(∣ψ1​⟩,∣ψ2​⟩,...,∣ψN​⟩), where ∣ψi⟩|\psi_i\rangle∣ψi​⟩ represents the state of the *i*-th qubit in the entangled pair. The compression ratio *R* is defined as: R=NNencodedR = \frac{N}{N_{encoded}}R=Nencoded​N​ where *N* is the length of the original data sequence and *Nencoded* is the number of qubits used to represent the data. The encoding process is described by: ∣ψi⟩=αi∣0⟩+βi∣1⟩|\psi_i\rangle = \alpha_i |0\rangle + \beta_i |1\rangle∣ψi​⟩=αi​∣0⟩+βi​∣1⟩ where αi\alpha_iαi​ and βi\beta_iβi​ are complex amplitudes determined by the data bit xix_ixi​. The decoding process reverses this operation, reconstructing the original data from the measured state of the qubits. The fidelity of the reconstruction is crucial, and the algorithm incorporates techniques to minimize errors due to measurement noise. The overall compression algorithm can be summarized as follows: