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:1801.05721 · Leibniz international proceedings in informatics

A Compressed Classical Description of Quantum States

David Gosset, John A. Smolin

Published Jan 17, 2018• 5 citations
arXivHTMLPDF

Abstract

We show how to approximately represent a quantum state using the square root of the usual amount of classical memory. The classical representation of an $n$-qubit state $ψ$ consists of its inner products with $O(\sqrt{2^n})$ stabilizer states. A quantum state initially specified by its $2^n$ entries in the computational basis can be compressed to this form in time $O(2^n \mathrm{poly}(n))$, and, subsequently, the compressed description can be used to additively approximate the expectation value of an arbitrary observable. Our compression scheme directly gives a new protocol for the vector in subspace problem with randomized one-way communication complexity that matches (up to polylogarithmic factors) the optimal upper bound, due to Raz. We obtain an exponential improvement over Raz's protocol in terms of computational efficiency.

DOI
10.4230/lipics.tqc.2019.8

Related papers

Multiple-basis representation of quantum states

Adrián Pérez-Salinas, Patrick Emonts, Jordi Tura +1 more

Classical simulation of quantum physics is a central approach to investigating physical phenomena. Quantum computers enhance computational capabilities beyond those of classical resources, but it remains unclear to what extent existing limited quantum computers can contribute to this enhancement. In this work, we explore a new hybrid, efficient quantum-classical representation of quantum states, the multiple-basis representation. This representation consists of a linear combination of states that are sparse in some given and different bases, specified by quantum circuits. Such representation is particularly appealing when considering depth-limited quantum circuits within reach of current hardware. We analyze the expressivity of multiple-basis representation states depending on the classical simulability of their quantum circuits. In particular, we show that multiple-basis representation states include, but are not restricted to, both matrix-product states and stabilizer states. Furthermore, we find cases in which this representation can be used, namely approximation of ground states, simulation of deeper computations by specifying bases with shallow circuits, and a tomographical protocol to describe states as multiple-basis representations. We envision this work to open the path of simultaneous use of several hardware-friendly bases, a natural description of hybrid computational methods accessible for near-term hardware.

arXiv:2411.03110•Nov 5, 2024•0 citations

An approximate description of quantum states

Marco Paini, Amir Kalev

We introduce an approximate description of an $N$-qubit state, which contains sufficient information to estimate the expectation value of any observable with precision independent of $N$. We show, in fact, that the error in the estimation of the observables' expectation values decreases as the inverse of the square root of the number of the system's identical preparations and increases, at most, linearly in a suitably defined, $N$-independent, seminorm of the observables. Building the approximate description of the $N$-qubit state only requires repetitions of single-qubit rotations followed by single-qubit measurements and can be considered for implementation on today's Noisy Intermediate-Scale Quantum (NISQ) computers. The access to the expectation values of all observables for a given state leads to an efficient variational method for the determination of the minimum eigenvalue of an observable. The method represents one example of the practical significance of the approximate description of the $N$-qubit state. We conclude by briefly discussing extensions to generative modelling and with fermionic operators.

arXiv:1910.10543•Oct 23, 2019•28 citations

Estimating expectation values using approximate quantum states

Marco Paini, Amir Kalev, Dan Padilha +1 more

We introduce an approximate description of an N -qubit state, which contains sufficient information to estimate the expectation value of any observable to a precision that is upper bounded by the ratio of a suitably-defined seminorm of the observable to the square root of the number of the system's identical preparations M , with no explicit dependence on N . We describe an operational procedure for constructing the approximate description of the state that requires, besides the quantum state preparation, only single-qubit rotations followed by single-qubit measurements. We show that following this procedure, the cardinality of the resulting description of the state grows as 3MN . We test the proposed method on Rigetti's quantum processor unit with 12, 16 and 25 qubits for random states and random observables, and find an excellent agreement with the theory, despite experimental errors.

arXiv:2011.04754•Quantum•Mar 16, 2021•26 citations

Tight Bounds on the Randomized Communication Complexity of Vector-in-Subspace

