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

Efficient quantum compression for identically prepared states with arbitrary dimensio

Zeyu Chen, Chunhe Xiong, Kamil Ravilevich Khadiev, Junde Wu

Published Jul 22, 2023• 0 citations
arXivHTMLPDF

Abstract

Identical preparation creates permutation symmetry that can be used for lossless quantum compression. For $n$ copies of an unknown $d$-dimensional pure state, the tensor-power input lies in the fully symmetric subspace, whose dimension is polynomial in $n$ for fixed local dimension. Schur--Weyl duality isolates this subspace coherently, allowing the fixed representation labels to be discarded while retaining all information needed for recovery. The resulting encoder and decoder are exact on the input family. Because tensor-power states span the symmetric subspace, the achieved memory dimension is also necessary for reversible coherent compression, so the scheme is space-optimal. The encoder is implemented recursively with Clebsch--Gordan transforms, and only the branches reached by symmetric inputs need to be reproduced. Standard efficient synthesis of these transforms yields polynomial-size circuits for fixed local dimension and arbitrary target accuracy. Thus identically prepared pure states in arbitrary dimension admit lossless, space-optimal compression with an efficient circuit implementation.

DOI
10.48550/arxiv.2307.12024

Related papers

Optimal Compression for Ensembles of Identically Prepared Mixed States

Yuxiang Yang, Daniel Ebler, Giulio Chiribella

We present an universal protocol, capable of compressing $N$ copies of a completely unknown mixed state into $O(\log N)$ qubits in a lossless fashion. Our result demonstrates that the exponential compression of identically prepared pure states, recently implemented in a prototype experiment by Rozema et. al. [Phys. Rev. Lett. 113, 160504 (2014)], can be extended to arbitrary mixed states, despite the fact that the latter cover an exponentially large space. Furthermore, we highlight a striking difference between the pure and the mixed state case, showing that, if the spectrum is known with sufficient precision, the number of qubits needed for compression of a mixed state will drop down discontinuously as soon as a small recovery error is allowed.

•Jun 11, 2015•1 citation

The quantum Schur and Clebsch-Gordan transforms: I. efficient qudit circuits

Dave Bacon, Isaac L. Chuang, Aram W. Harrow

We present an efficient family of quantum circuits for a fundamental primitive in quantum information theory, the Schur transform. The Schur transform on n d-dimensional quantum systems is a transform between a standard computational basis to a labelling related to the representation theory of the symmetric and unitary groups. If we desire to implement the Schur transform to an accuracy of e-1, then our circuit construction uses a number of gates which is polynomial in n, d and log(e-1). The key tool in our construction is a poly(d, log n, log(e-1)) algorithm for the ud Clebsch-Gordan transform. Our efficient circuit construction renders numerous protocols in quantum information theory computationally tractable and yields a new possible approach to quantum algorithms which is distinct from the standard paradigm of the quantum Fourier transform.

Symposium on Discrete Algorithms•Jan 7, 2007•19 citations

Efficient Quantum Compression for Ensembles of Identically Prepared Mixed States

Yuxiang Yang, Giulio Chiribella, Daniel Ebler

We present one-shot compression protocols that optimally encode ensembles of N identically prepared mixed states into O(logN) qubits. In contrast to the case of pure-state ensembles, we find that the number of encoding qubits drops down discontinuously as soon as a nonzero error is tolerated and the spectrum of the states is known with sufficient precision. For qubit ensembles, this feature leads to a 25% saving of memory space. Our compression protocols can be implemented efficiently on a quantum computer.

arXiv:1506.03542•Physical Review Letters•Feb 23, 2016•28 citations

Efficient compression of quantum information

Martin Plesch, Vladimír Bužek

We propose a scheme for an exact efficient transformation of a tensor product state of many identically prepared qubits into a state of a logarithmically small number of qubits. Using a quadratic number of elementary quantum gates we transform $N$ identically prepared qubits into a state, which is nontrivial only on the first $\ensuremath{\lceil}\mathrm{log}{}_{2}(N+1)\ensuremath{\rceil}$ qubits. This procedure might be useful for quantum memories, as only a small portion of the original qubits has to be stored. Another possible application is in communicating a direction encoded in a set of quantum states, as the compressed state provides a high-effective method for such an encoding.

