量子アニーリングによる 4 クウィーンのプログラムを書いてみた． もうすこしで N クウィーンへの拡張ができるが，いまのところは N = 4 に固定されている．
「カナダからのブログ」にもほぼおなじ内容を書いたが，4 クウィーンをとく量子アニーリングによるプログラムをここにものせておく． N クウィーンでもなく有名な 8 クウィーンでもなくて 4 クウィーンなのは，まず最低限の量子ビットでとける問題をためしたかったということだ． N クウィーンを量子コンピュータで解こうとした研究はいろいろあることがわかったが，このプログラムに一番ちかいのは [T-Wave] だ． 量子ゲートで 4 クウィーンを解く例としては [Jha] がある．
プログラムはここにある． 実行の様子は下記のとおりだ．
$ python3 Python 3.8.0 (v3.8.0:fa919fdf25, Oct 14 2019, 10:23:27) [Clang 6.0 (clang-600.0.57)] on darwin Type "help", "copyright", "credits" or "license" for more information. >>> from QuantumQueensE import queens, pprint >>> pprint(queens.sa()) .Q.. ...Q Q... ..Q. >>> exit()
4 × 4 の「チェスボード」の各ますを QUBO (16 行 16 列) の各行・各列に対応させる． とりうる値はクウィーンがそこにいれば 1，いなければ 0 だ． QUBO は 3 種類の項からなっている． 第 1 は縦・横の和 (Q1 + Q2 + Q3 + Q4 とする) に関するものだ． これらの和はかならず 1 になるので，(Q1 + Q2 + Q3 + Q4 − 1)2 とする． 第 2 は対角線方向の和 (Q1 + Q2 + Q3 + Q4, Q1 + Q2 + Q3, または Q1 + Q2) で，和は 0 または 1 なので，(Q1 + ... + Qn − 0.5)2 とする． 第 3 はクウィーンの数を 4 にするためのもので，(Q1 + Q2 + Q3 + Q4 − 4)2 だ． とりあえずこれらの項の係数は 1 にしている．第 3 の項はなくても 4 クウィーンの場合は解をもとめることができる．
queens.Ts などのパラメタや上記の係数の値をどうするのがよいかは，まだわかっていない． 4 クウィーンのばあいには，すくなくとも既定値で解をもとめることができる． しかし，シミュレータ (wildqat) で実行するかぎりは 4 クウィーンでも解をもとめるのにすこし時間がかかる． N クウィーンの N をおおきくするとかなり時間がかかりそうだ． N > 4 への拡張はもうすこしなのだが，まだ現在は N = 4 に固定されている． いまのところは N = 4 なので D-Wave では実行していない．
P.S. このプログラムのひとつの問題は探索空間が非常にひろいことだ． クウィーンの数 (4) もかわりうるし，行内や列内のクウィーンの数 (1) も固定されていない． 記号的なプログラムではこれらは通常は固定されているので，効率よく探索することができる．
参考文献
[T-Wave] T-QARD Crews, N-クイーン問題 を D-Waveマシンで解く
[Jha] Rounak Jha, Debaiudh Das, Avinash Dash, Sandhya Jayaraman, Bikash K. Behera, Prasanta K. Panigrahi, A Novel Quantum N-Queens Solver Algorithm and its Simulation and Application to Satellite Communication Using IBM Quantum Experience
[Torggler] Valentin Torggler, Philipp Aumann, Helmut Ritsch, and Wolfgang Lechner, A Quantum N-Queens Solver, Quantum Journal, accepted.
