記事

量子コンピューティング応用 - 最適化

22
3月
,
2022

最適化問題は多くの産業で見られる。以下はその一例である:

  • ポートフォリオの最適化あるマネー・マネジャーが一定の投資資金を持っている。この資金の最適な配分は?
  • ルートの最適化フェデックスのトラックが50個の荷物を配達する必要がある。荷物を配達する最適なルートは?
  • 空港のセキュリティある空港が、空港内の隅々まで監視するために監視カメラを設置したいと望んでいる。これを実現するカメラの最適な配置は?

それぞれの最適化には、最適解を構成するものの定義と、制約条件のセットがあります。それぞれの例について、最適解と可能な制約を探ってみましょう:

ポートフォリオの最適化。マネー・マネージャーは、最小のリスクで最大のリターンを求めるかもしれない。その制約とは、例えば、ポートフォリオの5%以上を単一の資産に投資しないことかもしれない。

ルートの 最 適 化:フェデックスのトラックは最短時間で配達を完了したいと考えるかもしれません。最適解の別の定義として、最短配達時間の代わりに、燃料費や通行料を考慮した最低コストのルートや、カーボンフットプリントが最も少なくなるルートが考えられます。

空港のセキュリティ。空港は、最小数のカメラですべての通路をカバーしたいと思うかもしれない。制約は、各コンコースに少なくとも1台のカメラを設置することかもしれない。

最適化問題がいかに複雑なものになりうるかは容易に理解できる。フェデックスのトラックは50カ所に停車するため、約30兆
(3×10^64)ものオプションが考えられます。最適化が妥当な時間で完了できたとしても、急にやり直しが必要になるかもしれません:ルート上で大渋滞が発生した、資産の価格が下がって購入の魅力が増した、などだ。

しかし、問題が難しい場合、それを解決することで大きな報酬が得られる可能性がある。最適化されたルーティングによって燃料費を15%節約した物流会社は、利益を増やし、市場シェアを拡大することができる。最適なポートフォリオは、顧客にとっても、ポートフォリオ・マネージャーにとっても、そしてその雇用主にとっても良いことである。

これらの問題を解くことの難しさと、最適な答えを得ることによる見返りが、企業が量子コンピューティングを検討する主な理由です。ボストンコンサルティンググループは最近、量子コンピュータを使った最適化問題の解決で解き放たれる価値は1,100~2,000億ドルに上ると推定しています。

Classiqとの組み合わせはこんな感じ:

空港のセキュリティ問題を考えてみよう。この種の問題は「最大頂点カバー」問題として知られている。 

ユーザーは空港の構成やフロアプラン、使用するカメラの台数を指定すると、Classiqの合成エンジンが問題の数学を設定する。 

専門用語で言えば、ユーザは重み付きエッジグラフと頂点カバーのサイズを提供します。Classiqは問題、制約、解を定義する関数を提供する。問題はQAOA(量子近似最適化アルゴリズム)を使って解かれる。これはハイブリッドなアルゴリズムで、量子的な部分(解や最適化したい期待値をエンコードする量子コスト関数、可能性のある解を探索する量子ミキサー関数、量子アサッツやパラメトリックな初期状態)と、古典的な最適化部分(我々の場合はPyomoパッケージを使用)があります。

ここでは、下の写真のような3つの外側ノードを持つスター・グラフを指定する。便宜上、各ノードには番号を付けました。カメラが1台しかない場合、空港の全エリアをカバーする位置は?


import networkx as nx
import pyomo.core as pyo
from classiq import combinatorial_optimization
from classiq_interface.combinatorial_optimization.preferences import QAOAPreferences
from classiq_interface.combinatorial_optimization.solver_types import QSolver


def mvc(graph: nx.Graph, k: int) -> pyo.ConcreteModel:
    model = pyo.ConcreteModel()
    model.x = pyo.Var(graph.nodes, domain=pyo.Binary)
    model.amount_constraint = pyo.Constraint(expr=sum(model.x.values()) == k)

    def obj_expression(model):
        return sum((1 - model.x[i]) * (1 - model.x[j]) for i, j in graph.edges)

    model.cost = pyo.Objective(rule=obj_expression, sense=pyo.minimize)

    モデルを返す


