PIRSA:12040101

Universal Low-rank Matrix Recovery from Pauli Measurements

Liu, Y. (2012). Universal Low-rank Matrix Recovery from Pauli Measurements. Perimeter Institute. https://pirsa.org/12040101

Liu, Yi-Kai. Universal Low-rank Matrix Recovery from Pauli Measurements. Perimeter Institute, Apr. 04, 2012, https://pirsa.org/12040101 

          @misc{ pirsa_PIRSA:12040101,
            doi = {10.48660/12040101},
            url = {https://pirsa.org/12040101},
            author = {Liu, Yi-Kai},
            keywords = {Quantum Information},
            language = {en},
            title = {Universal Low-rank Matrix Recovery from Pauli Measurements},
            publisher = {Perimeter Institute},
            year = {2012},
            month = {apr},
            note = {PIRSA:12040101 see, \url{https://pirsa.org}}
          }

Yi-Kai Liu National Institute of Standards & Technology

DOI 10.48660/12040101
Collection
Talk Type Scientific Series
Subject

Abstract

We study the problem of reconstructing an unknown matrix M, of rank r and dimension d, using O(rd poly log d) Pauli measurements. This has applications to compressed sensing methods for quantum state tomography.  We give a solution to this problem based on the restricted isometry property (RIP), which improves on previous results using dual certificates. In particular, we show that almost all sets of O(rd log^6 d) Pauli measurements satisfy the rank-r RIP. This implies that M can be recovered from a fixed ("universal") set of Pauli measurements, using nuclear-norm minimization (e.g., the matrix Lasso), with nearly-optimal bounds on the error. Our proof uses Dudley's inequality for Gaussian processes, together with bounds on covering numbers obtained via entropy duality.