12 citations · 51 across the 12 of their papers we have counts for
4 papers · 1 filter
Efficient quantum tomography
Ryan O'Donnell, John Wright
In the quantum state tomography problem, one wishes to estimate an unknown -dimensional mixed quantum state , given few copies. We show that copies suffice to obtain…
Improved and Simplified Inapproximability for k-means
Euiwoong Lee, Melanie Schmidt, John Wright
The k-means problem consists of finding k centers in the d-dimensional Euclidean space that minimize the sum of the squared distances of all points in an input set P to their close…
Beating the random assignment on constraint satisfaction problems of bounded degree
Boaz Barak, Ankur Moitra, Ryan O'Donnell +7
We show that for any odd and any instance of the Max-kXOR constraint satisfaction problem, there is an efficient algorithm that finds an assignment satisfying at least a $\frac…
Quantum Spectrum Testing
Ryan O'Donnell, John Wright
In this work, we study the problem of testing properties of the spectrum of a mixed quantum state. Here one is given copies of a mixed state and th…