G = nx.star_graph(3)
mvc_model = mvc(G, 1)

qaoaP = QAOAPreferences(qsolver=QSolver.QAOAMixer)
mvc_problem = combinatorial_optimization.CombinatorialOptimization(model=mvc_model、
                                                                   qaoa_preferences=qaoaP)
qc = mvc_problem.generate()
qc.show_interactive()

open("MVC_interactive_circuit.html", "w").write(qc.interactive_html)

result = mvc_problem.solve()
print(result)
NetworkXパッケージで生成されたスターグラフ

回路を生成すると、インタラクティブな回路が新しいウィンドウにポップアップ表示される。回路の構造がはっきりと見え、左上のプラスアイコンをクリックすることで、回路のどの部分にも深く入り込むことができる。

クラシックのロゴ

スクリプトにエラーがありました

この回路をQAOAで実行し、結果を印刷すると、このような解が得られる(アルゴリズムが「コスト」関数を最小化するように動作するため、この解が選択される)。

このリストはカメラの位置候補に対応しているので、位置0、つまり中央のノードにはカメラがあるはずだ。

別のグラフを使った解答はこんな感じです。角がないことを確認できますか?

トゥーラン・グラフの最適解:(1, 1, 0, 0, 0, 0, 0, 1, 0)

Classiqプラットフォームが御社にどのようなサービスを提供できるかご興味がおありですか?デモのご予約はこちらから

最適化問題は多くの産業で見られる。以下はその一例である:

  • ポートフォリオの最適化あるマネー・マネジャーが一定の投資資金を持っている。この資金の最適な配分は?
  • ルートの最適化フェデックスのトラックが50個の荷物を配達する必要がある。荷物を配達する最適なルートは?
  • 空港のセキュリティある空港が、空港内の隅々まで監視するために監視カメラを設置したいと望んでいる。これを実現するカメラの最適な配置は?

それぞれの最適化には、最適解を構成するものの定義と、制約条件のセットがあります。それぞれの例について、最適解と可能な制約を探ってみましょう:

ポートフォリオの最適化。マネー・マネージャーは、最小のリスクで最大のリターンを求めるかもしれない。その制約とは、例えば、ポートフォリオの5%以上を単一の資産に投資しないことかもしれない。

ルートの 最 適 化:フェデックスのトラックは最短時間で配達を完了したいと考えるかもしれません。最適解の別の定義として、最短配達時間の代わりに、燃料費や通行料を考慮した最低コストのルートや、カーボンフットプリントが最も少なくなるルートが考えられます。

空港のセキュリティ。空港は、最小数のカメラですべての通路をカバーしたいと思うかもしれない。制約は、各コンコースに少なくとも1台のカメラを設置することかもしれない。

最適化問題がいかに複雑なものになりうるかは容易に理解できる。フェデックスのトラックは50カ所に停車するため、約30兆
(3×10^64)ものオプションが考えられます。最適化が妥当な時間で完了できたとしても、急にやり直しが必要になるかもしれません:ルート上で大渋滞が発生した、資産の価格が下がって購入の魅力が増した、などだ。

しかし、問題が難しい場合、それを解決することで大きな報酬が得られる可能性がある。最適化されたルーティングによって燃料費を15%節約した物流会社は、利益を増やし、市場シェアを拡大することができる。最適なポートフォリオは、顧客にとっても、ポートフォリオ・マネージャーにとっても、そしてその雇用主にとっても良いことである。

これらの問題を解くことの難しさと、最適な答えを得ることによる見返りが、企業が量子コンピューティングを検討する主な理由です。ボストンコンサルティンググループは最近、量子コンピュータを使った最適化問題の解決で解き放たれる価値は1,100~2,000億ドルに上ると推定しています。

