@yuichirominato 2018.12.25更新 691views

【大規模問題分割】D-Waveのqbsolvのドキュメント全和訳

D-Wave Hybrid qbsolv 量子アニーリング

はじめに

量子アニーリングを使ってイジングやQUBOの大規模問題を解きたい場合には、問題分割手法を使います。ここでは、カナダのD-Wave Systems Inc.のqbsolvという問題分割フレームワークの説明を和訳します。元の文章は、

https://docs.ocean.dwavesys.com/projects/qbsolv/en/latest/

こちらにあります。

qbsolv

https://docs.ocean.dwavesys.com/projects/qbsolv/en/latest/

qbsolvは大規模な二次制約なし二値最適化(QUBO)問題の最小値を求める分解ソルバーです。タブーアルゴリズムを実行している古典的なソルバーを使用して問題を解きます。 qbsolvはD-Wave社のマシンををソルバーとして設定することもできます。

注)D-Wave社のマシンへの接続には別途の設定が必要です。

例題

from dwave_qbsolv import QBSolv
Q = {(0, 0): 1, (1, 1): 1, (0, 1): 1}
response = QBSolv().sample_qubo(Q)
print("samples=" + str(list(response.samples())))
print("energies=" + str(list(response.data_vectors['energy'])))

目次

  • 導入
  • 参考資料
  • ライセンス
  • qbsolvに貢献する

導入

https://docs.ocean.dwavesys.com/projects/qbsolv/en/latest/intro.html

分割統治法および動的計画法アルゴリズムは、コンピュータサイエンスにおいて多数の変数を伴う問題に関して豊富な歴史を持っています。量子コンピュータから恩恵を受けることができる多くの困難な問題は、QPUに直接問題をマッピングするには大きすぎることです。利用可能な量子ビット数よりも多くの変数を持つ問題を解くために、問題を部分問題に分割し、部分問題を解き、そして部分問題解から元の問題に対する答えを再構築します。

qbsolvはそのような分解ソルバーの1つで、 2つのインタフェースがあります。

・コマンドラインインターフェイス(CLI)
タブーアルゴリズムは、それぞれ多数のの部分問題に分割された問題に対して実行されます。

・Pythonインターフェイス
Pythonインターフェースは、qbsolvのC言語向けのQBSolvクラスラッパーを提供します。デフォルトのタブーアルゴリズムの代わりにdimod samplerを使うことができます。

アルゴリズムと実装の説明については、「ハイブリッド古典/量子実行のための分割最適化問題」を参照してください。
こちら

タブーサーチアルゴリズムの説明については、タブーサーチを参照してください。
こちら

例題

この例では、qbsolvのメインループで実行されるタブーサーチに組み込まれる500変数のQUBOの30変数のサブ問題をdwave-nealサンプラーで解いています。

>>> from dwave_qbsolv import QBSolv
>>> import neal
>>> import itertools
>>> import random
...
>>> qubo_size = 500
>>> subqubo_size = 30
>>> Q = {t: random.uniform(-1, 1) for t in itertools.product(range(qubo_size), repeat=2)}
>>> sampler = neal.SimulatedAnnealingSampler()
>>> response = QBSolv().sample_qubo(Q, solver=sampler, solver_limit=subqubo_size)
>>> print("energies=" + str(list(response.data_vectors['energy'])))   
energies=[-2800.794817495185]

参照資料

https://docs.ocean.dwavesys.com/projects/qbsolv/en/latest/source/index.html

  • コマンドラインインターフェイス
  • Pythonインターフェイス
  • qbsolv入力ファイルフォーマット

コマンドラインインターフェイス

https://docs.ocean.dwavesys.com/projects/qbsolv/en/latest/source/usage.html
コマンドラインからqbsolvを実行するには、次のコマンドとそのオプションを使用します。


qbsolv -i infile [-o outfile] [-m] [-T] [-n] [-S SubMatrix] [-w]
    [-h] [-a algorithm] [-v verbosityLevel] [-V] [-q] [-t seconds]

説明

qbsolvは、ファイルにある二次制約付き二次計画(QUBO)問題を実行します。 QUBOで表される目的関数の値を最小化する(またはオプションで最大化する)ビットの計算結果の値をベクトルの形で返します。問題はQUBO(5)ファイルフォーマットで表されます。

QUBO入力問題は、グラフサイズやサンプラーの接続性、例えばD-Waveシステムに制限されません。

オプションは下記の通りとなっています。


-i infile
    QUBOを入力するためのファイル名です。必須項目です。
