CS: Quantum Compressed Sensing

I just found the following online presentation entitled: Learning Much from Little: Compressed Sensing Approach to Quantum State Tomography and Other Ideas of Systems Identification presented by Jens Eisert. I'll shortly add it to the online video Compressive Sensing page.

Still on the subject of Quantum issues the paper mentioned yesterday that uses a quantum chip (or equivalent) to perform an l_0 regularization is:

NIPS 2009 Demonstration: Binary Classification using Hardware Implementation of Quantum Annealing by Hartmut Neven, Vasil S. Denchev, Marshall Drew-Brook, Jiayong Zhang, William G. Macready, Geordie Rose. The abstract reads:

Previous work [NDRM08, NDRM09] has sought the development of binary classifiers that exploit the ability to better solve certain discrete optimization problems with quantum annealing. The resultant training algorithm was shown to offer benefits over competing binary classifiers even when the discrete optimization problems were solved with software heuristics. In this progress update we provide first results on training using a physical implementation of quantum annealing for black-box optimization of Ising objectives. We successfully build a classifier for the detection of cars in digital images using quantum annealing in hardware. We describe the learning algorithm and motivate the particular regularization we employ. We provide results on the efficacy of hardware-realized quantum annealing, and compare the final classifier to software trained variants, and a highly tuned version of AdaBoost.

Hartmut Neven, one of the author, made a presentation on this subject at NIPS'08 entitled: Training a Binary Classifier with the Quantum Adiabatic Algorithm. The D-Wave folks who are making this quantum chip have a blog. The company website is here.

As I said yesterday, if this chip sees the light of the day and performs this l_0 regularization, then I believe compressive sensing studies could focus uniquely on the acquisition/sampling stage and go beyond the issue of sparsity.