arXiv:0907.1764•Physical Review A•Mar 18, 2010•49 citations

No Free Compression in Quantum Relaxations for Optimization

Stuart Hadfield

Qubit-efficient quantum relaxations compress classical decision variables into expectation values on substantially fewer qubits. We ask what resource tradeoffs this compression entails for quantum optimization. For the complete quadratic-Majorana encoding of $m=Θ(n^2)$ binary variables on~$n$ qubits, we define the universal margin as the smallest correlator magnitude that can be guaranteed with prescribed signs for every target sign (bit) assignment. We show that it is exactly $Δ_{\rm Maj}(n)=\tan\!\left(\fracπ{4n}\right)=Θ(1/n)$, whereas uniformly random sign assignments retain $Θ(1/\sqrt n)$ target-specific margins. Arbitrary density operators and mixed fermionic Gaussian states generate the same quadratic-Majorana covariance body, so non-Gaussian state resources cannot enlarge this two-point relaxation. More generally, standard quantum random access code bounds provide general information-theoretic baselines. For any fixed family of $m$ designated binary observables on~$n$ qubits, the universal margin is at most $\sqrt{(2\ln2\,n/m)}$, and random access decoding from $N$ copies with constant success probability above $1/2$ requires $nN=Ω(m)$. For a fixed Pauli correlation encoding required to work uniformly over all targets, maintaining a fixed nonzero decoded magnitude under smooth sign decoding therefore requires a rescaling parameter that grows as the available margin shrinks. Thus, while providing substantial qubit savings, compression can shift cost into restricted expectation value geometry, smaller expectation value magnitudes, or more demanding information recovery rather than eliminate it.

quant-pharXiv:2608.25151•Aug 27, 2026•0 citations

Quantum compression of tensor network states

Ge Bai, Yuxiang Yang, Giulio Chiribella

Abstract We design quantum compression algorithms for parametric families of tensor network states. We first establish an upper bound on the amount of memory needed to store an arbitrary state from a given state family. The bound is determined by the minimum cut of a suitable flow network, and is related to the flow of information from the manifold of parameters that specify the states to the physical systems in which the states are embodied. For given network topology and given edge dimensions, our upper bound is tight when all edge dimensions are powers of the same integer. When this condition is not met, the bound is optimal up to a multiplicative factor smaller than 1.585. We then provide a compression algorithm for general state families, and show that the algorithm runs in polynomial time for matrix product states.

