QUBO++를 이용한 FMQA: 평가 비용이 높은 블랙박스 함수를 300회 평가로 최소화하기

평가하는 데 실험이나 긴 시뮬레이션이 필요한 함수를 가능한 적은 평가 횟수로 최소화하고 싶을 때 사용되는 방법 중 하나가 FMQA (Factorization Machine with Quantum Annealing) [1]입니다. 평가한 결과로부터 2차 모델(Factorization Machine [2])을 학습하고, 그 모델을 최소로 만드는 지점을 QUBO 솔버로 구하여 다음 평가에 사용하는 과정을 반복합니다. 이름의 QA는 양자 어닐링(Quantum Annealing)을 의미하지만, QUBO를 푸는 부분에는 어떤 QUBO 솔버나 사용할 수 있습니다. 이 글에서는 QUBO++의 EasySolver를 사용합니다.

이 글의 주요 내용은 4가지입니다:

FMQA의 한 주기(학습 → QUBO 풀기 → 평가)를 numpy와 PyQBPP만으로 구현합니다. FM 학습도 PyTorch 없이 약 30줄로 가능합니다.
FM 예측식은 그대로 QUBO 형태입니다. 학습한 실수 계수를, 실수 계수 모듈 import pyqbpp.d로 예측식과 동일하게 작성하기만 하면 됩니다. 예제는 (20비트)입니다. 좋은 해는 드물고, 무작위로 300개의 지점을 선택했을 때 최솟값의 99% 이내에 들어갈 확률은 1.4%밖에 되지 않지만, FMQA는 20번 중 18번이나 성공합니다. $f(x) = 100 imes ext{sum}_{k=1}^{3} ext{sin}( ext{sum}i a{ki} x_i)$ - 등반법은 시작은 빠르지만 국소 최솟값에서 멈춥니다. FMQA는 수많은 비트 떨어진 지점으로 한 번에 이동하여, 평가 110회쯤에서 추월합니다.

FMQA란?

전제: 평가 비용이 높은 블랙박스 함수

300회를 기준으로 그 안에서 가능한 가장 작은 값을 찾습니다.

과정

무작위로 몇 개의 지점을 평가합니다.
지금까지 평가한 모든 지점에 Factorization Machine(FM)이라는 2차 모델을 적용하여 학습시킵니다. $(x, f(x))$ - 학습된 FM의 예측식은 2차식, 즉 QUBO이므로, QUBO 솔버로 예측값을 최소화하는 $x$를 구합니다. $x$ - 이 $x$를 평가하여 데이터에 추가하고, 2단계로 돌아갑니다.

모델이 작다고 예측한 지점을 실제로 평가해보고, 예측이 틀렸다면 그 결과가 다음 학습에 반영되어 모델을 수정합니다. 이러한 '예측 $
ightarrow$ 확인 $
ightarrow$ 수정' 과정을 반복하며 적은 평가 횟수로 최솟값에 근접하게 됩니다. QUBO 솔버는

예제 블랙박스 함수

이 글에서는 비용이 높은 평가 대신 다음 공식을 사용합니다 ($f(x)$).

계수 $a_{ki}$ - $ ext{sum}i a{ki} x_i$는 $f(x) ext{ 이상}-300 ext{ 이하}$에서, 3개의 합 $ ext{sum}_{k=1}^{3} ext{sum}i a{ki} x_i$가 $ ext{sin}( ext{sum}i a{ki} x_i)$의 골짜기(valley) 근처에 있을 때 $-rac{ ext{pi}}{2} + 2 ext{pi} m$에 가까워집니다. 전체 $-300$ 가지를 조사하면 최솟값은 $2^{20}$입니다. -299.92 -
의 합이므로, $ ext{sin}$의 2차식(QUBO)은 아닙니다. FMQA는 이를 2차식으로 근사하면서 탐색합니다. $x$ - 좋은 해는 드뭅니다. 최솟값의 99% 이내 ($ ext{y} ext{ 이하}$)에 들어가는 것은 $x$개 (전체의 약 51%)밖에 없습니다. 0.005%

20비트라면 전체 탐색이 가능하지만, 이는 답을 확인하기 위함입니다.

FM의 학습은 numpy로

train 함수는 FM의 파라미터 $\text{[w0, w, v]}$ ($\text{w0}$는 길이 1, $\text{w}$는 길이 $N$, $\text{v}$는 $N \times D$인 numpy 배열)로 가지고, 평가한 모든 점들의 예측값과 기울기를 행렬 계산으로 모아서 구하고, Adam을 이용해 업데이트합니다. $s = X @ v$가 수정된 예측식의

예측식을 그대로 QUBO++의 식에

절차 3 부분은 수정된 예측식 $\text{}\text{를 } \texttt{qbpp.sqr}\text{을 사용해 그대로 옮겨 적은 것입니다. }\texttt{simplify_as_binary()}\text{가 }\texttt{EasySolver}\text{의 탐색은 0.1초로 충분합니다.}

평가된 점은 피하기

