Image recognition paper April 28, 2008
Posted by Geordie in Uncategorized.trackback
The first of a series of publications on solving artificial intelligence problems with quantum computers.
Abstract:
Many artificial intelligence (AI) problems naturally map to NP-hard optimization problems. This has the interesting consequence that enabling human-level capability in machines often requires systems that can handle formally intractable problems. This issue can sometimes (but possibly not always) be resolved by building special-purpose heuristic algorithms, tailored to the problem in question. Because of the continued difficulties in automating certain tasks that are natural for humans, there remains a strong motivation for AI researchers to investigate and apply new algorithms and techniques to hard AI problems. Recently a novel class of relevant algorithms that require quantum mechanical hardware have been proposed. These algorithms, referred to as quantum adiabatic algorithms, represent a new approach to designing both complete and heuristic solvers for NP-hard optimization problems. In this work we describe how to formulate image recognition, which is a canonical NP-hard AI problem, as a Quadratic Unconstrained Binary Optimization (QUBO) problem. The QUBO format corresponds to the input format required for D-Wave superconducting adiabatic quantum computing (AQC) processors.
Did you submit it somewhere? It looks like a computer science paper to me. Are you planning to talk about particular algorithms use in the future publications?
AI: No, no submission yet (just arxiv). Algorithmic issues will be the focus of part II, while chip physics issues are to be the focus of III. Highly subject to change of course
I’m looking forward to seeing the experimental results, although I doubt that even a sucess in image recognition will silence the critics (maybe a skeptic or two will admit to a possibility of QC, however).
Any timeline for when this will be in the experimental phase? What size of chip will be necessary to compare 640×480 images, for starters?
Also, yay GSP! The last fight with Serra was totally not what I expected, I love his fights because I never know how he’ll fight…
Aleph, I don’t think that image resolution itself has much of an impact on the comparison except for that there may be more interest points and/or more accurate interest points. For comparing two images, the key number is the number of potentially matching interest point pairs between the two images. Those are the nodes/variables as the paper discusses. The number of qubits required is larger than that number, unless all pairwise connections exist between qubits.
I didn’t figure that there’d be more interest points in a hi-res picture, I just kinda picked a 640×480 number outta my ass as a reasonable size, to actually give decent data I suppose. For example, I can’t see an algorithm easily picking a point of interest in a 6×5 “photo”, it’d need enough pixel information. Although now I wonder about recognition of say a 16×16 8-bit sprite in different poses, as a limitation of colours could make point identification much easier (I was just reading Nuklear Power, which made me think that…).
I was thinking I guess more along the lines of: For two standard photos (say 2 similar photos of people), how many points of interest would it take to ensure say a 99% (or 99.9%) match (facial recognition), and how many qubits it would take to run this comparison?
Hi Geordie,
Using Quantum Computing for Artificial Intelligence is an interesting direction to explore. But you will not be exploring its full potential if you do not go after computational neuroscience models. Many AI researchers start from the assumption that they do no need these models but even if they were to reach it from any other direction they would be surprised on what they would find out.
It might be very useful from both a practical and theoretical perspective to explore the computational requirements of the brain using your platform.
Thanks,
Ovidiu