@article {2208, title = {Validating and Certifying Stabilizer States}, journal = {Phys. Rev. A }, volume = {99}, year = {2019}, month = {9/16/2019}, abstract = {

We propose a measurement scheme that validates the preparation of a target n-qubit stabilizer state. The scheme involves a measurement of n Pauli observables, a priori determined from the target stabilizer and which can be realized using single-qubit gates. Based on the proposed validation scheme, we derive an explicit expression for the worse-case fidelity, i.e., the minimum fidelity between the target stabilizer state and any other state consistent with the measured data. We also show that the worse-case fidelity can be certified, with high probability, using O(n) copies of the state of the system per measured observable.

}, doi = {https://doi.org/10.1103/PhysRevA.99.042337}, url = {https://arxiv.org/abs/1808.10786}, author = {Amir Kalev and Anastasios Kyrillidis} } @article {2258, title = {Implicit regularization and solution uniqueness in over-parameterized matrix sensing}, year = {2018}, abstract = {

We consider whether algorithmic choices in over-parameterized linear matrix factorization introduce implicit regularization. We focus on noiseless matrix sensing over rank-r positive semi-definite (PSD) matrices in Rn\×n, with a sensing mechanism that satisfies the restricted isometry property (RIP). The algorithm we study is that of \emph{factored gradient descent}, where we model the low-rankness and PSD constraints with the factorization UU⊤, where U\∈Rn\×r. Surprisingly, recent work argues that the choice of r\≤n is not pivotal: even setting U\∈Rn\×n is sufficient for factored gradient descent to find the rank-r solution, which suggests that operating over the factors leads to an implicit regularization. In this note, we provide a different perspective. We show that, in the noiseless case, under certain conditions, the PSD constraint by itself is sufficient to lead to a unique rank-r matrix recovery, without implicit or explicit low-rank regularization. \emph{I.e.}, under assumptions, the set of PSD matrices, that are consistent with the observed data, is a singleton, irrespective of the algorithm used.

}, url = {https://arxiv.org/abs/1806.02046}, author = {Anastasios Kyrillidis and Amir Kalev} } @article {2107, title = {Provable quantum state tomography via non-convex methods}, year = {2017}, month = {2017/11/19}, abstract = {

With nowadays steadily growing quantum processors, it is required to develop new quantum tomography tools that are tailored for high-dimensional systems. In this work, we describe such a computational tool, based on recent ideas from non-convex optimization. The algorithm excels in the compressed-sensing-like setting, where only a few data points are measured from a lowrank or highly-pure quantum state of a high-dimensional system. We show that the algorithm can practically be used in quantum tomography problems that are beyond the reach of convex solvers, and, moreover, is faster than other state-of-the-art non-convex approaches. Crucially, we prove that, despite being a non-convex program, under mild conditions, the algorithm is guaranteed to converge to the global minimum of the problem; thus, it constitutes a provable quantum state tomography protocol.

}, url = {https://arxiv.org/abs/1711.02524}, author = {Anastasios Kyrillidis and Amir Kalev and Dohuyng Park and Srinadh Bhojanapalli and Constantine Caramanis and Sujay Sanghavi} }