Quadratic unconstrained binary optimization

Quadratic unconstrained binary optimization (QUBO) is a pattern matching technique, common in machine learning applications. QUBO is an NP hard problem.

QUBO problems may sometimes be well-suited to algorithms aided by quantum annealing.^[1]

QUBO is the problem of minimizing a quadratic polynomial over binary variables. The quadratic polynomial will be of the form $E(X_{1},X_{2},...,X_{N})=\sum _{i=1}^{N}c_{i}X_{i}+\sum _{i=1}^{N}\sum _{j=1}^{i}Q_{ij}\times X_{i}\times X_{j}$ with $X_{i}\in \{0,1\}$ and $c_{i},Q_{ij}\in R$ .

References

↑ Tom Simonite (8 May 2013). "D-Wave’s Quantum Computer Goes to the Races, Wins". MIT Technology Review. Retrieved 12 May 2013.

External links

Endre Boros, Peter L Hammer & Gabriel Tavares (April 2007). "Local search heuristics for Quadratic Unconstrained Binary Optimization (QUBO)". Journal of Heuristics. Association for Computing Machinery. 13 (2): 99–132. doi:10.1007/s10732-007-9009-3. Retrieved 12 May 2013.
Di Wang & Robert Kleinberg (November 2009). "Analyzing quadratic unconstrained binary optimization problems via multicommodity flows". Discrete Applied Mathematics. Elsevier. 157 (18): 3746–3753. doi:10.1016/j.dam.2009.07.009. Retrieved 12 May 2013.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.