-o outfile
    出力ファイル名を決めるときのオプションです。指定のない場合には通常のファイル名を出力します。
-a algorithm
    外側のループを回すためのアルゴリズムのオプションです。初期値は "o"。
        "o"はオリジナルのqbsolvメソッドで、サブのmatrixはエネルギーの変化によって生成されます。
    "p"はパス再接続で、サブのmatrixは問題の種類によって決まります。
-m
    最小値の代わりに最大値を求める場合に使用
-T target
    目的とするコスト関数の値です。もしそれが見つかったら実行を止めます。
-t timeout
    時間制限値です。もしCPUの実行時間がこれと同じか超えると実行が停止します。このオプションはメインのループが終わってから確認されます。また、その他の停止オプションであるターゲットやリピートはこのタイムアウトよりも先に実行されます。デフォルト値は2592000.0.です。
-n repeats
    アルゴリズムのメインループの回数で、この値の前に最適解が見つかった場合にはループがとあります。初期値は50。
-S subproblemSize
    QUBOを分解したあとの問題の最適なサイズを指定します。基本的にはD-Wave側で設定したファイルを使って決めますが、環境が構築されていない場合には、タブーサーチを使って47という値を使います。もし値が設定されている場合にはタブーサーチを使って指定の値を使用します。
-w
    QUBOmatrixと結果がcsv形式で保存されます。
-h
    プログラムを実行せずにヘルプファイルやメッセージを表示します。
-v verbosityLevel
    出力ファイルの詳細度を設定します。初期値の0は答えの量子ビット数、その答え、エネルギー値を計算します。レベル1の場合には、それらと同じ情報を複数の解に対して提供します。レベル2以上は4まで各ステップに関してより詳細な情報を返却します。
-V
    実行せずにqbsolvのバージョンを表示します。
-q
    QUBOファイルを表示します。
-r seed
    乱数生成器のシードをリセットします。

Pythonインターフェイス

https://docs.ocean.dwavesys.com/projects/qbsolv/en/latest/source/python.html

クラス
classQBSolv

python用のqbsolv C言語パッケージをラップします。

この例では、タブーサーチアルゴリズムを使用して小さなイジング問題を解きます。

>>> h = {0: -1, 1: 1, 2: -1}
>>> J = {(0, 1): -1, (1, 2): -1}
>>> response = QBSolv().sample_ising(h, J)
>>> list(response.samples())
'[{0: 1, 1: 1, 2: 1}]'
>>> list(response.energies())
'[1.0]'

メソッド

QBSolv.sample(bqm, **kwargs)qbsolvを使って、QUBOで指定された局所状態のサンプリングを行います。

dwave_qbsolv.QBSolv.sample

https://docs.ocean.dwavesys.com/projects/qbsolv/en/latest/source/generated/dwave_qbsolv.QBSolv.sample.html

QBSolv.sample(bqm**kwargs)

qbsolvを使って、QUBOで指定された局所状態のサンプリングを行います。

注)このクラスのすべてのインスタンスで共有されているqbsolvライブラリは再入可能ではなく、スレッドセーフでもありません。それが解決されるまで、GILはこのメソッドによって解放されるべきではありません。

注)このライブラリのデフォルトビルドはdwライブラリを持っていません。 solver = ‘dw’を使用するには、このモジュールはそのライブラリのソースからビルドされなければなりません。

solverのパラメータは下記の通りです

  • 文字列 ‘tabu’(デフォルト):副問題はtabuの内部呼び出しによって呼び出されます。
  • 文字列 ‘dw’:副問題はdwライブラリに与えられます。
  • dimodサンプラーのインスタンス。 sample_quboメソッドが呼び出されます。
  • シグネチャ(qubo:dict、current_best:dict)を持ち、新しいソリューションを含む結果リスト/辞書を返し、呼び出し可能です。

パラメータ

  • Q (dict) – QUBOを定義する辞書で、 {(u, v): bias} の形式で書かれます。
  • num_repeats (int, optional) – 何回メインループを回すのかを決める値で、初期値は50です。
  • seed (int, optional) – 乱数生成モジュールで生成する乱数のシードです。
  • algorithm (int, optional) – 使用するアルゴリズム。初期値はENERGY_IMPACT. アルゴリズムの番号はENERGY_IMPACT と SOLUTION_DIVERSITYのモジュールから読み込むことができます。
  • verbosity (int, optional) – qbsolvの内部プロセスの記述を詳細度に合わせて出力します。
  • timeout (float, optional) – タイムアウトの値です。初期値は2592000です。
  • solver – サンプリング方法。上記を参照してください。
  • solver_limit (int, optional) – サブ問題のサイズ上限値。
  • target (float, optional) – ターゲットとなるコスト値。
  • find_max (bool, optional) – 最大値を探す時に使用。


