D-Wave システム入門
ユーザー・マニュアル※

本書は、D-Wave User Manual 09-1076A-T Getting Started with the D-Wave System を和訳したものです。

概要

CONTACT

本書では、D-Wave 量子コンピューターを紹介し、システムの動作に関する重要な背景情報を幾つか提供し、システムが解決できる簡単な問題を構築する方法を説明します。

Corporate Headquarters
3033 Beta Ave
Burnaby, BC V5G
4M9 Canada
Tel. 604-630-1428
US Office2650 E Bayshore Rd
Palo Alto, CA 94303
Email: info@dwavesys.com
www.dwavesys.com

D-Wave User Manual 09-1076A-T
Copyright © D-Wave Systems Inc.

Notice and Disclaimer

D-Wave Systems Inc. (D-Wave), its subsidiaries and affiliates, makes commercially reasonable efforts to ensure that the
information in this document is accurate and up to date, but errors may occur. NONE OF D-WAVE SYSTEMS INC., its
subsidiaries and affiliates, OR ANY OF ITS RESPEC- TIVE DIRECTORS, EMPLOYEES, AGENTS, OR OTHER
REPRESENTATIVES WILL BE LIABLE FOR DAMAGES, CLAIMS, EXPENSES OR OTHER COSTS (INCLUDINGWITHOUT LIMITATION LEGAL FEES) ARISING OUT OF OR IN CONNECTION WITH THE USE OF THIS DOCUMENT
OR ANY INFORMATION CONTAINED OR REFERRED TO IN IT. THIS IS A COMPREHENSIVE LIMITATION OF
LIABILITY THAT APPLIES TO ALL DAMAGES OF ANY KIND, INCLUDING (WITHOUT LIMITATION)COMPENSATORY, DIRECT, INDIRECT, EXEMPLARY, PUNITIVE AND CONSEQUENTIAL DAMAGES, LOSS OF
PROGRAMS OR DATA, INCOME OR PROFIT, LOSS OR DAMAGE TO PROPERTY, AND CLAIMS OF THIRD PARTIES.
D-Wave reserves the right to alter this document and other referenced documents without notice from time to time and atits sole discretion. D-Wave reserves its intellectual property rights in and to this document and its proprietary technology,
including copyright, trademark rights, industrial design rights, and patent rights. D-Wave trademarks used herein include
D-Wave®, D-Wave 2XTM, D-Wave 2000QTM, and the D-Wave logo (the D-Wave Marks). Other marks used in this document
are the property of their respective owners. D-Wave does not grant any license, assignment, or other grant of interest in or tothe copyright of this document, the D-Wave Marks, any other marks used in this document, or any other intellectual property
rights used or referred to herein, except as D-Wave may expressly provide in a written agreement. This document may refer toother documents, includ- ing documents subject to the rights of third parties. Nothing in this document constitutes a grantby D-Wave of any license, assignment, or any other interest in the copyright or other intellectual property rights of suchother documents. Any use of such other documents is subject to the rights of D-Wave and/or any applicable third parties inthose documents.
All installation, service, support, and maintenance of and for the D-Wave System must be performed by qualified factorytrained D-Wave personnel. Do not move, repair, alter, modify, or change the D-Wave System. If the equipment is used ina manner not specified by D-Wave, the protection pro- vided by the equipment may be impaired. Do not provide access to thecustomer site to anyone other than authorized and qualified personnel. Failure to follow these guidelines may result in
disruption of service, extended downtime, damage to equipment (customer’s, D-Wave’s, and/or third parties’), injury, loss oflife, or loss of property.

D-Wave User Manual 09-1076A-T
Copyright © D-Wave Systems Inc.

目次

第 1 章 D-Wave へようこそ .................................................................................................................... 1
1.1 私たちがすること .......................................................................................................................... 1
1.2 D-Wave システムの紹介 ............................................................................................................... 2
1.2.1 物理的な説明 ........................................................................................................................... 2
1.2.2 D-Wave ソフトウェア環境..................................................................................................... 3
1.3 Leap 量子アプリケーション環境.................................................................................................. 4
第 2 章 量子アニーリングの紹介 ............................................................................................................. 6
2.1 適用できる問題 .............................................................................................................................. 6
2.2 D-Wave システムでの量子アニーリングの仕組み ....................................................................... 7
2.3 基礎となる物理学 .......................................................................................................................... 8
2.3.1 ハミルトニアンと固有スペクトル .......................................................................................... 8
2.3.2 低エネルギー状態でのアニーリング ...................................................................................... 9
2.3.3 エネルギー状態の進化 .......................................................................................................... 10
2.4 アニーリング制御 ........................................................................................................................ 11
第 3 章 問題の定式化：主な概念 ........................................................................................................... 12
3.1 目的関数 ....................................................................................................................................... 12
3.2 問題の定式化：イジングと QUBO.............................................................................................. 123.2.1 イジング・モデル.................................................................................................................. 12
3.2.2 QUBO.................................................................................................................................... 13
3.2.3 表記の比較............................................................................................................................. 13
3.3 グラフ........................................................................................................................................... 14
第 4 章 D-WAVE QPU アーキテクチャ：キメラ .................................................................................... 15
4.1 キメラ・グラフ ............................................................................................................................ 15
4.2 接続性........................................................................................................................................... 15
4.3 チェーンとマイナー埋め込み ...................................................................................................... 17
第 5 章 簡単な問題の定義 ...................................................................................................................... 18
5.1 目的関数の定義 ............................................................................................................................ 18
5.2 問題のスケーリング..................................................................................................................... 19
第 6 章 QUBO を使用して制約を表現する ........................................................................................... 21
6.1 目的関数の真理値表を作成する .................................................................................................. 21
6.2 QUBO が 1 つの真値を持つ状態を見つける ............................................................................... 22
6.3 QUBO をグラフに変換する ........................................................................................................ 22
第 7 章 問題をキメラ・グラフへマイナー埋め込み................................................................................ 24
7.1 チェーンの作成 ............................................................................................................................ 24
7.2 使用するユニット・セルの選択 .................................................................................................. 25
7.3 問題のパラメーターを作業グラフにマップする ......................................................................... 25
7.4 ソリューションの埋め込み解除 .................................................................................................. 26
第 8 章 D-WAVE システムへ問題を投入 ................................................................................................. 27
8.1 問題の投入 ................................................................................................................................... 27
8.1.1 手動マイナー埋め込み .......................................................................................................... 27
8.1.2 自動化されたマイナー埋め込み ............................................................................................ 27
8.2 解のチェック................................................................................................................................ 28
8.3 読み取り回数を増やす ................................................................................................................. 28

D-Wave User Manual 09-1076A-T
Copyright © D-Wave Systems Inc.

D-Wave User Manual 09-1076A-T
Copyright © D-Wave Systems Inc.

Getting Started with the D-Wave System

第1章

D-Wave へようこそ

私はすべての解析が古典的な理論だけで行われることに満足していません。何故ならば、自然は本当に古典的なものではなく、そして自然のシミュレーションを行いたいならば、それを量子力学でやった方が良いだろうし、そして、それは本当に素晴らしい問題だからです。何故ならば、それはとても簡単には見えない問題だからです。
これはチューリング・マシンではなく、まったく別の種類のマシンだからです。
—Richard Feynman, 19811

1.1

私たちがすること

