Предисловие:

В пониманииQUBOНужно знать раньшеМодель Изинга (Ising Модель (пояснение взято из Википедии) — математическая модель имени физика Эрнста Изинга, которая используется для описания ферромагнетизма материи.

Эта модель включает параметр σi, который можно использовать для описания магнитного момента отдельного атома. Его значение может быть только +1 или -1, что соответствует увеличению или уменьшению спина соответственно. Эти магнитные моменты обычно располагаются по определенным правилам. Формируется решетка и в модель вводятся параметры конкретных взаимодействий, так что соседние спины влияют друг на друга.

Ising Model：

Пусть Λ — множество всех точек решетки, где каждая точка решетки имеет набор всех соседних с ней точек решетки (называемых в математике графом), и эти точки решетки образуют d-мерную решетку. Для каждой точки решетки k ∈ Λ Существует дискретная переменная σ(k) ,в σ(k) ∈ {+1, −1} представляет вращение точки решетки. А набор всех переменных σ = (σ(k))(kεΛ) называется Конфигурация спина.

Для двух соседних точек решеткиi, j ∈ Λ ,Мы можем ввести параметр взаимодействияJ(ij),также,Можно предположить, что каждый спинj ∈ Λ и внешнее магнитное поле h(j) эффект. Тогда гамильтониан всей системы можно записать как:

Гамильтониан всей системы можно описать как:

в <ij> представляет собой точку решетки i и точки решетки j являются соседними точками решетки. Следовательно, первый член гамильтониана представляет собой сумму каждой пары соседних точек решетки (каждая пара учитывается только один раз), представляя энергию взаимодействия между всеми спинами, а второй член представляет собой магнитное поле и спин. Энергия взаимодействие. µ — значение магнитного момента точки решетки. Стоит отметить, что магнитный момент электрона противоположен направлению его вращения, поэтому более разумно, чтобы второй член гамильтониана был положительным, но это так. принято делать Второе слагаемое имеет отрицательный знак.

QUBO:

Квадратичная неограниченная бинарная оптимизация (Quadratic unconstrained binary оптимизация, QUBO), также известный как неограниченное двоично-квадратичное программирование (неограниченное binary quadratic programming ,UBQP）,это задача комбинаторной оптимизации,От финансовой экономики к машинному обучению,Имеет широкий спектр применения. Задача QUBO является NP-сложной задачей.,Для многих классических задач теоретической информатики,Такие как максимальный разрез, раскраска графа и проблемы разделения.,Все можно превратить в задачи QUBO. Некоторые модели машинного обучения также могут быть встроены в QUBO.,Включает машины опорных векторов、Кластеризация и вероятностные графические модели。Более того, благодаря своей тесной связи с моделью Изинга, QUBO образует основной класс задач адиабатических квантовых вычислений.

Его выражение:

• XiПринадлежит двоичной переменной（0,1）；
• qij — действительное число, параметр и верхняя треугольная матрица.

QUBOПроблема в том, чтобы минимизироватьfQ,Найдите комбинацию Си по

Проблемы, которые можно решить с помощью QUBO:

Ниже перечислены 112 задач оптимизации, которые можно решить с помощью QUBO. Многие из этих задач представляют собой классические задачи оптимизации в математике (в основном задачи NP-Hard).

Список будет расширяться со временем. (Ссылка 3)

• Number Partitioning (NP)
• Maximum Cut (MC)
• Minimum Vertex Cover (MVC)
• Set Packing (SP)
• Set Partitioning (SPP)
• Maximum 2-SAT (M2SAT)
• Maximum 3-SAT (M3SAT)
• Graph Coloring (GC)
• General 0/1 Programming (G01P)
• Quadratic Assignment (QA)
• Quadratic Knapsack (QK)
• Graph Partitioning
• Decisional Clique Problem
• Maximum Clique Problem
• Binary Integer Linear Programming
• Exact Cover
• 3SAT
• Maximal Independent Set
• Minimal Maximal Matching
• Set Cover
• Knapsack with Integer Weights
• Clique Cover
• Job Sequencing Problem
• Hamiltonian Cycles Problem
• Minimal Spanning Tree
• Steiner Trees
• Directed Feedback Vertex Set
• Undirected Feedback Vertex Set
• Feedback Edge Set
• Traveling Salesman (TSP)
• Traveling Salesman with Time Windows (TSPTW)
• Graph Isomorphism
• Subgraph Isomorphism
• Induced Subgraph
• Capacitated Vehicle Routing (CVRP)
• Multi-Depot Capacitated Vehicle Routing (MDCVRP)
• L1 norm
• k-Medoids
• Contact Map Overlap Problem
• Minimum Multicut Problem
• Broadcast Time Problem
• Maximum Common Subgraph Isomorphism
• Densest k-subgraph
• Longest Path Problem
• Airport Gateway Assignment
• Linear regression
• Support Vector Machine
• k-means clustering
• Eigencentrality
• Container Assignment Problem
• k-colorable subgraph problem
• Routing and Wavelength Assignment with Protection
• Aircraft Loading Optimization
• Linear least squares / system of linear equations
• Traffic Flow Optimization
• Permutation Synchronization
• Max-Flow Problem
• Network Shortest Path Problem
• Structural Isomer Search Problem
• k-densest Common Sub-Graph Isomorphism
• Community Detection
• Nurse Scheduling problem
• Aircraft Loading Optimization
• PageRank
• Ramsey numbers
• Generalized Ramsey numbers
• Transaction Settlement
• Sensor placement problem in water distribution networks
• Fault Detection and Diagnosis of Graph-Based Systems
• Bounded-Depth Steiner Trees
• Graph Matching with Permutation Matrix Constraints
• Gaussian Process Variance Reduction
• Quantum Permutation Synchronization
• Unit Commitment Problem
• Heat Exchanger Network Synthesis
• Garden Optimization Problem
• Two-Dimensional Cutting Stock Problem
• Labelled Maximum Weighted Common Subgraph
• Maximum Weighted Co-k-plex
• Molecular Similarity based on Graphs
• Portfolio Optimization (Modern Portfolio Theory)
• Weighted Maximum Cut
• Weighted Maximum Clique
• Satellite Scheduling
• Refinery Scheduling
• Job Shop Scheduling
• Extended Job Shop Scheduling with Autonomous Ground Vehicles
• Parallel Flexible Job Shop Scheduling
• Bin Packing with Integer Weights
• Number Partitioning with m sets
• Graph Partitioning with m sets
• Subset Sum Problem
• Numerical Three-Dimensional Matching
• Social Workers Problem
• EV-Bus Charging Scheduling Problem
• Vehicle Routing Problem
• Robot Path Planning
• Scheduling on Undirected Hamiltonian Paths
• Market Graph Clustering
• Balanced k-Means Clustering
• Distance-based Clustering in general
• Credit Scoring and Classification
• Dynamic Portfolio Optimization
• Railway Dispatching and Conflict Management Optimization
• Workflow Application Scheduling
• Mirrored Double Round-robin Tournament
• Transaction Scheduling
• Transformation Estimation
• Point Set Registration
• Maximum Cardinality Matching
• Multi-car Paint Shop Optimization
• Binary Paint Shop Problem

Ссылки:

1. Википедия: https://en.wikipedia.org/wiki/Quadratic_unconstrained_binary_optimization
2. QUBO и ML: https://ecco2019.euro-online.org/talks/GloverF_KochenbergerG.pdf
3. List of QUBO formulations：https://blog.xa0.de/post/List-of-QUBO-formulations/
4. Учебное пособие по обучению и использованию QUBO: https://arxiv.org/pdf/1811.11538.pdf
5. Модель Изинга: https://zh.wikipedia.org/zh-cn/Модель Изинга