Regev, Oded and Vidick, Thomas
(2019)
*Bounds on Dimension Reduction in the Nuclear Norm.*
.
(Unpublished)
http://resolver.caltech.edu/CaltechAUTHORS:20190320-095834301

PDF
- Submitted Version
See Usage Policy. 340Kb |

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20190320-095834301

## Abstract

For all n ≥ 1, we give an explicit construction of m × m matrices A_1,…,A_n with m = 2^(⌊n/2⌋) such that for any d and d × d matrices A′_1,…,A′_n that satisfy ∥A_′i−A′_j∥S_1 ≤ ∥A_i−A_j∥S_1 ≤ (1+δ)∥A′_i−A′_j∥S_1 for all i,j∈{1,…,n} and small enough δ = O(n^(−c)), where c > 0 is a universal constant, it must be the case that d ≥ 2^(⌊n/2⌋−1). This stands in contrast to the metric theory of commutative ℓ_p spaces, as it is known that for any p ≥ 1, any n points in ℓ_p embed exactly in ℓ^d_p for d = n(n−1)/2. Our proof is based on matrices derived from a representation of the Clifford algebra generated by n anti-commuting Hermitian matrices that square to identity, and borrows ideas from the analysis of nonlocal games in quantum information theory.

Item Type: | Report or Paper (Discussion Paper) | ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

Related URLs: |
| ||||||||||||||

ORCID: |
| ||||||||||||||

Additional Information: | Supported by the Simons Collaboration on Algorithms and Geometry and by the National Science Foundation (NSF) under Grant No. CCF-1814524. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the NSF. Supported by NSF CAREER Grant CCF-1553477, a CIFAR Azrieli Global Scholar award, and the Institute for Quantum Information and Matter, an NSF Physics Frontiers Center (NSF Grant PHY-1733907) | ||||||||||||||

Group: | IQIM, Institute for Quantum Information and Matter | ||||||||||||||

Funders: |
| ||||||||||||||

Record Number: | CaltechAUTHORS:20190320-095834301 | ||||||||||||||

Persistent URL: | http://resolver.caltech.edu/CaltechAUTHORS:20190320-095834301 | ||||||||||||||

Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||||||

ID Code: | 93981 | ||||||||||||||

Collection: | CaltechAUTHORS | ||||||||||||||

Deposited By: | Tony Diaz | ||||||||||||||

Deposited On: | 20 Mar 2019 17:06 | ||||||||||||||

Last Modified: | 20 Mar 2019 17:06 |

Repository Staff Only: item control page