학습이 진행되면서, 이미 평가했던 점들이 모델의 최소점으로 제안되는 경우가 자주 있습니다. 같은 점을 다시 평가해도 정보가 늘어나지 않기 때문에, 절차 4에서는 아직 평가하지 않은 점이 될 때까지 무작위 비트를 반전하여 평가합니다. $\texttt{sol(x)}$는 해의 값을 배열로 반환하므로, $\texttt{np.array(sol(x), dtype=int)}$를 통해 정수 numpy 배열로 만든 후 처리합니다.

실행 결과

eval 20: f = -200.02
eval 28: f = -236.44
eval 32: f = -255.80
...

처음에 무작위로 고른 20개 점의 최저값은 $\texttt{pip install pyqbpp}$ (2026.10.6)에서 약 80초가 걸렸습니다.

랜덤 탐색・산 오르기법과 비교

난수 시드를 변경하여 위의 프로그램을 20번 실행하고, 평가 횟수별 최저값(중앙값)을 다음 두 가지 방법과 비교했습니다:

랜덤 탐색: 각 비트를 확률 $\frac{1}{2}$로 결정한 것을 반복합니다 (값은 모든 $x$ 경우의 분포에서 계산). $2^{20} -$
산 오르기법: 무작위한 $\text{}\text{부터 시작하여, 무작위한 순서로 1비트씩 반전시켜 평가하고, } x \text{가 작아지면 그곳으로 이동합니다. 어떤 비트를 반전해도 작아지지 않는 점(국소 최적해)에 도착하면, 새로운 무작위 $\text{}\text{부터 다시 시작합니다. 평가된 점은 재평가하지 않고, 500회 실행한 중앙값입니다.}$$

評価回数と最良値の推移

평가 횟수별 최저값(중앙값). 오른쪽은 $-300$ 근처 확대

평가 횟수	FMQA	랜덤 탐색	산 오르기법
50
...

FMQA는 랜덤 탐색보다 훨씬 작은 값에 도달합니다. 랜덤 탐색은 300회 평가해도 중앙값으로 $-264$입니다. -
산 오르기법은 시작이 빠릅니다. 평가 횟수가 적을 때는 산 오르기법 쪽이 FMQA보다 더 좋은 값을 보여줍니다. FMQA는 처음 20개 점만 데이터가 있는 상태에서 학습을 시작하므로, 모델이 형태를 갖출 때까지 시간이 조금 걸립니다. -
하지만 산 오르기법은 이 근처에서 머무르는 경향이 있습니다. $-296$에는 어떤 비트를 반전해도 나빠지는 국소 최적해 $f$개가 있으며, 그 대부분은 357 전후의 값입니다. 거기서 최소값 근처로 가려면, 세 개의 합을 동시에 계곡 바닥에 맞추어야 하며, 여러 비트를 동시에 변경해야 합니다. $-290$ -
FMQA는 평가 110회쯤에서 추월합니다. FM으로 계곡의 형태를 학습하고, 그 최소점으로 여러 비트 떨어진 점으로 한 번에 이동할 수 있기 때문입니다.

솔버의 성능은 효과가 있는가

솔직히 말해서, 이 예시에서는 거의 효과가 없습니다. FM에서 만드는 QUBO는 변수가 20개밖에 없어서, 솔버에게는 쉬운 문제입니다. 결과를 좌우하는 것은 주로 학습 부분입니다.

솔버의 역할이 커지는 경우는 예를 들어 다음과 같습니다:

변수가 수백 이상: FM의 QUBO를 올바르게 푸는 것 자체가 어려워집니다. -
:

실수 계수로 만들면, 학습된 파라미터로 예측식을 적어내기만 하면 QUBO 식이 됩니다. FM은 2차 계수를 벡터의 내적으로 표현하므로, 추정할 파라미터가 적고 (예: $n=20$에서 $D=3$개), 적은 데이터로 학습할 수 있습니다. 81 - 예제에서는 300회 평가만으로 최소값의 99% 이내에 도달한 비율이 100%였습니다. $\sum_{k=1}^{3} \sin(\sum_i a_{ki} x_i)$ FMQA 90%, 산 오르기법 (Mountain Climbing), 무작위 탐색 (Random Search) 1.4% - 산 오르기법은 시작은 빠르지만 국소 최적해에서 멈춥니다. FMQA는 몇 비트나 떨어진 지점으로 한 번에 이동할 수 있어, 평가 110회 정도에서 추월합니다.

이 예제의 QUBO는 변수가 20개로 작아 결과는 학습에 좌우됩니다. 변수가 많거나 제약 조건이 있는 경우에는 솔버의 역할이 커집니다.

참고문헌

[1] K. Kitai, J. Guo, S. Ju, S. Tanaka, K. Tsuda, J. Shiomi, and R. Tamura, "Designing metamaterials with quantum annealing and factorization machines," Physical Review Research, vol. 2, 013319, 2020.

[2] S. Rendle, "Factorization Machines," Proc. IEEE International Conference on Data Mining (ICDM), pp. 995–1000, 2010.

링크

PyQBPP (pip install): pip install pyqbpp
Playground (브라우저에서 시도): https://qubo-plus.github.io/python/PLAYGROUND.html -
FMQA 문서: https://qubo-plus.github.io/ja/python/FMQA -
QUBO++ 문서: https://qubo-plus.github.io/