Limitations on quantum dimensionality reduction
arXiv:1012.2262 · doi:10.1007/978-3-642-22006-7_8
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.
arXiv comment17 pages; v2: typo fixes and clarifications
References in corpus (7)
- Quantum fingerprinting
- Classical and quantum communication without a shared reference frame
- Distinguishability of quantum states under restricted families of measurements with an application to quantum data hiding
- Limitations of Quantum Advice and One-Way Communication
- From Low-Distortion Norm Embeddings to Explicit Uncertainty Relations and Efficient Information Locking
- Non-additivity of Renyi entropy and Dvoretzky's Theorem
- Strengths and Weaknesses of Quantum Fingerprinting
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