D-Wave Lecture on Quantum Compression Learning

[James A. Bowery]

Of particular relevance to the Hutter Prize is a recent lecture by the
CEO of D-Wave on their approach to machine learning based on
compression using quantum computing:

http://connect.arc.nasa.gov/p69sps0r4bc/?launcher=false&fcsContent=true&pbMode=normal

[James Bowery]

Here is a list of quantum learning lectures at the same conference:

http://dwave.wordpress.com/2012/02/04/videos-from-the-nasa-quantum-future-technologies-conference/ 

--
You received this message because you are subscribed to the Google Groups "Hutter Prize" group.
To post to this group, send email to hutter...@googlegroups.com.
To unsubscribe from this group, send email to hutter-prize...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/hutter-prize?hl=en.

[Matt Mahoney]

One of the videos (I didn't watch it) is on computing Ramsay numbers
on a quantum computer. I did read the paper at
http://arxiv.org/pdf/1201.1842v2.pdf and it does reveal some
limitations of the D-Wave machine that are hard to get from their
website. The D-Wave machine solves in about 1 ms the discrete
optimization problem of finding x that minimizes Ax + b, where x is a
128 qubit vector in {-1,+1}, and A is a programmable symmetric real
matrix and b is a vector in [-1,1]. This type of architecture is not a
general purpose quantum computer. For example, it can't implement
Shor's algorithm for factoring or breaking public key cryptography.
Also, the solution is probabilistic, which is a fundamental limitation
of quantum computing. Typically you would run it several times to get
a distribution of sub-optimal solutions.

In the paper, about 20% of the qubits are broken, so any algorithm you
design has to work around them. It also has to work around the layout
constraints. The weight matrix A is sparse. Each qubit connects to at
most 6 others. This allowed the computation of Ramsay numbers R(2,8)
and R(3,3), which are easy problems for a conventional computer. But
even a fully working chip would not extend the set of known solutions.
The chip requires cooling to 20 mK.

The video described an application to lossy image compression by
finding optimal feature sets to describe an image. So far it isn't
anything that we can't already do on a normal computer. Also,
probabilistic computation would not work for lossless modeling.

The video also said that D-Wave recently completed a 512 qubit chip.

--
-- Matt Mahoney, mattma...@gmail.com

[James Bowery]

On Friday, February 24, 2012 1:37:10 PM UTC-6, Matt Mahoney wrote:

...The video described an application to lossy image compression by

finding optimal feature sets to describe an image. So far it isn't
anything that we can't already do on a normal computer. Also,
probabilistic computation would not work for lossless modeling.

They're now talking about sparse coding as an application with compression/AI potential.