arXiv:1904.06772•New Journal of Physics•Feb 28, 2020•7 citations
Identical preparation creates permutation symmetry that can be used for lossless quantum compression. For nnn copies of an unknown ddd-dimensional pure state, the tensor-power input lies in the fully symmetric subspace, whose dimension is polynomial in nnn for fixed local dimension. Schur--Weyl duality isolates this subspace coherently, allowing the fixed representation labels to be discarded while retaining all information needed for recovery. The resulting encoder and decoder are exact on the input family. Because tensor-power states span the symmetric subspace, the achieved memory dimension is also necessary for reversible coherent compression, so the scheme is space-optimal. The encoder is implemented recursively with Clebsch--Gordan transforms, and only the branches reached by symmetric inputs need to be reproduced. Standard efficient synthesis of these transforms yields polynomial-size circuits for fixed local dimension and arbitrary target accuracy. Thus identically prepared pure states in arbitrary dimension admit lossless, space-optimal compression with an efficient circuit implementation.
We present an universal protocol, capable of compressing NNN copies of a completely unknown mixed state into O(log⁡N)O(\log N)O(logN) qubits in a lossless fashion. Our result demonstrates that the exponential compression of identically prepared pure states, recently implemented in a prototype experiment by Rozema et. al. [Phys. Rev. Lett. 113, 160504 (2014)], can be extended to arbitrary mixed states, despite the fact that the latter cover an exponentially large space. Furthermore, we highlight a striking difference between the pure and the mixed state case, showing that, if the spectrum is known with sufficient precision, the number of qubits needed for compression of a mixed state will drop down discontinuously as soon as a small recovery error is allowed.
We present an efficient family of quantum circuits for a fundamental primitive in quantum information theory, the Schur transform. The Schur transform on n d-dimensional quantum systems is a transform between a standard computational basis to a labelling related to the representation theory of the symmetric and unitary groups. If we desire to implement the Schur transform to an accuracy of e-1, then our circuit construction uses a number of gates which is polynomial in n, d and log(e-1). The key tool in our construction is a poly(d, log n, log(e-1)) algorithm for the ud Clebsch-Gordan transform. Our efficient circuit construction renders numerous protocols in quantum information theory computationally tractable and yields a new possible approach to quantum algorithms which is distinct from the standard paradigm of the quantum Fourier transform.
We present one-shot compression protocols that optimally encode ensembles of N identically prepared mixed states into O(logN) qubits. In contrast to the case of pure-state ensembles, we find that the number of encoding qubits drops down discontinuously as soon as a nonzero error is tolerated and the spectrum of the states is known with sufficient precision. For qubit ensembles, this feature leads to a 25% saving of memory space. Our compression protocols can be implemented efficiently on a quantum computer.
We propose a scheme for an exact efficient transformation of a tensor product state of many identically prepared qubits into a state of a logarithmically small number of qubits. Using a quadratic number of elementary quantum gates we transform NNN identically prepared qubits into a state, which is nontrivial only on the first $\ensuremath{\lceil}\mathrm{log}{}_{2}(N+1)\ensuremath{\rceil}$ qubits. This procedure might be useful for quantum memories, as only a small portion of the original qubits has to be stored. Another possible application is in communicating a direction encoded in a set of quantum states, as the compressed state provides a high-effective method for such an encoding.
Qubit-efficient quantum relaxations compress classical decision variables into expectation values on substantially fewer qubits. We ask what resource tradeoffs this compression entails for quantum optimization. For the complete quadratic-Majorana encoding of m=Θ(n2)m=Θ(n^2)m=Θ(n2) binary variables on~nnn qubits, we define the universal margin as the smallest correlator magnitude that can be guaranteed with prescribed signs for every target sign (bit) assignment. We show that it is exactly ΔMaj(n)=tan⁡ ⁣(π4n)=Θ(1/n)Δ_{\rm Maj}(n)=\tan\!\left(\fracπ{4n}\right)=Θ(1/n)ΔMaj​(n)=tan(4nπ​)=Θ(1/n), whereas uniformly random sign assignments retain Θ(1/n)Θ(1/\sqrt n)Θ(1/n​) target-specific margins. Arbitrary density operators and mixed fermionic Gaussian states generate the same quadratic-Majorana covariance body, so non-Gaussian state resources cannot enlarge this two-point relaxation. More generally, standard quantum random access code bounds provide general information-theoretic baselines. For any fixed family of mmm designated binary observables on~nnn qubits, the universal margin is at most (2ln⁡2 n/m)\sqrt{(2\ln2\,n/m)}(2ln2n/m)​, and random access decoding from NNN copies with constant success probability above 1/21/21/2 requires nN=Ω(m)nN=Ω(m)nN=Ω(m). For a fixed Pauli correlation encoding required to work uniformly over all targets, maintaining a fixed nonzero decoded magnitude under smooth sign decoding therefore requires a rescaling parameter that grows as the available margin shrinks. Thus, while providing substantial qubit savings, compression can shift cost into restricted expectation value geometry, smaller expectation value magnitudes, or more demanding information recovery rather than eliminate it.
Abstract We design quantum compression algorithms for parametric families of tensor network states. We first establish an upper bound on the amount of memory needed to store an arbitrary state from a given state family. The bound is determined by the minimum cut of a suitable flow network, and is related to the flow of information from the manifold of parameters that specify the states to the physical systems in which the states are embodied. For given network topology and given edge dimensions, our upper bound is tight when all edge dimensions are powers of the same integer. When this condition is not met, the bound is optimal up to a multiplicative factor smaller than 1.585. We then provide a compression algorithm for general state families, and show that the algorithm runs in polynomial time for matrix product states.