QUBO 문제란?

참고

설치 필요: 이 기능을 사용하려면 MATLAB Support Package for Quantum Computing이 있어야 합니다.

QUBO 및 Ising 문제 정의

QUBO 문제(Quadratic Unconstrained Binary Optimization: 2차 비제약 이진 최적화)는 이진 변수의 2차 최적화 문제입니다. N개의 성분을 갖는 이진 변수 x(i)에 대해, 최소화 목적 함수는 다음과 같은 형식을 가집니다.

$f (x) = \sum_{i = 1}^{N} \sum_{j = 1}^{N} Q_{i, j} x_{i} x_{j} + \sum_{i = 1}^{N} c_{i} x_{i} + d .$

Q는 실수 대칭 행렬일 수 있습니다. Q가 대칭이 아닌 경우, 소프트웨어가 내부적으로 Q를 다음과 같은 등가 대칭 행렬로 대체합니다.
$\hat{Q} = \frac{Q + Q^{'}}{2}$
이때 표현식은 다음과 같습니다.
$x' \overset{⌢}{Q} x = x' Q x .$
c는 N개의 성분을 갖는 숫자형 벡터입니다.
d는 스칼라입니다.

qubo 함수를 사용하여 문제를 QUBO 문제로 변환합니다.

qprob = qubo(Q)
% or
qprob = qubo(Q,c)
% or
qprob = qubo(Q,c,d)

Ising 문제는 QUBO 문제와 동일한 정식화가 적용되지만, Ising 변수 y(i)는 QUBO x 변수의 0 또는 1이 아니라 ±1의 값을 가집니다. 선형 매핑을 사용하여 두 정식화 간에 변환할 수 있습니다. 변수 x를 사용하여 표현된 QUBO 문제와 변수 y를 사용하여 표현된 Ising 문제 간의 매핑은 다음과 같습니다.

$\begin{array}{l} y = 2 x - 1 \\ x = \frac{y + 1}{2} . \end{array}$

이 두 정식화에서의 목적 함수 값은 쉽게 계산 가능한 양만큼의 차이를 가집니다.

$\begin{matrix} x' Q x + c' x + d = \frac{(y + 1)' Q (y + 1)}{4} + c' (\frac{y + 1}{2}) + d \\ = \frac{y' Q y}{4} + (\frac{1' Q + c'}{2}) y + d + \frac{1' Q 1}{4} + \frac{c' 1}{2}, \end{matrix}$

여기서 1은 y와 동일한 길이의, 1로 구성된 열 벡터를 나타냅니다.

QUBO 문제 응용 사례

Glover, Kochenberger, and Du[1]에서 설명하는 바에 따르면, 여행하는 외판원 문제(Traveling Salesperson Problem), 2차 할당 문제(Quadratic Assignment Problem)와 같은 다양한 조합 최적화 문제를 QUBO 문제로 정식화할 수 있습니다. 일반적인 조합 최적화 문제를 이 프레임워크로 정식화하는 여러 기법은 Lucas[2] 항목을 참조하십시오.

또한 현재 사용 중이거나 새로 제안된 많은 양자 컴퓨터에서 문제 유형으로 QUBO 또는 Ising을 사용합니다. 조합 최적화 문제에 대한 양자 해를 구해 보려면 QUBO 문제를 정식화한 후 양자 하드웨어로 문제를 전달하여 해를 구해 보십시오.

풀이 방법

QUBO 문제를 풀려면 아래의 2단계를 수행하십시오.

qubo를 호출하여 문제를 QUBO 객체로 만듭니다.
tabu 탐색 알고리즘을 사용하는 solve를 호출하여 QUBO를 풉니다.

예를 들어, 2차 행렬 Q, 선형 벡터 c, 상수항 d에 대한 QUBO 문제를 만듭니다.

Q = [0 -1 2;...
    -1 0 4;...
    2 4 0];
c = [-5 6 -4];
d = 12;
qprob = qubo(Q,c,d)

qprob = 

  qubo with properties:

    QuadraticTerm: [3×3 double]
       LinearTerm: [-5 6 -4]
     ConstantTerm: 12
     NumVariables: 3

tabu 탐색 알고리즘을 사용하여 문제를 풉니다.

result = solve(qprob)

result = 

  quboResult with properties:

                BestX: [3×1 double]
    BestFunctionValue: 7
      AlgorithmResult: [1×1 tabuSearchResult]

또는 Optimization Toolbox™ 라이선스를 보유하고 있고 풀려는 문제가 최대 100개 또는 200개의 변수를 가진다면, Verify Optimality by Solving QUBO as MILP에 나와 있는 대로 QUBO 문제를 혼합 정수 선형 계획법(MILP) 문제로 변환한 후 intlinprog를 사용하여 풀 수 있습니다.

참고 문헌

[1] Glover, Fred, Gary Kochenberger, and Yu Du. Quantum Bridge Analytics I: A Tutorial on Formulating and Using QUBO Models. Available at https://arxiv.org/abs/1811.11538.

[2] Lucas, Andrew. Ising formulations of many NP problems. Available at https://arxiv.org/pdf/1302.5843.pdf.

[3] Kochenberger, G. A., and F. Glover. A Unified Framework for Modeling and Solving Combinatorial Optimization Problems: A Tutorial. In: Hager, W. W., Huang, S. J., Pardalos, P. M., Prokopyev, O. A. (eds) Multiscale Optimization Methods and Applications. Nonconvex Optimization and Its Applications, vol 82. Springer, Boston, MA. https://doi.org/10.1007/0-387-29550-X_4. Available at https://www.researchgate.net/publication/226808473_A_Unified_Framework_for_Modeling_and_Solving_Combinatorial_Optimization_Problems_A_Tutorial.

참고 항목

solve | qubo