Chengu Wang

We prove that the randomized communication complexity of Vector-in-Subspace in $\mathbb R^n$ with error at most $1/3$ is $Θ(\sqrt n)$. Alice holds a unit vector $u$ and Bob holds an $n/2$-dimensional subspace $H$; they must distinguish $u\in H$ from $u\in H^\perp$. An exact one-way quantum protocol uses $O(\log n)$ qubits, making the problem a geometric example of an exponential quantum advantage over interactive classical communication. Our lower bound matches Raz's $O(\sqrt n)$ upper bound, improves the $Ω(n^{1/3})$ lower bound of Klartag and Regev, and removes the total-rank restriction in Grupel's $Ω(\sqrt n)$ result. The proof establishes a Gaussian moment bound over complete rectangle partitions. A complex Gaussian representation yields a vanishing even moment whose cancellation is preserved when averaging over the partition. We control the signed conditional moments around a real center by decomposing conditional Gaussian measures into fixed coordinates and sub-Gaussian components. Combining this estimate with spherical harmonic analysis gives the communication lower bound.

cs.CCCross-listedarXiv:2610.30052•Oct 22, 2026•0 citations

Efficient Inner-product Algorithm for Stabilizer States

Héctor J. García, Igor L. Markov, Andrew W. Cross

Large-scale quantum computation is likely to require massive quantum error correction (QEC). QEC codes and circuits are described via the stabilizer formalism, which represents stabilizer states by keeping track of the operators that preserve them. Such states are obtained by stabilizer circuits (consisting of CNOT, Hadamard and Phase only) and can be represented compactly on conventional computers using Omega(n^2) bits, where n is the number of qubits. Although techniques for the efficient simulation of stabilizer circuits have been studied extensively, techniques for efficient manipulation of stabilizer states are not currently available. To this end, we design new algorithms for: (i) obtaining canonical generators for stabilizer states, (ii) obtaining canonical stabilizer circuits, and (iii) computing the inner product between stabilizer states. Our inner-product algorithm takes O(n^3) time in general, but observes quadratic behavior for many practical instances relevant to QECC (e.g., GHZ states). We prove that each n-qubit stabilizer state has exactly 4(2^n - 1) nearest-neighbor stabilizer states, and verify this claim experimentally using our algorithms. We design techniques for representing arbitrary quantum states using stabilizer frames and generalize our algorithms to compute the inner product between two such frames.