Classiqとの組み合わせはこんな感じ:

空港のセキュリティ問題を考えてみよう。この種の問題は「最大頂点カバー」問題として知られている。 

ユーザーは空港の構成やフロアプラン、使用するカメラの台数を指定すると、Classiqの合成エンジンが問題の数学を設定する。 

専門用語で言えば、ユーザは重み付きエッジグラフと頂点カバーのサイズを提供します。Classiqは問題、制約、解を定義する関数を提供する。問題はQAOA(量子近似最適化アルゴリズム)を使って解かれる。これはハイブリッドなアルゴリズムで、量子的な部分(解や最適化したい期待値をエンコードする量子コスト関数、可能性のある解を探索する量子ミキサー関数、量子アサッツやパラメトリックな初期状態)と、古典的な最適化部分(我々の場合はPyomoパッケージを使用)があります。

ここでは、下の写真のような3つの外側ノードを持つスター・グラフを指定する。便宜上、各ノードには番号を付けました。カメラが1台しかない場合、空港の全エリアをカバーする位置は?


import networkx as nx
import pyomo.core as pyo
from classiq import combinatorial_optimization
from classiq_interface.combinatorial_optimization.preferences import QAOAPreferences
from classiq_interface.combinatorial_optimization.solver_types import QSolver


def mvc(graph: nx.Graph, k: int) -> pyo.ConcreteModel:
    model = pyo.ConcreteModel()
    model.x = pyo.Var(graph.nodes, domain=pyo.Binary)
    model.amount_constraint = pyo.Constraint(expr=sum(model.x.values()) == k)

    def obj_expression(model):
        return sum((1 - model.x[i]) * (1 - model.x[j]) for i, j in graph.edges)

    model.cost = pyo.Objective(rule=obj_expression, sense=pyo.minimize)

    モデルを返す


G = nx.star_graph(3)
mvc_model = mvc(G, 1)

qaoaP = QAOAPreferences(qsolver=QSolver.QAOAMixer)
mvc_problem = combinatorial_optimization.CombinatorialOptimization(model=mvc_model、
                                                                   qaoa_preferences=qaoaP)
qc = mvc_problem.generate()
qc.show_interactive()

open("MVC_interactive_circuit.html", "w").write(qc.interactive_html)

result = mvc_problem.solve()
print(result)
NetworkXパッケージで生成されたスターグラフ

回路を生成すると、インタラクティブな回路が新しいウィンドウにポップアップ表示される。回路の構造がはっきりと見え、左上のプラスアイコンをクリックすることで、回路のどの部分にも深く入り込むことができる。

クラシックのロゴ

スクリプトにエラーがありました

この回路をQAOAで実行し、結果を印刷すると、このような解が得られる(アルゴリズムが「コスト」関数を最小化するように動作するため、この解が選択される)。

このリストはカメラの位置候補に対応しているので、位置0、つまり中央のノードにはカメラがあるはずだ。

別のグラフを使った解答はこんな感じです。角がないことを確認できますか?

トゥーラン・グラフの最適解:(1, 1, 0, 0, 0, 0, 0, 1, 0)

Classiqプラットフォームが御社にどのようなサービスを提供できるかご興味がおありですか?デモのご予約はこちらから

"キュービット・ガイのポッドキャスト "について

The Qubit Guy(弊社最高マーケティング責任者ユヴァル・ボーガー)がホストを務めるこのポッドキャストは、量子コンピューティングのオピニオンリーダーをゲストに迎え、量子コンピューティングエコシステムに影響を与えるビジネスや技術的な疑問について議論します。ゲストは、量子コンピュータのソフトウェアやアルゴリズム、量子コンピュータのハードウェア、量子コンピューティングの主要なアプリケーション、量子産業の市場調査などについて興味深い見解を提供します。

ポッドキャストへのゲスト推薦をご希望の方は、こちらまでご連絡ください。

量子ソフトウェア開発を開始

お問い合わせ