Low rank matrix recovery from Clifford orbits

Abstract

We prove that low-rank matrices can be recovered efficiently from a small number of measurements that are sampled from orbits of a certain matrix group. As a special case, our theory makes statements about the phase retrieval problem. Here, the task is to recover a vector given only the amplitudes of its inner product with a small number of vectors from an orbit. Variants of the group in question have appeared under different names in many areas of mathematics. In coding theory and quantum information, it is the complex Clifford group; in time-frequency analysis the oscillator group; and in mathematical physics the metaplectic group. It affords one particularly small and highly structured orbit that includes and generalizes the discrete Fourier basis: While the Fourier vectors have coefficients of constant modulus and phases that depend linearly on their index, the vectors in said orbit have phases with a quadratic dependence. In quantum information, the orbit is used extensively and is known as the set of stabilizer states. We argue that due to their rich geometric structure and their near-optimal recovery properties, stabilizer states form an ideal model for structured measurements for phase retrieval. Our results hold for $m\ge C{\kappa }_{r}rd\log (d)$ measurements, where the oversampling factor k varies between ${\kappa }_r=1$ and ${\kappa }_r=r^2$ depending on the orbit. The reconstruction is stable towards both additive noise and deviations from the assumption of low rank. If the matrices of interest are in addition positive semidefinite, reconstruction may be performed by a simple constrained least squares regression. Our proof methods could be adapted to cover orbits of other groups.

arXiv comment19 pages, no figure

References in corpus (16)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Improved Simulation of Stabilizer Circuits
• Quantum state tomography via compressed sensing
• Symmetric Informationally Complete Quantum Measurements
• Femtosecond Diffractive Imaging with a Soft-X-ray Free-Electron Laser
• Quantum Tomography via Compressed Sensing: Error Bounds, Sample Complexity, and Efficient Estimators
• SIC-POVMs and the Extended Clifford Group
• Stabilizer states and Clifford operations for systems of arbitrary dimensions, and modular arithmetic
• Minimal Informationally Complete Measurements for Pure States
• A Partial Derandomization of PhaseLift using Spherical Designs
• Improved Recovery Guarantees for Phase Retrieval from Coded Diffraction Patterns
• The Clifford group fails gracefully to be a unitary 4-design
• Efficient Pure State Quantum Tomography from Five Orthonormal Bases
• A linearized stabilizer formalism for systems of finite dimension
• Qubit stabilizer states are complex projective 3-designs
• Distinguishing quantum states using Clifford orbits

Cited by in corpus (8)

• Multiqubit Clifford groups are unitary 3-designs
• Schur-Weyl Duality for the Clifford Group with Applications: Property Testing, a Robust Hudson Theorem, and de Finetti Representations
• Classical Shadows With Noise
• Recovering quantum gates from few average gate fidelities
• Representations of the multi-qubit Clifford group
• Kerdock Codes Determine Unitary 2-Designs
• Rapid characterisation of linear-optical networks via PhaseLift
• Predicting Features of Quantum Systems from Very Few Measurements