(57)【要約】複数の変数にわたっての離散的最適化を伴う問題について前処理を行うための方法を開示する。該方法は、離散的最適化を伴う問題についての指示を取得するステップと、離散的最適化を伴う問題を最適化オラクルの所定の最適化オラクルアーキテクチャに適した問題に変換するステップと、所定回数たるＭ回にわたって所定の最適化オラクルアーキテクチャに適した問題を最適化オラクルに提供するステップと、問題の提供毎に最適化オラクルに対しての所定個数たるＫ個のコールを行うステップであって各コールは所定のコンフィギュレーションを生成するステップと、変数選択基準を取得するステップであって変数選択基準は複数の生成済みコンフィギュレーションの固定することができる少なくとも１つの変数を決定するためのものであるステップと、変数選択基準に合致する少なくとも１つの変数と各変数についての対応する値とを決定するステップと、離散的最適化を伴う問題に関して少なくとも１つの決定された変数を対応する値に固定してそれによって問題を前処理して少なくとも１つの下位問題を生成するステップと、少なくとも１つの生成済み下位問題についての指示と少なくとも１つの固定済み変数についての指示とを提供するステップとを含む。【選択図】図１
2019512779.tif 000002
【特許請求の範囲】
【請求項１】
複数の変数にわたっての離散的最適化を伴う問題について前処理を行うための方法であって、該方法は、
デジタルコンピュータを用いて、離散的最適化を伴う問題についての指示を、取得するステップと、
前記デジタルコンピュータを用いて、前記離散的最適化を伴う問題を、最適化オラクルの所定の最適化オラクルアーキテクチャに適した問題に変換するステップと、
前記デジタルコンピュータを用いて、所定回数たるＭ回にわたって前記所定の最適化オラクルアーキテクチャに適した前記問題を前記最適化オラクルに提供するステップと、
前記問題の提供毎に、前記最適化オラクルを用いて、前記最適化オラクルに対しての所定個数たるＫ個のコールを行うステップであって、前記最適化オラクルに対しての各コールは所定のコンフィギュレーションを生成する、ステップと、
前記デジタルコンピュータを用いて、変数選択基準を取得するステップであって、前記変数選択基準は複数の生成済みコンフィギュレーションの固定されるべき少なくとも１つの変数を決定するためのものである、ステップと、
前記デジタルコンピュータを用いて、前記変数選択基準に合致する少なくとも１つの変数と各変数についての対応する値とを決定するステップと、
前記デジタルコンピュータを用いて、前記離散的最適化を伴う問題に関して前記少なくとも１つの決定された変数を前記対応する値に固定して、それによって前記問題を前処理して、少なくとも１つの下位問題を生成するステップと、
前記デジタルコンピュータを用いて、前記少なくとも１つの生成済み下位問題についての指示と前記少なくとも１つの固定済み変数についての指示とを提供するステップとを含む、方法。
【請求項２】
請求項１に記載の方法において、前記離散的最適化を伴う問題は２次無制約２値最適化問題及びイジング問題の１つを含む、方法。
【請求項３】
請求項１に記載の方法において、前記最適化オラクルは量子アニーラを含む、方法。
【請求項４】
請求項１〜３のいずれか１つに記載の方法において、前記所定回数たるＭ回にわたって前記所定の最適化オラクルアーキテクチャに適した前記問題を前記最適化オラクルに提供するステップは、並列的に行われる、方法。
【請求項５】
請求項３に記載の方法において、前記最適化オラクルに対しての所定個数たるＫ個のコールを行うステップは、ランダムなゲージを用いて行われる、方法。
【請求項６】
請求項１〜５のいずれか１つに記載の方法において、前記複数の生成済みコンフィギュレーションの所定変数が前記変数選択基準を満たすのは、前記所定変数についての対応する値が前記複数の生成済みコンフィギュレーションの丁度全てにおいて変化しないこととなる場合とされる、方法。
【請求項７】
請求項１〜５のいずれか１つに記載の方法において、前記複数の生成済みコンフィギュレーションの所定変数が前記変数選択基準を満たすのは、前記所定変数についての対応する値が前記複数の生成済みコンフィギュレーションの絶対的多数において変化しないこととなる場合とされる、方法。
【請求項８】
請求項７に記載の方法において、前記複数の生成済みコンフィギュレーションの前記絶対的多数は、ユーザによって定義される、方法。
【請求項９】
複数の変数にわたっての離散的最適化を伴う問題を解くための方法であって、該方法は、
デジタルコンピュータを用いて、複数の変数にわたっての離散的最適化を伴う問題についての指示を、受信するステップと、
終了基準が充足されるまでは：
複数の変数にわたっての離散的最適化を伴う問題を、請求項１〜８のいずれか１つに記載の方法を用いて、再帰的に前処理して、複数の下位問題を生成するステップと、
複数の対応する解を提供するために前記複数の生成済み下位問題の各々を解くステップと、
前記デジタルコンピュータを用いて、前記複数の対応する解を提供するステップとを含む、方法。
【請求項１０】
請求項９に記載の複数の変数にわたっての離散的最適化を伴う問題を解くための方法において、前記終了基準が満たされるのは、前記複数の生成済み下位問題の変数個数が所定変数個数よりも小さい場合とされる、方法。
【請求項１１】
請求項９に記載の複数の変数にわたっての離散的最適化を伴う問題を解くための方法において、前記終了基準が満たされるのは、所定量のサイズ削減が前記離散的最適化を伴う問題について達成された場合とされる、方法。
【請求項１２】
請求項９に記載の複数の変数にわたっての離散的最適化を伴う問題を解くための方法において、前記終了基準が満たされるのは、効率的最適化問題ソルバを用いて前記複数の生成済み下位問題を解くことが可能となっている場合とされる、方法。
【請求項１３】
請求項９〜１１のいずれか１つに記載の複数の変数にわたっての離散的最適化を伴う問題を解くための方法において、前記複数の生成済み下位問題の各々について行う解決は、前記最適化オラクルを用いて行われる、方法。
【請求項１４】
請求項９〜１２のいずれか１つに記載の複数の変数にわたっての離散的最適化を伴う問題を解くための方法において、前記複数の生成済み下位問題の各々について行う解決は、前記デジタルコンピュータを用いて行われる、方法。
【請求項１５】
請求項９〜１４のいずれか１つに記載の複数の変数にわたっての離散的最適化を伴う問題を解くための方法において、前記複数の対応する解は、前記デジタルコンピュータと対話しているユーザに対して提供される、方法。
【請求項１６】
請求項９〜１４のいずれか１つに記載の複数の変数にわたっての離散的最適化を伴う問題を解くための方法において、前記複数の対応する解を提供するステップは、前記デジタルコンピュータと動作可能に接続された別のコンピュータに前記複数の対応する解を提供することを含む、方法。
【請求項１７】
請求項９〜１１のいずれか１つに記載の複数の変数にわたっての離散的最適化を伴う問題を解くための方法において、前記複数の下位問題の各々を解くステップは：
前記デジタルコンピュータを用いて、少なくとも１つの下位問題の第１群を前記最適化オラクルに提供するステップと、
前記デジタルコンピュータを用いて、前記最適化オラクルから、前記第１群の下位問題の各々についての解を取得するステップと、
前記デジタルコンピュータを用いて、少なくとも１つの下位問題の第２群を古典型ソルバに提供するステップと、
前記デジタルコンピュータを用いて、前記古典型ソルバから、前記第２群の前記下位問題の各々について少なくとも１つの対応する解を取得するステップとを含む、方法。
【請求項１８】
請求項１７に記載の複数の変数にわたっての離散的最適化を伴う問題を解くための方法において、少なくとも１つの下位問題の前記第１群及び少なくとも１つの下位問題の前記第２群は、前記複数の下位問題のサイズに基づいて決定される、方法。
【請求項１９】
デジタルコンピュータであって、
中央処理装置と、
表示装置と、
前記デジタルコンピュータを最適化オラクルと動作可能に接続するための通信ポートと、
複数の変数にわたっての離散的最適化を伴う問題を前処理するためのアプリケーションを含むメモリ装置であって、該アプリケーションは：
離散的最適化を伴う問題についての指示を取得するための命令と、
前記離散的最適化を伴う問題を、前記最適化オラクルの所定の最適化オラクルアーキテクチャに適した問題に変換するための命令と、
所定回数たるＭ回にわたって前記所定の最適化オラクルアーキテクチャに適した前記問題を前記最適化オラクルに提供するための命令と、
前記最適化オラクルから、前記問題の提供毎に複数のコンフィギュレーションを取得するための命令であって、各コンフィギュレーションは前記最適化オラクルに対してのコールによって生成される、命令と、
変数選択基準を取得するための命令であって、前記変数選択基準は複数の生成済みコンフィギュレーションの固定されるべき少なくとも１つの変数を決定するためのものである、命令と、
前記変数選択基準に合致する少なくとも１つの変数と各変数についての対応する値とを決定するための命令と、
前記離散的最適化を伴う問題に関して前記少なくとも１つの決定された変数を前記対応する値に固定して、それによって前記問題を前処理して、少なくとも１つの下位問題を生成するための命令と、
前記少なくとも１つの生成済み下位問題についての指示と前記少なくとも１つの固定済み変数についての指示とを提供するための命令とを含む、メモリ装置と、
前記中央処理装置と前記表示装置と前記通信ポートと前記メモリ装置とを相互接続するためのデータバスとを含む、デジタルコンピュータ。
【請求項２０】
コンピュータ実行可能命令を格納するための非一時的コンピュータ可読記憶媒体であって、該命令が実行されると複数の変数にわたっての離散的最適化を伴う問題について前処理を行うための方法をデジタルコンピュータに行わせることになり、該方法は、
離散的最適化を伴う問題についての指示を取得するステップと、
前記離散的最適化を伴う問題を、前記最適化オラクルの所定の最適化オラクルアーキテクチャに適した問題に変換するステップと、
所定回数たるＭ回にわたって前記所定の最適化オラクルアーキテクチャに適した前記問題を前記最適化オラクルに提供するステップと、
前記最適化オラクルから、前記問題の提供毎に複数のコンフィギュレーションを取得するステップであって、各コンフィギュレーションは前記最適化オラクルに対してのコールによって生成される、ステップと、
変数選択基準を取得するステップであって、前記変数選択基準は複数の生成済みコンフィギュレーションの固定されるべき少なくとも１つの変数を決定するためのものである、ステップと、
前記変数選択基準に合致する少なくとも１つの変数と各変数についての対応する値とを決定するステップと、
前記離散的最適化を伴う問題に関して前記少なくとも１つの決定された変数を前記対応する値に固定して、それによって前記問題を前処理して、少なくとも１つの下位問題を生成するステップと、
前記少なくとも１つの生成済み下位問題についての指示と前記少なくとも１つの固定済み変数についての指示とを提供するステップとを含む、非一時的コンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はコンピューティングに関する。より正確には、本発明は離散的最適化を伴う問題を複数のより小さな下位問題に分解する方法及びシステム並びに問題を解くためのそれらの使用に関する。
【０００２】
関連出願への相互参照
本願は２０１６年３月２日に出願された米国仮特許出願第６２／３０２，４３７号の優先権を主張する。
【背景技術】
【０００３】
多くの興味深くまた重要な現実世界の問題を離散的最適化問題（discrete optimization problem）として定式化できるのであり、例えばポートフォリオ最適化とかオンライン取引用の詐欺検出やソーシャルネットワーク内でのコミュニティ検出等のリスク管理問題とかがこれにあたる。
【０００４】
これら現実世界の問題の多くは一般的にはＮＰ困難な問題であり、即ち最適解を発見するために要する時間が問題サイズとの関係で指数関数的に増大する。したがって、解の最適性を犠牲にして効率性を求めるヒューリスティック法を用いでもしない限り、大規模な実際的問題は扱えない。
【０００５】
上述の欠点の少なくとも１つを克服するような方法及びシステムが必要とされている。
【０００６】
本発明についての以下の本願開示、図面及び詳細な説明を検討することによって、本発明の特徴が明らかとなる。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Minor-Embedding in Adiabatic Quantum Computation: I. The Parameter Setting Problem. Quantum Information Processing, Volume 7, Number 5, 2008, pp. 193 209. arXiv:quant-ph/0804.4884
【非特許文献２】Quantum Annealing Correction with Minor Embedding, Phy. Rev. A 92, 042310 (2015), arXiv:quant-ph/1507.0265
【発明の概要】
【０００８】
広範な態様によれば、次の方法が開示されている：複数の変数にわたっての離散的最適化を伴う問題について前処理を行うための方法であって、該方法は、デジタルコンピュータを用いて離散的最適化を伴う問題についての指示を取得するステップと、デジタルコンピュータを用いて離散的最適化を伴う問題を最適化オラクルの所定の最適化オラクルアーキテクチャに適した問題に変換するステップと、デジタルコンピュータを用いて所定回数たるＭ回にわたって所定の最適化オラクルアーキテクチャに適した問題を最適化オラクルに提供するステップと、問題の提供毎に最適化オラクルを用いて最適化オラクルに対しての所定個数たるＫ個のコールを行うステップであって最適化オラクルに対しての各コールは所定のコンフィギュレーションを生成するステップと、デジタルコンピュータを用いて変数選択基準を取得するステップであって変数選択基準は複数の生成済みコンフィギュレーションの固定されるべき少なくとも１つの変数を決定するためのものであるステップと、デジタルコンピュータを用いて変数選択基準に合致する少なくとも１つの変数と各変数についての対応する値とを決定するステップと、デジタルコンピュータを用いて離散的最適化を伴う問題に関して少なくとも１つの決定された変数を対応する値に固定してそれによって問題を前処理して少なくとも１つの下位問題を生成するステップと、デジタルコンピュータを用いて少なくとも１つの生成済み下位問題についての指示と少なくとも１つの固定済み変数についての指示とを提供するステップとを含む、方法。
【０００９】
実施形態によれば、離散的最適化を伴う問題は２次無制約２値最適化問題（Quadratic Unconstrained Binary Optimization）及びイジング（Ising）問題の１つを含む。
【００１０】
実施形態によれば、最適化オラクルは量子アニーラを含む。
【００１１】
実施形態によれば、所定回数たるＭ回にわたって所定の最適化オラクルアーキテクチャに適した問題を最適化オラクルに提供するステップは、並列的に行われる。
【００１２】
実施形態によれば、最適化オラクルに対しての所定個数たるＫ個のコールを行うステップは、ランダムなゲージを用いて行われる。
【００１３】
実施形態によれば、複数の生成済みコンフィギュレーションの所定変数が変数選択基準を満たすのは、所定変数についての対応する値が複数の生成済みコンフィギュレーションの丁度全てにおいて変化しないこととなる場合とされる。
【００１４】
実施形態によれば、複数の生成済みコンフィギュレーションの所定変数が変数選択基準を満たすのは、所定変数についての対応する値が複数の生成済みコンフィギュレーションの絶対的多数において変化しないこととなる場合とされる。
【００１５】
実施形態によれば、複数の生成済みコンフィギュレーションの絶対的多数は、ユーザによって定義される。
【００１６】
実施形態によれば、次の方法が開示されている。即ち、複数の変数にわたっての離散的最適化を伴う問題を解くための方法であって該方法は、デジタルコンピュータを用いて複数の変数にわたっての離散的最適化を伴う問題についての指示を受信するステップと、終了基準が充足されるまでは：複数の変数にわたっての離散的最適化を伴う問題を本願記載の方法を用いて再帰的に前処理して複数の下位問題を生成するステップと、複数の対応する解を提供するために複数の生成済み下位問題の各々を解くステップと、デジタルコンピュータを用いて複数の対応する解を提供するステップとを含む、方法。
【００１７】
実施形態によれば、終了基準が満たされるのは、複数の生成済み下位問題の変数個数が所定変数個数よりも小さい場合とされる。
【００１８】
実施形態によれば、終了基準が満たされるのは、所定量のサイズ削減が離散的最適化を伴う問題について達成された場合とされる。
【００１９】
実施形態によれば、終了基準が満たされるのは、効率的最適化問題ソルバを用いて複数の生成済み下位問題を解くことが可能となっている場合とされる。
【００２０】
実施形態によれば、複数の生成済み下位問題の各々について行う解決は、最適化オラクルを用いて行われる。
【００２１】
実施形態によれば、複数の生成済み下位問題の各々について行う解決は、デジタルコンピュータを用いて行われる。
【００２２】
実施形態によれば、複数の対応する解は、デジタルコンピュータと対話しているユーザに対して提供される。
【００２３】
実施形態によれば、複数の対応する解を提供するステップは、デジタルコンピュータと動作可能に接続された別のコンピュータに複数の対応する解を提供することを含む。
【００２４】
実施形態によれば、複数の下位問題の各々を解くステップは、デジタルコンピュータを用いて少なくとも１つの下位問題の第１群を最適化オラクルに提供するステップと、デジタルコンピュータを用いて最適化オラクルから第１群の下位問題の各々についての解を取得するステップと、デジタルコンピュータを用いて少なくとも１つの下位問題の第２群を古典型ソルバに提供するステップと、デジタルコンピュータを用いて古典型ソルバから第２群の下位問題の各々について少なくとも１つの対応する解を取得するステップとを含む。
【００２５】
実施形態によれば、少なくとも１つの下位問題の第１群及び少なくとも１つの下位問題の第２群は、複数の下位問題のサイズに基づいて決定される。
【００２６】
広範な態様によれば、次のデジタルコンピュータが開示されている。即ち、デジタルコンピュータであって、中央処理装置と、表示装置と、デジタルコンピュータを最適化オラクルと動作可能に接続するための通信ポートと、複数の変数にわたっての離散的最適化を伴う問題を前処理するためのアプリケーションを含むメモリ装置であって、該アプリケーションは、離散的最適化を伴う問題についての指示を取得するための命令と、離散的最適化を伴う問題を最適化オラクルの所定の最適化オラクルアーキテクチャに適した問題に変換するための命令と、所定回数たるＭ回にわたって所定の最適化オラクルアーキテクチャに適した問題を最適化オラクルに提供するための命令と、最適化オラクルから問題の提供毎に複数のコンフィギュレーションを取得するための命令であって各コンフィギュレーションは最適化オラクルに対してのコールによって生成される命令と、変数選択基準を取得するための命令であって変数選択基準は複数の生成済みコンフィギュレーションの固定されるべき少なくとも１つの変数を決定するためのものである命令と、変数選択基準に合致する少なくとも１つの変数と各変数についての対応する値とを決定するための命令と、離散的最適化を伴う問題に関して少なくとも１つの決定された変数を対応する値に固定してそれによって問題を前処理して少なくとも１つの下位問題を生成するための命令と、少なくとも１つの生成済み下位問題についての指示と少なくとも１つの固定済み変数についての指示とを提供するための命令とを含む、メモリ装置と、中央処理装置と表示装置と通信ポートとメモリ装置とを相互接続するためのデータバスとを含む、デジタルコンピュータ。
【００２７】
広範な態様によれば、次の非一時的コンピュータ可読記憶媒体が開示されている。即ち、コンピュータ実行可能命令を格納するための非一時的コンピュータ可読記憶媒体であって該命令が実行されると複数の変数にわたっての離散的最適化を伴う問題について前処理を行うための方法をデジタルコンピュータに行わせることになり、該方法は、離散的最適化を伴う問題についての指示を取得するステップと、離散的最適化を伴う問題を最適化オラクルの所定の最適化オラクルアーキテクチャに適した問題に変換するステップと、所定回数たるＭ回にわたって所定の最適化オラクルアーキテクチャに適した問題を最適化オラクルに提供するステップと、最適化オラクルから問題の提供毎に複数のコンフィギュレーションを取得するステップであって各コンフィギュレーションは最適化オラクルに対してのコールによって生成されるステップと、変数選択基準を取得するステップであって変数選択基準は複数の生成済みコンフィギュレーションの固定されるべき少なくとも１つの変数を決定するためのものであるステップと、変数選択基準に合致する少なくとも１つの変数と各変数についての対応する値とを決定するステップと、離散的最適化を伴う問題に関して少なくとも１つの決定された変数を対応する値に固定してそれによって問題を前処理して少なくとも１つの下位問題を生成するステップと、少なくとも１つの生成済み下位問題についての指示と少なくとも１つの固定済み変数についての指示とを提供するステップとを含む、非一時的コンピュータ可読記憶媒体。
【００２８】
本願開示の方法の利点としては、準最適な又は最適解に近い解を探索した後に、離散的最適化を伴う問題の変数の部分集合の値に関して固定することによって、離散的最適化を伴う問題のサイズを減じることができるということが挙げられる。結果、問題は、離散的最適化を伴う少なくとも１つの下位問題に減じ得る。これによって、離散的最適化を伴い且つサイズが大きい問題を解くという技術的課題が解決される。
【００２９】
本願開示の方法の利点としては、準最適オラクルを用いて大きな問題をより小さい下位問題へと分解することが可能となる、ということが挙げられる。本願開示の方法の別の利点としては、次の技術的課題の解決がもたらされるということが挙げられる：即ち、離散的最適化を伴う大規模な問題を解くに際して準最適オラクルを用いることができないという課題。
【００３０】
本願開示の方法の別の利点としては、離散的最適化を伴う大規模な問題を有利な態様でより小さい下位問題へと分解することが可能となることによって、最適化問題を解決するために用いられるシステムの処理態様を著しく向上させることができるということが挙げられる。
【図面の簡単な説明】
【００３１】
発明の理解が容易となるようにするために、添付の図面を伴って本発明の実施形態について例示的に示す。
本発明のさらなる詳細及びそれらの利点は、後述の詳細な説明から明らかとなる。
【００３２】
【図１】離散的最適化を伴う問題を少なくとも１つの離散的最適化を伴う下位問題へと前処理する実施形態を示す流れ図である。
【図２】離散的最適化を伴う問題を解くための方法についての実施形態を示す流れ図であって、図１に開示されている前処理方法は再帰的に行われる、流れ図である。
【図３】システムについての実施形態を示すブロック図であって、システムにおいては離散的最適化を伴う問題を解くための方法が実施され得る、ブロック図であり、システムはデジタルコンピュータと最適化オラクルとを備える。
【図４】図３に開示されているシステム内において使用され得るデジタルコンピュータについての実施形態を示すブロック図である。
【発明を実施するための形態】
【００３３】
実施形態についての以下の説明においては、添付の図面への言及は事例に関しての例示としてされているのであり、これらは本発明を実施し得る態様を示している。
【００３４】
用語
「発明」等の語は、「本願にて開示される１つ以上の発明」を意味するが、明示的に別段の定めがされている場合はこの限りでない。
【００３５】
「態様」、不定冠詞を伴う「実施形態」、無冠詞の「実施形態」、無冠詞複数形の「実施形態」、定冠詞を伴う「実施形態」、定冠詞を伴う複数形の「実施形態」、「１つ以上の実施形態」、「幾つかの実施形態」、「特定の実施形態」、「或る実施形態」、「別の実施形態」等の語は、「本願開示の発明の１つ以上（但し、全部ではない）」を意味するが、明示的に別段の定めがされている場合はこの限りでない。
【００３６】
実施形態について説明するに際して「別の実施形態」や「別の態様」に言及しても、被言及側の実施形態が別の実施形態（例えば、被参照側実施形態の前に説明された実施形態）と相互排反的であることを暗示するわけではないが、明示的に別段の定めがされている場合はこの限りでない。
【００３７】
「含む」、「備える」、及びこれらのバリエーションは「含むがこれらには限られない」とのことを意味するが、明示的に別段の定めがされている場合はこの限りでない。
【００３８】
「不定冠詞たるa」、「不定冠詞たるan」及び「定冠詞たるthe」との語は、「１つ以上」を意味するが、明示的に別段の定めがされている場合はこの限りでない。
【００３９】
「複数」との語は「２つ以上」を意味するが、明示的に別段の定めがされている場合はこの限りでない。
【００４０】
「ここで」との語は「本願において、そして参照によって取り込まれる任意のものを含む」とのことを意味するが、明示的に別段の定めがされている場合はこの限りでない。
【００４１】
「これによって」との語は、明示的に先述されたものについての意図された結果、目的又は帰結のみを表す節又は他の単語群を先行するようにしてのみ用いられる。したがって、「これによって」との語が請求項にて用いられる場合においては、「これによって」が修飾する節又は他の語群は、請求項についての更なる具体的限定を確立せず、また、請求項の意義若しくは範囲を他の態様で限定はしない。
【００４２】
「exempli gratis」等の語は「例えば」を意味するのであり、説明される語又はフレーズを限定はしない。例えば、「コンピュータはインターネット上にデータ（e.g.，命令やデータ構造）を送る」とのセンテンスにおいては、「e.g.」との語は「命令」というものがコンピュータによってインターネット上に送られ得る「データ」の例であることを説明し、また、「データ構造」というものがコンピュータによってインターネット上に送られ得る「データ」の例であることをも説明する。もっとも、「命令」も「データ構造」も「データ」の例に過ぎず、「データ構造」や「データ」以外のものも「データ」たり得る。
【００４３】
「id est」等の語は「即ち」を意味するのであり、説明される語又はフレーズを限定する。
【００４４】
「離散的最適化問題」との語は、問題の変数が、連続的な値ではなく、離散的な値をとる類いの問題を意味する。
【００４５】
「最適化オラクル」等の語は、最適化問題について最適に近い（即ち、準最適な）解をもたらすことができるマシン又はアルゴリズムを意味する。
【００４６】
「地形（landscape）」等の語は、最適化問題の変数についての可能なコンフィギュレーションの全てを含む集合を意味する。
【００４７】
「最適に近い地形」及び「準最適地形」との語は、変数の目的関数値が最適解の値に十分に近いような、最適化問題の変数についての可能な実現可能コンフィギュレーション（possible feasible configuration）の全てを含む集合を意味する。
【００４８】
「準最適オラクル」等の語は、特定の確率で最適解を返し、その余の場合は準最適解（最適ではないが最適解に近い解）を返すようなオラクルを意味する。
【００４９】
発明の名称及び要約のいずれも、何らの観点からも、開示された発明の範囲を限定するために用いられてはならない。本願の発明の名称及び明細書中の項目名は利便性のためだけに付されているのであり、何らの観点からも開示内容を限定するものとして用いられてはならない。
【００５０】
本願においては様々な実施形態が説明されており、例示的目的のみのために提示されている。説明された実施形態は何らの意味合いにおいても限定的なものではなく、またそのような意図すらないことに留意されたい。開示内容から明らかなように、開示されている発明は様々な実施形態に適用可能である。当業者であれば、開示されている発明には構造的な変更や論理的な変更等の様々な変更や改変を加えた上で実施することができることに気付くであろう。開示されている発明の特定の特徴は１つ以上の特定の実施形態及び／又は図面との関係で説明されている場合があり得るが、そのような特徴はそれらの説明に際して参照される特定の実施形態や図面における用例に限定されないことに留意されたい。もっとも、明示的に別段の定めがされている場合はこの限りでない。
【００５１】
本発明は様々な態様で実施されることができ、これらには方法やシステムやコンピュータ可読媒体（例えば、コンピュータ可読記憶媒体）が含まれる。本明細書においては、これらの実施態様及び本発明が取り得る他の任意の形式を、システムや手法と称することができることに留意されたい。あるタスクを行うように構成されているものとして説明されているプロセッサやメモリ等のコンポーネントには、次のいずれもが含まれ得る：所定の時期においてタスクを行うように一時的に構成されている汎用コンポーネント、及び、タスクを行うように製造された具体的コンポーネント。
【００５２】
上記全てを考慮に入れた上で、以下において本発明は、離散的最適化を伴う問題を複数のより小さい下位問題へと分解するための方法及びシステムに関する発明並びに離散的最適化を伴う問題を解くためのそれらの使用について説明する。
【００５３】
図１を参照するところ、処理ステップ１００によれば、離散的最適化問題を伴う問題についての指示を、入力として入手する。
【００５４】
離散的最適化を伴う問題は様々な種類のものであり得ることが理解されるであろう。実際に、離散的最適化を伴う問題が非線形整数計画問題であることができる。
【００５５】
１つの実施形態では、離散的最適化を伴う問題は、２次無制約最適化（quadratic unconstrained optimization）（QUBO）問題を含む。
【００５６】
代替の実施形態では、離散的最適化を伴う問題は、イジング（Ising）問題を含む。
【００５７】
１つの実施形態では、離散的最適化を伴う問題についての指示は、デジタルコンピュータを用いて取得される。
【００５８】
処理ステップ１０２では、離散的最適化を伴う問題は、最適化オラクルの所定の最適化オラクルアーキテクチャに適した問題に変換される。
【００５９】
１つの実施形態では、離散的最適化を伴う問題は、デジタルコンピュータを用いて、最適化オラクルの所定の最適化オラクルアーキテクチャに適した問題に変換される。
【００６０】
１つの実施形態では、最適化オラクルは、例えばD Wave 2Xマシン等の量子アニーラである。別の代替的実施形態では、最適化オラクルは次のものからなる群から選択される：シミュレーションされた焼き鈍しアルゴリズム（simulated annealing algorithm）、経路積分量子モンテカルロアルゴリズム（path integral quantum Monte-Carlo algorithm）、及び並列焼き戻しアルゴリズム（parallel tempering algorithm）。
【００６１】
このような実施形態では、２次無制約最適化（ＱＵＢＯ）問題又はイジング問題は、D Wave 2Xマシンの構造と互換性があるイジング問題へと変形される。
【００６２】
場合によっては、問題を（最適化オラクルの）アーキテクチャ適合型問題へと変形するために、問題について軽度の埋め込みを用いることを要するかもしれない。
【００６３】
この処理ステップに続いて、最適化オラクルを用いて、離散的最適化を伴う問題の準最適又は最適に近い地形（landscape）を探索するのであり、これによって固定できる変数についての指示を取得するのであり、この点の詳細については後述参照。
【００６４】
実際のところ、準最適地形の探索の目的は、離散的最適化を伴う問題の変数のうちどれについて最適化オラクルを用いて固定できるかを見出すことにある。
【００６５】
より正確には、そして処理ステップ１０４によれば、所定の最適化オラクルアーキテクチャに適した問題を、所定回数たるＭ回にわたって最適化オラクルに提供する。
【００６６】
１つの実施形態では、最適化オラクルからのＭ回のクエリは、並列で行われることに留意されたい。
【００６７】
別の実施形態では、Ｍ回のクエリは、一度に最適化オラクルへと送られることに留意されたい。
【００６８】
１つの実施形態では、デジタルコンピュータを用いて所定の最適化オラクルアーキテクチャに適した問題を最適化オラクルに提供する。
【００６９】
処理ステップ１０６によれば、最適化オラクルに対しての所定の最適化オラクルアーキテクチャに適した問題の提供毎に、最適化オラクルに対しての所定個数たるＫ個のコールを行う。
【００７０】
最適化オラクルに対して各コールは、所定のコンフィギュレーション（状態又は解ともいう。）を生成することに留意されたい。
【００７１】
１つの実施形態では、D Wave 2X量子アニーラを最適化オラクルとして用いるのであり、所定の最適化オラクルアーキテクチャに適した問題をＭ回送信するのであり、各回においてＫ回のアニーリングサイクルを伴う。１つの実施形態では、ランダムなゲージを量子アニーラに対しての各コールで用いるのであり、これは、マシンにおいてより良い性能を得るためになされるのであり、結果的には入力問題についてより高速でかつより良好な分解を達成するためになされる。
【００７２】
当業者であれば、ランダムなゲージとは、問題を等価な問題へと変形する可逆変形であるということが分かろう。変形された問題は異なる解を有するが、変形が可逆的である故に、変形された問題を解いた上で当初の問題の解へと逆戻りすることができる。
【００７３】
量子アニーラがコールされる度にランダムなゲージを用いることによって、性能を相当に向上させることができると理解される。
【００７４】
そして、量子アニーラから、Ｍ＊Ｋ個のコンフィギュレーションが取得されるということに留意されたい。
【００７５】
代替的実施形態では別の最適化オラクルを用いて準最適解又は最適解に近い解についてのサンプルをもたらすことが可能であるということに、当業者は気付くであろう。
【００７６】
処理ステップ１０８によれば、変数選択基準が取得される。
【００７７】
変数選択基準は、複数の生成済みコンフィギュレーションの固定可能な少なくとも１つの変数を決定するために用いられることに留意されたい。
【００７８】
１つの実施形態では、変数選択基準は、デジタルコンピュータを用いて取得される。
【００７９】
変数選択基準に関しては、様々な実施形態を持たし得ることに留意されたい。
【００８０】
１つの実施形態では、変数選択基準は、最も低い客観的関数値（lowest objective function value）を有するコンフィギュレーション群のみを返すのであり、例えば変数の少なくとも３０％が選択されている等が挙げられる。
【００８１】
１つの実施形態では、複数の生成済みコンフィギュレーションの所定変数が変数選択基準を満たすのは、所定コンフィギュレーションについての対応する値が複数の生成済みコンフィギュレーションの丁度全てにおいて変化しないこととなる場合とされる。
【００８２】
１つの実施形態では、変数選択基準（variable selection criterion）は変数選択基準から返されたコンフィギュレーションのみを考慮するのであり、それらのコンフィギュレーションの丁度全てにおいて対応する値が変化しないこととなる場合に、変数選択基準が満たされる。当業者であれば、コンフィギュレーション選択基準（configuration selection criterion）をユーザが定義できるということが分かるであろう。１つの実施形態では、コンフィギュレーション選択基準は、客観的関数値でいうと２０％パーセンタイルのコンフィギュレーションのみを返す。
【００８３】
最適化オラクルがD Wave 2X量子アニーラである場合、Ｍ＊Ｋのコンフィギュレーション全てにおいて自己の状態又は値を維持する量子ビットが選択される。
【００８４】
代替的実施形態では、変数選択基準は取得されたコンフィギュレーション全てを考慮するのであり、少なくとも１つの所定の変数について対応する値がコンフィギュレーションの絶対的多数において変化しない場合に、少なくとも１つの所定の変数がこれを満たすものとする。１つの実施形態では、絶対的多数はユーザによって定義され得るということを、当業者であれば分かるであろう。１つの実施形態では、絶対的多数は、コンフィギュレーションの９９％として定義される。
【００８５】
離散的最適化を伴う問題を所定の最適化オラクルアーキテクチャに適した問題に変形することによって次の制約に影響が及ぶことに留意されたい：最適化オラクルによってサンプリングされた異なる変数の観測値についての受容基準に関しての制約。
【００８６】
１つの実施形態では、最適化オラクルはD Wave 2X量子アニーラであり、一般的な問題については埋め込みを要し得る。当業者が知っているように、埋め込みプロセスにおいては、論理的な量子ビットを表すものとしての物理的な量子ビットの連鎖の作成が必要とされ得る。論理的な量子ビットの値を固定するために、取得された変数についての多数決を採用し得る（非特許文献１）。当業者であれば、論理的な量子ビットの値を決するに際しては色々な方法があることが分かろう。代替的実施形態では、このことを、エネルギーが最小化されるように値を反復的に割り当てることによって達成する（非特許文献２）。
【００８７】
１つの実施形態では、１つの実施形態では、D Wave 2X量子アニーラを、最適化オラクルとして用いるのであり、論理的な量子ビットは７つの物理的な量子ビットの連鎖で表される。１つの実施形態に関していえば、この処理ステップの結果から分かることは、連鎖内の７つの量子ビットのうち４つの量子ビットが、全てのコンフィギュレーションにて自己の値を維持したということである。この結果、論理的な量子ビットの値は、多数たるそれら４つの量子ビットに合わせて固定された。
【００８８】
処理ステップ１１０によれば、少なくとも１つの変数が変数選択基準に合致するのであり、各変数についての対応する値が決せられる。
【００８９】
１つの実施形態では、変数選択基準に合致する少なくとも１つの変数及び各変数についての対応する値の決定は、デジタルコンピュータを用いてなされる、ということに留意されたい。
【００９０】
処理ステップ１１２によれば、少なくとも１つの決定済み変数は、離散的最適化を伴う問題において対応する値に固定されて、問題が前処理されて少なくとも１つの下位問題が生成される。
【００９１】
１つの実施形態では、この処理ステップは、デジタルコンピュータを用いて行われる。
【００９２】
処理ステップ１１４によれば、少なくとも１つ生成済み下位問題の指示及び少なくとも１つの固定済み変数の指示が提供される。
【００９３】
１つの実施形態では、少なくとも１つの生成済み下位問題の指示及び少なくとも１つの固定済み変数の指示は、デジタルコンピュータを用いて提供される。
【００９４】
１つの実施形態では、そのような前処理がなされると問題のサイズが５０％減じられ得るということに留意されたい。
【００９５】
図２に転じるに、同図には複数の変数にわたっての離散的最適化を伴う問題を解くための方法に関する実施形態が示されている。後述のように、該方法は図１に開示されている前処理を活用している。
【００９６】
処理ステップ２００によれば、複数の変数にわたっての離散的最適化を伴う問題についての指示が受信される。
【００９７】
１つの実施形態では、デジタルコンピュータを用いて、複数の変数にわたっての離散的最適化を伴う問題についての指示が受信される。
【００９８】
処理ステップ２０２によれば、終了基準が充足されているかを見出すために、検査を行う。
【００９９】
１つの実施形態では、終了基準はユーザ定義型の終了基準である。
【０１００】
終了基準は、さらなる処理ステップを以後行わないかを決定するために用いる。上述のように、前処理ステップを再帰的に適用するのであり、これによって離散的最適化を伴う問題のサイズを減じて、より小さなサイズをもたらす。前処理ステップを、第１の前処理の結果に対してさらに適用することができ、サイズをさらに減じることができる。
【０１０１】
例えば、終了基準は、下位問題が所定の変数個数よりも少ない個数の変数を有している場合にさらなる前処理ステップを行わないものとして、定義され得るのであり、例えば変数１０個等とし得る。当業者であれば、所定の変数個数は別の個数とすることもできる、ということを理解するであろう。
【０１０２】
代替的実施形態では、終了基準は、前処理ステップが指定されたパーセントのサイズ減少を離散的最適化を伴う問題に関してもたらした場合として、定義され得る。例えば、問題サイズが少なくとも５％減じられていないのであれば、反復は完了される。
【０１０３】
別の代替的実施形態では、終了基準は、結果として生じた下位問題の複雑度が効率的最適化問題ソルバによって解かれ得る程度である場合（即ち、それが多項式時間で解かれ得る場合）にさらなる前処理がなされない、との基準として定義される。結果として生じた下位問題が平面構造を有している場合にこのようになり得る。
【０１０４】
終了基準が充足されない場合においては、処理ステップ５０によれば、問題は前処理されて複数の下位問題が生成（generate）される。
【０１０５】
１つの実施形態では、問題は、図１に開示の方法に従って前処理される。
【０１０６】
上述のように、問題の前処理によって、少なくとも１つの下位問題が作成（create）される。少なくとも１つの下位問題に対して前処理を再適用することによって、少なくとも１つの下位問題が作成される。既述のように、後続の下位問題に対して前処理を再帰的に適用して、終了基準が満たされるまでそうする。その結果、複数の下位問題が得られる。
【０１０７】
処理ステップ２１２によれば、複数の下位問題が解かれる。
【０１０８】
様々な実施形態に従って複数の下位問題を解くことができるということに留意されたい。
【０１０９】
特に、複数の下位問題を解くための１つの実施形態が、処理ステップ２０４，２０６，２０８にて開示されている。
【０１１０】
より正確には、そして終了基準が充足された場合において、そして処理ステップ２０４によれば、下位問題についての第１群を、最適化オラクルに提供する。
【０１１１】
実際のところ、最適化オラクルを用いて特定の問題を解くことが適切とされ得るのであり、他方では他の問題はデジタルコンピュータによって解かれ得る。したがって、下位問題の第１群を最適化オラクルに提供しつつ、下位問題の第２群をデジタルコンピュータに提供することができる。
【０１１２】
１つの実施形態では、或る下位問題が一方の群に属するか別の群に属するかの決定は、下位問題のサイズに基づいてなされ得る。例えば、第１群は、サイズが１５変数以上の問題で構成され得る。第２群は、サイズが１５変数未満の問題で構成され得る。
【０１１３】
結果生じる下位問題についてのソルバを指定するためには、ユーザ入力決定基準についての任意の組み合わせを用い得る点に留意されたい。
【０１１４】
実際のところ、１つの実施形態では、下位問題のサイズがとても小さく（so small）、網羅的探索が効率的な解法となり得る場合があり得る点に留意されたい。
【０１１５】
代替的実施形態では、問題のサイズが十分に小さく（small enough）ヒューリスティック法で効率的に最適点に至るように解き得る場合があることに留意されたいのであり、その際の成功確率が高いものとなり得る。
【０１１６】
代替的実施形態では、問題のサイズは十分に小さく、分枝限定法が効率的に解くことができる場合があり得ることに留意されたい。
【０１１７】
代替的実施形態では、下位問題が代替的なアーキテクチャを有しており、それによるとより低位な複雑度クラスに分類される場合があり得ることに留意されたい。下位問題は事例に固有なアルゴリズムで解かれることができる。
【０１１８】
代替的実施形態では、下位問題が平面グラフ構造を有している場合があることに留意されたい。最適化問題の多くの系統においては、平面グラフ構造を有するということは、問題がとても簡単であり低複雑度問題であることを意味する。よって、これらのインスタンスを多項式時間で解くアルゴリズムを見出し得る。
【０１１９】
代替的実施形態では、下位問題は、同じ最適化オラクル（この実施形態の場合においては量子アニーラ）がより簡単に解くことできるようになる表現形式を、有している場合があることに留意されたい。
【０１２０】
当初において問題が大きすぎて量子アニーラが正確に解くことができないほどに問題が難しい場合があり得る。それでも、量子アニーラは実際の解に近い良好な（準最適な）推測値をもたらす。開示の方法は、量子アニーラからのこれらの準最適解を用いて、当初の問題をより小さな下位問題へと分解するために用いられ得る。より小さい問題は、量子アニーラのスイートスポット内に収まる性質を有している場合があり、例えばそれらは間違いなく当初の問題よりも小さい。このことは、量子アニーラがこれらの問題を正確に解くことができる可能性がより高くなることを意味し得る。そうでなければ、同じプロセスの反復によって下位問題をさらに小さな断片に分解することができる。
【０１２１】
１つの実施形態では、デジタルコンピュータを用いて、下位問題の第１群を最適化オラクルに提供する。
【０１２２】
処理ステップ２０６によれば、各下位問題について解が受信される。
【０１２３】
１つの実施形態では、最適化オラクルから解がデジタルコンピュータによって受信される。
【０１２４】
図２について引き続き言及するに、そして処理ステップ２０８によれば、第２群の各下位問題が解かれる。
【０１２５】
１つの実施形態では、第２群の各下位問題は、デジタルコンピュータを用いて解かれる。
【０１２６】
複数の下位問題を解くための１つの実施形態について開示したものの、様々な他の実施形態に従って複数の下位問題について解くことも可能であるということにも留意されたい。
【０１２７】
例えば、代替的実施形態では、最適化オラクルのみを用いて複数の下位問題を解くことができる。
【０１２８】
別の代替的実施形態では、下位問題が十分に単純な場合、デジタルコンピュータのみを用いて複数の下位問題を解くことができる。
【０１２９】
処理ステップ２１０によれば、複数の下位問題の各々についての解が提供される。
【０１３０】
複数の下位問題の各々についての解が、様々な実施形態に従って提供され得ることに留意されたい。
【０１３１】
１つの実施形態では、複数の下位問題の各々についての解が、デジタルコンピュータと対話しているユーザに対して提供される。
【０１３２】
代替的実施形態では、複数の下位問題の各々についての解が、デジタルコンピュータと動作可能に接続された別のコンピュータに対して提供される。
【０１３３】
図３に転じるに、同図ではシステム３００が示されており、該システムにて、複数の変数にわたっての離散的最適化を伴う問題を解くための方法についての実施形態を、実施し得る。
【０１３４】
システム３００は、デジタルコンピュータ３０２と最適化オラクル３０４とを備える。
【０１３５】
デジタルコンピュータ３０２は、離散的最適化を伴う問題を受信し、また、少なくとも１つの解を提供する。
【０１３６】
様々な実施形態に従って離散的最適化を伴う問題を提供することができることに留意されたい。
【０１３７】
１つの実施形態では、離散的最適化を伴う問題は、デジタルコンピュータ３０２と対話しているユーザによって提供される。
【０１３８】
代替的には、離散的最適化を伴う問題は、デジタルコンピュータ３０２と動作可能に接続された不図示の別のコンピュータによって提供される。
【０１３９】
代替的には、離散的最適化を伴う問題は、独立のソフトウェアパッケージによって提供される。
【０１４０】
代替的には、離散的最適化を伴う問題は、インテリジェントエージェントによって提供される。
【０１４１】
同様に、様々な実施形態に従って少なくとも１つの解を提供することができることに留意されたい。
【０１４２】
或る実施形態によれば、少なくとも１つの解は、デジタルコンピュータ３０２と対話しているユーザに提供される。
【０１４３】
代替的には、少なくとも１つの解は、デジタルコンピュータ３０２と動作可能に接続された別のコンピュータに提供される。
【０１４４】
実際のところ、当業者であれば、デジタルコンピュータ３０２は任意のタイプのコンピュータとすることができることが分かるであろう。
【０１４５】
１つの実施形態では、デジタルコンピュータ３０２は次のものからなる群から選択される：デスクトップコンピュータ、ラップトップコンピュータ、タブレットコンピュータ、サーバ、スマートフォン等。
【０１４６】
そして、図４を参照するに、デジタルコンピュータ３０２についての実施形態が同図に示されている。デジタルコンピュータ３０２は、広い意味ではプロセッサとしても言及され得ることに留意されたい。
【０１４７】
この実施形態では、デジタルコンピュータ３０２は、マイクロプロセッサとも称される中央処理装置（ＣＰＵ）４０２と、表示装置４０４と、入力装置４０６と、通信ポート４０８と、データバス４１０と、メモリ装置４１２とを備える。
【０１４８】
ＣＰＵ４０２は、コンピュータ命令を処理するために用いられる。当業者にとっては、ＣＰＵについて様々な実施形態があり得るということが明らかである。
【０１４９】
１つの実施形態では、ＣＰＵ４０２は、インテル（登録商標）製の３．６ＧＨｚで稼働中のＣＰＵたるCore i7 3820である。
【０１５０】
表示装置４０４は、データをユーザに対して表示するために用いられる。当業者であれば、様々なタイプの表示装置４０４を用いることができることが分かろう。
【０１５１】
１つの実施形態では、表示装置４０４は標準的な液晶ディスプレイ（ＬＣＤ）モニタである。
【０１５２】
通信ポート４０８は、デジタルコンピュータ３０２とデータを共有するために用いられる。
【０１５３】
通信ポート４０８は、例えば、キーボード及びマウスをデジタルコンピュータ３０２に接続するためのユニバーサルシリアルバス（ＵＳＢ）ポートを備えることができる。
【０１５４】
通信ポート４０８は、データネットワーク通信ポートをさらに備えることができ、例えば、デジタルコンピュータ３０２と別のコンピュータとをデータネットワークを介して接続可能とするためのIEEE 802.3ポートが挙げられる。
【０１５５】
当業者であれば、通信ポート４０８については様々な代替的実施形態が可能であることが分かるであろう。
【０１５６】
１つの実施形態では、通信ポート４０８は、イーサネット（登録商標）ポート及びマウスポート（例えば、Logitech（登録商標））を含む。
【０１５７】
メモリ装置４１２は、コンピュータ実行可能命令を格納するために用いられる。
【０１５８】
１つの実施形態では、メモリ装置４１２は、オペレーティングシステムモジュール４１４を含む。
【０１５９】
当業者であれば、オペレーティングシステムモジュール４１４は様々なタイプのものとすることができることが分かるであろう。
【０１６０】
１つの実施形態では、オペレーティングシステムモジュール４１４は、マイクロソフト（登録商標）製のウインドウズ（登録商標）８とされる。
【０１６１】
メモリ装置４１２は、複数の変数にわたっての離散的最適化を伴う問題を前処理するためのアプリケーション４１６をさらに含む。
【０１６２】
複数の変数にわたっての離散的最適化を伴う問題を前処理するためのアプリケーション４１６は、次の命令を含む：離散的最適化を伴う問題を、最適化オラクルの所定の最適化オラクルアーキテクチャに適した問題に変換するための命令。
【０１６３】
複数の変数にわたっての離散的最適化を伴う問題を前処理するためのアプリケーション４１６は、次の命令をさらに含む：所定回数たるＭ回にわたって所定の最適化オラクルアーキテクチャに適した問題を最適化オラクルに提供するための命令。
【０１６４】
複数の変数にわたっての離散的最適化を伴う問題を前処理するためのアプリケーション４１６は、次の命令をさらに含む：最適化オラクルから、問題の提供毎に複数のコンフィギュレーションを取得するための命令であって、各コンフィギュレーションは最適化オラクルに対してのコールによって生成される、命令。
【０１６５】
複数の変数にわたっての離散的最適化を伴う問題を前処理するためのアプリケーション４１６は、次の命令をさらに含む：変数選択基準を取得するための命令であって、変数選択基準は複数の生成済みコンフィギュレーションを用いて固定することができる少なくとも１つの変数を決定するためのものである、命令。
【０１６６】
複数の変数にわたっての離散的最適化を伴う問題を前処理するためのアプリケーション４１６は、次の命令をさらに含む：変数選択基準に合致する少なくとも１つの変数と各変数についての対応する値とを決定するための命令。
【０１６７】
複数の変数にわたっての離散的最適化を伴う問題を前処理するためのアプリケーション４１６は、次の命令をさらに含む：離散的最適化を伴う問題に関して少なくとも１つの決定された変数を対応する値に固定して、それによって問題を前処理して、少なくとも１つの下位問題を生成するための命令。
【０１６８】
複数の変数にわたっての離散的最適化を伴う問題を前処理するためのアプリケーション４１６は、次の命令をさらに含む：少なくとも１つの生成済み下位問題についての指示と少なくとも１つの固定済み変数についての指示とを提供するための命令。
【０１６９】
メモリ装置４１２は、複数の変数にわたっての離散的最適化を伴う問題を解くためのアプリケーション４１８をさらに含む。
【０１７０】
複数の変数にわたっての離散的最適化を伴う問題を解くためのアプリケーション４１８は、次の命令を含む：複数の変数にわたっての離散的最適化を伴う問題についての指示を、受信するための命令。
【０１７１】
複数の変数にわたっての離散的最適化を伴う問題を解くためのアプリケーション４１８は、次の命令を含む：複数の変数にわたっての離散的最適化を伴う問題を前処理するためのアプリケーション４１６を用いて離散的最適化を伴う問題を前処理するための命令。
【０１７２】
複数の変数にわたっての離散的最適化を伴う問題を解くためのアプリケーション４１８は、次の命令をさらに含む：少なくとも１つの下位問題の第１群を最適化オラクルに提供するための命令。
【０１７３】
複数の変数にわたっての離散的最適化を伴う問題を解くためのアプリケーション４１８は、次の命令をさらに含む：第１群の下位問題の各々についての解を取得するための命令。
【０１７４】
複数の変数にわたっての離散的最適化を伴う問題を解くためのアプリケーション４１８は、次の命令をさらに含む：少なくとも１つの下位問題の第２群を効率的最適化問題ソルバに提供するための命令。１つの実施形態では、効率的最適化問題ソルバは、デジタルコンピュータ３０２である。
【０１７５】
複数の変数にわたっての離散的最適化を伴う問題を解くためのアプリケーション４１８は、次の命令をさらに含む：少なくとも１つの第２群の下位問題の各々について少なくとも１つの対応する解を取得するための命令。
【０１７６】
複数の変数にわたっての離散的最適化を伴う問題を解くためのアプリケーション４１８は、次の命令をさらに含む：少なくとも１つの第１群の下位問題の各々についての少なくとも１つの対応する解と、少なくとも１つの第２群の下位問題の各々についての少なくとも１つの対応する解とを提供するための命令。
【０１７７】
中央処理装置４０２、表示装置４０４、入力装置４０６、通信ポート４０８、及びメモリ装置４１２のそれぞれは、データバス４１０を介して相互接続されている。
【０１７８】
図３に戻るに、オラクル３０４は、デジタルコンピュータ３０２と動作可能な態様で接続されている。
【０１７９】
最適化オラクル３０４からデジタルコンピュータ３０２への接続は、様々な実施形態で達成され得ることに留意されたい。
【０１８０】
１つの実施形態では、最適化オラクル３０４のデジタルコンピュータ３０２への接続は、データネットワークを介してなされる。
【０１８１】
最適化オラクル３０４は、様々なタイプのものとされ得ることに留意されたい。
【０１８２】
１つの実施形態では、最適化オラクル３０４は、D Wave Systems Inc.製である。３０４に適用可能な量子アニーラについてのこの実施形態についての更なる情報は、http://www.dwavesys.comにて入手可能である。当業者であれば、最適化オラクル３０４について様々な代替的実施形態をもたらし得ることに気付くであろう。
【０１８３】
より正確には、最適化オラクル３０４は、デジタルコンピュータ３０２から、所定の最適化オラクルに適した問題を受信する。
【０１８４】
最適化オラクル３０４は、所定の最適化オラクルに適した問題を解くことできるのであり、また、複数のコンフィギュレーションを提供することができる。
【０１８５】
複数のコンフィギュレーションは、最適化オラクル３０４によってデジタルコンピュータ３０２に対して提供される。
【０１８６】
非一時的コンピュータ可読記憶媒体がさらに開示されている。非一時的コンピュータ可読記憶媒体は、実行されるとデジタルコンピュータに次の方法を行わせるコンピュータ実行可能命令を格納するために用いられるものである。即ち、複数の変数にわたっての離散的最適化を伴う問題について前処理を行うための方法であって、該方法は、離散的最適化を伴う問題を最適化オラクルの所定の最適化オラクルアーキテクチャに適した問題に変換するステップと、所定回数たるＭ回にわたって所定の最適化オラクルアーキテクチャに適した問題を最適化オラクルに提供するステップと、最適化オラクルから問題の提供毎に複数のコンフィギュレーションを取得するステップであって各コンフィギュレーションは最適化オラクルに対してのコールによって生成されるステップと、変数選択基準を取得するステップであって変数選択基準は複数の生成済みコンフィギュレーションの固定することができる少なくとも１つの変数を決定するためのものであるステップと、変数選択基準に合致する少なくとも１つの変数と各変数についての対応する値とを決定するステップと、離散的最適化を伴う問題に関して少なくとも１つの決定された変数を対応する値に固定してそれによって問題を前処理して少なくとも１つの下位問題を生成するステップと、少なくとも１つの生成済み下位問題についての指示と少なくとも１つの固定済み変数についての指示とを提供するステップとを含む、方法。
【０１８７】
上述の説明は発明者らによって現在検討されている具体的な実施形態に関連しているが、広義の意味合いにおいては、本発明は説明された要素についての機能的等価物をも含むものであると解されるべきである。
【０１８８】
＜項１＞  複数の変数にわたっての離散的最適化を伴う問題について前処理を行うための方法であって、該方法は、
デジタルコンピュータを用いて、離散的最適化を伴う問題についての指示を、取得するステップと、
前記デジタルコンピュータを用いて、前記離散的最適化を伴う問題を、最適化オラクルの所定の最適化オラクルアーキテクチャに適した問題に変換するステップと、
前記デジタルコンピュータを用いて、所定回数たるＭ回にわたって前記所定の最適化オラクルアーキテクチャに適した前記問題を前記最適化オラクルに提供するステップと、
前記問題の提供毎に、前記最適化オラクルを用いて、前記最適化オラクルに対しての所定個数たるＫ個のコールを行うステップであって、前記最適化オラクルに対しての各コールは所定のコンフィギュレーションを生成する、ステップと、
前記デジタルコンピュータを用いて、変数選択基準を取得するステップであって、前記変数選択基準は複数の生成済みコンフィギュレーションの固定されるべき少なくとも１つの変数を決定するためのものである、ステップと、
前記デジタルコンピュータを用いて、前記変数選択基準に合致する少なくとも１つの変数と各変数についての対応する値とを決定するステップと、
前記デジタルコンピュータを用いて、前記離散的最適化を伴う問題に関して前記少なくとも１つの決定された変数を前記対応する値に固定して、それによって前記問題を前処理して、少なくとも１つの下位問題を生成するステップと、
前記デジタルコンピュータを用いて、前記少なくとも１つの生成済み下位問題についての指示と前記少なくとも１つの固定済み変数についての指示とを提供するステップとを含む、方法。
【０１８９】
＜項２＞  項１に記載の方法において、前記離散的最適化を伴う問題は２次無制約２値最適化問題及びイジング問題の１つを含む、方法。
【０１９０】
＜項３＞  項１に記載の方法において、前記最適化オラクルは量子アニーラを含む、方法。
【０１９１】
＜項４＞  項１〜３のいずれか１つに記載の方法において、前記所定回数たるＭ回にわたって前記所定の最適化オラクルアーキテクチャに適した前記問題を前記最適化オラクルに提供するステップは、並列的に行われる、方法。
【０１９２】
＜項５＞  項３に記載の方法において、前記最適化オラクルに対しての所定個数たるＫ個のコールを行うステップは、ランダムなゲージを用いて行われる、方法。
【０１９３】
＜項６＞  項１〜５のいずれか１つに記載の方法において、前記複数の生成済みコンフィギュレーションの所定変数が前記変数選択基準を満たすのは、前記所定変数についての対応する値が前記複数の生成済みコンフィギュレーションの丁度全てにおいて変化しないこととなる場合とされる、方法。
【０１９４】
＜項７＞  項１〜５のいずれか１つに記載の方法において、前記複数の生成済みコンフィギュレーションの所定変数が前記変数選択基準を満たすのは、前記所定変数についての対応する値が前記複数の生成済みコンフィギュレーションの絶対的多数において変化しないこととなる場合とされる、方法。
【０１９５】
＜項８＞  項７に記載の方法において、前記複数の生成済みコンフィギュレーションの前記絶対的多数は、ユーザによって定義される、方法。
【０１９６】
＜項９＞  複数の変数にわたっての離散的最適化を伴う問題を解くための方法であって、該方法は、
デジタルコンピュータを用いて、複数の変数にわたっての離散的最適化を伴う問題についての指示を、受信するステップと、
終了基準が充足されるまでは：
複数の変数にわたっての離散的最適化を伴う問題を、項１〜８のいずれか１つに記載の方法を用いて、再帰的に前処理して、複数の下位問題を生成するステップと、
複数の対応する解を提供するために前記複数の生成済み下位問題の各々を解くステップと、
前記デジタルコンピュータを用いて、前記複数の対応する解を提供するステップとを含む、方法。
【０１９７】
＜項１０＞  項９に記載の複数の変数にわたっての離散的最適化を伴う問題を解くための方法において、前記終了基準が満たされるのは、前記複数の生成済み下位問題の変数個数が所定変数個数よりも小さい場合とされる、方法。
【０１９８】
＜項１１＞  項９に記載の複数の変数にわたっての離散的最適化を伴う問題を解くための方法において、前記終了基準が満たされるのは、所定量のサイズ削減が前記離散的最適化を伴う問題について達成された場合とされる、方法。
【０１９９】
＜項１２＞  項９に記載の複数の変数にわたっての離散的最適化を伴う問題を解くための方法において、前記終了基準が満たされるのは、効率的最適化問題ソルバを用いて前記複数の生成済み下位問題を解くことが可能となっている場合とされる、方法。
【０２００】
＜項１３＞  項９〜１１のいずれか１つに記載の複数の変数にわたっての離散的最適化を伴う問題を解くための方法において、前記複数の生成済み下位問題の各々について行う解決は、前記最適化オラクルを用いて行われる、方法。
【０２０１】
＜項１４＞  項９〜１２のいずれか１つに記載の複数の変数にわたっての離散的最適化を伴う問題を解くための方法において、前記複数の生成済み下位問題の各々について行う解決は、前記デジタルコンピュータを用いて行われる、方法。
【０２０２】
＜項１５＞  項９〜１４のいずれか１つに記載の複数の変数にわたっての離散的最適化を伴う問題を解くための方法において、前記複数の対応する解は、前記デジタルコンピュータと対話しているユーザに対して提供される、方法。
【０２０３】
＜項１６＞  項９〜１４のいずれか１つに記載の複数の変数にわたっての離散的最適化を伴う問題を解くための方法において、前記複数の対応する解を提供するステップは、前記デジタルコンピュータと動作可能に接続された別のコンピュータに前記複数の対応する解を提供することを含む、方法。
【０２０４】
＜項１７＞  項９〜１１のいずれか１つに記載の複数の変数にわたっての離散的最適化を伴う問題を解くための方法において、前記複数の下位問題の各々を解くステップは：
前記デジタルコンピュータを用いて、少なくとも１つの下位問題の第１群を前記最適化オラクルに提供するステップと、
前記デジタルコンピュータを用いて、前記最適化オラクルから、前記第１群の下位問題の各々についての解を取得するステップと、
前記デジタルコンピュータを用いて、少なくとも１つの下位問題の第２群を古典型ソルバに提供するステップと、
前記デジタルコンピュータを用いて、前記古典型ソルバから、前記第２群の前記下位問題の各々について少なくとも１つの対応する解を取得するステップとを含む、方法。
【０２０５】
＜項１８＞  項１７に記載の複数の変数にわたっての離散的最適化を伴う問題を解くための方法において、少なくとも１つの下位問題の前記第１群及び少なくとも１つの下位問題の前記第２群は、前記複数の下位問題のサイズに基づいて決定される、方法。
【０２０６】
＜項１９＞  デジタルコンピュータであって、
中央処理装置と、
表示装置と、
前記デジタルコンピュータを最適化オラクルと動作可能に接続するための通信ポートと、
複数の変数にわたっての離散的最適化を伴う問題を前処理するためのアプリケーションを含むメモリ装置であって、該アプリケーションは：
離散的最適化を伴う問題についての指示を取得するための命令と、
前記離散的最適化を伴う問題を、前記最適化オラクルの所定の最適化オラクルアーキテクチャに適した問題に変換するための命令と、
所定回数たるＭ回にわたって前記所定の最適化オラクルアーキテクチャに適した前記問題を前記最適化オラクルに提供するための命令と、
前記最適化オラクルから、前記問題の提供毎に複数のコンフィギュレーションを取得するための命令であって、各コンフィギュレーションは前記最適化オラクルに対してのコールによって生成される、命令と、
変数選択基準を取得するための命令であって、前記変数選択基準は複数の生成済みコンフィギュレーションの固定されるべき少なくとも１つの変数を決定するためのものである、命令と、
前記変数選択基準に合致する少なくとも１つの変数と各変数についての対応する値とを決定するための命令と、
前記離散的最適化を伴う問題に関して前記少なくとも１つの決定された変数を前記対応する値に固定して、それによって前記問題を前処理して、少なくとも１つの下位問題を生成するための命令と、
前記少なくとも１つの生成済み下位問題についての指示と前記少なくとも１つの固定済み変数についての指示とを提供するための命令とを含む、メモリ装置と、
前記中央処理装置と前記表示装置と前記通信ポートと前記メモリ装置とを相互接続するためのデータバスとを含む、デジタルコンピュータ。
【０２０７】
＜項２０＞  コンピュータ実行可能命令を格納するための非一時的コンピュータ可読記憶媒体であって、該命令が実行されると複数の変数にわたっての離散的最適化を伴う問題について前処理を行うための方法をデジタルコンピュータに行わせることになり、該方法は、
離散的最適化を伴う問題についての指示を取得するステップと、
前記離散的最適化を伴う問題を、前記最適化オラクルの所定の最適化オラクルアーキテクチャに適した問題に変換するステップと、
所定回数たるＭ回にわたって前記所定の最適化オラクルアーキテクチャに適した前記問題を前記最適化オラクルに提供するステップと、
前記最適化オラクルから、前記問題の提供毎に複数のコンフィギュレーションを取得するステップであって、各コンフィギュレーションは前記最適化オラクルに対してのコールによって生成される、ステップと、
変数選択基準を取得するステップであって、前記変数選択基準は複数の生成済みコンフィギュレーションの固定されるべき少なくとも１つの変数を決定するためのものである、ステップと、
前記変数選択基準に合致する少なくとも１つの変数と各変数についての対応する値とを決定するステップと、
前記離散的最適化を伴う問題に関して前記少なくとも１つの決定された変数を前記対応する値に固定して、それによって前記問題を前処理して、少なくとも１つの下位問題を生成するステップと、
前記少なくとも１つの生成済み下位問題についての指示と前記少なくとも１つの固定済み変数についての指示とを提供するステップとを含む、非一時的コンピュータ可読記憶媒体。
【図１】
2019512779.tif 000003
【図２】
2019512779.tif 000004
【図３】
2019512779.tif 000005
【図４】
2019512779.tif 000006
【国際調査報告】
2019512779.tif 000007
2019512779.tif 000008