arXiv:1210.6646•Oct 24, 2012•15 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
We show how to approximately represent a quantum state using the square root of the usual amount of classical memory. The classical representation of an nnn-qubit state ψψψ consists of its inner products with O(2n)O(\sqrt{2^n})O(2n​) stabilizer states. A quantum state initially specified by its 2n2^n2n entries in the computational basis can be compressed to this form in time O(2npoly(n))O(2^n \mathrm{poly}(n))O(2npoly(n)), and, subsequently, the compressed description can be used to additively approximate the expectation value of an arbitrary observable. Our compression scheme directly gives a new protocol for the vector in subspace problem with randomized one-way communication complexity that matches (up to polylogarithmic factors) the optimal upper bound, due to Raz. We obtain an exponential improvement over Raz's protocol in terms of computational efficiency.
Classical simulation of quantum physics is a central approach to investigating physical phenomena. Quantum computers enhance computational capabilities beyond those of classical resources, but it remains unclear to what extent existing limited quantum computers can contribute to this enhancement. In this work, we explore a new hybrid, efficient quantum-classical representation of quantum states, the multiple-basis representation. This representation consists of a linear combination of states that are sparse in some given and different bases, specified by quantum circuits. Such representation is particularly appealing when considering depth-limited quantum circuits within reach of current hardware. We analyze the expressivity of multiple-basis representation states depending on the classical simulability of their quantum circuits. In particular, we show that multiple-basis representation states include, but are not restricted to, both matrix-product states and stabilizer states. Furthermore, we find cases in which this representation can be used, namely approximation of ground states, simulation of deeper computations by specifying bases with shallow circuits, and a tomographical protocol to describe states as multiple-basis representations. We envision this work to open the path of simultaneous use of several hardware-friendly bases, a natural description of hybrid computational methods accessible for near-term hardware.
We introduce an approximate description of an NNN-qubit state, which contains sufficient information to estimate the expectation value of any observable with precision independent of NNN. We show, in fact, that the error in the estimation of the observables' expectation values decreases as the inverse of the square root of the number of the system's identical preparations and increases, at most, linearly in a suitably defined, NNN-independent, seminorm of the observables. Building the approximate description of the NNN-qubit state only requires repetitions of single-qubit rotations followed by single-qubit measurements and can be considered for implementation on today's Noisy Intermediate-Scale Quantum (NISQ) computers. The access to the expectation values of all observables for a given state leads to an efficient variational method for the determination of the minimum eigenvalue of an observable. The method represents one example of the practical significance of the approximate description of the NNN-qubit state. We conclude by briefly discussing extensions to generative modelling and with fermionic operators.
We introduce an approximate description of an N -qubit state, which contains sufficient information to estimate the expectation value of any observable to a precision that is upper bounded by the ratio of a suitably-defined seminorm of the observable to the square root of the number of the system's identical preparations M , with no explicit dependence on N . We describe an operational procedure for constructing the approximate description of the state that requires, besides the quantum state preparation, only single-qubit rotations followed by single-qubit measurements. We show that following this procedure, the cardinality of the resulting description of the state grows as 3MN . We test the proposed method on Rigetti's quantum processor unit with 12, 16 and 25 qubits for random states and random observables, and find an excellent agreement with the theory, despite experimental errors.
We prove that the randomized communication complexity of Vector-in-Subspace in Rn\mathbb R^nRn with error at most 1/31/31/3 is Θ(n)Θ(\sqrt n)Θ(n​). Alice holds a unit vector uuu and Bob holds an n/2n/2n/2-dimensional subspace HHH; they must distinguish u∈Hu\in Hu∈H from u∈H⊥u\in H^\perpu∈H⊥. An exact one-way quantum protocol uses O(log⁡n)O(\log n)O(logn) qubits, making the problem a geometric example of an exponential quantum advantage over interactive classical communication. Our lower bound matches Raz's O(n)O(\sqrt n)O(n​) upper bound, improves the Ω(n1/3)Ω(n^{1/3})Ω(n1/3) lower bound of Klartag and Regev, and removes the total-rank restriction in Grupel's Ω(n)Ω(\sqrt n)Ω(n​) result. The proof establishes a Gaussian moment bound over complete rectangle partitions. A complex Gaussian representation yields a vanishing even moment whose cancellation is preserved when averaging over the partition. We control the signed conditional moments around a real center by decomposing conditional Gaussian measures into fixed coordinates and sub-Gaussian components. Combining this estimate with spherical harmonic analysis gives the communication lower bound.
Large-scale quantum computation is likely to require massive quantum error correction (QEC). QEC codes and circuits are described via the stabilizer formalism, which represents stabilizer states by keeping track of the operators that preserve them. Such states are obtained by stabilizer circuits (consisting of CNOT, Hadamard and Phase only) and can be represented compactly on conventional computers using Omega(n^2) bits, where n is the number of qubits. Although techniques for the efficient simulation of stabilizer circuits have been studied extensively, techniques for efficient manipulation of stabilizer states are not currently available. To this end, we design new algorithms for: (i) obtaining canonical generators for stabilizer states, (ii) obtaining canonical stabilizer circuits, and (iii) computing the inner product between stabilizer states. Our inner-product algorithm takes O(n^3) time in general, but observes quadratic behavior for many practical instances relevant to QECC (e.g., GHZ states). We prove that each n-qubit stabilizer state has exactly 4(2^n - 1) nearest-neighbor stabilizer states, and verify this claim experimentally using our algorithms. We design techniques for representing arbitrary quantum states using stabilizer frames and generalize our algorithms to compute the inner product between two such frames.
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.