>>> Q = {(0, 0): 1, (1, 1): 1, (0, 1): 1}
>>> response = QBSolv().sample_qubo(Q)
>>> list(response.samples())
'[{0: 0, 1: 0}]'
>>> list(response.energies())
'[0.0]'

qbsolv入力ファイル形式

https://docs.ocean.dwavesys.com/projects/qbsolv/en/latest/source/format.html

.quboファイルは二次制約なし二次計画問題のファイルを含みます。これは4種類の行を含むASCIIファイルです。

  • “c”で定義されたコメントは様々なところに出現しますが、同時に読み込みは無視されます。
  • “p”はファイルの最初にコメントなしで書かれており、6つの必須項目がスペースによって分割されて記述されています。下記の通りです。
p   qubo  topology   maxNodes   nNodes   nCouplers 

詳細は、

p          番兵

qubo ファイルタイプ識別子

topology 問題のトポロジーと問題タイプを識別します。"0"もしくは"unconstrained"の場合には、制約なし問題で、将来的には"chimera128"や"chimera512"が実装予定です。

maxNodes トポロジー内のノード数です。

nNodes 問題内部にあるノード数でnNodes <= maxNodesである必要があります。各ノードは特定の通し番号をもち、0からmaxNodes-1までの値を取ります。重複した値はエラーとなり、順序は問わず、連続でなくても大丈夫です。

nCouplers 問題内のカプラーの数です。それぞれのカプラーは2ノード間の特定の接続を持ちます。最大のカプラー数はnNodesの二乗です。重複はエラーになります。
  • nNodes 各々は空白で区切られた3つの数字からなります。最初の2つは整数でノードの番号が繰り返されます。ノード番号は0からmaxNodes-1までの番号の間です。三番目はノードの重みに対応しています。重みは整数もしくは浮動小数点で、0か正負の値を取ります。
  • nCouplers 各々は空白で区切られた3つの数字からなります。最初の2つはそれぞれ異なる整数でノードの番号が指定されiとjが割り当てられ、i<jを満たします。最初の2つは0からmaxNodes-1までの番号を取り、三番目の数字は、カプラーの強度を表します。強度は整数もしくは不動小数点で、0ではない正か負の値を取ります。各々のノードは少なくとも1つのコネクションを持ちます。

下記は4ノード、6エッジのQUBOファイルの例です。この例はQUBOの基本要素を示すための例題ファイルで実際の問題を反映しているわけではありません。


| <--- column 1
c
c  This is a sample .qubo file
c  with 4 nodes and 6 couplers
c
p  qubo  0  4  4  6
c ------------------
0  0   3.4
1  1   4.5
2  2   2.1
3  3   -2.4
c ------------------
0  1   2.2
0  2   3.4
1  2   4.5
0  3   -2
1  3   4.5678
2  3   -3.22

インストール

Python

PyPIから入手できるほか、ソース配布からもインストールできます。

pip install dwave-qbsolv

セットアップツールからもインストールできます。

pip install -r python/requirements.txt
pip install cython==0.27
python setup.py install

C

Cライブラリをビルドするには、cmakeを使ってシステム用のビルドコマンドを生成します。 Linuxでは、コマンドは次のようになります。

mkdir build; cd build
cmake ..
make

コマンドラインインターフェースを作成するには、cmakeオプションのQBSOLV_BUILD_CMDをオンにします。これを行うためのcmakeのコマンドラインオプションは-DQBSOLV_BUILD_CMD = ONです。テストを構築するには、cmakeオプションQBSOLV_BUILD_TESTSをオンにします。これを行うためのcmakeのコマンドラインオプションは-DQBSOLV_BUILD_TESTS = ONです。

ライセンス(こちらは英語のままで)

https://docs.ocean.dwavesys.com/projects/qbsolv/en/latest/license.html

Apache License

Version 2.0, January 2004

http://www.apache.org/licenses/

TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION

  1. Definitions.“License” shall mean the terms and conditions for use, reproduction, and distribution as defined by Sections 1 through 9 of this document.“Licensor” shall mean the copyright owner or entity authorized by the copyright owner that is granting the License.“Legal Entity” shall mean the union of the acting entity and all other entities that control, are controlled by, or are under common control with that entity. For the purposes of this definition, “control” means (i) the power, direct or indirect, to cause the direction or management of such entity, whether by contract or otherwise, or (ii) ownership of fifty percent (50%) or more of the outstanding shares, or (iii) beneficial ownership of such entity.“You” (or “Your”) shall mean an individual or Legal Entity exercising permissions granted by this License.“Source” form shall mean the preferred form for making modifications, including but not limited to software source code, documentation source, and configuration files.“Object” form shall mean any form resulting from mechanical transformation or translation of a Source form, including but not limited to compiled object code, generated documentation, and conversions to other media types.“Work” shall mean the work of authorship, whether in Source or Object form, made available under the License, as indicated by a copyright notice that is included in or attached to the work (an example is provided in the Appendix below).“Derivative Works” shall mean any work, whether in Source or Object form, that is based on (or derived from) the Work and for which the editorial revisions, annotations, elaborations, or other modifications represent, as a whole, an original work of authorship. For the purposes of this License, Derivative Works shall not include works that remain separable from, or merely link (or bind by name) to the interfaces of, the Work and Derivative Works thereof.“Contribution” shall mean any work of authorship, including the original version of the Work and any modifications or additions to that Work or Derivative Works thereof, that is intentionally submitted to Licensor for inclusion in the Work by the copyright owner or by an individual or Legal Entity authorized to submit on behalf of the copyright owner. For the purposes of this definition, “submitted” means any form of electronic, verbal, or written communication sent to the Licensor or its representatives, including but not limited to communication on electronic mailing lists, source code control systems, and issue tracking systems that are managed by, or on behalf of, the Licensor for the purpose of discussing and improving the Work, but excluding communication that is conspicuously marked or otherwise designated in writing by the copyright owner as “Not a Contribution.”“Contributor” shall mean Licensor and any individual or Legal Entity on behalf of whom a Contribution has been received by Licensor and subsequently incorporated within the Work.
  2. Grant of Copyright License. Subject to the terms and conditions of this License, each Contributor hereby grants to You a perpetual, worldwide, non-exclusive, no-charge, royalty-free, irrevocable copyright license to reproduce, prepare Derivative Works of, publicly display, publicly perform, sublicense, and distribute the Work and such Derivative Works in Source or Object form.
  3. Grant of Patent License. Subject to the terms and conditions of this License, each Contributor hereby grants to You a perpetual, worldwide, non-exclusive, no-charge, royalty-free, irrevocable (except as stated in this section) patent license to make, have made, use, offer to sell, sell, import, and otherwise transfer the Work, where such license applies only to those patent claims licensable by such Contributor that are necessarily infringed by their Contribution(s) alone or by combination of their Contribution(s) with the Work to which such Contribution(s) was submitted. If You institute patent litigation against any entity (including a cross-claim or counterclaim in a lawsuit) alleging that the Work or a Contribution incorporated within the Work constitutes direct or contributory patent infringement, then any patent licenses granted to You under this License for that Work shall terminate as of the date such litigation is filed.
  4. Redistribution. You may reproduce and distribute copies of the Work or Derivative Works thereof in any medium, with or without modifications, and in Source or Object form, provided that You meet the following conditions:
    1. You must give any other recipients of the Work or Derivative Works a copy of this License; and
    2. You must cause any modified files to carry prominent notices stating that You changed the files; and
    3. You must retain, in the Source form of any Derivative Works that You distribute, all copyright, patent, trademark, and attribution notices from the Source form of the Work, excluding those notices that do not pertain to any part of the Derivative Works; and
    4. If the Work includes a “NOTICE” text file as part of its distribution, then any Derivative Works that You distribute must include a readable copy of the attribution notices contained within such NOTICE file, excluding those notices that do not pertain to any part of the Derivative Works, in at least one of the following places: within a NOTICE text file distributed as part of the Derivative Works; within the Source form or documentation, if provided along with the Derivative Works; or, within a display generated by the Derivative Works, if and wherever such third-party notices normally appear. The contents of the NOTICE file are for informational purposes only and do not modify the License. You may add Your own attribution notices within Derivative Works that You distribute, alongside or as an addendum to the NOTICE text from the Work, provided that such additional attribution notices cannot be construed as modifying the License.You may add Your own copyright statement to Your modifications and may provide additional or different license terms and conditions for use, reproduction, or distribution of Your modifications, or for any such Derivative Works as a whole, provided Your use, reproduction, and distribution of the Work otherwise complies with the conditions stated in this License.
  5. Submission of Contributions. Unless You explicitly state otherwise, any Contribution intentionally submitted for inclusion in the Work by You to the Licensor shall be under the terms and conditions of this License, without any additional terms or conditions. Notwithstanding the above, nothing herein shall supersede or modify the terms of any separate license agreement you may have executed with Licensor regarding such Contributions.
  6. Trademarks. This License does not grant permission to use the trade names, trademarks, service marks, or product names of the Licensor, except as required for reasonable and customary use in describing the origin of the Work and reproducing the content of the NOTICE file.
  7. Disclaimer of Warranty. Unless required by applicable law or agreed to in writing, Licensor provides the Work (and each Contributor provides its Contributions) on an “AS IS” BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied, including, without limitation, any warranties or conditions of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A PARTICULAR PURPOSE. You are solely responsible for determining the appropriateness of using or redistributing the Work and assume any risks associated with Your exercise of permissions under this License.
  8. Limitation of Liability. In no event and under no legal theory, whether in tort (including negligence), contract, or otherwise, unless required by applicable law (such as deliberate and grossly negligent acts) or agreed to in writing, shall any Contributor be liable to You for damages, including any direct, indirect, special, incidental, or consequential damages of any character arising as a result of this License or out of the use or inability to use the Work (including but not limited to damages for loss of goodwill, work stoppage, computer failure or malfunction, or any and all other commercial damages or losses), even if such Contributor has been advised of the possibility of such damages.
  9. Accepting Warranty or Additional Liability. While redistributing the Work or Derivative Works thereof, You may choose to offer, and charge a fee for, acceptance of support, warranty, indemnity, or other liability obligations and/or rights consistent with this License. However, in accepting such obligations, You may act only on Your own behalf and on Your sole responsibility, not on behalf of any other Contributor, and only if You agree to indemnify, defend, and hold each Contributor harmless for any liability incurred by, or claims asserted against, such Contributor by reason of your accepting any such warranty or additional liability.

