ピタゴラス関数をHOBOとQUBOで解いて比べてみた！

今回のブログでは、ピタゴラス関数を解く問題に対して、HOBO (Higher-Order Binary Optimization) を使って効率的に解決する方法をご紹介します！従来のQUBO Solverに比べ、圧倒的に量子ビット数を削減したことがポイントです。

1. 問題背景：ピタゴラス関数とは？

ピタゴラス関数は、以下の式で表される関係です：

x^2 + y^2 = z^2

この式を満たす整数解 (x, y, z)を見つけることが目的です。例えば、(3,4,5)や(6, 8, 10)などが有名ですね。

2. QUBOでの解法

従来のQUBOを用いた場合、解の候補が増えると共に、量子ビットの数が膨大になります。例えば、x, y, z の範囲を2^4までとすると、各変数に対して16個の量子ビットが必要です。

コード例

以下はQUBO形式で定式化した例です：

from tytan import *

Power = 4

x = np.arange(1, 1 + 2**Power)

y = np.arange(1, 1 + 2**Power)

z = np.arange(1, 1 + 2**Power)

x2 = x**2

y2 = y**2

z2 = z**2


# 量子ビットを定義

qx = symbols_list(len(x2), 'qx{}')

qy = symbols_list(len(y2), 'qy{}')

qz = symbols_list(len(z2), 'qz{}')


# 一つの変数に対して1つのビットのみが1になる制約条件

H += (sum(qx) - 1)**2

H += (sum(qy) - 1)**2

H += (sum(qz) - 1)**2


# ピタゴラス条件を表現するコスト条件

H += 0.01 * (sum(x2*qx) + sum(y2*qy) - sum(z2*qz))**2


# QUBO行列をコンパイル

qubo, offset = Compile(H).get_qubo()

print(f'offset\n{offset}')


# サンプラーを選択

solver = sampler.AnnealingSampler()


# サンプリング

result = solver.run(qubo, shots=10000)


# 上位10件の結果を表示

ans = []

for r in result[:10]:

    print(f'Energy {r[1]}, Occurrence {r[2]}')


# One-hot制約を確認

xs, xsubs = Auto_array(r[0]).get_ndarray('qx{}')

ys, ysubs = Auto_array(r[0]).get_ndarray('qy{}')

zs, zsubs = Auto_array(r[0]).get_ndarray('qz{}')

if sum(xs) != 1:

    print('ERR: x がOne-hotになっていません.')

    continue

if sum(ys) != 1:

    print('ERR: y がOne-hotになっていません.')

    continue

if sum(zs) != 1:

    print('ERR: z がOne-hotになっていません.')

    continue


# 最適解を出力

print('x = ', x[np.argmax(xs)])

print('y = ', y[np.argmax(ys)])

print('z = ', z[np.argmax(zs)])

この方法では、各変数に16個の量子ビットを割り当てる必要があり、計48個の量子ビットを使用します。

3. HOBOでの解法

一方、HOBOでは、変数をバイナリ形式 (2進数) で表現することで、量子ビット数を劇的に削減します。4ビットのバイナリ変数で x, y, zを表現し、最適化問題を直接HOBO形式で定式化します。

コード例

from tytan import *

# 量子ビットを定義

qx = symbols_list(4, 'qx{}')

qy = symbols_list(4, 'qy{}')

qz = symbols_list(4, 'qz{}')


# x, y, zを2進数表現

x = 1 + 1*qx[0] + 2*qx[1] + 4*qx[2] + 8*qx[3]

y = 1 + 1*qy[0] + 2*qy[1] + 4*qy[2] + 8*qy[3]

z = 1 + 1*qz[0] + 2*qz[1] + 4*qz[2] + 8*qz[3]


#　ピタゴラス条件を表現する制約条件

H = (x**2 + y**2 - z**2)**2


# 最適化

solver = sampler.MIKASampler()

result = solver.run(Compile(H).get_hobo()[0], shots=10000)

この方法では、各変数にlog2(16)、つまり4個の量子ビットを割り当てる必要があり、計12個の量子ビットを使用します。

4. HOBOの結果

実行環境

• MODE: GPU

• DEVICE: cuda:0

結果

HOBOのサンプリング結果は次の通りです：

エネルギー	x	y	z	出力回数
-1.0	8	6	10	1234
-1.0	12	5	13	929
-1.0	12	9	15	775
-1.0	4	3	5	983

注目ポイント：

• x = 4, y = 3, z = 5 は典型的なピタゴラス数です。

• 量子ビット数が劇的に削減されながらも、正しい解を効率的に求めることができました！

5. QUBO vs HOBO: 量子ビットの比較

方法	QUBO	HOBO
変数の表現	ワンホット	2進数
量子ビット	48	12
解の効率	非効率	効率的

HOBOでは、QUBOの1/4の量子ビット数で解が得られました！

6. まとめ

今回は、ピタゴラス関数をHOBOを使って効率的に解く方法をご紹介しました。従来のQUBO Solverと比較して、HOBOでは大幅に量子ビットを削減しつつ、正しい解を求めることができます。

この発見は以下で詳しく説明していますので参照してください： https://arxiv.org/abs/2408.11076

HOBOは複雑な最適化問題を効率的に解く強力な手法です。これを活用すれば、さまざまな最適化問題での計算効率を劇的に向上させることができるでしょう！

次回のブログでは、さらに複雑な問題やHOBOの応用事例について解説しますので、お楽しみに！