Limitations on quantum dimensionality reduction

Abstract

The Johnson-Lindenstrauss Lemma is a classic result which implies that any set of n real vectors can be compressed to O(log n) dimensions while only distorting pairwise Euclidean distances by a constant factor. Here we consider potential extensions of this result to the compression of quantum states. We show that, by contrast with the classical case, there does not exist any distribution over quantum channels that significantly reduces the dimension of quantum states while preserving the 2-norm distance with high probability. We discuss two tasks for which the 2-norm distance is indeed the correct figure of merit. In the case of the trace norm, we show that the dimension of low-rank mixed states can be reduced by up to a square root, but that essentially no dimensionality reduction is possible for highly mixed states.

17 pages; v2: typo fixes and clarifications

References in corpus (2)

• Classical and quantum communication without a shared reference frame
• From Low-Distortion Norm Embeddings to Explicit Uncertainty Relations and Efficient Information Locking

Cited by in corpus (10)

• Adversarial quantum circuit learning for pure state approximation
• Distinguishing multi-partite states by local measurements
• Compressibility of positive semidefinite factorizations and quantum models
• Identification Via Quantum Channels
• Dimensionality reduction of SDPs through sketching
• Embeddings of Schatten Norms with Applications to Data Streams
• Quantum Decimation in Hilbert Space: Coarse-Graining without Structure
• A quantum Johnson-Lindenstrauss lemma via unitary t-designs
• A stable quantum Darmois-Skitovich theorem
• Nonlocal games with noisy maximally entangled states are decidable