Квадратичная безусловная двоичная оптимизация - Quadratic unconstrained binary optimization

Не путать с Кубо, телевизионная служба, принадлежащая Ion Media Networks.

Квадратичная безусловная двоичная оптимизация (QUBO) это сопоставление с образцом техника, распространенная в машинное обучение Приложения. QUBO - это NP жесткий проблема. Примеры проблем, которые можно сформулировать как проблемы QUBO: Максимальный разрез, Раскраска графика и Проблема с разделом.^[1]

Проблемы QUBO могут иногда хорошо подходить для алгоритмов, которым помогает квантовый отжиг.^[2]

QUBO - это проблема минимизации квадратичный многочлен над двоичными переменными. Квадратичный многочлен будет иметь вид ${displaystyle E(X_{1},X_{2},...,X_{N})=sum _{i=1}^{N}sum _{j=1}^{i}Q_{ij} imes X_{i} imes X_{j}}$с ${displaystyle X_{i}in {0,1}}$ и ${displaystyle Q_{ij}in R}$.

Рекомендации

1. Гловер, Фред; Кохенбергер, Гэри (2019). «Учебное пособие по формулированию и использованию моделей QUBO». arXiv:1811.11538 [cs.DS ].
2. Том Симонит (8 мая 2013 г.). «Квантовый компьютер D-Wave идет в гонки, побеждает». Обзор технологий MIT. Получено 12 мая 2013.

внешняя ссылка

• Эндре Борос, Питер Л. Хаммер и Габриэль Таварес (апрель 2007 г.). «Эвристика локального поиска для квадратичной неограниченной двоичной оптимизации (QUBO)». Журнал эвристики. Ассоциация вычислительной техники. 13 (2): 99–132. Дои:10.1007 / s10732-007-9009-3. S2CID  32887708. Получено 12 мая 2013.
• Ди Ван и Роберт Клейнберг (ноябрь 2009 г.). «Анализ квадратичных задач безусловной бинарной оптимизации через многопродуктовые потоки». Дискретная прикладная математика. Эльзевир. 157 (18): 3746–3753. Дои:10.1016 / j.dam.2009.07.009. ЧВК  2808708. PMID  20161596.