今日のスーパーコンピューターの驚異的な能力にもかかわらず、多くの複雑なコンピューティングの問題は従来のシステムでは対処できていません。 データ量の膨大な伸びと、宇宙から私たち自身のDNA に至るまであらゆることをさらによく理解することの必要性は、答えを出すことを可能とする新しいツールを探すことにつながっています。 量子コンピューティングはコンピューティングの次のフ
ロンティアであり、世界で最も難しい問題を解決するためのまったく新しいアプローチを提供するものです。
確かに簡単ではありませんが、ファインマンがカリフォルニア工科大学で有名な講義を行った 1981 年
以来、量子コンピューティングの分野で大きな進歩がありました。 まだ比較的若い分野ですが、量子コンピューティングは複雑であり、世界中でさまざまなアプローチが追求されています。 現在、量子コンピューターには、ゲート・モデルと量子アニーリングという 2 つの先導的な候補アーキテクチャがあります。 ゲート・モデルの量子コンピューティングでは、量子システムの進化は非常にデリケートであるため、時間の経過に伴う量子状態の変化を制御および操作することを目的としています。
D-Wave 社のアプローチは、量子状態の自然な進み具合を利用する量子アニーリングです。このシステ
ムを非局在化状態で初期化し、解きたい問題の記述を徐々にオンにして行きます。システムがこれら変化に従っていくことは量子物理学が保証しています。最終の状態の構成は、見つけようとしている
答えに対応しています。 量子アニーリングは、単一の量子アルゴリズムとして D-Wave システムに実装されており、この量子コンピューティングへのスケーラブルなアプローチにより、2000 を超える量
子ビット（qubit）を持つ量子処理ユニット（QPU）を作成できました。これは ゲート・モデル量子コンピューティングの技術よりはるかに進んでいます。
D-Wave 社は、1999 年以来、ファインマンの言葉を実現するために、さまざまな世代の「異なる種類のマシン」を研究開発し続けてきました。私たちは、世界初の商用量子コンピューター会社です。

1

Feynman, Richard P. “Simulating physics with computers.” International Journal of Theoretical Physics 21, no.6
(1982): 467-488.
1
D-Wave User Manual 09-1076A-T
Copyright © D-Wave Systems Inc.

Getting Started with the D-Wave System

1.2

D-Wave システムの紹介

このセクションでは、システムの概要を説明します。 物理システムの詳細、お客様の役割の説明、および物理システムにアクセスする人に必要な基本的な安全情報については、D-Wave 社から入手可能な DWave Quantum Computer Operations マニュアルを参照してください。

図 1.1：D-Wave システム

1.2.1 物理的な説明
D-Wave システムには、量子力学的に動作するために絶対零度近くの温度に保ち、周囲の環境から隔絶することが必須の QPU（量子処理ユニット）が含まれています。 システムはこれらの要件を次のように達成しています：・ 極低温、これは閉ループ極低温希釈冷凍システムを使用して達成しています。 QPU は 15 mK（ミリ・ケルビン）未満の温度で作動します。
・ 電磁干渉からのシールド、無線周波数（RF）シールド・エンクロージャと磁気シールド・サブシ
ステムを使用して達成されています。

量子処理ユニット
D-Wave QPU（図 1.2）は、それぞれが量子ビットまたはカプラーである小さな金属ループ（環状）の格子からなっています。 9.2 度ケルビン以下の温度では、これらのループは超伝導体となり、量子力学的効果を示します。
D-Wave 2000Q QPU には、最大 2048 個の量子ビットと 6016 個のカプラーがあります。 この規模に到達するために、128,000 個のジョセフソン接合を使用しているため、D-Wave 2000Q QPU はこれまでで最も複雑な超伝導集積回路となりました。
QPU のトポロジの詳細については、第 4 章「D-Wave QPU アーキテクチャ：キメラ」セクションを参照してください。

2
D-Wave User Manual 09-1076A-T
Copyright © D-Wave Systems Inc.

Getting Started with the D-Wave System

図 1.2： D-Wave QPU

1.2.2

D-Wave ソフトウェア環境

ユーザーは、Web ユーザー・インターフェイス（UI）、およびソルバーAPI（SAPI2 – Solver
Application Program Interface）と通信するクライアント・ライブラリを介して D-Wave 量子コンピ
ューターとやり取りします。SAPI コンポーネントは、ユーザーとのやり取り、ユーザー認証、および作業スケジューリングを担当します。次に、SAPI は、量子機械命令を介して QPU に問題を送信し、QPU から結果を返すバックエンド・サーバーに接続し、（オプションで）結果に対して後処理アルゴ
リズムを実行します。 D-Wave ソフトウェア環境の簡略図については、図 1.3 を参照してください。

図 1.3：

D-Wave ソフトウェア環境

2

D-Wave システムでは、ソルバーは単に問題を解くだけのリソースです。 一部のソルバーは QPU に接続しており；
その他のソルバーは CPU および GPU リソースを活用します。
3
D-Wave User Manual 09-1076A-T
Copyright © D-Wave Systems Inc.

Getting Started with the D-Wave System

D-Wave クライアントを使用することで、さまざまなプラットフォームから D-Wave のアプリケーシ
ョンを簡単にコーディングできます。 REST / HTTPS プロトコルを使用して SAPI Web サービスコ
ンポーネントと通信し、次のことを可能にします。
・
・
・
・
・
・

利用可能なソルバーとソルバー・プロパティの問い合わせ
問題の投入
以前に実行に移された問題のキャンセル
問題のステータスを取得
成功したら結果を取得
失敗した場合はエラーを取得

D-Wave クライアントは、従来の要求/応答のやり方（パラダイム）を使用します。すなわち、アプリ
ケーション・コードがクライアント・システムで実行され、クライアント・コマンドが REST / HTTP
呼び出しに変換され、そして、サーバーに送信されます。詳細については、Solver API REST Web
Services Developer Guide をご覧ください。
D-Wave のオープンソース・ソフトウェア・ツール類の一式である Ocean は、量子コンピューターのアプリケーション開発をより迅速かつ効率的にします。 GitHub で利用できるこれらのツールは、量子コンピューティング・システム・リソースを活用できる共同プロジェクトを促進します。 Ocean
SDK をアクセスするには https://github.com/dwavesystems を参照し、関連するドキュメントについては、https://docs.ocean.dwavesys.com を参照してください。

1.3

Leap 量子アプリケーション環境

Leap は、D-Wave Systems Inc.のリアルタイム量子アプリケーション環境です。
Leap はシステムへのクラウド・アクセスを提供し、無料で試したい人に実際の量子コンピューティン
グを提供します。 Leap を通じて、D-Wave 量子コンピューターが解くことのできる問題の種類について学び、実際に量子コンピューターに問題を投入するインタラクティブなデモおよびコーディング
例を実行し、Ocean（当社のオープンソース・ソフトウェア・ツール）にアクセスし、コーディングのアイデアで皆に貢献し、志を同じくするユーザーのコミュニティで進化する会話に参加できます。
Leap のサインアップはこちら： https://cloud.dwavesys.com/leap

4
D-Wave User Manual 09-1076A-T
Copyright © D-Wave Systems Inc.

Getting Started with the D-Wave System

5
D-Wave User Manual 09-1076A-T
Copyright © D-Wave Systems Inc.

Getting Started with the D-Wave System

第2章

量子アニーリングの紹介

この章では、量子アニーリングとは何か、どのように機能するかを説明し、その振る舞いを支配する基礎となる量子物理学を紹介します。 D-Wave システムでの量子アニーリングの詳細については、Technical Description of the D-Wave Quantum Processing Unit（D-Wave 量子処理ユニットの技術説明）を参照してください。参照： https://docs.dwavesys.com/docs/latest/doc_qpu.html

2.1

適用できる問題

