ECE Seminar: Scalable quantum tomography via sparse projections onto the simplex.
Friday, January 25, 2013 - 12:00pm to 1:00pm
Volkan Cevher, Ph.D., Assistant Professor, Ecole Polytechnique Federale de Lausanne
In this talk, we describe a scalable and accurate quantum tomography (QT) recovery framework with approximation guarantees. Our objective is to accurately recover a d x d complex positive semi-definite (PSD) matrix X with a known rank r from dimensionality reducing measurements as y=A(X)+e, where A is a subsampled Pauli operator, and e is some bounded perturbation. The QT problem has three salient aspects that set it apart from the existing low-rank recovery problems: 1. Standard nuclear norm minimization approaches are not directly applicable in QT since X is a PSD density matrix and must have a trace of 1. 2. The Pauli measurement operator A in QT creates a major scalability bottleneck as the range of its adjoint is fully dense and the size of X is exponential in the number of quantum bits q (qubits): d=2^q. 3. The Pauli measurement operator A has the rank restricted isometry property (RIP) from O(rdlog^6d) measurements. We show how to achieve provable QT recovery in linear space and quadratic time (in d) and computationally demonstrate 16-qubit recovery from 4rd Pauli measurements. To this end, we derive new sparse simplex projections, leverage randomized SVD¿s, and propose a new online subspace reweighting technique. We also describe how our algorithmic developments apply to seemingly different problems, where convex relaxations of the sparsity and rank appear as constraints, such as measure learning, Markowitz portfolio optimization, and metric learning problems.