qbsolvに貢献する

qbsolvの開発者は様々な形での貢献を期待しています。バグレポートから、例題の提案、チュートリアルやコアアルゴリズムの提案などです。ここでは実際に貢献をしたい方向けにどのように私たちが対応したいかを記述します。

イシュー

ツール内でのバグや異常、インストール時の異常、ドキュメントの変更リクエスト、設計や開発のイシュー、昨日要求などはGithubのイシュー機能を使って管理します。

バグがある場合には下記の情報を記述してください。

  • どのような手順でバグを再現できますか、出来るだけ簡潔に書いてもらえると助かります。
  • 最終版でも同様のバグが起こりますか?
  • qbsolvとご使用のOSのバージョンを書いてください。

貢献

私たちはqbsolvがエンドユーザーが問題を解き、メタヒューリスティクスのアルゴリズム開発者が新しいメタヒューリスティクスアルゴリズムを開発するためにたくさん使われ、量子速度向上を活用して堅牢なメタヒューリスティックスソルバーの実現に向けてより高速な開発を実現することを望んでいます。

一般的には、qbsolvを利用して、その強みや弱みを報告を通じて段階的な貢献を行うのが望ましいと思われますが、そうすることによってqbsolv開発者と信頼関係を結ぶことができます。 そして、貢献はコードやドキュケントの形でのみ行われ、例題やチュートリアルを作ることは、新規の参入者を増やしとても価値のあることであるということを忘れないで欲しいです。

そして、有望で保証されたアルゴリズムの変更も盛り込んでいます。アルゴリズム開発者によって使われているアルゴリズムは変更を受け入れる体制と、エンドユーザーへの安定したアルゴリズムの提供のバランスで成り立っています。近い将来、テストを通じた受け入れ態勢を整えたいと思います。

貢献の提案について

これよりGithubによるPull Requestを受け付けます。下記のような手順に沿ってください。

  • もし変更が多い場合、開発者と議論するためにqbsolvの計画に沿った要望を提示するために機能要求を作ってください。
  • 物事をスムーズに進めるために、1つのPRには明確な目的をもって、1つだけ行うことを決めてください。
  • PR内でのそれぞれのコミットは開発が少しずつ進むように1つずつにしてください。
  • コードでわかりづらいところは、コメントやコミットメッセージやPRに書いてください。
  • git commit -s でできるように、パッチに署名を追加してください。これによりあなたが書いたことが証明されます。匿名にしない、デフォルトの署名にしないでください。

ライセンス

qbsolvはライセンスのページに準拠しています。プロジェクトに貢献をしていただきますと、ライセンスに承諾したこととなり、貢献がこれらのライセンスに準じて公開されます。

Recommended


Wikiへ移動