量子アニーリング・プロセッサーは自然に低エネルギー・ソリューションを返します。 実際の最小エネルギーを必要とするアプリケーション（最適化問題）と、適切な低エネルギー・サンプル（確率的サンプリング問題）を必要とするアプリケーションがあります。
最適化問題。 最適化問題では、可能な多くの組み合わせの中から最良のものを探します。 最適化問
題には、スケジュール調整、例えば「この荷物をこのトラックに積むべきかあるいは次のトラックに積むべきか？」あるいは「巡回セールスマンが同一でない都市を訪問するために最も効率的なルートはどうとるべきか？」といった問題が含まれます。
物理学は、このような種類の問題をエネルギー最小化問題として組み立てることができるので、その解決に役立ちます。 物理学の基本的な法則は、すべてが最小エネルギー状態に向かう傾向があるということです。 オブジェクトは高いところから滑り落ちてきます；熱いものは時間の経過とともに冷めてきます。 この動きは、量子物理学の世界にも当てはまります。 量子アニーリングは、量子物理学を使用して、問題の低エネルギー状態を見つけるもので、その結果、要素の最適またはほぼ最適な組
み合わせを見つけているだけです。
サンプリングの問題。 多くの低エネルギー状態からサンプリングし、エネルギー・ランドスケープの形状を特徴付けることは、現実の確率モデルを構築する機械学習の問題に役立ちます。 サンプルは、与えられた一連のパラメーターのモデル状態に関する情報を提供し、モデルの改善に使用できます。
確率モデルは、データ・ソースの知識とエラーのギャップを考慮して、不確実性を明示的に処理します。 確率分布は、モデルで観測されていない量（ノイズ効果を含む）と、データとの関係を表します。 データの分布は、サンプルの有限セットに基づいて近似されます。 モデルは観測されたデータから推測し、データを観測する前に定義された事前分布を、後で定義された事後分布に変換する際に学習が行われます。 トレーニング・プロセスが成功した場合、学習した分布はデータを生成した分布に似ているため、観測されていないデータについて予測を行うことができます。 たとえば、有名な手書き数字の MNIST データセットでトレーニングを行う場合、そのようなモデルは、トレーニング・
セットと一致する手書き数字に似た画像を生成できます。
エネルギーベースの分布からのサンプリングは、計算集中型のタスクであり、D-Wave システムが問題を解く方法と非常によく一致しています。 すなわち、低エネルギー状態を探すからです。

6
D-Wave User Manual 09-1076A-T
Copyright © D-Wave Systems Inc.

Getting Started with the D-Wave System

2.2

D-Wave システムでの量子アニーリングの仕組み

量子ビット（qubits‐キュービットとも呼ばれる）は、D-Wave QPU を構成する超伝導ループの最低エネルギー状態を表します。これらの状態には、循環電流と対応する磁場があります。 古典的ビットと同様に、量子ビットは 0 または 1 の状態になります。 図 2.1 を参照してください。 しかし、量子ビットは量子オブジェクトであるため、0 状態と 1 状態が同時に重なることもあります。 量子アニー
リング・プロセスの終了時に、各量子ビットは重ね合わせ状態から（古典的な状態の）0 または 1 になります。

図 2.1：

量子ビットの状態は循環電流として実装され、磁場に対応して、
時計回りは 0 を、反時計回りは 1 を、表わしています。

このプロセスの物理は、図 2.2 のようなエネルギー図で表示（視覚化）できます。 図中の（a）、（b）、および（c）で分かるように、この図は時間とともに変化します。 最初に、最小値が 1 つだけの谷（a）が 1 つあるだけです。 量子アニーリング・プロセスが実行され、障壁が上昇し、これによりエネルギー図が二重井戸型ポテンシャル（b）に変わります。 ここで、左の谷の低点は 0 状態に対応し、右の谷の低点は 1 状態に対応します。 量子ビットは、焼きなましの終わりにこれらの谷の一つに行き着きます。

図 2.2：

量子アニーリング・プロセスが実行され、バイアスが適用されると、エネルギー図は時間とともに変化します。

何もかもすべてが等しい場合、0 または 1 状態で終了する量子ビットの確率は等しくなります（50 パーセント）。 ただし、外部磁場を量子ビットに加えることにより、0 または 1 状態になる確率を制御できます（c）。 この場は二重井戸型ポテンシャルを傾斜させ、量子ビットがより低い井戸で終わる確率を高めます。 外部磁場を制御するプログラム可能な量はバイアスと呼ばれ、量子ビットはバイアスの存在下でエネルギーを最小化します。
ただし、バイアス項だけでは役に立ちません。 量子ビットの本当の力は、互いに影響を与えることができるように、量子ビットを互いにリンクするときに発生します。 これは、カプラーと呼ばれるデバ
イスを使用して行われます。 カプラーは、2 つの量子ビットを同じ状態（両方 0 か、両方 1）にする傾向があるか、逆の状態にする傾向があります。 量子ビット・バイアスと同様に、結合強度を設定することで、結合量子ビット間の相関重みをプログラムできます。 プログラム可能なバイアスと重みを共に与えることが、D-Wave システムに問題を定義する方法です。

7
D-Wave User Manual 09-1076A-T
Copyright © D-Wave Systems Inc.

Getting Started with the D-Wave System

カプラーを使用するとき、量子もつれと呼ばれる別の現象を使用しています。 2 つの量子ビットが絡み合っている場合、それらは 4 つの可能な状態を持つ単一のオブジェクトと考えることができます。
図 2.3 はこの考え方を示しており、それぞれが 2 つの量子ビット（0,0）
、
（0,1）
、
（1,1）、および（1,0）の異なる組み合わせに対応する 4 つの状態を持つポテンシャルを示しています。 各状態の相対エネルギーは、量子ビットのバイアスとそれらの間の結合に依存します。 アニール中に、量子ビット状態は、アニールの終了時に最終的に（1,1）に落ち着く前に、このランドスケープで非局在化される可能性があります。

図 2,3

最良の答えを示すエネルギー図

これまで見てきたように、各量子ビットにはバイアスがあり、量子ビットはカプラーを介して相互作用します。 問題を定式化するとき、ユーザーはバイアスとカプラーの値を選択します。 バイアスとカップリングはエネルギー・ランドスケープを定義し、D-Wave 量子コンピューターはそのランドスケ
ープの最小エネルギーを見つけます。これが量子アニーリングです。
量子ビットを追加すると、システムはますます複雑になります。 2 個の量子ビットでは、エネルギーの状況を定義する 4 通りの可能な状態があります。 3 個の量子ビットで、8 通りの状態があります。
1 量子ビットを追加するごとに、エネルギー・ランドスケープを定義できる状態の数が 2 倍になります。状態の数は、量子ビットの数とともに指数関数的に増加します。
要約すると、それぞれが 0 と 1 の重ね合わせ状態にある一連の量子ビットから始めます。それらはまだ結合されていません。 それらが量子アニーリングを受けると、カプラーとバイアスが導入され、量子ビットがもつれた状態になります。 この時点で、システムは多くの可能な答えのもつれた状態にあります。 アニールの終了までに、各量子ビットは、問題の最小エネルギー状態または非常に近い状態を表す古典的な状態になります。 これはすべてが、D-Wave システムの中でマイクロ秒単位で起こっていることです。

2.3

基礎となる物理学

このセクションでは、D-Wave 量子アニーリング・プロセスを制御する量子物理学を理解するために不可欠な 2、3 の概念について説明します。

2.3.1 ハミルトニアンと固有スペクトル
古典的なハミルトニアンは、エネルギーに関する物理システムの数学的記述です。 システムの特定の状態を入力でき、ハミルトニアンはその状態のエネルギーを返します。 ほとんどの非凸ハミルトニア
ンにとって、最小エネルギー状態を見つけることは、古典コンピューターが効率的に解けない NP 困
難な問題の一つです。
古典的なシステムの例として、テーブルとリンゴの非常に単純なシステムを考えてみましょう。 このシステムには 2 つの状態があります：テーブル上のリンゴと床上のリンゴです。 ハミルトニアンは私
8
D-Wave User Manual 09-1076A-T
Copyright © D-Wave Systems Inc.

Getting Started with the D-Wave System

たちにそれらのエネルギーを教えてくれます。すなわち、テーブルの上にリンゴがある状態は、リンゴが床にある状態よりも高いエネルギーを持っていることがわかります。
量子システムでは、ハミルトニアンは固有状態と呼ばれる特定の状態をエネルギーにマッピングする関数です。 システムがハミルトニアンの固有状態にある場合にのみ、そのエネルギーは明確に定義され、固有エネルギーと呼ばれます。 システムが他の状態にあるとき、そのエネルギーは不確かです。
定義された固有エネルギーを持つ固有状態の集まりが固有スペクトルを構成します。
D-Wave システムの場合、ハミルトニアンは次のように表されます。

