やること
2024/09/07追記
試験問題の役割を終えたため解答の一例を公開しました。
QUBOアニーリングのDiscordコミュニティで面白い問題が共有されました。アニーリングでピタゴラス数を見つける、というものです。
ピタゴラス数は、x2 + y2 = z2 を満たす自然数 (x, y, z) の組です。
ピタゴラス数（英: Pythagorean triple）とは、a2 + b2 = c2 を満たす3つの自然数の組 (a, b, c) のことである。これはピタゴラスの定理に由来しており（中略）最小のピタゴラス数は (3, 4, 5) である。
Wikipedia「ピタゴラス数」
「qubomaster」認定試験にちょうど良いので、実力テスト２として調整しました。腕に自信がある方は挑戦してみてください。認定試験として挑戦する場合は別途その指示に従ってください。
TYTANについて
「TYTAN」はOSSのアニーリングSDKです。
筆者はチュートリアルコースを担当しています。
discordコミュニティもあるので気軽に質問できます。どなたでも参加できます → https://discord.gg/qT5etstPW8
チュートリアルを終えて試験に合格するとblueqat社が認定する「qubomaster」という資格が与えられます。qubomasterになると（blueqatサイト上で）認定バッジが付与され、有償業務の受託可能者リストに入ります。
おさらい
QUBOで設定できる条件式についてはこちらの記事にまとめてあります。暗記する必要はありませんが概要は把握しておくと良さそうです。
これまでのQUBOアニーリング系の記事はサイドバーの「カテゴリ一覧」→「量子コンピュータ」から絞れます。
実力テスト問題２
ピタゴラス数は、x2 + y2 = z2 を満たす自然数 (x, y, z) の組です。参考→ Wikipedia「ピタゴラス数」
(x, y, z) ともに20未満のピタゴラス数（原始ピタゴラス数）をすべて求めてください。
想定される解は
- 原始ピタゴラス数：(3, 4, 5), (5, 12, 13), (8, 15, 17)
- それらの倍数：(6, 8, 10), (9, 12, 15)
の５組で、少なくとも原始ピタゴラス数の３組が見つかれば良いこととします。また、xとyは入れ変わっても差し支えありません。
提出方法、注意事項など
解答は、そのまま実行するだけのpythonコードを「.py」または「.ipynb」のファイル形式で以下フォームから提出してください。すぐに自動返信メールが届きます。
※100KBまでの.py, .ipynbファイルのみ受け付けます
※受付完了メールが自動送信されます
▼注意事項
- テキスト欄やコメントアウトにより最低限の説明や思考過程を含めてください
- その際、チュートリアルの「おすすめコース」のどれと関連があるかにも触れてください
- 説明のための図は必ずしも必要ありません
- アニーリングのソルバーには必ずTYTANパッケージを使用してください
- 必ずしも1回の実行で正解が得られる必要はなく、正解が得られることが期待できるコードであれば問題ありません
▼合格条件
- QUBO条件式が妥当であること
- 説明や思考過程が妥当であること
- 十分な可読性のPythonコードであること
- チュートリアル「おすすめコース」を把握していること
解答の一例（2024/09/07追記）
この問題のポイントは、x, y, z を直接量子ビットで（二進数）表現すると制約条件が４次式になってしまいQUBOの範囲に収まらないことである。そこで妥協策として、整数を二乗した数を用意しておきワンホットで一つだけ選択する方法を用いる。
また、探索範囲を狭める工夫として「xは1以上の奇数」、「yは2以上の偶数」、「zは1以上の奇数」に限定してみる。これは比較的容易に証明できる原始ピタゴラス数の要件である。（もっと狭めることもできる）
ただしこれはあくまで探索範囲を狭める工夫であり、原始ピタゴラス数を生成するための式（m2 − n2, 2mn, m2 + n2が登場するやつ）を使用してしまうのは反則である。（問題に書いとけよ）
pip install tytanfrom tytan import *
import numpy as np
#一乗の数
x = np.arange(1, 20, 2) #1以上の奇数
y = np.arange(2, 20, 2) #2以上の偶数
z = np.arange(1, 20, 2) #1以上の奇数
#二乗の数
xx = x**2
yy = y**2
zz = z**2
#量子ビット
qx = symbols_list(len(xx), 'qx{}')
qy = symbols_list(len(yy), 'qy{}')
qz = symbols_list(len(zz), 'qz{}')
#ワンホット
Hconst = 0
Hconst += (sum(qx) - 1)**2
Hconst += (sum(qy) - 1)**2
Hconst += (sum(qz) - 1)**2
#ピタゴラス条件
Hcost = 0
Hconst += (sum(xx * qx) + sum(yy * qy) - sum(zz * qz))**2
#合体
H = Hconst + 0.01*Hconst
#コンパイル
qubo, offset = Compile(H).get_qubo()
print(f'offset = {offset}')
#サンプラー選択
solver = sampler.ArminSampler()
#サンプリング
result = solver.run(qubo, shots=10000)
#上位5件
for r in result[:5]:
print(f'Energy {r[1]}, Occurrence {r[2]}')
#確認
qx, _ = Auto_array(r[0]).get_ndarray('qx{}')
qy, _ = Auto_array(r[0]).get_ndarray('qy{}')
qz, _ = Auto_array(r[0]).get_ndarray('qz{}')
print(f'x = {x[np.argmax(qx)]}')
print(f'y = {y[np.argmax(qy)]}')
print(f'z = {z[np.argmax(qz)]}')
if sum(qx) != 1:
print("WARNING: x is not One-hot.", qx)
if sum(qy) != 1:
print("WARNING: y is not One-hot.", qy)
if sum(qz) != 1:
print("WARNING: z is not One-hot.", qz)offset = 3.0300000000000002
MODE: GPU
DEVICE: cuda:0
Energy -3.03125, Occurrence 6
x = 9
y = 12
z = 15
Energy -3.03125, Occurrence 30
x = 15
y = 8
z = 17
Energy -3.030029296875, Occurrence 5
x = 3
y = 4
z = 5
Energy -3.029296875, Occurrence 7
x = 5
y = 12
z = 13
Energy -2.04296875, Occurrence 6
x = 15
y = 6
z = 19
WARNING: y is not One-hot. [0 0 1 0 1 0 0 0 0](3, 4, 5), (5, 12, 13), (8, 15, 17) の原始３種が得られた。
＜補足＞
TYTANがHOBO対応したことにより3次以上の式が扱えるようになった。HOBOでは今回のようにワンホットにする必要がなくシンプルに記述できる。今度解説を出します。