𝐇𝐢𝐬𝐢𝐧𝐠 = −

𝐀(𝐬)
𝐁(𝐬)
(𝐢)
(𝐢)
(𝐢) (𝐣)̂𝐱 ) +
̂ 𝐳 + ∑ 𝐉𝐢,𝐣 𝛔
̂𝐳 𝛔
̂𝐳 )
(∑ 𝛔
(∑ 𝐡𝐢 𝛔𝟐𝟐𝐢𝐢

初期ハミルトニアン(𝟐. 𝟏)

𝐢>𝐣

最終ハミルトニアン(𝑖)

ここで、𝜎̂𝑥,𝑧 は量子ビット qi のパウリ・マトリックスであり、hi と Ji,j はそれぞれ量子ビット・バイア
スと結合強度 です。3
ハミルトニアンは、初期ハミルトニアンと最終ハミルトニアンの 2 つの項の合計です：
・ 初期ハミルトニアン（第 1 項）－ 初期ハミルトニアンの最低エネルギー状態は、すべての量子ビットが 0 と 1 の重ね合わせ状態にあるときです。この項は、トンネリング・ハミルトニアンとも呼ばれます。
・ 最終ハミルトニアン（第 2 項）— 最終ハミルトニアンの最低エネルギー状態は、解こうとしている問題に対する答えです。 最終状態は古典的な状態であり、量子ビット：バイアスと量子ビット間の結合が含まれます。 この項は、問題ハミルトニアンとも呼ばれます。
量子アニーリングでは、初期ハミルトニアンの最低エネルギーの固有状態から始めます。 アニールする際に、バイアスとカプラーを含む問題ハミルトニアンを導入し、初期ハミルトニアンの影響を減らします。 アニールの終わりで、問題ハミルトニアンは固有状態になります。 理想的には、量子アニーリング・プロセス全体を通じて最小エネルギー状態にとどまり、最終的には問題のハミルトニアンの最小エネルギー状態になり、したがって、解決したい問題に対する答えを得ることができます。 アニールの終了までに、各量子ビットは古典的な状態になります。

2.3.2 低エネルギー状態でのアニーリング
固有エネルギー対時間のプロットは、量子アニーリング・プロセスを視覚化するための便利な方法です。 アニール中の最低エネルギー状態－基底状態（ground state）－は通常、下部に表示され、より高い励起状態はその上に示されます； 図 2.4 を参照してください。

3

hi および、Ji,j のゼロ以外の値は、作業グラフで使用可能な値に制限されています。 D-Wave QPU Architecture：
Chimera の章を参照してください。
9
D-Wave User Manual 09-1076A-T
Copyright © D-Wave Systems Inc.

Getting Started with the D-Wave System

図 2.4： 基底状態が下にあり、より高い励起状態が上にある固有スペクトル。

アニールが開始されると、システムはすべての他のエネルギー・レベルから十分に離れた最低エネル
ギー状態で開始されます。 問題ハミルトニアンが導入されると、他のエネルギー・レベルが基底状態に近づく可能性があります。 それらが近づくほど、システムが最低エネルギー状態から励起状態の 1
つにジャンプする可能性が高くなります。 アニール中に、基底状態から離れた最も低いエネルギーを持つ最初の励起状態が基底状態に近づき、その後再び発散するポイントがあります。 アニール中の任意のポイントを通じて基底状態と最初の励起状態の間の最小距離は、ミニマム・ギャップ（minimumgap）と呼ばれます。
特定の要因により、システムが基底状態からより高いエネルギー状態にジャンプする場合があります。 1 つは、すべての物理システムに存在する熱変動です。 もう 1 つは、アニーリング・プロセスの実行が速すぎることです。 外部エネルギー源からの干渉を受けず、ハミルトニアンを十分にゆっくりと進化させるアニーリング・プロセスは、断熱プロセスと呼ばれます。これが断熱量子コンピューテ
ィングの名前の由来です。 現実世界の計算を完全に隔離して実行することはできないため、量子アニ
ーリングは、理論的な理想である断熱量子計算の現実世界における対応物と考えることができます。
実際には、いくつかの問題については、基底状態にとどまる確率が小さい場合があります。 ただし、返される低エネルギー状態は依然として非常に役立つものです。
指定するすべての異なる問題に対して、異なるハミルトニアンと異なる対応する固有スペクトルがあります。 量子アニーリングに関して最も難しい問題は、一般に複数の最小のミニマム・ギャップ（smallest minimum gap）がある問題です。

2.3.3 エネルギー状態の進化
図 2.5 は、物理的温度が一定である間のエネルギー関数の時間経過を示しています。 この図は、エネ
ルギー/h（Energy/h）を GHz 単位でプロットしています。ここで、h は Planck 定数4です。もう一つの軸 s は 0〜1 の範囲の抽象パラメーターに正規化されたアニールの割合です。A(s)曲線はトンネル・エネルギーであり、B(s)曲線は s における問題のハミルトニアン・エネルギーです。 線形アニール
は、s = t / t f と設定します。ここで、t は時間であり、t f はアニールの合計時間です。 t = 0 で、A(0)≫ B(0)ならば、各スピンはその古典的な状態の非局在化された組み合わせで、存在するシステムの量
子基底状態に導かれます。 システムがアニールされると、A は減少し、時間 t f まで B は増加し、この時量子ビットの最終状態が低エネルギー解を表しています。

4

6.6 × 10−34 joule-seconds

10
D-Wave User Manual 09-1076A-T
Copyright © D-Wave Systems Inc.

Getting Started with the D-Wave System

アニールの終了時に、このハミルトニアンには B(s)項のみが含まれます。 古典的なハミルトニアンであり、可能なすべての古典的なビット列（つまり、0 または 1 のいずれかの量子ビット状態の並び）は固有状態に対応し、固有エネルギーはシステムに入力した古典的なエネルギー目的関数です。

図 2.5： アニーリング関数 A(s)、B(s)。 アニーリングは s = 0 の時、A(s)≫ B(s)で始まり、s = 1 の時 A(s)≪ B(s)で終わります。 表示のデータは、D-Wave 2X システムの代表的なものです。

2.4

アニーリング制御

私たちは量子アニーリングの細部までさらに深く理解し、より良い制御を考案し続けています。 DWave 2000Q システムのリリースには、ユーザーがアニーリング・スケジュールをプログラムで制御できる機能が含まれており、エネルギー・ランドスケープ全体でさまざまな検索が可能となります。
これらの制御により、特定の種類の問題に対する最適化とサンプリングの両方のパフォーマンスが向上し、アニーリング・プロセスの途中で何が起こっているかを調査するのに役立ちます。
使用可能なアニーリング・コントロールの詳細については、Technical Description of the D-Wave
Quantum Processing Unit.を参照してください。

11
D-Wave User Manual 09-1076A-T
Copyright © D-Wave Systems Inc.

Getting Started with the D-Wave System

第3章

問題の定式化：主な概念

このセクションでは、D-Wave QPU の問題を定式化する前に理解する必要があるいくつかの鍵となる概念を紹介します：目的関数、イジング・モデル、2 次非制約バイナリ最適化問題（QUBO）、およびグラフ、です。

3.1

目的関数

D-Wave システムが解決できる形式で問題を表現する方法を理解するには、最初に目的関数を展開する必要があります。目的関数は、量子ビットを表す 2 進変数の関数として表現されるシステムのエネル
ギーを表す数式です。 ほとんどの場合、目的関数のエネルギーが低いほど、良い解になります。時として、より低いエネルギー状態が元の問題の容認可能な解である場合があり、その他の問題については、最適解のみが容認可能です。 通常、最良の解は、解空間の中で大域的最小（global minimum）のエネルギーに対応します。 図 3.1 を参照してください。

図 3.1：目的関数のエネルギー

項ごとに 1 つまたは 2 つの変数を持つ 2 次関数を考えてみましょう：

D = Ax + By + Cxy(3.1)

ここで、A、B、および C は定数です。 1 変数の項－例えば、Ax や By など－は線形であり、変数にバイアスをかけます。 2 変数項 － 例えば、Cxy － は、変数間の関係を持つ 2 次項です。

3.2

問題の定式化：イジングと QUBO

目的関数について検討している 2 つの定式化は、イジング・モデルと QUBO 問題の中に見つけられます。これら 2 つの定式化の間での変換は簡単です。

3.2.1 イジング・モデル
イジング・モデルは伝統的に統計力学で使用されます。 変数は「スピン・アップ」（↑）および「スピン・ダウン」（↓）であり、+ 1 および－1 の値に対応します。 カップリングで表されるスピン間の関係は、相関または反相関です。 イジング・モデルとして表される目的関数は次のとおりです：

12
D-Wave User Manual 09-1076A-T
Copyright © D-Wave Systems Inc.

Getting Started with the D-Wave System
𝑁𝑁

𝑁

𝐸𝑖𝑠𝑖𝑛𝑔 (𝑠) = ∑ ℎ𝑖 𝑠𝑖 + ∑ ∑ 𝐽𝑖,𝑗 𝑠𝑖 𝑠𝑗
𝑖=1

(3.2)

𝑖=1 𝑗=𝑖+1

ここで、量子ビット・バイアスに対応する線形係数は hi であり、結合強度に対応する 2 次係数は J i,jです。

3.2.2 QUBOQUBO 問題は、伝統的にコンピューター・サイエンスで使用されています。 変数は TRUE と FALSE
で、1 と 0 の値に対応します。
QUBO 問題は、実数の重みの N x N 上三角行列である上対角行列 Q と、および 2 値変数のベクトル xを使用して定義される関数で、次の関数を最小化する問題です：
𝑓(𝑥) = ∑ 𝑄𝑖,𝑖 𝑥𝑖 + ∑ 𝑄𝑖,𝑗 𝑥𝑖 𝑥𝑗
𝑖

(3.3)

𝑖<𝑗

ここで、対角項 Qi,i は線形係数であり、非ゼロの非対角項は 2 次係数 Qi,j です。
これは次のように簡潔に表現できます：min 𝑥 𝑇 𝑄𝑥

(3.4)

𝑥∈{0,1}𝑛

このドキュメントの大部分で使用されているスカラー表記では、QUBO として表される目的関数は次のとおりです：E𝑞𝑢𝑏𝑜 (𝑎𝑖 , 𝑏𝑖,𝑗 ; 𝑞𝑖 ) = ∑ 𝑎𝑖 𝑞𝑖 + ∑ 𝑏𝑖,𝑗 𝑞𝑖 𝑞𝑗
𝑖

(3.5)

𝑖<𝑗

注： Quadratic Unconstrained Binary Optimization (QUBO－制約なし 2 次形式 2 値変数最適化) 問題は、Q で表されるもの以外の変数に制約がないという点で、制約がありません。

3.2.3 表記の比較
イジングと QUBO の間の変換は次式で表されます：
𝑠 = 2𝑞 – 1(3.6)

図 3.2 は、イジングと QUBO の表記法および関連する用語を比較しています。

13
D-Wave User Manual 09-1076A-T
Copyright © D-Wave Systems Inc.

Getting Started with the D-Wave System

図 3.2： 表記の規則

3.3

グラフ

目的関数はグラフで表すことができます。 グラフは、ノード（変数を表す）とノード間の接続（エッジ）の集合で構成されます。
(3.7)

𝐻(𝑎, 𝑏) = 5𝑎 + 7𝑎𝑏 − 3𝑏

5 と-3 のバイアスを持つ 2 つのノード a と b、および強度 7 のノード間の接続が必要です。 図 3.3 を参照してください。

図 3.3： 2 変数の目的関数
D-Wave システムでは、ノードは量子ビットであり、エッジはカプラーです。

14
D-Wave User Manual 09-1076A-T
Copyright © D-Wave Systems Inc.

Getting Started with the D-Wave System

第 4 章 D-WAVE QPU アーキテクチャ：キメラ
D-Wave QPU のレイアウトを理解することは、QUBO またはイジング目的関数を D-Wave システムで解くことのできる形式に変換するために必須です。 2 進目的関数がグラフで表現できることはわかっていますが、これらを QPU で解くべく D-Wave システムに送信する前に、まずそのアーキテクチャをよりよく理解する必要があります。
D-Wave QPU は相互接続された量子ビットの格子です。 一部の量子ビットはカプラーを介して他の量子ビットに接続しますが、D-Wave QPU は完全には接続されていません。 代わりに、量子ビットはキメラとして知られるアーキテクチャで相互接続します。

4.1

キメラ・グラフキメラ・アーキテクチャは、接続されたユニット・セル（Unit Cell）の集合で構成され、各ユニッ
ト・セルには、カプラーを介して 4 つの垂直量子ビットに接続された 4 つの水平量子ビットがあります。 ユニット・セルは、隣接する量子ビットが接続された状態で縦横に並べられ、まばらに接続された量子ビットの格子を作成します。 図 4.1 を参照してください。

CN という表記は、ユニット・セルの N×N グリッドで構成されるキメラ・グラフを指します。 DWave 2000Q QPU は、C16 キメラ・グラフをサポートしています。2048 量子ビットは、8 量子ビッ
トのユニット・セルの 16×16 マトリックスに論理的にマッピングされます。
D-Wave QPU では、計算に使用できる量子ビットとカプラーの集合は作業グラフと呼ばれます。 作業
グラフの歩留まりは、通常、QPU 内に製造され物理的に存在する量子ビットとカプラーの総数よりも少なくなります。

4.2

接続性

ユニット・セルは、クロス（cross）またはカラム（column）として表すことができます。 図 4.2 を参照してください。
これらの各表現では、4 つの量子ビットのセットが 2 つあることがわかります。 4 つの量子ビットのセット内の各量子ビットは、もう 1 つのセット内のすべての量子ビットに接続されますが、同一セット内にある 4 つの量子ビットは、そのセット内の他の量子ビットには接続されません。 ユニット・セル内では、量子ビットは 2 つの部分からなる接続性を持ちます。

15
D-Wave User Manual 09-1076A-T
Copyright © D-Wave Systems Inc.

Getting Started with the D-Wave System

図 4.1： 3x3 キメラ・グラフ、これは C3 と表示されます。 量子ビットは 9 個のユニット・セルに配置されています

16
D-Wave User Manual 09-1076A-T
Copyright © D-Wave Systems Inc.

Getting Started with the D-Wave System

図 4.2：ユニット・セルの量子ビットのカラムまたはクロスのレイアウト

4.3

チェーンとマイナー埋め込み

目的関数を表すグラフ上のノードとエッジは、キメラの量子ビットとカプラーに変換されます。 目的
関数のグラフ内の各論理量子ビットは、ひとつまたは複数の物理量子ビットで表すことができます。 論
理量子ビットを物理量子ビットにマッピングするプロセスは、マイナー埋め込みと呼ばれます。

注： SAPI を介してマイナー埋め込み用のツールを使用できますが、「キメラ・グラフへの問題のマイナー埋め込み」の章で説明されているように、手動でこれを行うこともできます。

17
D-Wave User Manual 09-1076A-T
Copyright © D-Wave Systems Inc.

Getting Started with the D-Wave System

第5章

簡単な問題の定義

D-Wave システムが良い解を出すと期待できる問題の 1 つのタイプは、2 値変数問題の最適化です。 2
値変数の値は 0（NO、または FALSE）または 1（YES、または TRUE）のみです。 これらは、「荷物をこのトラックで配送すべきでしょうか？」などの質問に答えるような問題です。
従来のコンピューターは、最大のスーパーコンピューターであっても、入力に基づいて出力を生成する
単純な決定デバイスである論理ゲートで構成されていると考えることができます。一方、 D-Wave シス
テムはゲートに基づいていませんが、最適化問題を解くために最も相応しい特殊な回路がシステムを形成しています。
XNOR（排他的 NOR）ゲートは、両方の入力が同じ（両方 TRUE または両方 FALSE）の場合にのみTRUE 出力を返し、入力が異なる場合（1 つが TRUE、1 つが FALSE）に FALSE を返します。
・ 2 つの 2 値入力、a および b があります
・ a = 0 および b = 0 の場合、出力は 1
・ a = 1 および b = 1 の場合、出力は 1・ それ以外の場合、出力は 05.1

目的関数の定義

単純な 2 量子ビットの問題を考えてみましょう。この問題では、アニール後にこれら量子ビットを同じ値にしたいというものです。次の表から明らかなように、量子ビットには 4 通りの可能な最終状態があ
ります。

q0
0
0
1
1

q1
0
1
0
1

そして、D-Wave システムが状態（0,0）と（1,1）を優先し、状態（0,1）と（1,0）にペナルティを与えるようにします。 そうなるように目的関数を定義する必要があります。
目的関数の中で、量子ビットは変数です。 バイアスと強さは、線形項と 2 次項の係数です。 2 量子ビット問題の目的関数には、2 つの線形項と 1 つの 2 次項の 3 つの項があります。 線形項の係数は量子ビットのバイアスに対応し、2 次項の係数はカプラー強度に対応します。
必要な目的関数は次のように記述されます：
f (s) = a1q1 + a2q2 + b1,2q1q2(5.1)

ここで、s は変数 q = [qi,q2]のベクトル、a1 と a2 は量子ビット・バイアス、q1 と q2 は量子ビット 1 と 2を表す 2 進変数、b1,2 はカプラーの強度です。
元の目標を満たすために、a1 と a2 および b1,2 を設定します。 まず、q1 と q2 の両方が 0（状態 1、（0,0）と表記）に等しい場合、目的関数の値は 0 であり、他の調整可能なパラメーターがないことに注意してください。 この状態を優先するため、基底状態に対応する最小エネルギーは 0 でなければなりません。
また、状態 1（0,0）に対して、状態 2（0,1）および 3（1,0）にペナルティを科します。 これを行う 1
つの方法は、a1 と a2 の両方を 0.1 に設定して、量子ビット 1 と 2 に 0.1 のバイアスを割り当てることです。
18
D-Wave User Manual 09-1076A-T
Copyright © D-Wave Systems Inc.

Getting Started with the D-Wave System

q0
0
0
1
1

q1
0
1
0
1

Objective Value
0
0.1
0.1
0.2 + b1,2

また、状態 1（0,0）とともに状態 4（1,1）を優先することも忘れないでください。 これを行う 1 つの方法は、カプラーの強度を b1,2 = −0.2 に設定することです。 結果の目的関数は次式のようになり、
f (s) = 0.1q1 + 0.1q2 − 0.2q1q2(5.2)

そして、以下の表を得ることができます。

q0
0
0
1
1

q1
0
1
0
1

Objective Value
0
0.1
0.1
0

このようにして、D-Wave システムでこの問題を多数回アニールさせると（その結果はサンプルまたは
読み取りとも呼ばれます）、私たちは返された結果が、励起状態の（0,1）および（1,0）よりも基底状態の（0,0）および（1,1）の方がはるかに多く出てくるだろうと期待します。
1000 個のソリューションのサンプルを取得するために、この問題を D-Wave 2000Q システムで 1000回実行した結果を次に示します：
Energy State Occurrences
0(0,0) 5550(1,1) 443
0.1(0,1) 10.1(1,0) 1
この問題を再度実行すると、エネルギー0 に関連付けられた数値は変化しますが、数値 500（サンプルの 50％）の近くに留まると予想されます。 完全なシステムでは、統計的な意味で、いずれかの基底状態が他方よりも支配的であるとは考えていません。 ただし、実行ごとに異なる数値が生成されます。
結果の大多数は（0,0）と（1,1）ですが、QPU を十分に多数回呼び出すと、ときどき（0,1）と（1,0）の解が表示されることに注意してください。 より複雑な QUBO の場合、同じ問題を繰り返し解いてさまざまな答えを得るこのプロセスは、サンプリングと呼ばれ、また、機械学習を含む多くの分野で強力なアプリケーションを可能とします。

5.2

問題のスケーリング

別の 2 量子ビット問題を考えてみましょう。今回は、2 個の量子ビット・バイアスとして（0.5）、カプ
ラー強度として（-1）と異なる値が割り当てられています。 この問題は前の問題から均一にスケーリン
グされていることに注意してください（5 倍）：
f (s) = 0.5q1 + 0.5q2 − q1q2

(5.3)

この問題も状態（0,0）と（1,1）に有利ですが、励起状態の目的値が最初の問題の 0.1 に対して 0.5 になっています。 下記を参照のこと。

19
D-Wave User Manual 09-1076A-T
Copyright © D-Wave Systems Inc.

Getting Started with the D-Wave System

q0
0
0
1
1

q1
0
1
0
1

Objective Value
0
0.5
0.5
0

励起状態の値は前の問題の値とは異なるため、基底状態と励起状態との間のエネルギー・ギャップが大きくなるため（0.5 対 0.1）
、今回は異なる結果が出てくるとが予想されます。 言い換えれば、基底状態と励起状態の間に大きなギャップがある場合、励起状態に到達するのが難しく、したがって、あまり有利ではないと予想されます。
最初の問題では、返された結果には励起状態のごく一部しか見られなかったことを思い出してください。
予想に反して、両方の問題を何度も実行すると、2 番目の問題の（見かけの）ギャップが大きいにもかかわらず、一般に同じ結果が観察されます。
この結果は、自動スケーリングと呼ばれる D-Wave システムの機能によるものです。 各 QPU には、aと b のバイアスと強度の値の許容範囲があります。 自動スケーリングを明示的に無効にしない限り、
D-Wave ソフトウェアは問題の a 値と b 値を調整して、QPU に送信する前に使用可能な（a、b）範囲全体を取得します。 その結果、これらの 2 つの問題が実行されるまでに、QPU に同じ（a、b）値を提示するため、返される解は事実上同じです。 実行の最後にエネルギーと目的値が報告される場合、スケーリングされる前の値を使用しています。
これをテストするには、自動スケーリングを無効にして、最初の問題（励起状態の目的値が 0.1）の 1000
回の読み取りを実行します。 このとき、次のような結果が表示されます。
Energy State Occurrences
0(0,0) 2720(1,1) 536
0.1(0,1) 124
0.1(1,0) 68
自動スケーリングを無効にした状態で 2 番目の問題（励起状態の目的値が 0.5）の 1000 回の読み取りを実行すると、次のような結果が表示されます。
Energ
0
y
0
0.5
0.5

Stat
(0,0)
e
(1,1)
(0,1)
(1,0)

Occurrenc
436
es
563
1
0

これらの結果は、スケーリングなしでは、最初の問題のギャップは 2 番目の問題よりも小さく、励起状
態のサンプルが多く返されることを示しています。

20
D-Wave User Manual 09-1076A-T
Copyright © D-Wave Systems Inc.

Getting Started with the D-Wave System

第6章

QUBO を使用して制約を表現する

QUBO を使用して、より大きく複雑な問題を重要な構成ブロックにした単純な複数の制約に定義することが出来ます。 正確に 1 個の真値の制約は、ブール代数の充足可能性の問題であり、その問題で、与えられた変数の集合のうち、唯 1 個の変数が 1 に等しい（TRUE である）場合のみ教えてくれる必要があります。
例えば、一連の都市を通る巡回セールスマンのルートを最適化する場合、旅の各段階でセールスマン
は 1 度に 1 都市しか訪問できないと強制する制約が必要です：セールスマンを 1 度に 2 つ以上の都市に配置する解は無効です 。

図 6.1： 巡回セールスマン問題は、正確に 1 個の真値の制約を使用して解決できる最適化問題です。 地図データ©2017 GeoBasis-DE / BKG(©2009）,Google。

この章では、D-Wave システムが解くことのできる形式で、正確に 1 個の真値の制約を作成する方法について説明します。 次の手順を説明します：
1． 目的から開始します：この場合、3 つの変数を持つ正確に 1 個の真値の制約から開始し、この目的を満たす真理値表を作成します。
2． 訪問したい州を優先し、他の州にペナルティを与える QUBO を作成します。
3． QUBO をグラフに変換します。

6.1

目的関数の真理値表を作成する

簡単な例を考えてみましょう：3 つの変数 a、b、c が与えられたとき、正確に 1 つの変数が 1 である
ときを知りたいとします（つまり、a、b、c の 1 つだけが 1 で；他の 2 つが 0 であるとき） これは、次の真理値表に変換されます：

a
0
1
0
1
0
1
0
1

b
0
0
1
1
0
0
1
1

c

0
0
0
0
1
1
1
1

Exactly 1
FALSE
TRUE
TRUE
FALSE
TRUE
FALSE
FALSE
FALSE

21
D-Wave User Manual 09-1076A-T
Copyright © D-Wave Systems Inc.

Getting Started with the D-Wave System

6.2

QUBO が 1 つの真値を持つ状態を見つける

この目的が真であるときに最小になる関数 E（a、b、c）を見つけたい。 これは次のように表現できます

a+b+c=1(6.1)

a+b+c−1=0(6.2)

あるいは同様に

上記の 2 番目の式の問題は、a、b、および c がすべて 0 の場合、-1 の結果が得られることです。これは、TRUE 状態よりも低いエネルギーです。 解決策は、元の方程式を 2 乗することです：(a + b + c − 1)2(6.3)

E (a, b, c) = (a + b + c − 1)2(6.4)

2 乗式を詳しく見ると、変数が 2 進数（0 または 1）であるため、

a2 = a(6.5)

E (a, b, c) = 2ab + 2ac + 2bc − a − b − c + 1(6.6)

目的関数は 2 次形式の式になります

ここで、関数 E(a, b, c) のエネルギーは目的関数の値です。
真理値表をもう一度見てみましょう。今回はエネルギーを表す列を追加します。 最低エネルギー状態
は、厳密に 1 つの真値という制約に一致するものであることに注意してください。 解が優れているほど、エネルギーは低くなることを忘れないでください。

a
0
1
0
1
0
1
0
1

b
0
0
1
1
0
0
1
1

c

0
0
0
0
1
1
1
1

Exactly 1 Energy
FALSE 1
TRUE
0
TRUE
0
FALSE 1TRUE
0FALSE 1FALSE 1FALSE 4QUBO として表現されると、次の式となります𝐸 (𝑥0 , 𝑥1 , 𝑥2 ) = 2𝑥0 𝑥1 + 2𝑥0 𝑥2 + 2𝑥1 𝑥2 − 𝑥0 − 𝑥1 − 𝑥2 + 1

6.3

(6.7)

QUBO をグラフに変換する

QUBO エネルギー関数は、図 6.2 に示す 3 角形のグラフで表すことができます。 各 2 進変数は、その1 次係数でバイアスされたノードになります。 各 2 次項の係数はノード間のエッジになります。
22
D-Wave User Manual 09-1076A-T
Copyright © D-Wave Systems Inc.

Getting Started with the D-Wave System

図 6.2：バイアス付きノードとエッジを示した 3 角形グラフ

23
D-Wave User Manual 09-1076A-T
Copyright © D-Wave Systems Inc.

Getting Started with the D-Wave System

第 7 章 問題をキメラ・グラフへマイナー埋め込み
この章では、前の章で作成した QUBO をキメラ・グラフにマイナー埋め込みする方法を示します。
マイナー埋め込みには、チェーンが必要になることがよくあります。これについては、ここで説明します。 QPU から受け取った解は、埋め込み手順を逆にすることで埋め込みを解除できます。

注： この例は、単純な問題のマイナーな埋め込みおよび埋め込み解除プロセスを順を追って説明し、その仕組みを理解することを目的としていますが、D-Wave にはこのプロセスを能率化するための自動の埋め込みおよび埋め込み解除のツールが用意されています。

7.1

チェーンの作成

三角グラフがキメラ・グラフにどのように適合するかを判断するには、図 7.1 に示すキメラ構造を詳しく調べる必要があります。 図 6.2 の三角グラフ構成を実現するために、閉ループに 3 つの量子ビットを設定する方法がないことに注意してください。 ただし、たとえば、量子ビット 0、1、4、5 を使用
して、4 量子ビットの閉ループを作成することはできます。

図 7.1： キメラ・ユニット・セル。

3 量子ビット・ループを 4 面構造に収めるために、1 つの変数を表す 2 つの物理量子ビットのチェーンを作成します； 図 7.2 を参照してください。 この場合、変数 b を表すために量子ビット 0 と量子ビ
ット 5 をチェーンします。

図 7.2： チェーンを使用して三角グラフをキメラに埋め込む。

24
D-Wave User Manual 09-1076A-T
Copyright © D-Wave Systems Inc.

Getting Started with the D-Wave System

変数 b を表す q0 と q5 の間のカプラーの強度は、量子ビットを強く相関させるように設定する必要があります（次に説明します）。そのため、ほとんどの最適な解では q0 = q5 = b です。 変数から量子ビットへのマッピングは、マイナー埋め込みと呼ばれます。

7.2

使用するユニット・セルの選択

D-Wave QPU アーキテクチャ：キメラの章で説明したように、ユーザーがアクセスできるキメラ・グ
ラフのサブセット（部分集合）は作業グラフです。 作業グラフに問題を埋め込む前に、QPU の物理
レイアウトを確認して、どの量子ビットとカプラーがファブリックに存在しないか、したがってどの
ユニット・セルが適切な選択かを理解してください。

7.3

問題のパラメーターを作業グラフにマップする

ここで、前のステップで行った作業を翻訳して、問題を物理 QPU の実際の作業グラフにマッピングします。 どの量子ビットにどの変数をマッピングするかはすでにわかっており、また、元のグラフからノード・バイアスとエッジ強度についても知っています。 ノード・バイアスは、変数 a および c を表す量子ビットの量子ビット・バイアスに変換されます。 以下の表を参照してください。
Qubit
0
Variable b
Bias
?

5
b
?

4
a
-1

1
c
-1

Coupler (0,4) (5,0) (4,1) (1,5)
Strength 2?
22
しかし、変数 b とそれらの間の結合強度を表す 2 つの量子ビットはどうでしょうか？ 量子ビット 0 と5 を連鎖させるために強力な負値のカプラーが必要です。これにより、必要な接続性を持つ単一の論理量子ビットが作成されます。 また、既存の量子ビット値に追加して、追加する負の結合を補正する必要があります。5

このプロセスにはいくつかの手順が必要です：
1．
2．

3．
4．

q0 と q5 の間で変数 b から-1 のバイアスを均等に分割します。 よって、これらの 2 つの量子ビットのバイアスは-0.5 です。
q0 と q5 の間のチェーンに強い負の結合強度を選択します。この例では、-3 を結合強度として任意に選択します。これは、周囲の他のカプラーの値よりも強い値であり、負であり、2 つの量子ビットを強制的に等しくするためです。
ここで、ステップ 2 で追加した-3 を補正するために、q0 と q5 の各バイアスに 1.5 を加える必要があります。そして今、q0 と q5 の両方のバイアスは 1 となります。
最後に、すべての値を 3 で除算することにより、最大カプラー強度が-1 になるように、グラフ全体をシステムの物理的境界内に収まるように正規化します。

結果として得られる値は次のとおりです。連鎖した量子ビットは強い負の結合（-1）を持ちます：6

5

イジング・モデルでは、問題の基底状態を変更せずに 2 次項にバイアスを導入できます。 ただし、QUBO 問題の場
合（ここにあるように）、2 次項のバイアスを変更すると、2 つの 1 次項のそれぞれにバイアス（2 次項バイアスの0.5）を追加して補正しない限り、基底状態が変わってしまいます。
6
一部のソルバーは、より強力な結合を可能にするために拡張 J 範囲をサポートしています。 拡張 J 範囲および関連するコントロールの詳細については、Technical Description of the D-Wave Quantum Processing Unit.を参照してください。
25
D-Wave User Manual 09-1076A-T
Copyright © D-Wave Systems Inc.

Getting Started with the D-Wave System

Qubit
0
5
4
1
Variable b
b
a
c
Bias
0.33 0.33 -0.33 -0.33
Coupler (0,4) (5,0) (4,1) (1,5)
Strength 0.667 -1
0.667 0.667
これで、問題を D-Wave システムの QPU に送信して解くことができます。

7.4

ソリューションの埋め込み解除

QPU が正確に 1 つの真の問題を解き、組み込み問題の解のサンプルを返した後、元の問題の解を得るには、それらの解を組み込み解除する必要があります。
ここでの問題に対して返される可能性のある値は次のとおりです。
••••

q0 = 1
q5 = 1
q4 = 0q1 = 0

埋め込みプロセスを逆にして、元の問題の解を取得します：• a = q4 = 0• b = q0, q5 = 1• c = q1 = 0
そして、これは 3 つの期待される解の 1 つを与えます：(a, b, c) = (0, 1, 0)
他の可能な解は、（1、0、0）および（0、0、1）です。

注： チェーンが壊れている場合、2 つの強く結合された量子ビットは、論理値がどうあるべきかについて「一致しない」可能性があります。 この問題に対処するために、SAPI には、破損したチェーンを持つソリューションを完全なソリューションに変換する後処理ユーティリティが含まれています。

26
D-Wave User Manual 09-1076A-T
Copyright © D-Wave Systems Inc.

Getting Started with the D-Wave System

第 8 章 D-WAVE システムへ問題を投入
このセクションでは、Ocean ソフトウェアを使用して正確に 1 つの問題を QPU に実行させ、返された状態を出力する様子を示します。 作業グラフで表現できる問題がすでに定義されていることを前提としています： 前のセクションを参照して、このポイントに到達する方法を確認してください。
注： 次の例では、SAPI を介して問題を実行させるのに必要な情報が構成されていることを前提としています。 これは通常、Ocean SDK をインストールするときの最初のステップとして行われます。 Ocean SDK のインストール手順や詳細な例を含む情報についてもっと知りたいときは、次の URL にある Ocean ソフトウェアのドキュメントを参照してください： https://docs.ocean.dwavesys.com 。

8.1

問題の投入

問題を投入するとき、それをキメラ・トポロジーに手動でマイナー埋め込みするか、Ocean ツールを使用して自動的にマイナー埋め込みするかを決定できます。

8.1.1 手動マイナー埋め込み
ここまでに必要な量子ビットが存在するシステムの埋め込みを作成したので、QPU に量子ビットを直接設定することができます。 自動化されたマイナー埋め込みセクションでは、Ocean ソフトウェア・
ツールを使用してマイナー埋め込みを自動化し、元の QUBO 変数を使用して問題を実行させることができるようにします。
>>> from dwave.system.samplers import DWaveSampler>>> # Set Q for the minor-embedded problem QUBO>>> qubit_biases = {(0, 0): 0.3333, (1, 1): -0.333, (4, 4): -0.333, (5, 5): 0.333}>>> coupler_strengths = {(0, 4): 0.667, (0, 5): -1, (1, 4): 0.667, (1, 5): 0.667}>>> Q = dict(qubit_biases)>>> Q.update(coupler_strengths)>>> # Sample once on a D-Wave system and print the returned sample>>> response = DWaveSampler().sample_qubo(Q, num_reads=1)>>> print(next(response.samples())){0: 1, 1: 0, 4: 0, 5: 1}

注： 通常、作業グラフの総量は、QPU に組み込まれて物理的に存在する量子ビットとカプラーの総数よりも少ないた
め、選択した量子ビットがアクティブであることを最初に確認する必要があります。 例えば、最初のユニット・セルの量子ビットを確認するには：>>> print(DWaveSampler().nodelist[0:8])[0, 1, 2, 3, 4, 5, 6, 7]

選択したカプラーについても同様です。 非アクティブなものがある場合、別のユニット・セルを使用できます。

8.1.2 自動化されたマイナー埋め込み
Ocean ソフトウェアは、マイナー埋め込みをヒューリスティックに見つけ出すことにより、QUBO ま
たはイジング変数で定義された問題を受け入れることができます>>> from dwave.system.samplers import DWaveSampler>>> from dwave.system.composites import EmbeddingComposite>>> # Set Q for the problem QUBO

27
D-Wave User Manual 09-1076A-T
Copyright © D-Wave Systems Inc.

Getting Started with the D-Wave System>>> linear = {('x0', 'x0'): -1, ('x1', 'x1'): -1, ('x2', 'x2'): -1}>>> quadratic = {('x0', 'x1'): 2, ('x0', 'x2'): 2, ('x1', 'x2'): 2}>>> Q = dict(linear)>>> Q.update(quadratic)>>> # Minor-embed and sample 1000 times on a default D-Wave system>>> response = EmbeddingComposite(DWaveSampler()).sample_qubo(Q, num_reads=1000)>>> for sample, energy, num_occurrences in response.data():... print(sample, "Energy: ", energy, "Occurrences: ", num_occurrences){'x0': 0, 'x1': 0, 'x2': 1} Energy: -1.0 Occurrences: 254{'x0': 0, 'x1': 1, 'x2': 0} Energy: -1.0 Occurrences: 408{'x0': 1, 'x1': 0, 'x2': 0} Energy: -1.0 Occurrences: 337{'x0': 1, 'x1': 1, 'x2': 0} Energy: 0.0 Occurrences: 1

再度 1000 回の読み取りの結果では、この問題において 3 つの有効な状態が最低エネルギーであることが見て取れます。4 つの固有の状態が返されますが、3 つの有効な状態に対して最低エネルギーであり、これらが最も頻繁に起こる解となります。

8.2

解のチェック

出て来た解を見てみましょう。元の問題の変数にマッピングして戻します。 正確に 1 つの問題に対する有効な解があります：a と c は FALSE です； b は TRUE です。 チェーンされた量子ビット 0 と 5は両方とも同じ値を返します。
Variables
Qubit
Returned Values

8.3

b
0
1

c
1
0

a
4
0

b
5
1

読み取り回数を増やす

ここで、読み取り数を 1000 回に増やします。読み取り回数を増やすと、通常、返される解のバリエー
ションが増えます。

>>> response = DWaveSampler().sample_qubo(Q, num_reads=1000)>>> for (sample, energy, num) in response.data():...
print(sample, "Energy: ", energy, "Occurrences: ", num)
{0: 1, 1: 0, 4: 0, 5: 1} -0.33370000000000005 322{0: 0, 1: 0, 4: 1, 5: 0} -0.33300000000000013 340{0: 0, 1: 1, 4: 0, 5: 0} -0.333 335{0: 0, 1: 0, 4: 1, 5: 1} 0.0 1{0: 1, 1: 1, 4: 0, 5: 1} 0.00030000000000002247 1{0: 0, 1: 1, 4: 1, 5: 0} 0.0010000000000000009 1

1000 回の読み取りの結果では、この問題において 3 つの有効な状態が最低エネルギーであることが分かります。 この 3 変数の問題に対する有効な解答は 3 つしかありませんが、6 つ異なった状態が返されています。 3 つの有効な状態で最低エネルギーが発生し、ここまででこれが最も頻繁に発生する解です。 ある範囲の解を返すことは、サンプリング問題に役立ちます。

28
D-Wave User Manual 09-1076A-T
Copyright © D-Wave Systems Inc.