自動画像認識用のシステム、方法、および装置
連合グラフおよび量子プロセッサの実装により自動画像認識の精度および計算時間を向上させる方法。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照
本出願は、米国特許法施行規則１１９（ｅ）条の下で、２００７年４月１９日出願の米国仮特許出願第６０／９１２，９０４号「自動画像認識用のシステム、方法、および装置(Systems, Methods and Apparatus for Automatic Image Recognition)」を優先権主張するものであり、本明細書にその全文を援用している。
【０００２】
背景
分野
本システム、方法、および装置は、画像データベースから顔画像等の画像を自動認識する量子プロセッサの実装に関する。
【背景技術】
【０００３】
関連技術の説明
チューリングマシンは、１９３６年にAlan Turingによって述べられた理論的計算システムである。任意の他のチューリングマシンを効率的にシミュレートすることが可能なチューリングマシンは、汎用チューリングマシン(Universal Turing Machine)（ＵＴＭ）と呼ばれる。チャーチ・チューリングの提唱(Church-Turing thesis)では、いかなる実際的な計算モデルも、ＵＴＭの機能の同等物またはサブセットのいずれかを有すると述べられている。
【０００４】
量子コンピュータは、計算を実行するために１つ以上の量子効果を利用する、任意の物理システムである。任意の他の量子コンピュータを効率的にシミュレートすることが可能な量子コンピュータは、汎用量子コンピュータ(Universal Quantum Computer)（ＵＱＣ）と呼ばれる。
【０００５】
１９８１年に、Richard P.Feynmanは、量子コンピュータは、特定の計算問題を解くために、ＵＴＭよりも効率的に使用されることが可能であり、したがってチャーチ・チューリングの提唱を無効にする、ということを提唱した。例えば、Feynman R.P., "Simulating Physics with Computers", International Journal of Theoretical Physics", Vol.21 (1982) pp.467-488を参照されたい。例えば、Feynmanは、量子コンピュータが、特定の他の量子系をシミュレートするために使用されることが可能であり、それにより、ＵＴＭを使用して可能であるよりも指数関数的に高速な、シミュレートされる量子系の特定の特性の計算を可能にするということを指摘した。
【０００６】
量子計算へのアプローチ
量子コンピュータの設計および動作への、いくつかの一般的なアプローチがある。１つのそのようなアプローチは、量子計算の「回路モデル(circuit model)」である。このアプローチでは、量子ビットが、アルゴリズムのコンパイルされた表現である、論理ゲートのシーケンスによる作用を受ける。回路モデル量子コンピュータは、実際的な実施のためには、いくつかの重大な障害を有する。回路モデルでは、量子ビットが、１ゲート時間(single-gate time)よりもはるかに長い期間にわたってコヒーレントのままであることが要求される。この要求が発生する理由は、回路モデル量子コンピュータは、動作するために、量子誤り訂正と集合的に呼ばれる動作を必要とするからである。量子誤り訂正は、回路モデル量子コンピュータの量子ビットが量子コヒーレンスを、１ゲート時間の１０００倍のオーダーの期間にわたって維持することが可能でなければ、実行されることはできない。多くの研究が、回路モデル量子コンピュータの基本情報単位を形成するための十分なコヒーレンスを有する量子ビットの開発に焦点を置いてきた。例えば、Shor, P.W. "Introduction to Quantum Algorithms", arXiv.org:quant-ph/0005003 (2001), pp.1-27を参照されたい。当該技術分野は、量子ビットのコヒーレンスを、実際的な回路モデル量子コンピュータの設計および動作のための許容可能なレベルまで増加させることが不可能であることによって、依然として阻まれている。
【０００７】
量子計算への別のアプローチは、結合された量子系の、系の自然な物理的進化を、計算システムとして使用することを含む。このアプローチでは、量子ゲートおよび回路を不可欠なものとして使用することはしない。その代りに、このアプローチは、既知の初期ハミルトニアン(initial Hamiltonian)から開始して、結合された量子系の、系のガイドされた物理的進化に依拠し、ここで、解かれるべき問題は、系のハミルトニアンの項内に符号化されており、それにより、結合された量子系の、系の最終状態が、解かれるべき問題への答えに関連する情報を含む。このアプローチは、長い量子ビットコヒーレンス時間を必要としない。このタイプのアプローチの例は、断熱量子計算(adiabatic quantum computation)、クラスタ状態量子計算(cluster-state quantum computation)、一方向量子計算(one-way quantum computation)、量子アニーリング(quantum annealing)および古典的アニーリング(classical annealing)を含み、例えば、Farhi, E et. al., "Quantum Adiabatic Evolution Algorithms versus Simulated Annealing" arXiv.org:quant-ph/0201031 (2002), pp.1-16に記載されている。
【０００８】
量子ビット
前述のように、量子ビットは、量子コンピュータのための情報の基本単位として使用されてもよい。ＵＴＭにおけるビットと同様に、量子ビットは、少なくとも２つの別個の量を意味してもよい。量子ビットは、情報が記憶される実際の物理デバイスを意味してもよく、そして量子ビットは、さらに、その物理デバイスから離れて抽象化された、情報の単位そのものを意味してもよい。量子ビットの例としては、量子粒子、原子、電子、光子、イオンなどが挙げられる。
【０００９】
量子ビットは、古典的デジタルビットの概念を一般化する。古典的情報記憶デバイスは、一般に「０」および「１」とラベル付けされる、２つの離散的な状態を符号化することが可能である。物理的には、これらの２つの離散的な状態は、磁場、電流、または電圧の、方向または大きさなどの、古典的情報記憶デバイスの２つの異なる、かつ区別できる物理的状態によって表され、ここで、ビット状態を符号化する量は、古典物理学の法則に従って振る舞う。量子ビットも、同様に、やはり「０」および「１」とラベル付けされてもよい、２つの離散的な物理的状態を含む。物理的には、これらの２つの離散的な状態は、磁場、電流、または電圧の、方向または大きさなどの、量子情報記憶デバイスの２つの異なる、かつ区別できる物理的状態によって表され、ここで、ビット状態を符号化する量は、量子物理学の法則に従って振る舞う。これらの状態を記憶する物理量が量子力学的に振る舞う場合、デバイスはさらに、０および１の重ね合わせに位置してもよい。すなわち、量子ビットは、同時に「０」および「１」状態の両方に存在してもよく、したがって、両方の状態についての計算を同時に実行することが可能である。一般に、Ｎ個の量子ビットは、２Ｎ個の状態の重ね合わせにあることが可能である。量子アルゴリズムは、いくつかの計算を高速化するために、重ね合わせの特性を利用する。
【００１０】
標準的な記法では、量子ビットの基底状態(basis states)は、｜０＞および｜１＞状態と呼ばれる。量子計算の間、量子ビットの状態は、一般に、基底状態の重ね合わせであり、そのため量子ビットは、｜０＞基底状態を占める０ではない確率と、それと同時の、｜１＞基底状態を占める０ではない確率とを有する。数学的には、基底状態の重ね合わせは、｜Ψ＞で示される量子ビットの全体的状態が、｜Ψ＞＝ａ｜０＞＋ｂ｜１＞の形式を有することを意味し、式中、ａおよびｂは、それぞれ、確率｜ａ｜２および｜ｂ｜２に対応する係数である。係数ａおよびｂは、量子ビットの位相が特徴付けられることを可能にする、実数および虚数成分をそれぞれが有する。量子ビットの量子的性質は、大部分が、基底状態のコヒーレントな重ね合わせに存在する量子ビットの能力、および量子ビットの状態が位相を有する能力に由来する。量子ビットは、デコヒーレンスの源から十分に分離されている場合、基底状態のコヒーレントな重ね合わせとして存在するこの能力を維持する。
【００１１】
量子ビットを使用した計算を完了するためには、量子ビットの状態が測定される（すなわち、読み取られる）。一般に、量子ビットの測定が実行される場合、量子ビットの量子的性質は一時的に失われて、基底状態の重ね合わせは、｜０＞基底状態または｜１＞基底状態のいずれかに崩壊し、それにより、従来のビットとの類似性が取り戻される。崩壊した後の量子ビットの実際の状態は、読み取り動作の直前の確率｜ａ｜２および｜ｂ｜２に依存する。
【００１２】
超伝導量子ビット
量子計算に使用するために検討されている多くのさまざまなハードウェアおよびソフトウェアアプローチがある。１つのハードウェアアプローチでは、アルミニウムまたはニオブなどの超伝導材料で形成された集積回路を使用する。超伝導集積回路の設計および製造に含まれる、技術および処理は、従来の集積回路のために使用されるものに類似している。
【００１３】
超伝導量子ビットは、超伝導集積回路内に含まれることが可能なタイプの超伝導デバイスである。典型的な超伝導量子ビットは例えばスケーラビリティを利点としており、一般に、例えば電荷および位相素子、位相または磁束素子、ハイブリッド素子等を含む情報の符号化に用いられる物理的特性に応じて分類される。超伝導量子ビットは、情報を符号化するために使用される物理的特性に応じて、いくつかのカテゴリに分けられてもよい。例えば、超伝導量子ビットは、例えば、Makhlin et. al., 2001, Reviews of Modern Physics 73, pp.357-400で述べられているように、電荷、磁束、および位相デバイスに分けられてもよい。電荷デバイスは、デバイスの電荷状態内で、情報を記憶および操作し、ここで、電気素量はクーパー対と呼ばれる一対の電子からなる。クーパー対は２ｅの電荷を有し、例えばフォノン相互作用によって共に結合された、２つの電子からなる。例えば、NielsenおよびChuang、Quantum Computation and Quantum Information, Cambridge University Press、Cambridge (2000), pp.343-345を参照されたい。磁束デバイスは、デバイスの何らかの部分を通る磁束に関連する変数内に、情報を記憶する。位相デバイスは、位相デバイスの２つの領域間の超伝導位相の差に関連する変数内に、情報を記憶する。最近、電荷、磁束、および位相のうちの２つ以上の自由度を使用するハイブリッドデバイスが開発された。例えば、米国特許第６，８３８，６９４号および米国特許第７，３３５，９０９号を参照されたい。
【００１４】
使用されてもよい磁束量子ビットの例としては、１つのジョセフソン接合または複合接合（単一のジョセフソン接合が２つの並列なジョセフソン接合によって置き換えられる）によって遮断される超伝導ループを含む、ｒｆ−ＳＱＵＩＤ、あるいは、３つのジョセフソン接合によって遮断される超伝導ループを含む、永久電流量子ビットなどが挙げられる。例えば、Mooij et. al., 1999, Science 285, p.1036、およびOrlando et. al., 1999, Phys. Rev. B 60, p.15398を参照されたい。超伝導量子ビットのその他の例は、例えば、Il'ichev et. al., 2003, Phys.Rev.Lett.91,097906、Blatter et. al., 2001, Phys. Rev. B 63, 174511、およびFriedman et. al., 2000, Nature 406, p.43に見出すことができる。さらに、ハイブリッド電荷−位相量子ビットも使用されてもよい。
【００１５】
量子ビットは、対応する局所的バイアスデバイスを含んでもよい。局所的バイアスデバイスは、量子ビットに外部磁束バイアスを提供する、超伝導量子ビットに近接した金属ループを含んでもよい。局所的バイアスデバイスは、さらに、複数のジョセフソン接合を含んでもよい。量子プロセッサ内の各超伝導量子ビットが、対応する局所的バイアスデバイスを有してもよく、または、量子ビットよりも少数の局所的バイアスデバイスが存在してもよい。いくつかの実施形態では、電荷ベースの読み出しおよび局所的バイアスデバイスが使用されてもよい。読み出しデバイスは、それぞれがトポロジ内の異なる量子ビットに誘導結合される、複数のｄｃ−ＳＱＵＩＤ磁力計を含んでもよい。読み出しデバイスは、電圧または電流を提供してもよい。少なくとも１つのジョセフソン接合によって遮断される、超伝導材料のループを含むｄｃ−ＳＱＵＩＤ磁力計は、当該技術分野で周知である。
【００１６】
実効量子ビット
本明細書および添付の特許請求の範囲を通じて、用語「実効量子ビット」を用いて２準位系として表現可能な量子系を表記する。当業者には、２つの特定の準位が多準位量子系から分離され、実効量子ビットとして使用できることが理解されよう。更に、用語「実効量子ビット」を用いて、単一の２準位系を表すために使用可能な任意の数のデバイスを含む量子系を表記する。例えば、結合された量子ビット群の全ての集合またはその一部が単一の２準位系を表すように、複数の個別量子ビットを互いに結合することができる。
【００１７】
量子プロセッサ
コンピュータプロセッサは、例えば、超伝導量子プロセッサなどの量子プロセッサのような、アナログプロセッサの形態を取ってもよい。超伝導量子プロセッサは、例えば、２つ以上の超伝導量子ビットなどの、複数の量子ビットおよび関連する局所的バイアスデバイスを含んでもよい。本システム、方法、およびデバイスと共に利用できる例示的な量子プロセッサの更なる詳細および実施形態が米国特許出願公開第２００６−０２２５１６５号、米国特許出願第１２／０１３，１９２号および２００７年１１月８日出願の米国仮特許出願第６０／９８６，５５４号「アナログ処理用のシステム、デバイス、および方法(Systems, Devices and Methods for Analog Processing)」に記述されている。
【００１８】
超伝導量子プロセッサは、量子ビットのそれぞれ数対を選択的に結合するように動作可能な、複数の結合デバイスを含んでもよい。超伝導結合デバイスの例としては、磁束によって量子ビットを共に結合する、ｒｆ−ＳＱＵＩＤおよびｄｃ−ＳＱＵＩＤが挙げられる。ＳＱＵＩＤは、１つのジョセフソン接合（ｒｆ−ＳＱＵＩＤ）または２つのジョセフソン接合（ｄｃ−ＳＱＵＩＤ）によって遮断される超伝導ループを含む。結合デバイスは、相互接続トポロジ内で結合デバイスがどのように利用されるかに応じて、強磁性結合および反強磁性結合の両方が可能であってもよい。磁束結合の場合、強磁性結合は、平行な磁束がエネルギー的に好都合であることを意味し、反強磁性結合は、逆平行の磁束がエネルギー的に好都合であることを意味する。あるいは、電荷をベースとする結合デバイスが使用されてもよい。その他の結合デバイスは、例えば、米国特許出願公開第２００６−０１４７１５４号および米国特許出願第１２／０１７，９９５号に見出すことができる。結合デバイスのそれぞれの結合強度は、例えば、量子ビット間の強磁性または反強磁性結合を提供するために、０と最大値との間で調整されてもよい。
【００１９】
量子アニーリング
量子アニーリングとは、通常好適には系の基底状態である低エネルギー状態を見つけるために利用できる計算方法である。本方法は古典的アニーリングと概念的に類似していて、より低いエネルギー状態がより安定しているため、自然の系はより低いエネルギー状態へ向かう傾向があるとの原理に依っている。しかし、古典的アニーリングが系をその大域的な最低エネルギー状態へ導くために古典的な熱ゆらぎを用いるのに対し、量子アニーリングはより正確にまたはより速く大域的な最低エネルギー状態に到達すべく量子トンネリング等の自然の量子ゆらぎを用いることができる。組合せ最適化問題等の困難問題の解が、系の基底状態に符号化することが可能であり、従って量子アニーリングを用いてそのような困難問題の解を見つけることができる。
【００２０】
断熱量子計算
上述のように、断熱量子計算は通常、既知の初期ハミルトニアン（ハミルトニアンとは系の許されたエネルギーを固有値とする作用素）からハミルトニアンを徐々に変えることにより最終ハミルトニアンへ系を発展させるステップを含んでいる。断熱発展の簡単な例として次式がある。
Ｈｅ＝（１−ｓ）Ｈｉ＋ｓＨｆ
式中、Ｈｉは初期ハミルトニアン、Ｈｆは最終ハミルトニアン、Ｈｅは発展または瞬間ハミルトニアンであり、ｓは発展の速度を制御する発展係数である。係数ｓは０〜１の範囲であって、発展過程の開始時点において発展ハミルトニアンは初期ハミルトニアンに等しく、過程の終了時点において発展ハミルトニアンは最終ハミルトニアンに等しい。発展が速過ぎる場合、系は第１励起状態等のより高い状態に励起させることができる。本システム、方法、およびデバイスでは、「断熱」発展は断熱条件を満たす発展であると考えられ、ここで、断熱条件は次式で表される。
【数１】
式中、
【数２】
はｓの時間導関数、ｇ（ｓ）はｓの関数としての系の基底状態と第１励起状態との間のエネルギー差（本明細書では「ギャップサイズ」とも称す）、δは１より極めて小さい係数である。
【００２１】
断熱量子計算における発展過程をアニーリングと呼ぶ場合がある。ｓが変化する速度は発展またはアニーリングスケジュールとも呼ばれ、通常は一定且つ系が発展している間は常に発展ハミルトニアンの瞬間的基底状態にあるように十分遅く、反交差（すなわち、ギャップサイズが最小の時）における遷移が避けられる。断熱量子計算システム、方法、およびデバイスに関する更なる詳細は、米国特許第７，１３５，７０１号に記述されている。
【００２２】
断熱量子計算は、系が始まってから発展を通じて基底状態のままである量子アニーリングの特別な場合である。従って、当業者には、量子アニーリング法が一般に断熱量子コンピュータ上で実装でき、その逆も成立つことが理解されよう。本明細書を通じて、用語「断熱量子コンピュータ」を用いて断熱量子計算および／または量子アニーリングを実行すべく設計されている計算システムを記述する。
【００２３】
最適化問題
最適化問題は、制約条件の組に従う場合もあるが、変数の組について１つ以上の目的関数を最小化または最大化する問題である。例えば、巡回セールスマン問題（「ＴＳＰ」）は、例えば距離やコストを表す目的関数を最適化して、問題に対する最適化された解を表す変数の組として符号化されている経路を発見する最適化問題である。例えば、場所のリストが与えられている場合、問題は、全ての場所を一度だけ訪問する最短経路を発見することである。最適化問題の他の例として、最大独立集合（ＭＩＳ）、整数計画法、制約の最適化、因数分解、予測モデリング、およびｋ−ＳＡＴが含まれる。これらの問題は、オペレーションズ・リサーチ、金融ポートフォリオ選択、スケジューリング、供給管理、回路設計、および旅程最適化等、多くの現実的な最適化問題を抽象化したものである。多くの大規模な意思決定に基づく最適化問題はＮＰ困難である。例えば、「A High-Level Look at Optimization: Past, Present, and Future” e-Optimization.com, 2000」を参照されたい。
【００２４】
最適化問題の多くはＵＴＭを用いて解くことができない。この制約のため、ＵＴＭの能力を超える計算問題を解くことができる計算装置が当該技術分野で必要とされている。古典的なデジタルコンピュータは一般に、ＵＴＭの能力を超えられず、従って問題の規模と解決時間との間に好ましくない尺度を課す古典的計算の制約を受けるものと考えられている。本システム、方法、および装置によれば、量子断熱アルゴリズムを用いて、これらの問題に対し古典的最適化アルゴリズムで実現できるものよりも優れた解を得ることができる。
【００２５】
グラフ埋め込み
グラフは、対象同士の関係を表す有効な方法であって、経済学、数学、自然科学、および社会科学等の分野で共通に用いられている。ある種のグラフは単なる視覚的な支援ツールとして用いられるが、他のグラフは解くべき問題を表現するために用いることができる。実際、問題をグラフ形式にマッピングすることが問題の解決に役立つ場合がある。そのような問題の例として、株式ポートフォリオ選択、マイクロ波送信塔の配置、配送経路の最適化その他の大規模な問題が含まれる。元の問題を量子コンピュータが解ける形式に変換することにより、量子コンピュータを用いてそのような問題を解くことができる。これを行なう一方法としてグラフ埋め込みがあり、解くべき問題を表す頂点の集合および様々な頂点を接続する辺の集合からなるグラフを量子プロセッサの量子ビット構造にマッピングして問題を解く。
【００２６】
グラフ埋め込みは、全ての節点または頂点を平面上の点にマッピングし、２つの節点を接続する直線または曲線に全ての辺をマッピングすることにより、特定のグラフを描くステップを含んでいる。同一のグラフに多くの順列が存在し得るため、この描画は一意ではない。グラフを埋め込む方法の数は、これらを描画する格子系の特徴および規則に依存する。例えば、ある格子系は２次元格子であり得る。辺は、例えば、２つの互いに直角方向（例えば、上下または左右）に制約されている場合がある。そのような格子系は連結度が４、すなわち各々の節点に最大４本の辺が連結していることを意味し、これらの辺は上述の方向のみを向いている。辺が斜め（例えば、４５°）方向にも伸びて、交差可能であるような同様の格子系の連結度は８である。グラフ埋め込みの一形式には、ある格子系に描かれたグラフを取り上げて、他の格子系に等価なグラフを描くステップを含んでいる。
【００２７】
埋め込み可能グラフは、平面および非平面の２種類に分類することができる。平面グラフは、どの２本の辺も交差しないように２次元平面上に埋め込み可能なグラフである。非平面グラフは、少なくとも２本の辺が交差するグラフである。グラフ埋め込みのいくつかの形式には、平面グラフの非平面グラフへの埋め込み、または非平面グラフをできるだけ平面化する、すなわち交差の数を減らす試みが含まれる。しかし、ある種の非平面グラフは平面グラフに埋め込むことができない。そのようなグラフの最も有名な例としてグラフＫ５およびＫ（３、３）がある。非平面グラフおよびその埋め込みに関するより詳細な情報をBoyer et al., 2004, Journal of Graph Algorithms and Applications 8, pp. 241-273に見ることができる。
【００２８】
グラフを量子ビット群の格子に埋め込む技術がKnysh et al., 2005, arXiv.org:quant-ph/0511131に記述されている。Knyshは、ＮＰ完全な問題を量子ビット群の格子にマッピングして断熱量子計算を実行して問題を解く技術を記述している。しかし、Knyshは量子ビット群間の定常結合および最も近い隣接結合のみを使用しており、両方共に埋め込みおよび後続する計算の柔軟性および効率が悪い。
【００２９】
量子ビット群の格子にグラフを埋め込む更なる技術が米国特許出願第１１／９３２，２４８号に記述されている。
【００３０】
関係データベース
情報の格納に関係データベースを用いる場合が多い。情報は、任意の形態の企業、政府または個人に関連していてよい。例えば、情報は、人的資源、輸送、発注または取出し、倉庫保管、配送、予算編成、石油探査、測量、世論調査、画像、地図、ネットワークトポロジ、認証および／またはセキュリティに関連するものであってよい。
【００３１】
データベースを探索する多くの代替的な技術があるが、大多数の方法では通常１つ以上のクエリーを用意する。例えば、米国特許出願第１１／９３２，２６１号に記述されている技術では、クエリーは節点と辺からなるグラフの形式で与えられる。この技術では、データベースのエントリを用いてデータベースグラフを生成し、各々のデータベースグラフをクエリーグラフと組み合わせて一組の連合グラフを生成する。次いで連合グラフを用いて、クエリーグラフと対応するデータベースグラフの関係を評価することができる。ある実施形態において、連合グラフは量子ビットの集合からなる量子プロセッサに埋め込まれる。連合グラフの頂点が量子ビット群により表され、連合グラフの辺が量子ビット間の結合素子により表される。量子ビットおよび結合素子は超伝導素子であってよい。連合グラフに対応するクエリーは、量子プロセッサを用いてクリーク問題として解くことができる。例えば、量子プロセッサは第１または「初期」状態から第２または「最終」状態へ発展することができ、最終状態は連合グラフの任意のクリークを表していても、あるいは最大クリークまたは連合グラフの最大クリークを表していてもよい。ある実施形態において、対応する連合グラフが最大クリークを生成するデータベースグラフによってクエリーが最適な条件を満たす。
【００３２】
弾性バンチグラフマッチング
弾性バンチグラフマッチング（ＥＢＧＭ）は、多くの一意な顔画像データベースにおいて一人の人間の顔を認識するシステムである。具体的には、ＥＢＧＭは人間の顔画像を解析してラベル付けされたグラフ表現を生成する処理である。ラベル付けされたグラフ表現は節点および辺を含み、画像グラフと呼ばれる。グラフの節点は、顔の様々な「基準」位置（目、鼻および口等）を表現し、これらの節点は「ジェット」と呼ばれるガボールウェーブレット成分の集合により重み付けされている。グラフの辺は基準点間の関係を表し、辺には２次元距離ベクトルによりラベル付けされている。ＥＢＧＭによる画像グラフ表現の自動生成に続いて、クエリー画像の画像グラフをデータベース内の全ての画像の各画像グラフと比較することにより顔を認識することができる。
【発明の概要】
【発明が解決しようとする課題】
【００３３】
ＥＢＧＭにおける画像グラフの自動生成は、一般化された「バンチ」グラフに顔画像を整合させることにより実現される。バンチグラフは基本的に、１つの特定のジェットではなく多数のジェットの集合（または「バンチ」）により個々の基準点がラベル付けされているモデル格子である。バンチグラフは顔画像を覆い、画像内の各基準点を最も良く表現するジェットが識別される。バンチグラフは従って、成形可能なマスクのように組合されたものとして機能する。バンチグラフの辺は十分な弾性を有しているため、結果的に得られた画像グラフが特定の顔画像により良くフィットすることができる。最初に、手作業でバンチグラフを画定し、より多くの顔画像がバンチに組み込まれるにつれて適合度と精度が向上する。ＥＢＧＭの処理のより詳細な記述をWiskott et al., Face Recognition by Elastic Bunch Graph Matching, IEEE Transactions on Pattern Analysis and Machine Intelligence, 19(7):775-779, 1997に見ることができる。重要な点は、ＥＢＧＭの精度向上には計算量の増大が伴うことである。例えば、バンチグラフ内の基準点の数を増やすことにより精度が向上する。しかし、そのような増加はＥＢＧＭ画像グラフ生成段階でより多くの計算量を必要とし、より多くの節点および辺を含む画像グラフが生じることになる。そのようにより大きな画像グラフは、認識段階を通じてデータベース内の他の全ての画像グラフと比較する際により多くの計算量を必要とする。従って、自動顔面マッチングの現行技術は、所望のレベルの精度が得られないか、または処理速度が遅過ぎる。
【００３４】
画像マッチング問題は特に上記のような量子プロセッサで解くのに適している。現在実用化されている画像認識技術は精度に限界があり、一般に極めて遅い。認識の精度はグラフ表現の精度に依存し、精度自体が最終的には識別された画像特徴の数に依存する。従来、より多くの画像特徴を組み込む試みは、認識処理において網羅的計算を要するグラフ表現に行き着く。従って、通常は計算時間を管理可能にすべくある程度まで精度を犠牲にされてきた。量子プロセッサ上で認識処理を実行することにより、従来の方法よりより高い精度および／またはより高速に認識を行なうことができる。
【課題を解決するための手段】
【００３５】
概要
少なくとも１つの実施形態は、画像データベース内のクエリー画像の特徴を識別するコンピュータに実装された方法として要約することができ、クエリー画像の少なくとも１つの特徴のグラフ表現を、画像データベース内の複数のデータベース画像のうち少なくともいくつかの画像の各々の少なくとも一部の各グラフ表現と比較するステップであって、各々の比較が各連合グラフを生成するステップを含むステップと、量子プロセッサを介して各連合グラフの少なくとも１つの特徴を決定するステップとを含み、各連合グラフの少なくとも１つの特徴がクエリー画像の少なくとも１つの特徴と連合グラフが対応する各データベース画像の少なくとも一部との類似度を表す。
【００３６】
本方法は更に、各連合グラフの少なくとも１つの特徴を決定した結果を格納するステップと、結果に対してランク付けをして、最高ランクの結果がクエリー画像の特徴とデータベース画像のうち少なくとも１つとの間の最良の合致を表すようにするステップとを含んでいてよい。複数のデータベース画像の少なくともいくつかは、各々少なくとも一人の人間の顔を表すデータを含んでいてよく、クエリー画像の特徴は、少なくとも一人の人間の顔を表すデータを含んでいてよい。本方法は更に、画像データベース内のデータベース画像のうち少なくともいくつかの画像の各々の少なくとも一部の各グラフ表現を生成するステップと、クエリー画像の少なくとも１つの特徴のグラフ表現を生成するステップとを含んでいてよい。データベース画像のうち少なくともいくつかの画像の各々の少なくとも一部のグラフ表現、およびクエリー画像の少なくとも１つの特徴のグラフ表現を生成するステップは、弾性バンチグラフマッチングを実行するステップを含んでいてよい。各データベース画像の少なくとも一部の各々のグラフ表現を生成するステップは、古典的デジタルプロセッサを用いて各々のグラフ表現を生成するステップを含んでいてよい。クエリー画像の少なくとも１つの特徴のグラフ表現を生成するステップは、古典的デジタルプロセッサを用いてグラフ表現を生成するステップを含んでいてよい。各連合グラフの少なくとも１つの特徴を決定するステップは、各連合グラフの最大独立集合を決定するステップを含んでいてよい。各連合グラフの少なくとも１つの特徴を決定するステップは、各連合グラフの最大クリークを決定するステップを含んでいてよい。量子プロセッサを介して各連合グラフの少なくとも１つの特徴を決定するステップは、複数の超伝導量子ビット群を含む超伝導量子プロセッサを介して各連合グラフの少なくとも１つの特徴を決定するステップを含んでいてよい。本方法は更に、古典的デジタルプロセッサを介して画像データベースにアクセスするステップを含んでいてよい。各連合グラフを生成するステップは、古典的デジタルプロセッサを用いて各連合グラフを生成するステップを含んでいてよい。本方法は更に、各連合グラフを古典的デジタルプロセッサから量子プロセッサへ送信するステップを含んでいてよい。本方法は更に、量子プロセッサにより決定された各連合グラフの少なくとも１つの特徴を量子プロセッサから古典的デジタルプロセッサへ送信するステップを更に含んでいてよい。本方法は更に、クエリー画像のグラフ表現をデータベース画像のグラフ表現と比較する前にクエリー画像の少なくとも一部を調べるステップと、データベース画像の部分集合に共通するクエリー画像の態様を識別するステップとを含んでいてよく、クエリー画像の少なくとも１つの特徴のグラフ表現を複数のデータベース画像のうち少なくともいくつかの画像の各々の各グラフ表現と比較するステップは、クエリー画像の少なくとも１つの特徴のグラフ表現をデータベース画像の部分集合内のデータベース画像のグラフ表現のみと比較し、そのために対応する連合グラフを生成するステップを含んでいてよい。クエリー画像の少なくとも１つの特徴によりクエリー画像の大多数を表現することができる。クエリー画像の特徴と、連合グラフが対応する各データベース画像の少なくとも一部との間の類似度は、連合グラフが対応する各データベース画像内にクエリー画像の少なくとも１つの特徴が存在するか否かを示すことができる。
【００３７】
少なくとも１つの実施形態は、画像マッチング問題を解くコンピュータ実装された方法として要約することができ、画像マッチング問題を２次無制約２値最適化問題として定式化するステップと、２次無制約２値最適化問題を量子プロセッサにマッピングするステップと、２次無制約２値最適化問題への解を与えるべく量子プロセッサを動作させるステップとを含む。
【００３８】
少なくとも１つの実施形態は、２つの物体を比較するコンピュータ実装された方法として要約することができ、第１の物体の少なくとも一部のグラフ表現を第２の物体の少なくとも一部のグラフ表現と比較するステップであって、比較に際して連合グラフを生成するステップを含むステップと、量子プロセッサを介して連合グラフの少なくとも１つの特徴を決定するステップであって、連合グラフの少なくとも１つの特徴が、第１の物体の少なくとも一部と第２の物体の少なくとも一部との間の類似度を表すようにするステップとを含んでいる。
【００３９】
本方法は更に、共に画像である第１の物体および第２の物体を含んでいてよい。連合グラフの少なくとも１つの特徴を決定するステップは、連合グラフの最大独立集合を決定するステップを含んでいてよい。連合グラフの少なくとも１つの特徴を決定するステップは、連合グラフの最大クリークを決定するステップを含んでいてよい。連合グラフの少なくとも１つの特徴を決定するステップの結果、量子プロセッサが、第１の物体の少なくとも一部と第２の物体の少なくとも一部との間の類似度を表す値を返すことができる。
【００４０】
図面において、同じ参照番号は、同様の要素または動作を識別する。図中の要素のサイズおよび相対位置は、必ずしも一定の縮尺で描かれてはいない。例えば、さまざまな要素の形状、および角度は、一定の縮尺で描かれてはおらず、これらの要素のいくつかは、図面の可読性を向上するために任意に拡大および配置されている。さらに、描かれているとおりの要素の特定の形状は、特定の要素の実際の形状に関するいかなる情報も伝えることは意図されておらず、図中での認識を容易にするためにのみ選択されている。
【図面の簡単な説明】
【００４１】
図面の簡単な説明
【図１】量子プロセッサを含むシステムにより自動画像認識を実行する方法の実施形態のフロー図である。
【図２Ａ】顔画像自体を覆う顔画像のグラフ表現を示す例示的な図である。
【図２Ｂ】古典的プロセッサから量子プロセッサへ問題を伝達する方法の実施形態のフロー図である。
【図３】断熱量子計算（および／または量子アニーリング）用に設計された従来の超伝導量子プロセッサの一部の模式図である。
【図４】量子プロセッサにより画像マッチング問題を解く際のネイティブ動作モードの方法の実施形態のフロー図である。
【図５】量子プロセッサにより画像マッチング問題を解く際の混合動作モードの方法の実施形態のフロー図である。
【発明を実施するための形態】
【００４２】
詳細な説明
以下の説明は、開示する各種の実施形態が完全に理解されることを目的として記述するものである。しかし、関連技術の当業者には、各種実施形態が、これらの具体的な詳細事項が無くても、あるいは他の方法、構成要素、材料等によっても実施可能であることが理解されよう。他の例では、実施形態の説明が無用に分かり難くならないように、アナログプロセッサに関連付けられた周知の構造、例えば量子プロセッサ、量子素子、結合素子およびマイクロプロセッサおよび駆動回路を含む制御システムの図示および詳述は行ない。
【００４３】
別途文脈上必要とされない限り、本明細書および特許請求の範囲を通じて、用語「含む」および「含んでいる」等の変化形は、開いた包含的な意味、すなわち「含んでいるがこれに限定されない」旨の意味に解釈されるものとする。
【００４４】
本明細書を通じて、「１つの実施形態」または「一実施形態」とは、当該実施形態に関連付けられて記述された特定の特徴、構造または特性が少なくとも１つの実施形態に含まれていることを意味する。従って、本明細書を通じて各所に現れる「１つの実施形態において」または「一実施形態において」という語句は必ずしも全て同一の実施形態を指す訳ではない。更に、特定の特徴、構造または特性は、任意の適当な方法で１つ以上の実施形態に組み込むことができる。
【００４５】
本明細書および添付の特許請求の範囲において用いられているように、単数形の「ａ」、「ａｎ」および「ｔｈｅ」は、記述内容が別途明示しない限り複数の対象を含んでいる。また、用語「または」は一般に、記述内容が別途明示しない限り「および／または」を含む意味で用いられている点に注意されたい。
【００４６】
本明細書の開示内容の見出しおよび要約は、便宜上のものに過ぎず、実施形態の範囲または意味を解釈するものではない。
【００４７】
本システム、方法、および装置は、画像データベース内で自動画像認識を実行すべく量子プロセッサを実装する技術を記述する。これを行なうために、画像マッチング問題を量子プロセッサにより処理可能な形式にマッピングする。画像は各種の形式であってよい。通常、画像は、例えばディスプレイ装置または紙に画像の視覚的表現を生成すべく利用可能なデジタル情報の形式である。画像は、例えば２次元配列の各種のピクセルの輝度および／または色を指定するようなビットマップを定義する情報の形式であってよい。また、例えば、画像は数学的表現、例えば１つ以上の多項式（例えば、Ｂ−Ｓｐｌｉｎｅ多項式）またはベクトル形式であってよい。画像は他の形式であってもよい。
【００４８】
画像マッチングはその最も単純な形式において、同一物理構造に対応する２つの画像から一対の画像機能を見つけようと試みる。画像機能は例えば、所与の画像位置の近隣を記述するベクトルを含んでいてよい。対応する特徴を見つけるために、通常２つの要素が考慮される。すなわち、例えば特徴ベクトル同士のスカラー積により決定される特徴類似度、および幾何学的整合性である。剛体に注目する場合、後者の要素が最も良くあてはまる。この場合、特徴の変移は無秩序ではなく、むしろ視点の変化がもたらす相関を示す。例えば、カメラが左へ移動すると、画像内の特徴位置が右へ移動することが観察できる。物体が変形可能または関節移動可能である場合、特徴変移はカメラ視点のみでは決定されないが、隣接する特徴は依然として同様の仕方で移動する傾向があるだろう。このように、画像マッチングは、少なくとも２項を含む目的関数の最小化を含む最適化問題として定式化することができる。第１の項は、第１の画像から抽出されて第２の画像内の対応する位置に置かれた特徴同士の不整合に対して不利益をもたらす。第２の項は、隣接する合致箇所同士の相違を測定することにより、両者を空間的に整合させる。Felzenzwalb & Huttenlocher, “Pictorial Structures for Object Recognition,” Intl. Journal of Computer Visions 61(1), 55-79 (2005)に、これがＮＰ困難な最適化問題を構成することが示されている。
【００４９】
画像マッチング問題を量子アルゴリズムで解けるようにするために、画像マッチング問題を以下の形式の２次無制約２値最適化（「ＱＵＢＯ」）問題にマッピングすることができる。
【数３】
２値最適化変数ｘｉ、ｘｊはある画像の特徴がどのように他の画像にマッピングされるかを決定する。係数Ｑｉｊは、得られた目的関数の最小化により特徴類似度および幾何学的整合性を共に最大化すべく選択される。式（１）は量子断熱アルゴリズム等の量子計算・アルゴリズムを用いて解くことができる。
【００５０】
画像マッチング問題を解く量子プロセッサを実装する一般的な方法を以下に提示する。図１は、本方法１００の実施形態を示すフロー図である。方法１００は、３つのステップの新規な組合せである。すなわち、画像１０１、１０２（例えば、視覚的な画像を表す電子データまたは情報）のグラフ表現を生成し、連合グラフ１０３を用いてパターンマッチングを行ない、量子プロセッサを含むシステムを用いて問題１０４を解くことである。ステップ１０１において、画像データベース（「データベースグラフ」）内のいくつかまたは全ての画像（「データベース画像」）のグラフ表現を決定する。これは例えば、従来の（デジタル）プロセッサを用いて行なうことができる。ステップ１０２において、クエリー画像（「クエリーグラフ」）のグラフ表現を決定する。ステップ１０３において、クエリーグラフをデータベースグラフと比較し、各々の比較に際して対応する連合グラフを生成する。ステップ１０４において、量子プロセッサを用いて各連合グラフの少なくとも１つの特徴を決定する。ステップ１０５において、量子プロセッサにより決定された連合グラフの少なくとも１つの特徴に従い、これらの結果をランク付けする。ランク付けは、最も高いランクがクエリーグラフと対応するデータベースグラフとの間、すなわちクエリー画像と対応するデータベース画像との間で最良の合致を示すように決定することができる。
【００５１】
ステップ１０４において、量子プロセッサにより決定できる連合グラフの特徴または特徴群は、調べられている画像の種類または認識アルゴリズムの特性に依存する場合がある。二つの適切な特徴として、連合グラフの最大独立集合（「ＭＩＳ」）および最大クリーク（「ＭＣ」）が含まれる。これら二つの特徴は関連しており、従って各連合グラフにおけるこれら二つの特徴のうち一方のみを決定することにより画像認識を実行することができる。グラフのＭＩＳとは、全てが辺により連結されている節点の最大部分集合である。連合グラフ内のＭＩＳが大きいほど、クエリーグラフと対応するデータベースグラフの合致がより良いことを示す。従って、最大ＭＩＳを有していると決定された連合グラフは、クエリー画像とデータベース画像とが最も良く合致していると思われる。ＭＩＳを代替するものとして、ＭＣは、どの辺も共有しない節点の最大部分集合であり、従って最大ＭＩＳを有する連合グラフは通常、最小ＭＣを有する。従って、当業者には、ランキングの順序が逆である点を唯一の違いとして、ＭＣ問題を解くことはＭＩＳ問題を解くことと同様であることが理解されよう。方法１００を実装することにより、現在実用化されている技術に対して、自動画像認識の速度および／または精度を向上させることができる。
【００５２】
方法１００を適用してクエリー画像に合致するデータベース画像を見つけることができる。しかし、方法１００はまた、クエリー画像に含まれる特定の特徴に合致する特定の特徴を含むデータベース画像を見つけるべく適用することもできる。この場合の違いは、画像全部のマッチングに加え、方法１００を適用することにより、クエリー画像内の特徴を識別して画像データベース内で当該特徴との合致を見つけることができる点である。例えば、クエリー画像が人間の顔を含み、方法１００を適用することにより、得られるデータベース画像が複数の人間の顔を含み、合致する顔がデータベース画像の１つの特徴でしかない場合であっても、画像データベース内で合致する人間の顔を含むデータベース画像を見つけることができる。そのようなアプリケーションにおいて、方法１００のいくつかの実施形態により、ステップ１０２で決定されたクエリー画像のグラフ表現を、マッチングしたいクエリー画像の特定の特徴のグラフ表現に限定することができる。
【００５３】
本システム、方法、および装置は、自動画像認識を実行する際にデジタルプロセッサと量子プロセッサの両方を用いることを記述する。いくつかの実施形態において、画像のグラフ表現（または、所望するクエリーに応じて画像の特定の特徴）の生成および連合グラフの生成はデジタルプロセッサを用いて実行することができる一方、各連合グラフの少なくとも１つの特徴の決定は量子プロセッサを用いて実行することができる。
【００５４】
顔画像は、グラフにより表現できる画像の種類の具体例である。顔画像のグラフ表現の生成は進歩の途上にある研究分野である。その基本原理は、顔の特定の特徴（目、鼻および口等、および他の多くのより微妙な特徴も同様に）の相対位置が最終的に各々の顔毎に一意である組合せを画定する点である。従って、これらの相対位置のグラフ表現を用いて指紋とほぼ同様に個人を識別することができる。そのようなグラフ表現において、識別可能な特徴（再び目や口等）を辺の網の目により連結された節点または頂点により表現することができる。辺は節点の相対位置を画定することができる。節点の個数が多いほど（すなわち、画像で識別される特徴の数が多いほど）グラフ表現の精度が高い。体の他の部位、例えば虹彩または指紋、を表現する画像に関して同一または類似の方法を行なうことができる。
【００５５】
図２Ａは、元の顔画像を覆うグラフ表現２００を示す例示的な図である。図２Ａにおいて、節点２０１〜２０４は口の輪郭を画定する。簡潔にするため、グラフ表現２００は比較的少ない節点（同図では４つのみ明示）で構成されているため、元の顔画像の比較的不正確な表現となっている。しかし、当業者には、グラフの節点数を増やして画像内でより多くの顔の特徴を表現することにより、顔画像のグラフ表現の精度を向上できる点が理解されよう。更に、図２Ａは顔画像のグラフ表現の一例を示しているに過ぎない。図２Ａの節点および節点間の対応する辺により識別される具体的な顔の特徴は、必要とされるグラフスキームを表現していない。当業者には、グラフ表現並びに節点間の辺の対応するネットワークにより識別される特定の顔の特徴が、グラフ表現を生成する方法に応じて異なり得る点が理解されよう。当業者にはまた、顔画像のグラフ表現を生成する原理および技術が他の種類の画像、例えば物体、景色、地図、指紋等の画像にも適用できる点が理解されよう。このように、図２Ａは顔画像のグラフ表現のみを示しているが、当業者にはどのように任意の種類の画像のグラフ表現が同様に決定できることが理解されよう。
【００５６】
画像のグラフ表現は手操作で描画しても、あるいは自動的に生成してもよい。そのようなグラフ表現の究極の目的は画像認識であって、膨大な画像データベース内の全ての画像に対してグラフ表現を決定することが必要な場合がある。従って、手で全てを描画するのではなく、画像のグラフ表現を自動的に生成するシステムを開発する方がより現実的である。そのようなシステムの例として、弾性バンチグラフマッチング（ＥＢＧＭ）がある。ＥＢＧＭは、特に顔画像に適用されるべく設計されている。しかし、その基本原理は任意の種類の画像に適用することができる。ＥＢＧＭにおいて、一般化されたモデルグラフが決定されており、これらを新規の顔画像に当てはめて成型することにより新たなグラフを作成する。この技術の完全な詳細は、Wiskott et al., Face Recognition by Elastic Bunch Graph Matching, IEEE Transactions on Pattern Analysis and Machine Intelligence, 19(7):775-779, 1997に記述されている。グラフ表現の精度を上げると結果的に認識処理における計算量が増大するため、この技術の継続的な課題は精度と速度の間のトレードオフである。しかし、連合グラフを用いてパターンマッチングを組み込み、次いでその結果生じたＭＩＳ問題を量子プロセッサを用いて解くことにより、現在実用化されている技術に比べて精度と計算時間の両方を向上させることができる。
【００５７】
ＥＢＧＭは、顔画像のグラフ表現の自動生成における主要な技術である。しかし、当業者には、本システム、方法、および装置ではＥＢＧＭによりグラフ表現が生成する必要がない点が理解されよう。先に述べたように、意味のある連合グラフを生成できる程度にクエリーとデータベースグラフの間に十分な整合性がある限り、顔画像または他の任意の種類の画像のグラフ表現を手動で、または他の任意のシステムを用いて生成することができる。
【００５８】
特定のクエリーの場合、古典的デジタルプロセッサを用いて、データベースの特定の部分集合を自動的に表すクエリー画像の特定のキーとなる態様を識別することが望ましいであろう。例えば、クエリー画像のグラフ表現が生成されている間、あるいは連合グラフが生成される前にグラフ表現から、クエリーをデータベース内の何らかの部分集合に直ちに関連付けるクエリー画像の何らかの態様を識別することが可能な場合がある。そのような識別が行なわれた場合、クエリー画像を、同一の態様を共有するデータベース画像のみと比較すればよく、従って生成される連合グラフが少なくなる。基本的に、データベースをフィルタリングまたはプルーニング（剪定）することにより、合致する、認められる可能性のある画像のみを比較して連合グラフを生成する。一例として、最初にクエリー画像を人間の顔に関するものとして分類し、次いで対応する画像データベースを、少なくとも一人の人間の顔を含む画像の部分集合に絞り込むことができる。更に顔画像認識では、データベース画像との比較の前にクエリー画像のグラフ表現から顔画像の人種または性別を識別することが可能である。この例では、調べられるデータベースをクエリー画像の人種または性別に合致する顔画像の部分集合に絞り込まれる。このために生成する必要のある連合グラフが少なくて済み、その結果量子プロセッサの呼び出しが減少して計算時間が短縮される。この事前フィルタリングまたはプルーニングは、ユーザまたはデジタルコンピュータにより実行することができる。
【００５９】
当業者には、グラフ表現が任意の種類の画像に対して生成できる点が理解されよう。例えば、物体、景色、地図、指紋および星座の画像は全てグラフにより表現することができる。更に、グラフ表現は、画像全体ではなく、画像の態様の特定の特徴に対して生成することができる。
【００６０】
本明細書および添付の請求項を通じて、古典的プロセッサと量子プロセッサとの間の通信に言及する。例えば、連合グラフは、方法１００のステップ１０３にあるように古典的プロセッサを用いて生成でき、次いで方法１００のステップ１０４にあるように量子プロセッサを用いて連合グラフを解析することができる。図２Ｂは、古典的プロセッサと量子プロセッサとの間で通信する方法２５０の実施形態を示すフロー図である。方法２５０は４つのステップ２５１〜２５４を含んでいる。ステップ２５１において、古典的プロセッサを用いてクエリーを処理する。クエリーの処理は、クエリーのパラメータを定義するステップ、クエリー画像の特定の特徴を識別するステップ、連合グラフを生成するステップ、クエリーを分類するステップ、および終了基準を決めるステップを含むがこれに限定されない各種の動作を含んでいてよい。クエリーの処理はまた、量子プロセッサにより送信および管理可能な形式にクエリーを変換するステップを含んでいてよい。ステップ２５２において、処理されたクエリーを古典的プロセッサから量子プロセッサへ送信する。ステップ２５３において、量子プロセッサを用いてクエリーに回答する。クエリーに回答するステップは、連合グラフの少なくとも１つの特徴（例えば、ＭＩＳまたはＭＣ）を決定するステップを含むがこれに限定されない各種の処理を含んでいてよい。量子プロセッサは、クエリーが満足されるまでクエリーを管理する。ステップ２５４において、クエリーへの回答結果を古典的プロセッサに返す。これには、クエリーの結果を量子プロセッサから古典的プロセッサに送信するステップが含まれていてよい。
【００６１】
本システム、方法および装置によれば、断熱量子計算のアルゴリズムおよび／または量子アニーリングは発見的方法で実装することができ、その場合、解の大域的最適性の要件は取り下げられる。量子プロセッサはそのようなアルゴリズムを用いて、ａ）古典的な解決システムと同じ長さの時間でより正確な解を与え、ｂ）古典的な解決システムより短い時間で同程度の精度を与え、あるいはｃ）古典的な解決システムより短い時間でより正確な解を与えることができる。
【００６２】
断熱量子計算、および同様に量子アニーリングは各種の異なる方法で実装することができる。断熱量子計算の特定の実装例は、米国特許出願第１１／３１７，８３８号、およびWocjan et. al., 2003, "Treating the Independent Set Problem by 2D Ising Interactions with Adiabatic Quantum Computing", arXiv.org:quant-ph/0302027 (2003), pp.1-13に記述されており、量子ビット結合アーキテクチャを用いて、式（２）で与えるように１局所横磁場を有する２局所イジングハミルトニアンを実現する。
【数４】
【００６３】
式中、ｎは量子ビットの個数、
【数５】
は第ｉ量子ビットのパウリＺ行列、
【数６】
は第ｉ量子ビットのパウリＸ行列、またｈｉ、ΔｉおよびＪｉｊは各量子ビットに結合された無次元の局所場である。式（２）のｈｉ項は、各々の第ｉ量子ビットのＺ基底に信号または場を結合することにより物理的に実現することができる。式（２）のΔｉ項は各々の第ｉ量子ビットのＸ基底に信号または場を結合することにより物理的に実現することができる。式（２）のＪｉｊ項は、量子ビットの対（量子ビットｉおよびｊの各々）のＺ基底を互いに結合することにより物理的に実現することができる。
【００６４】
図３は、断熱量子計算（および／または量子アニーリング）用に設計された従来の超伝導量子プロセッサ３００の一部の模式図である。図３に示す超伝導量子プロセッサ３００の部分は、２つの超伝導量子ビット３０１、３０２と、その間で情報を結合する調整可能ＺＺカプラ３１１を含んでいる。図３に示す量子プロセッサ３００の部分が２つの量子ビット３０１、３０２および１つのカプラ３１１のみを含んでいるが、当業者には、量子プロセッサ３００が任意の数の量子ビット、およびその間で情報を結合する任意の数の結合素子を含んでいてよいことが理解されよう。
【００６５】
図３に示す量子プロセッサ３００の部分は、式２に記述されたハミルトニアンを物理的に実現すべく実装することができる。σｚおよびσｘの項を与えるべく、量子プロセッサ３００は、量子プロセッサ３００の状態を設定および制御するために用いるプログラミング・インターフェース３２１〜３２４を含んでいる。各々のプログラミング・インターフェース３２１〜３２４は図示するように、プログラミング・システム（図示せず）への各々の誘導結合により実現することができる。そのようなプログラミング・システムは量子プロセッサ３００とは分離されていても、あるいは米国特許出願第１１／９５０，２７６号に記述されているように局所的に（すなわち、量子プロセッサ３００にオンチップに）含まれていてもよい。
【００６６】
量子プロセッサ３００のプログラミングにおいて、プログラミング・インターフェース３２１および３２４の各々を用いて磁束信号を量子ビット３０１および３０２の各々の複合ジョセフソン接合３３１および３３２に結合することにより、系のハミルトニアンのΔｉ項を実現することができる。この結合により式２のσｘ項が得られる。同様に、プログラミング・インターフェース３２２および３２３の各々を用いて磁束信号を量子ビット３０１および３０２の各々の量子ビットループに結合することにより、系のハミルトニアンのｈｉ項が実現される。この結合により２のσｚ項が得られる。図３において、プログラミング・インターフェース３２１〜３２４の各々の系のハミルトニアンに対する寄与を枠３２１ａ〜３２４ａに示す。
【００６７】
当業者には、断熱量子計算および／または量子アニーリングが図３のシステム３００とは異なるシステムを実装することにより、および／または式２と異なるハミルトニアンを実装することにより実現できることが理解されよう。システム３００およびハミルトニアン２は、本システム、方法、および装置の実施形態の単なる具体例としての役割のみ意図されている。
【００６８】
本システム、方法、および装置は、画像マッチング問題を解くために量子プロセッサを用いる少なくとも２種類のモードを提供するが、好適なモードは問題の規模（すなわち連合グラフ内の頂点の数）に依存する。第１の動作モードすなわち「ネイティブモード」では、問題の規模は、問題全体を直接量子プロセッサにマッピング可能な程度に十分に小さい。第２の動作モードすなわち「混合モード」では、問題の規模が直接量子プロセッサにマッピングするには大き過ぎ、これを補償すべく当該問題をより小さい問題の集合に分解して個別に量子プロセッサにマッピング可能にする。
【００６９】
ネイティブモード動作では、画像マッチング問題は直接量子プロセッサにマッピングされる。画像の任意の対（すなわちクエリー画像とデータベース画像を合わせたもの）に対して、連合グラフを用いて２つの画像のグラフ表現間の類似度を測定することができる。連合グラフの各頂点は、第１の画像内の特徴αと第２の画像内の特徴βとの間の関連に対応していてよい。連合グラフ内の各辺は、第１の画像内の特徴ベクトルの対と第２の画像内の特徴ベクトルの対との間で何らかの幾何学的整合性を符号化することができる。連合グラフのＭＩＳは、類似度（ＭＩＳが大きいほど相互の重なり領域が大きい）および、第１の画像の特徴から第２の画像の特徴への最大無衝突マッピングの両方を提供する。上述のように、この技術を用いて２つの画像全体同士をマッチングさせる、あるいはデータベース画像の集合内でクエリー画像から特定の特徴を見つけることができる。例えば、「クエリー画像の全体または一部が対応するデータベース画像内のどこかに含まれていれば合致」が得られる。本システム、方法、および装置によれば、連合グラフのＭＩＳを見つける問題は、全ての頂点に対してＱｉｉ＝−１、および頂点間に辺が存在する場合は常にＱｉｊ＝Ｌを設定することによりＱＵＢＯ問題として定式化することができる。ＱＵＢＯ問題の最小エネルギー設定により、対応する頂点がＭＩＳの成分である場合に限りｘｉ＝１でなければならず、それ以外の場合はｘｉ＝０である。
【００７０】
図４は、量子プロセッサにより画像マッチング問題を解く際のネイティブ動作モードの場合の方法４００の実施形態のフロー図である。方法４００は、図１で方法１００により記述される一般的な方法をより詳細に述べる。具体的には、方法４００は、図３のシステム３００と同様の量子プロセッサを用い、且つ式２に記述されているハミルトニアンを実装することにより、方法１００のステップ１０４の実行に用いるステップの例を示す。方法１００のステップ１０４において、量子プロセッサを用いて連合グラフの少なくとも１つの特徴を決定する。従って、方法４００のステップ４０１において、結合されたｎ頂点ＱＵＢＯを記述する行列Ｑとして連合グラフを定義し、ｎは量子プロセッサ内の量子ビットまたは実効量子ビットの個数により制限される。ステップ４０２において、式２における目標値ｈｉおよびＪｉｊを行列Ｑから決定する。ステップ４０３において、ｎ個の頂点の各々を、量子プロセッサ内の各量子ビットまたは実効量子ビットにより識別する。ステップ４０４において、量子プロセッサにより量子アルゴリズムを実行する。このアルゴリズムは、適切な時間依存関数ｈｉ（ｔ）、Δｉ（ｔ）、およびＪｉｊ（ｔ）を適用することにより断熱量子計算および／または量子アニーリングを含んでいてよい。ステップ４０５において、量子アルゴリズムの結果を評価する。解決が満足できない場合、本方法はステップ４０４に戻る。解決が満足できる場合、本方法は４０６へ進む。ステップ４０６において、画像マッチング問題の解を出力する。
【００７１】
図４に記述する方法４００は、単一の連合グラフのＭＩＳ（または代替的にＭＣ）を決定する手順を提供する。図１の方法１００に記述したように、画像マッチング問題において、連合グラフの集合が生成され、各連合グラフはクエリー画像と一意なデータベース画像との間の比較の各々に対応する。方法４００は、クエリー画像と単一のデータベース画像との間でどれほど良好な合致が得られたかを決定する手順を効果的に提供する。従って、画像マッチング問題を解くには、各連合グラフについて方法４００を終了させ、次いで方法１００のステップ１０５のように結果にランク付けする必要がある。
【００７２】
多くの断熱量子計算・アーキテクチャの場合、利用できる物理的量子ビットの数は、解くべき画像マッチング問題の変数の数より極めて少ない（すなわちｎ＞量子ビットの数）。従って、大きなマッチング問題画像をより小さい問題の集合に分解する必要がある。そのような場合、完全な画像マッチング問題をより小さい問題の集合に分解して、量子プロセッサにより各々のより小さい問題を解くことができるようにする混合動作モードを実装する必要がある。当業者には、各種の分解技術をこの目的に実装できることが理解されよう。本システム、方法、および装置は、局所探索アルゴリズムを実行することにより量子プロセッサを用いてこの分解を実行する技術について記述する。
【００７３】
図５は、量子プロセッサにより画像マッチング問題を解く際の混合動作モードの方法５００の実施形態のフロー図である。図４の方法４００と同様に、方法５００の目的はＱＵＢＯ問題を解くことであり、解は連合グラフのＭＩＳ（または代替的にＭＣ）を表す。ステップ５０１において、例えば古典的な発見的ソルバーを用いて解の初期近似を決定する。ＱＵＢＯ問題の適当な古典的発見的ソルバーの例として、http://hces.bus.olemiss.edu/reports/hces0900.pdfに開示されているGlover et al., "One pass heuristics for large scale unconstrained binary quadratic problems," University of Mississippi Technical Report HCES-09-00 (2000)に記述されている要約−貪欲−清掃アルゴリズムがあるが、当業者には他の古典的発見的なソルバーを代替的に用いてもよいことが理解されよう。解の初期近似は局所探索アルゴリズムの出発点として使われる。解の初期近似は変数の集合Ｘｏを含んでいる。ステップ５０２において、変数集合Ｘｏの部分集合Ｓｏを選択することから局所探索アルゴリズムが開始される。部分集合Ｓｏの変数の数は、量子プロセッサに直接マッピング可能な変数の数に等しいか少ない。ステップ５０３において、変数の部分集合Ｓｏを、式３に記述されている最適化問題として量子プロセッサにマッピングする。
【数７】
このように、ステップ５０３において量子プロセッサを用いて変数の部分集合Ｓｏを最適化して解の初期近似を改良する。ステップ５０４において、ステップ５０３で決定された改良解が解の初期近似として再使用される。ステップ５０５において、何らかの終了基準が満たされるまでステップ５０２〜５０４を繰り返す。適切な終了基準の例として、指定された繰り返し回数、指定された時間、および／または指定された精度が含まれるがこれに限定されない。ステップ５０６において、問題の最終解を出力する。量子計算の再帰的技術が２００７年６月１２日出願の米国仮特許出願第６０／９４３，５１９号、「再帰的量子計算アルゴリズムのシステム、方法、および装置(Systems, Methods, and Apparatus for Recursive Quantum Computing Algorithms)」に記述されている。
【００７４】
方法５００の潜在的な短所は、全変数Ｘｏの空間における大域的最小値ではなく、変数の部分集合Ｓｏの空間における局所最小値しか特定しない点である。本システム、方法、および装置によれば、局所最小値の回避を支援すべくタブー探索ヒューリスティックにおいて方法５００の局所探索アルゴリズムを実行することができる。タブー探索の各々の繰り返しは（当該技術分野で知られているように）、先行する繰り返しの結果を格納して呼び出す。従って、いくつかの実施形態では、方法５００が実装されているのと同様に、各々の繰り返しからの結果を格納することができる。これらの格納された結果は、各々の単一の変数を変えて、それによりコストに変化する各変数を関連付けることによる効果に関するデータを含んでいてよい。各々の連続する繰り返しにおいて、当該アルゴリズムは、まだ変更されていない変数を調整して、格納されたデータに新しいエントリを生成することを選択できる。この格納されたデータは次いで、解の起伏の勾配に対する見通しを与えて、後続する繰り返しが「最適な」局所最小値、または理想的には大域的最小値へ向かって進むことができるようする。
【００７５】
当業者には、本明細書を通じて用語「解く」が厳密解および近似解の両方を包含するように用いられていることが理解されよう。
【００７６】
上述のように、本システム、方法、および装置は画像マッチングに用いることができる。本出願は、２つの完全な画像をマッチングさせるステップを含んでいても、あるいは、画像データベース内でクエリー画像の全てまたは一部を含むデータベース画像を見つけるステップを含んでいてよい。例えば、クエリー画像は道路標識を含み、画像データベース内で合致する道路標識を含むデータベース画像を見つけることを望んでもよい。しかし、本システム、方法、および装置が提示する概念はより広範な問題の集合に適用することができる。データベース内でクエリーに合致するものを見つけることが望ましい広範なアプリケーションが存在する。いくつかの実施形態において、本システム、方法、および装置を、２つの物体同士の類似度を決定する方法として一般化することができ、２つの物体の特徴は量子プロセッサにより解析される連合グラフに組み込まれる。量子プロセッサは、連合グラフを解析して、２つの物体同士の類似度を表す値を返すことができる。いくつかのアプリケーションにおいて、２つの物体は、クエリー画像およびデータベース画像等の画像であってよい。しかし、他のアプリケーションでは２つの目的が他の形式であってもよい。例えば、いくつかの実施形態は、関係データベースのエントリ間のクエリーをマッチングさせるステップを提供することができる。他の実施形態は、音声パターンマッチング、ＤＮＡ配列マッチングを含むがこれに限定されない、他の形式のパターンマッチングを提供することができる。
【００７７】
要約書の記述を含め、例示する実施形態の上の説明は網羅的ではなく、また実施形態を開示した形式通りに限定することを意図していない。本明細書では特定の実施形態および例を例示目的で記述しているが、当業者には理解されるように、本開示の概念および範囲から逸脱することなく各種の等価な変更を施すことが可能である。本明細書に提示する各種の実施形態は必ずしも上で一般的に述べた量子計算の例示的なシステム、方法、およびデバイスではなく、量子計算の他のシステム、方法、およびデバイスにも適用可能である。
【００７８】
上述の各種の実施形態を組み合わせて更なる実施形態を提供することができる。本明細書で参照した、および／または出願データシートに掲載されている全ての米国特許、米国特許出願公開、米国特許出願、外国特許、外国特許出願、および非特許文献の全文が本明細書に援用されている。すなわち以下の文献が含まれるがこれらに限定されない。２００７年４月１９日出願の米国仮特許出願第６０／９１２，９０４号「自動画像認識用のシステム、方法、および装置(Systems, Methods and Apparatus for Automatic Image Recognition)」、米国特許第６，８３８，６９４号、米国特許第７，３３５，９０９号、米国特許公開第２００６−０２２５１６５号、米国特許出願第１２／０１３，１９２号、２００７年１１月８日出願の米国仮特許出願第６０／９８６，５５４号「アナログ処理用のシステム、デバイス、および方法(Systems, Devices and Methods for Analog Processing)」、米国特許公開第２００６−０１４７１５４号、米国特許出願第１２／０１７，９９５号、米国特許第７，１３５，７０１号、米国特許出願第１１／９３２，２４８号、米国特許出願第１１／９３２，２６１号、米国特許出願第１１／３１７，８３８号、米国特許出願第１１／９５０，２７６号、および２００７年６月１２日出願の米国仮特許出願第６０／９４３，５１９号「再帰的量子計算アルゴリズムのシステム、方法、および装置(Systems, Methods, and Apparatus for Recursive Quantum Computing Algorithms)」。必要に応じて、各種の特許、出願および刊行物のシステム、回路および概念を採用すべく実施形態の態様を修正して更なる実施形態を提供することができる。
【００７９】
上で詳述された内容を考慮して実施形態に対し上記および他の変型を施すことができる。一般に、以下の特許請求の範囲において、使用する用語は、本明細書および特許請求の範囲に開示された特定の実施形態に特許請求の範囲が限定されると解釈すべきではなく、それらの特許請求の範囲が対応する等価物の完全な範囲に含まれる全ての可能な実施形態を含むものと解釈すべきである。従って、特許請求の範囲は本開示に限定されない。
【技術分野】
【０００１】
関連出願の相互参照
本出願は、米国特許法施行規則１１９（ｅ）条の下で、２００７年４月１９日出願の米国仮特許出願第６０／９１２，９０４号「自動画像認識用のシステム、方法、および装置(Systems, Methods and Apparatus for Automatic Image Recognition)」を優先権主張するものであり、本明細書にその全文を援用している。
【０００２】
背景
分野
本システム、方法、および装置は、画像データベースから顔画像等の画像を自動認識する量子プロセッサの実装に関する。
【背景技術】
【０００３】
関連技術の説明
チューリングマシンは、１９３６年にAlan Turingによって述べられた理論的計算システムである。任意の他のチューリングマシンを効率的にシミュレートすることが可能なチューリングマシンは、汎用チューリングマシン(Universal Turing Machine)（ＵＴＭ）と呼ばれる。チャーチ・チューリングの提唱(Church-Turing thesis)では、いかなる実際的な計算モデルも、ＵＴＭの機能の同等物またはサブセットのいずれかを有すると述べられている。
【０００４】
量子コンピュータは、計算を実行するために１つ以上の量子効果を利用する、任意の物理システムである。任意の他の量子コンピュータを効率的にシミュレートすることが可能な量子コンピュータは、汎用量子コンピュータ(Universal Quantum Computer)（ＵＱＣ）と呼ばれる。
【０００５】
１９８１年に、Richard P.Feynmanは、量子コンピュータは、特定の計算問題を解くために、ＵＴＭよりも効率的に使用されることが可能であり、したがってチャーチ・チューリングの提唱を無効にする、ということを提唱した。例えば、Feynman R.P., "Simulating Physics with Computers", International Journal of Theoretical Physics", Vol.21 (1982) pp.467-488を参照されたい。例えば、Feynmanは、量子コンピュータが、特定の他の量子系をシミュレートするために使用されることが可能であり、それにより、ＵＴＭを使用して可能であるよりも指数関数的に高速な、シミュレートされる量子系の特定の特性の計算を可能にするということを指摘した。
【０００６】
量子計算へのアプローチ
量子コンピュータの設計および動作への、いくつかの一般的なアプローチがある。１つのそのようなアプローチは、量子計算の「回路モデル(circuit model)」である。このアプローチでは、量子ビットが、アルゴリズムのコンパイルされた表現である、論理ゲートのシーケンスによる作用を受ける。回路モデル量子コンピュータは、実際的な実施のためには、いくつかの重大な障害を有する。回路モデルでは、量子ビットが、１ゲート時間(single-gate time)よりもはるかに長い期間にわたってコヒーレントのままであることが要求される。この要求が発生する理由は、回路モデル量子コンピュータは、動作するために、量子誤り訂正と集合的に呼ばれる動作を必要とするからである。量子誤り訂正は、回路モデル量子コンピュータの量子ビットが量子コヒーレンスを、１ゲート時間の１０００倍のオーダーの期間にわたって維持することが可能でなければ、実行されることはできない。多くの研究が、回路モデル量子コンピュータの基本情報単位を形成するための十分なコヒーレンスを有する量子ビットの開発に焦点を置いてきた。例えば、Shor, P.W. "Introduction to Quantum Algorithms", arXiv.org:quant-ph/0005003 (2001), pp.1-27を参照されたい。当該技術分野は、量子ビットのコヒーレンスを、実際的な回路モデル量子コンピュータの設計および動作のための許容可能なレベルまで増加させることが不可能であることによって、依然として阻まれている。
【０００７】
量子計算への別のアプローチは、結合された量子系の、系の自然な物理的進化を、計算システムとして使用することを含む。このアプローチでは、量子ゲートおよび回路を不可欠なものとして使用することはしない。その代りに、このアプローチは、既知の初期ハミルトニアン(initial Hamiltonian)から開始して、結合された量子系の、系のガイドされた物理的進化に依拠し、ここで、解かれるべき問題は、系のハミルトニアンの項内に符号化されており、それにより、結合された量子系の、系の最終状態が、解かれるべき問題への答えに関連する情報を含む。このアプローチは、長い量子ビットコヒーレンス時間を必要としない。このタイプのアプローチの例は、断熱量子計算(adiabatic quantum computation)、クラスタ状態量子計算(cluster-state quantum computation)、一方向量子計算(one-way quantum computation)、量子アニーリング(quantum annealing)および古典的アニーリング(classical annealing)を含み、例えば、Farhi, E et. al., "Quantum Adiabatic Evolution Algorithms versus Simulated Annealing" arXiv.org:quant-ph/0201031 (2002), pp.1-16に記載されている。
【０００８】
量子ビット
前述のように、量子ビットは、量子コンピュータのための情報の基本単位として使用されてもよい。ＵＴＭにおけるビットと同様に、量子ビットは、少なくとも２つの別個の量を意味してもよい。量子ビットは、情報が記憶される実際の物理デバイスを意味してもよく、そして量子ビットは、さらに、その物理デバイスから離れて抽象化された、情報の単位そのものを意味してもよい。量子ビットの例としては、量子粒子、原子、電子、光子、イオンなどが挙げられる。
【０００９】
量子ビットは、古典的デジタルビットの概念を一般化する。古典的情報記憶デバイスは、一般に「０」および「１」とラベル付けされる、２つの離散的な状態を符号化することが可能である。物理的には、これらの２つの離散的な状態は、磁場、電流、または電圧の、方向または大きさなどの、古典的情報記憶デバイスの２つの異なる、かつ区別できる物理的状態によって表され、ここで、ビット状態を符号化する量は、古典物理学の法則に従って振る舞う。量子ビットも、同様に、やはり「０」および「１」とラベル付けされてもよい、２つの離散的な物理的状態を含む。物理的には、これらの２つの離散的な状態は、磁場、電流、または電圧の、方向または大きさなどの、量子情報記憶デバイスの２つの異なる、かつ区別できる物理的状態によって表され、ここで、ビット状態を符号化する量は、量子物理学の法則に従って振る舞う。これらの状態を記憶する物理量が量子力学的に振る舞う場合、デバイスはさらに、０および１の重ね合わせに位置してもよい。すなわち、量子ビットは、同時に「０」および「１」状態の両方に存在してもよく、したがって、両方の状態についての計算を同時に実行することが可能である。一般に、Ｎ個の量子ビットは、２Ｎ個の状態の重ね合わせにあることが可能である。量子アルゴリズムは、いくつかの計算を高速化するために、重ね合わせの特性を利用する。
【００１０】
標準的な記法では、量子ビットの基底状態(basis states)は、｜０＞および｜１＞状態と呼ばれる。量子計算の間、量子ビットの状態は、一般に、基底状態の重ね合わせであり、そのため量子ビットは、｜０＞基底状態を占める０ではない確率と、それと同時の、｜１＞基底状態を占める０ではない確率とを有する。数学的には、基底状態の重ね合わせは、｜Ψ＞で示される量子ビットの全体的状態が、｜Ψ＞＝ａ｜０＞＋ｂ｜１＞の形式を有することを意味し、式中、ａおよびｂは、それぞれ、確率｜ａ｜２および｜ｂ｜２に対応する係数である。係数ａおよびｂは、量子ビットの位相が特徴付けられることを可能にする、実数および虚数成分をそれぞれが有する。量子ビットの量子的性質は、大部分が、基底状態のコヒーレントな重ね合わせに存在する量子ビットの能力、および量子ビットの状態が位相を有する能力に由来する。量子ビットは、デコヒーレンスの源から十分に分離されている場合、基底状態のコヒーレントな重ね合わせとして存在するこの能力を維持する。
【００１１】
量子ビットを使用した計算を完了するためには、量子ビットの状態が測定される（すなわち、読み取られる）。一般に、量子ビットの測定が実行される場合、量子ビットの量子的性質は一時的に失われて、基底状態の重ね合わせは、｜０＞基底状態または｜１＞基底状態のいずれかに崩壊し、それにより、従来のビットとの類似性が取り戻される。崩壊した後の量子ビットの実際の状態は、読み取り動作の直前の確率｜ａ｜２および｜ｂ｜２に依存する。
【００１２】
超伝導量子ビット
量子計算に使用するために検討されている多くのさまざまなハードウェアおよびソフトウェアアプローチがある。１つのハードウェアアプローチでは、アルミニウムまたはニオブなどの超伝導材料で形成された集積回路を使用する。超伝導集積回路の設計および製造に含まれる、技術および処理は、従来の集積回路のために使用されるものに類似している。
【００１３】
超伝導量子ビットは、超伝導集積回路内に含まれることが可能なタイプの超伝導デバイスである。典型的な超伝導量子ビットは例えばスケーラビリティを利点としており、一般に、例えば電荷および位相素子、位相または磁束素子、ハイブリッド素子等を含む情報の符号化に用いられる物理的特性に応じて分類される。超伝導量子ビットは、情報を符号化するために使用される物理的特性に応じて、いくつかのカテゴリに分けられてもよい。例えば、超伝導量子ビットは、例えば、Makhlin et. al., 2001, Reviews of Modern Physics 73, pp.357-400で述べられているように、電荷、磁束、および位相デバイスに分けられてもよい。電荷デバイスは、デバイスの電荷状態内で、情報を記憶および操作し、ここで、電気素量はクーパー対と呼ばれる一対の電子からなる。クーパー対は２ｅの電荷を有し、例えばフォノン相互作用によって共に結合された、２つの電子からなる。例えば、NielsenおよびChuang、Quantum Computation and Quantum Information, Cambridge University Press、Cambridge (2000), pp.343-345を参照されたい。磁束デバイスは、デバイスの何らかの部分を通る磁束に関連する変数内に、情報を記憶する。位相デバイスは、位相デバイスの２つの領域間の超伝導位相の差に関連する変数内に、情報を記憶する。最近、電荷、磁束、および位相のうちの２つ以上の自由度を使用するハイブリッドデバイスが開発された。例えば、米国特許第６，８３８，６９４号および米国特許第７，３３５，９０９号を参照されたい。
【００１４】
使用されてもよい磁束量子ビットの例としては、１つのジョセフソン接合または複合接合（単一のジョセフソン接合が２つの並列なジョセフソン接合によって置き換えられる）によって遮断される超伝導ループを含む、ｒｆ−ＳＱＵＩＤ、あるいは、３つのジョセフソン接合によって遮断される超伝導ループを含む、永久電流量子ビットなどが挙げられる。例えば、Mooij et. al., 1999, Science 285, p.1036、およびOrlando et. al., 1999, Phys. Rev. B 60, p.15398を参照されたい。超伝導量子ビットのその他の例は、例えば、Il'ichev et. al., 2003, Phys.Rev.Lett.91,097906、Blatter et. al., 2001, Phys. Rev. B 63, 174511、およびFriedman et. al., 2000, Nature 406, p.43に見出すことができる。さらに、ハイブリッド電荷−位相量子ビットも使用されてもよい。
【００１５】
量子ビットは、対応する局所的バイアスデバイスを含んでもよい。局所的バイアスデバイスは、量子ビットに外部磁束バイアスを提供する、超伝導量子ビットに近接した金属ループを含んでもよい。局所的バイアスデバイスは、さらに、複数のジョセフソン接合を含んでもよい。量子プロセッサ内の各超伝導量子ビットが、対応する局所的バイアスデバイスを有してもよく、または、量子ビットよりも少数の局所的バイアスデバイスが存在してもよい。いくつかの実施形態では、電荷ベースの読み出しおよび局所的バイアスデバイスが使用されてもよい。読み出しデバイスは、それぞれがトポロジ内の異なる量子ビットに誘導結合される、複数のｄｃ−ＳＱＵＩＤ磁力計を含んでもよい。読み出しデバイスは、電圧または電流を提供してもよい。少なくとも１つのジョセフソン接合によって遮断される、超伝導材料のループを含むｄｃ−ＳＱＵＩＤ磁力計は、当該技術分野で周知である。
【００１６】
実効量子ビット
本明細書および添付の特許請求の範囲を通じて、用語「実効量子ビット」を用いて２準位系として表現可能な量子系を表記する。当業者には、２つの特定の準位が多準位量子系から分離され、実効量子ビットとして使用できることが理解されよう。更に、用語「実効量子ビット」を用いて、単一の２準位系を表すために使用可能な任意の数のデバイスを含む量子系を表記する。例えば、結合された量子ビット群の全ての集合またはその一部が単一の２準位系を表すように、複数の個別量子ビットを互いに結合することができる。
【００１７】
量子プロセッサ
コンピュータプロセッサは、例えば、超伝導量子プロセッサなどの量子プロセッサのような、アナログプロセッサの形態を取ってもよい。超伝導量子プロセッサは、例えば、２つ以上の超伝導量子ビットなどの、複数の量子ビットおよび関連する局所的バイアスデバイスを含んでもよい。本システム、方法、およびデバイスと共に利用できる例示的な量子プロセッサの更なる詳細および実施形態が米国特許出願公開第２００６−０２２５１６５号、米国特許出願第１２／０１３，１９２号および２００７年１１月８日出願の米国仮特許出願第６０／９８６，５５４号「アナログ処理用のシステム、デバイス、および方法(Systems, Devices and Methods for Analog Processing)」に記述されている。
【００１８】
超伝導量子プロセッサは、量子ビットのそれぞれ数対を選択的に結合するように動作可能な、複数の結合デバイスを含んでもよい。超伝導結合デバイスの例としては、磁束によって量子ビットを共に結合する、ｒｆ−ＳＱＵＩＤおよびｄｃ−ＳＱＵＩＤが挙げられる。ＳＱＵＩＤは、１つのジョセフソン接合（ｒｆ−ＳＱＵＩＤ）または２つのジョセフソン接合（ｄｃ−ＳＱＵＩＤ）によって遮断される超伝導ループを含む。結合デバイスは、相互接続トポロジ内で結合デバイスがどのように利用されるかに応じて、強磁性結合および反強磁性結合の両方が可能であってもよい。磁束結合の場合、強磁性結合は、平行な磁束がエネルギー的に好都合であることを意味し、反強磁性結合は、逆平行の磁束がエネルギー的に好都合であることを意味する。あるいは、電荷をベースとする結合デバイスが使用されてもよい。その他の結合デバイスは、例えば、米国特許出願公開第２００６−０１４７１５４号および米国特許出願第１２／０１７，９９５号に見出すことができる。結合デバイスのそれぞれの結合強度は、例えば、量子ビット間の強磁性または反強磁性結合を提供するために、０と最大値との間で調整されてもよい。
【００１９】
量子アニーリング
量子アニーリングとは、通常好適には系の基底状態である低エネルギー状態を見つけるために利用できる計算方法である。本方法は古典的アニーリングと概念的に類似していて、より低いエネルギー状態がより安定しているため、自然の系はより低いエネルギー状態へ向かう傾向があるとの原理に依っている。しかし、古典的アニーリングが系をその大域的な最低エネルギー状態へ導くために古典的な熱ゆらぎを用いるのに対し、量子アニーリングはより正確にまたはより速く大域的な最低エネルギー状態に到達すべく量子トンネリング等の自然の量子ゆらぎを用いることができる。組合せ最適化問題等の困難問題の解が、系の基底状態に符号化することが可能であり、従って量子アニーリングを用いてそのような困難問題の解を見つけることができる。
【００２０】
断熱量子計算
上述のように、断熱量子計算は通常、既知の初期ハミルトニアン（ハミルトニアンとは系の許されたエネルギーを固有値とする作用素）からハミルトニアンを徐々に変えることにより最終ハミルトニアンへ系を発展させるステップを含んでいる。断熱発展の簡単な例として次式がある。
Ｈｅ＝（１−ｓ）Ｈｉ＋ｓＨｆ
式中、Ｈｉは初期ハミルトニアン、Ｈｆは最終ハミルトニアン、Ｈｅは発展または瞬間ハミルトニアンであり、ｓは発展の速度を制御する発展係数である。係数ｓは０〜１の範囲であって、発展過程の開始時点において発展ハミルトニアンは初期ハミルトニアンに等しく、過程の終了時点において発展ハミルトニアンは最終ハミルトニアンに等しい。発展が速過ぎる場合、系は第１励起状態等のより高い状態に励起させることができる。本システム、方法、およびデバイスでは、「断熱」発展は断熱条件を満たす発展であると考えられ、ここで、断熱条件は次式で表される。
【数１】
式中、
【数２】
はｓの時間導関数、ｇ（ｓ）はｓの関数としての系の基底状態と第１励起状態との間のエネルギー差（本明細書では「ギャップサイズ」とも称す）、δは１より極めて小さい係数である。
【００２１】
断熱量子計算における発展過程をアニーリングと呼ぶ場合がある。ｓが変化する速度は発展またはアニーリングスケジュールとも呼ばれ、通常は一定且つ系が発展している間は常に発展ハミルトニアンの瞬間的基底状態にあるように十分遅く、反交差（すなわち、ギャップサイズが最小の時）における遷移が避けられる。断熱量子計算システム、方法、およびデバイスに関する更なる詳細は、米国特許第７，１３５，７０１号に記述されている。
【００２２】
断熱量子計算は、系が始まってから発展を通じて基底状態のままである量子アニーリングの特別な場合である。従って、当業者には、量子アニーリング法が一般に断熱量子コンピュータ上で実装でき、その逆も成立つことが理解されよう。本明細書を通じて、用語「断熱量子コンピュータ」を用いて断熱量子計算および／または量子アニーリングを実行すべく設計されている計算システムを記述する。
【００２３】
最適化問題
最適化問題は、制約条件の組に従う場合もあるが、変数の組について１つ以上の目的関数を最小化または最大化する問題である。例えば、巡回セールスマン問題（「ＴＳＰ」）は、例えば距離やコストを表す目的関数を最適化して、問題に対する最適化された解を表す変数の組として符号化されている経路を発見する最適化問題である。例えば、場所のリストが与えられている場合、問題は、全ての場所を一度だけ訪問する最短経路を発見することである。最適化問題の他の例として、最大独立集合（ＭＩＳ）、整数計画法、制約の最適化、因数分解、予測モデリング、およびｋ−ＳＡＴが含まれる。これらの問題は、オペレーションズ・リサーチ、金融ポートフォリオ選択、スケジューリング、供給管理、回路設計、および旅程最適化等、多くの現実的な最適化問題を抽象化したものである。多くの大規模な意思決定に基づく最適化問題はＮＰ困難である。例えば、「A High-Level Look at Optimization: Past, Present, and Future” e-Optimization.com, 2000」を参照されたい。
【００２４】
最適化問題の多くはＵＴＭを用いて解くことができない。この制約のため、ＵＴＭの能力を超える計算問題を解くことができる計算装置が当該技術分野で必要とされている。古典的なデジタルコンピュータは一般に、ＵＴＭの能力を超えられず、従って問題の規模と解決時間との間に好ましくない尺度を課す古典的計算の制約を受けるものと考えられている。本システム、方法、および装置によれば、量子断熱アルゴリズムを用いて、これらの問題に対し古典的最適化アルゴリズムで実現できるものよりも優れた解を得ることができる。
【００２５】
グラフ埋め込み
グラフは、対象同士の関係を表す有効な方法であって、経済学、数学、自然科学、および社会科学等の分野で共通に用いられている。ある種のグラフは単なる視覚的な支援ツールとして用いられるが、他のグラフは解くべき問題を表現するために用いることができる。実際、問題をグラフ形式にマッピングすることが問題の解決に役立つ場合がある。そのような問題の例として、株式ポートフォリオ選択、マイクロ波送信塔の配置、配送経路の最適化その他の大規模な問題が含まれる。元の問題を量子コンピュータが解ける形式に変換することにより、量子コンピュータを用いてそのような問題を解くことができる。これを行なう一方法としてグラフ埋め込みがあり、解くべき問題を表す頂点の集合および様々な頂点を接続する辺の集合からなるグラフを量子プロセッサの量子ビット構造にマッピングして問題を解く。
【００２６】
グラフ埋め込みは、全ての節点または頂点を平面上の点にマッピングし、２つの節点を接続する直線または曲線に全ての辺をマッピングすることにより、特定のグラフを描くステップを含んでいる。同一のグラフに多くの順列が存在し得るため、この描画は一意ではない。グラフを埋め込む方法の数は、これらを描画する格子系の特徴および規則に依存する。例えば、ある格子系は２次元格子であり得る。辺は、例えば、２つの互いに直角方向（例えば、上下または左右）に制約されている場合がある。そのような格子系は連結度が４、すなわち各々の節点に最大４本の辺が連結していることを意味し、これらの辺は上述の方向のみを向いている。辺が斜め（例えば、４５°）方向にも伸びて、交差可能であるような同様の格子系の連結度は８である。グラフ埋め込みの一形式には、ある格子系に描かれたグラフを取り上げて、他の格子系に等価なグラフを描くステップを含んでいる。
【００２７】
埋め込み可能グラフは、平面および非平面の２種類に分類することができる。平面グラフは、どの２本の辺も交差しないように２次元平面上に埋め込み可能なグラフである。非平面グラフは、少なくとも２本の辺が交差するグラフである。グラフ埋め込みのいくつかの形式には、平面グラフの非平面グラフへの埋め込み、または非平面グラフをできるだけ平面化する、すなわち交差の数を減らす試みが含まれる。しかし、ある種の非平面グラフは平面グラフに埋め込むことができない。そのようなグラフの最も有名な例としてグラフＫ５およびＫ（３、３）がある。非平面グラフおよびその埋め込みに関するより詳細な情報をBoyer et al., 2004, Journal of Graph Algorithms and Applications 8, pp. 241-273に見ることができる。
【００２８】
グラフを量子ビット群の格子に埋め込む技術がKnysh et al., 2005, arXiv.org:quant-ph/0511131に記述されている。Knyshは、ＮＰ完全な問題を量子ビット群の格子にマッピングして断熱量子計算を実行して問題を解く技術を記述している。しかし、Knyshは量子ビット群間の定常結合および最も近い隣接結合のみを使用しており、両方共に埋め込みおよび後続する計算の柔軟性および効率が悪い。
【００２９】
量子ビット群の格子にグラフを埋め込む更なる技術が米国特許出願第１１／９３２，２４８号に記述されている。
【００３０】
関係データベース
情報の格納に関係データベースを用いる場合が多い。情報は、任意の形態の企業、政府または個人に関連していてよい。例えば、情報は、人的資源、輸送、発注または取出し、倉庫保管、配送、予算編成、石油探査、測量、世論調査、画像、地図、ネットワークトポロジ、認証および／またはセキュリティに関連するものであってよい。
【００３１】
データベースを探索する多くの代替的な技術があるが、大多数の方法では通常１つ以上のクエリーを用意する。例えば、米国特許出願第１１／９３２，２６１号に記述されている技術では、クエリーは節点と辺からなるグラフの形式で与えられる。この技術では、データベースのエントリを用いてデータベースグラフを生成し、各々のデータベースグラフをクエリーグラフと組み合わせて一組の連合グラフを生成する。次いで連合グラフを用いて、クエリーグラフと対応するデータベースグラフの関係を評価することができる。ある実施形態において、連合グラフは量子ビットの集合からなる量子プロセッサに埋め込まれる。連合グラフの頂点が量子ビット群により表され、連合グラフの辺が量子ビット間の結合素子により表される。量子ビットおよび結合素子は超伝導素子であってよい。連合グラフに対応するクエリーは、量子プロセッサを用いてクリーク問題として解くことができる。例えば、量子プロセッサは第１または「初期」状態から第２または「最終」状態へ発展することができ、最終状態は連合グラフの任意のクリークを表していても、あるいは最大クリークまたは連合グラフの最大クリークを表していてもよい。ある実施形態において、対応する連合グラフが最大クリークを生成するデータベースグラフによってクエリーが最適な条件を満たす。
【００３２】
弾性バンチグラフマッチング
弾性バンチグラフマッチング（ＥＢＧＭ）は、多くの一意な顔画像データベースにおいて一人の人間の顔を認識するシステムである。具体的には、ＥＢＧＭは人間の顔画像を解析してラベル付けされたグラフ表現を生成する処理である。ラベル付けされたグラフ表現は節点および辺を含み、画像グラフと呼ばれる。グラフの節点は、顔の様々な「基準」位置（目、鼻および口等）を表現し、これらの節点は「ジェット」と呼ばれるガボールウェーブレット成分の集合により重み付けされている。グラフの辺は基準点間の関係を表し、辺には２次元距離ベクトルによりラベル付けされている。ＥＢＧＭによる画像グラフ表現の自動生成に続いて、クエリー画像の画像グラフをデータベース内の全ての画像の各画像グラフと比較することにより顔を認識することができる。
【発明の概要】
【発明が解決しようとする課題】
【００３３】
ＥＢＧＭにおける画像グラフの自動生成は、一般化された「バンチ」グラフに顔画像を整合させることにより実現される。バンチグラフは基本的に、１つの特定のジェットではなく多数のジェットの集合（または「バンチ」）により個々の基準点がラベル付けされているモデル格子である。バンチグラフは顔画像を覆い、画像内の各基準点を最も良く表現するジェットが識別される。バンチグラフは従って、成形可能なマスクのように組合されたものとして機能する。バンチグラフの辺は十分な弾性を有しているため、結果的に得られた画像グラフが特定の顔画像により良くフィットすることができる。最初に、手作業でバンチグラフを画定し、より多くの顔画像がバンチに組み込まれるにつれて適合度と精度が向上する。ＥＢＧＭの処理のより詳細な記述をWiskott et al., Face Recognition by Elastic Bunch Graph Matching, IEEE Transactions on Pattern Analysis and Machine Intelligence, 19(7):775-779, 1997に見ることができる。重要な点は、ＥＢＧＭの精度向上には計算量の増大が伴うことである。例えば、バンチグラフ内の基準点の数を増やすことにより精度が向上する。しかし、そのような増加はＥＢＧＭ画像グラフ生成段階でより多くの計算量を必要とし、より多くの節点および辺を含む画像グラフが生じることになる。そのようにより大きな画像グラフは、認識段階を通じてデータベース内の他の全ての画像グラフと比較する際により多くの計算量を必要とする。従って、自動顔面マッチングの現行技術は、所望のレベルの精度が得られないか、または処理速度が遅過ぎる。
【００３４】
画像マッチング問題は特に上記のような量子プロセッサで解くのに適している。現在実用化されている画像認識技術は精度に限界があり、一般に極めて遅い。認識の精度はグラフ表現の精度に依存し、精度自体が最終的には識別された画像特徴の数に依存する。従来、より多くの画像特徴を組み込む試みは、認識処理において網羅的計算を要するグラフ表現に行き着く。従って、通常は計算時間を管理可能にすべくある程度まで精度を犠牲にされてきた。量子プロセッサ上で認識処理を実行することにより、従来の方法よりより高い精度および／またはより高速に認識を行なうことができる。
【課題を解決するための手段】
【００３５】
概要
少なくとも１つの実施形態は、画像データベース内のクエリー画像の特徴を識別するコンピュータに実装された方法として要約することができ、クエリー画像の少なくとも１つの特徴のグラフ表現を、画像データベース内の複数のデータベース画像のうち少なくともいくつかの画像の各々の少なくとも一部の各グラフ表現と比較するステップであって、各々の比較が各連合グラフを生成するステップを含むステップと、量子プロセッサを介して各連合グラフの少なくとも１つの特徴を決定するステップとを含み、各連合グラフの少なくとも１つの特徴がクエリー画像の少なくとも１つの特徴と連合グラフが対応する各データベース画像の少なくとも一部との類似度を表す。
【００３６】
本方法は更に、各連合グラフの少なくとも１つの特徴を決定した結果を格納するステップと、結果に対してランク付けをして、最高ランクの結果がクエリー画像の特徴とデータベース画像のうち少なくとも１つとの間の最良の合致を表すようにするステップとを含んでいてよい。複数のデータベース画像の少なくともいくつかは、各々少なくとも一人の人間の顔を表すデータを含んでいてよく、クエリー画像の特徴は、少なくとも一人の人間の顔を表すデータを含んでいてよい。本方法は更に、画像データベース内のデータベース画像のうち少なくともいくつかの画像の各々の少なくとも一部の各グラフ表現を生成するステップと、クエリー画像の少なくとも１つの特徴のグラフ表現を生成するステップとを含んでいてよい。データベース画像のうち少なくともいくつかの画像の各々の少なくとも一部のグラフ表現、およびクエリー画像の少なくとも１つの特徴のグラフ表現を生成するステップは、弾性バンチグラフマッチングを実行するステップを含んでいてよい。各データベース画像の少なくとも一部の各々のグラフ表現を生成するステップは、古典的デジタルプロセッサを用いて各々のグラフ表現を生成するステップを含んでいてよい。クエリー画像の少なくとも１つの特徴のグラフ表現を生成するステップは、古典的デジタルプロセッサを用いてグラフ表現を生成するステップを含んでいてよい。各連合グラフの少なくとも１つの特徴を決定するステップは、各連合グラフの最大独立集合を決定するステップを含んでいてよい。各連合グラフの少なくとも１つの特徴を決定するステップは、各連合グラフの最大クリークを決定するステップを含んでいてよい。量子プロセッサを介して各連合グラフの少なくとも１つの特徴を決定するステップは、複数の超伝導量子ビット群を含む超伝導量子プロセッサを介して各連合グラフの少なくとも１つの特徴を決定するステップを含んでいてよい。本方法は更に、古典的デジタルプロセッサを介して画像データベースにアクセスするステップを含んでいてよい。各連合グラフを生成するステップは、古典的デジタルプロセッサを用いて各連合グラフを生成するステップを含んでいてよい。本方法は更に、各連合グラフを古典的デジタルプロセッサから量子プロセッサへ送信するステップを含んでいてよい。本方法は更に、量子プロセッサにより決定された各連合グラフの少なくとも１つの特徴を量子プロセッサから古典的デジタルプロセッサへ送信するステップを更に含んでいてよい。本方法は更に、クエリー画像のグラフ表現をデータベース画像のグラフ表現と比較する前にクエリー画像の少なくとも一部を調べるステップと、データベース画像の部分集合に共通するクエリー画像の態様を識別するステップとを含んでいてよく、クエリー画像の少なくとも１つの特徴のグラフ表現を複数のデータベース画像のうち少なくともいくつかの画像の各々の各グラフ表現と比較するステップは、クエリー画像の少なくとも１つの特徴のグラフ表現をデータベース画像の部分集合内のデータベース画像のグラフ表現のみと比較し、そのために対応する連合グラフを生成するステップを含んでいてよい。クエリー画像の少なくとも１つの特徴によりクエリー画像の大多数を表現することができる。クエリー画像の特徴と、連合グラフが対応する各データベース画像の少なくとも一部との間の類似度は、連合グラフが対応する各データベース画像内にクエリー画像の少なくとも１つの特徴が存在するか否かを示すことができる。
【００３７】
少なくとも１つの実施形態は、画像マッチング問題を解くコンピュータ実装された方法として要約することができ、画像マッチング問題を２次無制約２値最適化問題として定式化するステップと、２次無制約２値最適化問題を量子プロセッサにマッピングするステップと、２次無制約２値最適化問題への解を与えるべく量子プロセッサを動作させるステップとを含む。
【００３８】
少なくとも１つの実施形態は、２つの物体を比較するコンピュータ実装された方法として要約することができ、第１の物体の少なくとも一部のグラフ表現を第２の物体の少なくとも一部のグラフ表現と比較するステップであって、比較に際して連合グラフを生成するステップを含むステップと、量子プロセッサを介して連合グラフの少なくとも１つの特徴を決定するステップであって、連合グラフの少なくとも１つの特徴が、第１の物体の少なくとも一部と第２の物体の少なくとも一部との間の類似度を表すようにするステップとを含んでいる。
【００３９】
本方法は更に、共に画像である第１の物体および第２の物体を含んでいてよい。連合グラフの少なくとも１つの特徴を決定するステップは、連合グラフの最大独立集合を決定するステップを含んでいてよい。連合グラフの少なくとも１つの特徴を決定するステップは、連合グラフの最大クリークを決定するステップを含んでいてよい。連合グラフの少なくとも１つの特徴を決定するステップの結果、量子プロセッサが、第１の物体の少なくとも一部と第２の物体の少なくとも一部との間の類似度を表す値を返すことができる。
【００４０】
図面において、同じ参照番号は、同様の要素または動作を識別する。図中の要素のサイズおよび相対位置は、必ずしも一定の縮尺で描かれてはいない。例えば、さまざまな要素の形状、および角度は、一定の縮尺で描かれてはおらず、これらの要素のいくつかは、図面の可読性を向上するために任意に拡大および配置されている。さらに、描かれているとおりの要素の特定の形状は、特定の要素の実際の形状に関するいかなる情報も伝えることは意図されておらず、図中での認識を容易にするためにのみ選択されている。
【図面の簡単な説明】
【００４１】
図面の簡単な説明
【図１】量子プロセッサを含むシステムにより自動画像認識を実行する方法の実施形態のフロー図である。
【図２Ａ】顔画像自体を覆う顔画像のグラフ表現を示す例示的な図である。
【図２Ｂ】古典的プロセッサから量子プロセッサへ問題を伝達する方法の実施形態のフロー図である。
【図３】断熱量子計算（および／または量子アニーリング）用に設計された従来の超伝導量子プロセッサの一部の模式図である。
【図４】量子プロセッサにより画像マッチング問題を解く際のネイティブ動作モードの方法の実施形態のフロー図である。
【図５】量子プロセッサにより画像マッチング問題を解く際の混合動作モードの方法の実施形態のフロー図である。
【発明を実施するための形態】
【００４２】
詳細な説明
以下の説明は、開示する各種の実施形態が完全に理解されることを目的として記述するものである。しかし、関連技術の当業者には、各種実施形態が、これらの具体的な詳細事項が無くても、あるいは他の方法、構成要素、材料等によっても実施可能であることが理解されよう。他の例では、実施形態の説明が無用に分かり難くならないように、アナログプロセッサに関連付けられた周知の構造、例えば量子プロセッサ、量子素子、結合素子およびマイクロプロセッサおよび駆動回路を含む制御システムの図示および詳述は行ない。
【００４３】
別途文脈上必要とされない限り、本明細書および特許請求の範囲を通じて、用語「含む」および「含んでいる」等の変化形は、開いた包含的な意味、すなわち「含んでいるがこれに限定されない」旨の意味に解釈されるものとする。
【００４４】
本明細書を通じて、「１つの実施形態」または「一実施形態」とは、当該実施形態に関連付けられて記述された特定の特徴、構造または特性が少なくとも１つの実施形態に含まれていることを意味する。従って、本明細書を通じて各所に現れる「１つの実施形態において」または「一実施形態において」という語句は必ずしも全て同一の実施形態を指す訳ではない。更に、特定の特徴、構造または特性は、任意の適当な方法で１つ以上の実施形態に組み込むことができる。
【００４５】
本明細書および添付の特許請求の範囲において用いられているように、単数形の「ａ」、「ａｎ」および「ｔｈｅ」は、記述内容が別途明示しない限り複数の対象を含んでいる。また、用語「または」は一般に、記述内容が別途明示しない限り「および／または」を含む意味で用いられている点に注意されたい。
【００４６】
本明細書の開示内容の見出しおよび要約は、便宜上のものに過ぎず、実施形態の範囲または意味を解釈するものではない。
【００４７】
本システム、方法、および装置は、画像データベース内で自動画像認識を実行すべく量子プロセッサを実装する技術を記述する。これを行なうために、画像マッチング問題を量子プロセッサにより処理可能な形式にマッピングする。画像は各種の形式であってよい。通常、画像は、例えばディスプレイ装置または紙に画像の視覚的表現を生成すべく利用可能なデジタル情報の形式である。画像は、例えば２次元配列の各種のピクセルの輝度および／または色を指定するようなビットマップを定義する情報の形式であってよい。また、例えば、画像は数学的表現、例えば１つ以上の多項式（例えば、Ｂ−Ｓｐｌｉｎｅ多項式）またはベクトル形式であってよい。画像は他の形式であってもよい。
【００４８】
画像マッチングはその最も単純な形式において、同一物理構造に対応する２つの画像から一対の画像機能を見つけようと試みる。画像機能は例えば、所与の画像位置の近隣を記述するベクトルを含んでいてよい。対応する特徴を見つけるために、通常２つの要素が考慮される。すなわち、例えば特徴ベクトル同士のスカラー積により決定される特徴類似度、および幾何学的整合性である。剛体に注目する場合、後者の要素が最も良くあてはまる。この場合、特徴の変移は無秩序ではなく、むしろ視点の変化がもたらす相関を示す。例えば、カメラが左へ移動すると、画像内の特徴位置が右へ移動することが観察できる。物体が変形可能または関節移動可能である場合、特徴変移はカメラ視点のみでは決定されないが、隣接する特徴は依然として同様の仕方で移動する傾向があるだろう。このように、画像マッチングは、少なくとも２項を含む目的関数の最小化を含む最適化問題として定式化することができる。第１の項は、第１の画像から抽出されて第２の画像内の対応する位置に置かれた特徴同士の不整合に対して不利益をもたらす。第２の項は、隣接する合致箇所同士の相違を測定することにより、両者を空間的に整合させる。Felzenzwalb & Huttenlocher, “Pictorial Structures for Object Recognition,” Intl. Journal of Computer Visions 61(1), 55-79 (2005)に、これがＮＰ困難な最適化問題を構成することが示されている。
【００４９】
画像マッチング問題を量子アルゴリズムで解けるようにするために、画像マッチング問題を以下の形式の２次無制約２値最適化（「ＱＵＢＯ」）問題にマッピングすることができる。
【数３】
２値最適化変数ｘｉ、ｘｊはある画像の特徴がどのように他の画像にマッピングされるかを決定する。係数Ｑｉｊは、得られた目的関数の最小化により特徴類似度および幾何学的整合性を共に最大化すべく選択される。式（１）は量子断熱アルゴリズム等の量子計算・アルゴリズムを用いて解くことができる。
【００５０】
画像マッチング問題を解く量子プロセッサを実装する一般的な方法を以下に提示する。図１は、本方法１００の実施形態を示すフロー図である。方法１００は、３つのステップの新規な組合せである。すなわち、画像１０１、１０２（例えば、視覚的な画像を表す電子データまたは情報）のグラフ表現を生成し、連合グラフ１０３を用いてパターンマッチングを行ない、量子プロセッサを含むシステムを用いて問題１０４を解くことである。ステップ１０１において、画像データベース（「データベースグラフ」）内のいくつかまたは全ての画像（「データベース画像」）のグラフ表現を決定する。これは例えば、従来の（デジタル）プロセッサを用いて行なうことができる。ステップ１０２において、クエリー画像（「クエリーグラフ」）のグラフ表現を決定する。ステップ１０３において、クエリーグラフをデータベースグラフと比較し、各々の比較に際して対応する連合グラフを生成する。ステップ１０４において、量子プロセッサを用いて各連合グラフの少なくとも１つの特徴を決定する。ステップ１０５において、量子プロセッサにより決定された連合グラフの少なくとも１つの特徴に従い、これらの結果をランク付けする。ランク付けは、最も高いランクがクエリーグラフと対応するデータベースグラフとの間、すなわちクエリー画像と対応するデータベース画像との間で最良の合致を示すように決定することができる。
【００５１】
ステップ１０４において、量子プロセッサにより決定できる連合グラフの特徴または特徴群は、調べられている画像の種類または認識アルゴリズムの特性に依存する場合がある。二つの適切な特徴として、連合グラフの最大独立集合（「ＭＩＳ」）および最大クリーク（「ＭＣ」）が含まれる。これら二つの特徴は関連しており、従って各連合グラフにおけるこれら二つの特徴のうち一方のみを決定することにより画像認識を実行することができる。グラフのＭＩＳとは、全てが辺により連結されている節点の最大部分集合である。連合グラフ内のＭＩＳが大きいほど、クエリーグラフと対応するデータベースグラフの合致がより良いことを示す。従って、最大ＭＩＳを有していると決定された連合グラフは、クエリー画像とデータベース画像とが最も良く合致していると思われる。ＭＩＳを代替するものとして、ＭＣは、どの辺も共有しない節点の最大部分集合であり、従って最大ＭＩＳを有する連合グラフは通常、最小ＭＣを有する。従って、当業者には、ランキングの順序が逆である点を唯一の違いとして、ＭＣ問題を解くことはＭＩＳ問題を解くことと同様であることが理解されよう。方法１００を実装することにより、現在実用化されている技術に対して、自動画像認識の速度および／または精度を向上させることができる。
【００５２】
方法１００を適用してクエリー画像に合致するデータベース画像を見つけることができる。しかし、方法１００はまた、クエリー画像に含まれる特定の特徴に合致する特定の特徴を含むデータベース画像を見つけるべく適用することもできる。この場合の違いは、画像全部のマッチングに加え、方法１００を適用することにより、クエリー画像内の特徴を識別して画像データベース内で当該特徴との合致を見つけることができる点である。例えば、クエリー画像が人間の顔を含み、方法１００を適用することにより、得られるデータベース画像が複数の人間の顔を含み、合致する顔がデータベース画像の１つの特徴でしかない場合であっても、画像データベース内で合致する人間の顔を含むデータベース画像を見つけることができる。そのようなアプリケーションにおいて、方法１００のいくつかの実施形態により、ステップ１０２で決定されたクエリー画像のグラフ表現を、マッチングしたいクエリー画像の特定の特徴のグラフ表現に限定することができる。
【００５３】
本システム、方法、および装置は、自動画像認識を実行する際にデジタルプロセッサと量子プロセッサの両方を用いることを記述する。いくつかの実施形態において、画像のグラフ表現（または、所望するクエリーに応じて画像の特定の特徴）の生成および連合グラフの生成はデジタルプロセッサを用いて実行することができる一方、各連合グラフの少なくとも１つの特徴の決定は量子プロセッサを用いて実行することができる。
【００５４】
顔画像は、グラフにより表現できる画像の種類の具体例である。顔画像のグラフ表現の生成は進歩の途上にある研究分野である。その基本原理は、顔の特定の特徴（目、鼻および口等、および他の多くのより微妙な特徴も同様に）の相対位置が最終的に各々の顔毎に一意である組合せを画定する点である。従って、これらの相対位置のグラフ表現を用いて指紋とほぼ同様に個人を識別することができる。そのようなグラフ表現において、識別可能な特徴（再び目や口等）を辺の網の目により連結された節点または頂点により表現することができる。辺は節点の相対位置を画定することができる。節点の個数が多いほど（すなわち、画像で識別される特徴の数が多いほど）グラフ表現の精度が高い。体の他の部位、例えば虹彩または指紋、を表現する画像に関して同一または類似の方法を行なうことができる。
【００５５】
図２Ａは、元の顔画像を覆うグラフ表現２００を示す例示的な図である。図２Ａにおいて、節点２０１〜２０４は口の輪郭を画定する。簡潔にするため、グラフ表現２００は比較的少ない節点（同図では４つのみ明示）で構成されているため、元の顔画像の比較的不正確な表現となっている。しかし、当業者には、グラフの節点数を増やして画像内でより多くの顔の特徴を表現することにより、顔画像のグラフ表現の精度を向上できる点が理解されよう。更に、図２Ａは顔画像のグラフ表現の一例を示しているに過ぎない。図２Ａの節点および節点間の対応する辺により識別される具体的な顔の特徴は、必要とされるグラフスキームを表現していない。当業者には、グラフ表現並びに節点間の辺の対応するネットワークにより識別される特定の顔の特徴が、グラフ表現を生成する方法に応じて異なり得る点が理解されよう。当業者にはまた、顔画像のグラフ表現を生成する原理および技術が他の種類の画像、例えば物体、景色、地図、指紋等の画像にも適用できる点が理解されよう。このように、図２Ａは顔画像のグラフ表現のみを示しているが、当業者にはどのように任意の種類の画像のグラフ表現が同様に決定できることが理解されよう。
【００５６】
画像のグラフ表現は手操作で描画しても、あるいは自動的に生成してもよい。そのようなグラフ表現の究極の目的は画像認識であって、膨大な画像データベース内の全ての画像に対してグラフ表現を決定することが必要な場合がある。従って、手で全てを描画するのではなく、画像のグラフ表現を自動的に生成するシステムを開発する方がより現実的である。そのようなシステムの例として、弾性バンチグラフマッチング（ＥＢＧＭ）がある。ＥＢＧＭは、特に顔画像に適用されるべく設計されている。しかし、その基本原理は任意の種類の画像に適用することができる。ＥＢＧＭにおいて、一般化されたモデルグラフが決定されており、これらを新規の顔画像に当てはめて成型することにより新たなグラフを作成する。この技術の完全な詳細は、Wiskott et al., Face Recognition by Elastic Bunch Graph Matching, IEEE Transactions on Pattern Analysis and Machine Intelligence, 19(7):775-779, 1997に記述されている。グラフ表現の精度を上げると結果的に認識処理における計算量が増大するため、この技術の継続的な課題は精度と速度の間のトレードオフである。しかし、連合グラフを用いてパターンマッチングを組み込み、次いでその結果生じたＭＩＳ問題を量子プロセッサを用いて解くことにより、現在実用化されている技術に比べて精度と計算時間の両方を向上させることができる。
【００５７】
ＥＢＧＭは、顔画像のグラフ表現の自動生成における主要な技術である。しかし、当業者には、本システム、方法、および装置ではＥＢＧＭによりグラフ表現が生成する必要がない点が理解されよう。先に述べたように、意味のある連合グラフを生成できる程度にクエリーとデータベースグラフの間に十分な整合性がある限り、顔画像または他の任意の種類の画像のグラフ表現を手動で、または他の任意のシステムを用いて生成することができる。
【００５８】
特定のクエリーの場合、古典的デジタルプロセッサを用いて、データベースの特定の部分集合を自動的に表すクエリー画像の特定のキーとなる態様を識別することが望ましいであろう。例えば、クエリー画像のグラフ表現が生成されている間、あるいは連合グラフが生成される前にグラフ表現から、クエリーをデータベース内の何らかの部分集合に直ちに関連付けるクエリー画像の何らかの態様を識別することが可能な場合がある。そのような識別が行なわれた場合、クエリー画像を、同一の態様を共有するデータベース画像のみと比較すればよく、従って生成される連合グラフが少なくなる。基本的に、データベースをフィルタリングまたはプルーニング（剪定）することにより、合致する、認められる可能性のある画像のみを比較して連合グラフを生成する。一例として、最初にクエリー画像を人間の顔に関するものとして分類し、次いで対応する画像データベースを、少なくとも一人の人間の顔を含む画像の部分集合に絞り込むことができる。更に顔画像認識では、データベース画像との比較の前にクエリー画像のグラフ表現から顔画像の人種または性別を識別することが可能である。この例では、調べられるデータベースをクエリー画像の人種または性別に合致する顔画像の部分集合に絞り込まれる。このために生成する必要のある連合グラフが少なくて済み、その結果量子プロセッサの呼び出しが減少して計算時間が短縮される。この事前フィルタリングまたはプルーニングは、ユーザまたはデジタルコンピュータにより実行することができる。
【００５９】
当業者には、グラフ表現が任意の種類の画像に対して生成できる点が理解されよう。例えば、物体、景色、地図、指紋および星座の画像は全てグラフにより表現することができる。更に、グラフ表現は、画像全体ではなく、画像の態様の特定の特徴に対して生成することができる。
【００６０】
本明細書および添付の請求項を通じて、古典的プロセッサと量子プロセッサとの間の通信に言及する。例えば、連合グラフは、方法１００のステップ１０３にあるように古典的プロセッサを用いて生成でき、次いで方法１００のステップ１０４にあるように量子プロセッサを用いて連合グラフを解析することができる。図２Ｂは、古典的プロセッサと量子プロセッサとの間で通信する方法２５０の実施形態を示すフロー図である。方法２５０は４つのステップ２５１〜２５４を含んでいる。ステップ２５１において、古典的プロセッサを用いてクエリーを処理する。クエリーの処理は、クエリーのパラメータを定義するステップ、クエリー画像の特定の特徴を識別するステップ、連合グラフを生成するステップ、クエリーを分類するステップ、および終了基準を決めるステップを含むがこれに限定されない各種の動作を含んでいてよい。クエリーの処理はまた、量子プロセッサにより送信および管理可能な形式にクエリーを変換するステップを含んでいてよい。ステップ２５２において、処理されたクエリーを古典的プロセッサから量子プロセッサへ送信する。ステップ２５３において、量子プロセッサを用いてクエリーに回答する。クエリーに回答するステップは、連合グラフの少なくとも１つの特徴（例えば、ＭＩＳまたはＭＣ）を決定するステップを含むがこれに限定されない各種の処理を含んでいてよい。量子プロセッサは、クエリーが満足されるまでクエリーを管理する。ステップ２５４において、クエリーへの回答結果を古典的プロセッサに返す。これには、クエリーの結果を量子プロセッサから古典的プロセッサに送信するステップが含まれていてよい。
【００６１】
本システム、方法および装置によれば、断熱量子計算のアルゴリズムおよび／または量子アニーリングは発見的方法で実装することができ、その場合、解の大域的最適性の要件は取り下げられる。量子プロセッサはそのようなアルゴリズムを用いて、ａ）古典的な解決システムと同じ長さの時間でより正確な解を与え、ｂ）古典的な解決システムより短い時間で同程度の精度を与え、あるいはｃ）古典的な解決システムより短い時間でより正確な解を与えることができる。
【００６２】
断熱量子計算、および同様に量子アニーリングは各種の異なる方法で実装することができる。断熱量子計算の特定の実装例は、米国特許出願第１１／３１７，８３８号、およびWocjan et. al., 2003, "Treating the Independent Set Problem by 2D Ising Interactions with Adiabatic Quantum Computing", arXiv.org:quant-ph/0302027 (2003), pp.1-13に記述されており、量子ビット結合アーキテクチャを用いて、式（２）で与えるように１局所横磁場を有する２局所イジングハミルトニアンを実現する。
【数４】
【００６３】
式中、ｎは量子ビットの個数、
【数５】
は第ｉ量子ビットのパウリＺ行列、
【数６】
は第ｉ量子ビットのパウリＸ行列、またｈｉ、ΔｉおよびＪｉｊは各量子ビットに結合された無次元の局所場である。式（２）のｈｉ項は、各々の第ｉ量子ビットのＺ基底に信号または場を結合することにより物理的に実現することができる。式（２）のΔｉ項は各々の第ｉ量子ビットのＸ基底に信号または場を結合することにより物理的に実現することができる。式（２）のＪｉｊ項は、量子ビットの対（量子ビットｉおよびｊの各々）のＺ基底を互いに結合することにより物理的に実現することができる。
【００６４】
図３は、断熱量子計算（および／または量子アニーリング）用に設計された従来の超伝導量子プロセッサ３００の一部の模式図である。図３に示す超伝導量子プロセッサ３００の部分は、２つの超伝導量子ビット３０１、３０２と、その間で情報を結合する調整可能ＺＺカプラ３１１を含んでいる。図３に示す量子プロセッサ３００の部分が２つの量子ビット３０１、３０２および１つのカプラ３１１のみを含んでいるが、当業者には、量子プロセッサ３００が任意の数の量子ビット、およびその間で情報を結合する任意の数の結合素子を含んでいてよいことが理解されよう。
【００６５】
図３に示す量子プロセッサ３００の部分は、式２に記述されたハミルトニアンを物理的に実現すべく実装することができる。σｚおよびσｘの項を与えるべく、量子プロセッサ３００は、量子プロセッサ３００の状態を設定および制御するために用いるプログラミング・インターフェース３２１〜３２４を含んでいる。各々のプログラミング・インターフェース３２１〜３２４は図示するように、プログラミング・システム（図示せず）への各々の誘導結合により実現することができる。そのようなプログラミング・システムは量子プロセッサ３００とは分離されていても、あるいは米国特許出願第１１／９５０，２７６号に記述されているように局所的に（すなわち、量子プロセッサ３００にオンチップに）含まれていてもよい。
【００６６】
量子プロセッサ３００のプログラミングにおいて、プログラミング・インターフェース３２１および３２４の各々を用いて磁束信号を量子ビット３０１および３０２の各々の複合ジョセフソン接合３３１および３３２に結合することにより、系のハミルトニアンのΔｉ項を実現することができる。この結合により式２のσｘ項が得られる。同様に、プログラミング・インターフェース３２２および３２３の各々を用いて磁束信号を量子ビット３０１および３０２の各々の量子ビットループに結合することにより、系のハミルトニアンのｈｉ項が実現される。この結合により２のσｚ項が得られる。図３において、プログラミング・インターフェース３２１〜３２４の各々の系のハミルトニアンに対する寄与を枠３２１ａ〜３２４ａに示す。
【００６７】
当業者には、断熱量子計算および／または量子アニーリングが図３のシステム３００とは異なるシステムを実装することにより、および／または式２と異なるハミルトニアンを実装することにより実現できることが理解されよう。システム３００およびハミルトニアン２は、本システム、方法、および装置の実施形態の単なる具体例としての役割のみ意図されている。
【００６８】
本システム、方法、および装置は、画像マッチング問題を解くために量子プロセッサを用いる少なくとも２種類のモードを提供するが、好適なモードは問題の規模（すなわち連合グラフ内の頂点の数）に依存する。第１の動作モードすなわち「ネイティブモード」では、問題の規模は、問題全体を直接量子プロセッサにマッピング可能な程度に十分に小さい。第２の動作モードすなわち「混合モード」では、問題の規模が直接量子プロセッサにマッピングするには大き過ぎ、これを補償すべく当該問題をより小さい問題の集合に分解して個別に量子プロセッサにマッピング可能にする。
【００６９】
ネイティブモード動作では、画像マッチング問題は直接量子プロセッサにマッピングされる。画像の任意の対（すなわちクエリー画像とデータベース画像を合わせたもの）に対して、連合グラフを用いて２つの画像のグラフ表現間の類似度を測定することができる。連合グラフの各頂点は、第１の画像内の特徴αと第２の画像内の特徴βとの間の関連に対応していてよい。連合グラフ内の各辺は、第１の画像内の特徴ベクトルの対と第２の画像内の特徴ベクトルの対との間で何らかの幾何学的整合性を符号化することができる。連合グラフのＭＩＳは、類似度（ＭＩＳが大きいほど相互の重なり領域が大きい）および、第１の画像の特徴から第２の画像の特徴への最大無衝突マッピングの両方を提供する。上述のように、この技術を用いて２つの画像全体同士をマッチングさせる、あるいはデータベース画像の集合内でクエリー画像から特定の特徴を見つけることができる。例えば、「クエリー画像の全体または一部が対応するデータベース画像内のどこかに含まれていれば合致」が得られる。本システム、方法、および装置によれば、連合グラフのＭＩＳを見つける問題は、全ての頂点に対してＱｉｉ＝−１、および頂点間に辺が存在する場合は常にＱｉｊ＝Ｌを設定することによりＱＵＢＯ問題として定式化することができる。ＱＵＢＯ問題の最小エネルギー設定により、対応する頂点がＭＩＳの成分である場合に限りｘｉ＝１でなければならず、それ以外の場合はｘｉ＝０である。
【００７０】
図４は、量子プロセッサにより画像マッチング問題を解く際のネイティブ動作モードの場合の方法４００の実施形態のフロー図である。方法４００は、図１で方法１００により記述される一般的な方法をより詳細に述べる。具体的には、方法４００は、図３のシステム３００と同様の量子プロセッサを用い、且つ式２に記述されているハミルトニアンを実装することにより、方法１００のステップ１０４の実行に用いるステップの例を示す。方法１００のステップ１０４において、量子プロセッサを用いて連合グラフの少なくとも１つの特徴を決定する。従って、方法４００のステップ４０１において、結合されたｎ頂点ＱＵＢＯを記述する行列Ｑとして連合グラフを定義し、ｎは量子プロセッサ内の量子ビットまたは実効量子ビットの個数により制限される。ステップ４０２において、式２における目標値ｈｉおよびＪｉｊを行列Ｑから決定する。ステップ４０３において、ｎ個の頂点の各々を、量子プロセッサ内の各量子ビットまたは実効量子ビットにより識別する。ステップ４０４において、量子プロセッサにより量子アルゴリズムを実行する。このアルゴリズムは、適切な時間依存関数ｈｉ（ｔ）、Δｉ（ｔ）、およびＪｉｊ（ｔ）を適用することにより断熱量子計算および／または量子アニーリングを含んでいてよい。ステップ４０５において、量子アルゴリズムの結果を評価する。解決が満足できない場合、本方法はステップ４０４に戻る。解決が満足できる場合、本方法は４０６へ進む。ステップ４０６において、画像マッチング問題の解を出力する。
【００７１】
図４に記述する方法４００は、単一の連合グラフのＭＩＳ（または代替的にＭＣ）を決定する手順を提供する。図１の方法１００に記述したように、画像マッチング問題において、連合グラフの集合が生成され、各連合グラフはクエリー画像と一意なデータベース画像との間の比較の各々に対応する。方法４００は、クエリー画像と単一のデータベース画像との間でどれほど良好な合致が得られたかを決定する手順を効果的に提供する。従って、画像マッチング問題を解くには、各連合グラフについて方法４００を終了させ、次いで方法１００のステップ１０５のように結果にランク付けする必要がある。
【００７２】
多くの断熱量子計算・アーキテクチャの場合、利用できる物理的量子ビットの数は、解くべき画像マッチング問題の変数の数より極めて少ない（すなわちｎ＞量子ビットの数）。従って、大きなマッチング問題画像をより小さい問題の集合に分解する必要がある。そのような場合、完全な画像マッチング問題をより小さい問題の集合に分解して、量子プロセッサにより各々のより小さい問題を解くことができるようにする混合動作モードを実装する必要がある。当業者には、各種の分解技術をこの目的に実装できることが理解されよう。本システム、方法、および装置は、局所探索アルゴリズムを実行することにより量子プロセッサを用いてこの分解を実行する技術について記述する。
【００７３】
図５は、量子プロセッサにより画像マッチング問題を解く際の混合動作モードの方法５００の実施形態のフロー図である。図４の方法４００と同様に、方法５００の目的はＱＵＢＯ問題を解くことであり、解は連合グラフのＭＩＳ（または代替的にＭＣ）を表す。ステップ５０１において、例えば古典的な発見的ソルバーを用いて解の初期近似を決定する。ＱＵＢＯ問題の適当な古典的発見的ソルバーの例として、http://hces.bus.olemiss.edu/reports/hces0900.pdfに開示されているGlover et al., "One pass heuristics for large scale unconstrained binary quadratic problems," University of Mississippi Technical Report HCES-09-00 (2000)に記述されている要約−貪欲−清掃アルゴリズムがあるが、当業者には他の古典的発見的なソルバーを代替的に用いてもよいことが理解されよう。解の初期近似は局所探索アルゴリズムの出発点として使われる。解の初期近似は変数の集合Ｘｏを含んでいる。ステップ５０２において、変数集合Ｘｏの部分集合Ｓｏを選択することから局所探索アルゴリズムが開始される。部分集合Ｓｏの変数の数は、量子プロセッサに直接マッピング可能な変数の数に等しいか少ない。ステップ５０３において、変数の部分集合Ｓｏを、式３に記述されている最適化問題として量子プロセッサにマッピングする。
【数７】
このように、ステップ５０３において量子プロセッサを用いて変数の部分集合Ｓｏを最適化して解の初期近似を改良する。ステップ５０４において、ステップ５０３で決定された改良解が解の初期近似として再使用される。ステップ５０５において、何らかの終了基準が満たされるまでステップ５０２〜５０４を繰り返す。適切な終了基準の例として、指定された繰り返し回数、指定された時間、および／または指定された精度が含まれるがこれに限定されない。ステップ５０６において、問題の最終解を出力する。量子計算の再帰的技術が２００７年６月１２日出願の米国仮特許出願第６０／９４３，５１９号、「再帰的量子計算アルゴリズムのシステム、方法、および装置(Systems, Methods, and Apparatus for Recursive Quantum Computing Algorithms)」に記述されている。
【００７４】
方法５００の潜在的な短所は、全変数Ｘｏの空間における大域的最小値ではなく、変数の部分集合Ｓｏの空間における局所最小値しか特定しない点である。本システム、方法、および装置によれば、局所最小値の回避を支援すべくタブー探索ヒューリスティックにおいて方法５００の局所探索アルゴリズムを実行することができる。タブー探索の各々の繰り返しは（当該技術分野で知られているように）、先行する繰り返しの結果を格納して呼び出す。従って、いくつかの実施形態では、方法５００が実装されているのと同様に、各々の繰り返しからの結果を格納することができる。これらの格納された結果は、各々の単一の変数を変えて、それによりコストに変化する各変数を関連付けることによる効果に関するデータを含んでいてよい。各々の連続する繰り返しにおいて、当該アルゴリズムは、まだ変更されていない変数を調整して、格納されたデータに新しいエントリを生成することを選択できる。この格納されたデータは次いで、解の起伏の勾配に対する見通しを与えて、後続する繰り返しが「最適な」局所最小値、または理想的には大域的最小値へ向かって進むことができるようする。
【００７５】
当業者には、本明細書を通じて用語「解く」が厳密解および近似解の両方を包含するように用いられていることが理解されよう。
【００７６】
上述のように、本システム、方法、および装置は画像マッチングに用いることができる。本出願は、２つの完全な画像をマッチングさせるステップを含んでいても、あるいは、画像データベース内でクエリー画像の全てまたは一部を含むデータベース画像を見つけるステップを含んでいてよい。例えば、クエリー画像は道路標識を含み、画像データベース内で合致する道路標識を含むデータベース画像を見つけることを望んでもよい。しかし、本システム、方法、および装置が提示する概念はより広範な問題の集合に適用することができる。データベース内でクエリーに合致するものを見つけることが望ましい広範なアプリケーションが存在する。いくつかの実施形態において、本システム、方法、および装置を、２つの物体同士の類似度を決定する方法として一般化することができ、２つの物体の特徴は量子プロセッサにより解析される連合グラフに組み込まれる。量子プロセッサは、連合グラフを解析して、２つの物体同士の類似度を表す値を返すことができる。いくつかのアプリケーションにおいて、２つの物体は、クエリー画像およびデータベース画像等の画像であってよい。しかし、他のアプリケーションでは２つの目的が他の形式であってもよい。例えば、いくつかの実施形態は、関係データベースのエントリ間のクエリーをマッチングさせるステップを提供することができる。他の実施形態は、音声パターンマッチング、ＤＮＡ配列マッチングを含むがこれに限定されない、他の形式のパターンマッチングを提供することができる。
【００７７】
要約書の記述を含め、例示する実施形態の上の説明は網羅的ではなく、また実施形態を開示した形式通りに限定することを意図していない。本明細書では特定の実施形態および例を例示目的で記述しているが、当業者には理解されるように、本開示の概念および範囲から逸脱することなく各種の等価な変更を施すことが可能である。本明細書に提示する各種の実施形態は必ずしも上で一般的に述べた量子計算の例示的なシステム、方法、およびデバイスではなく、量子計算の他のシステム、方法、およびデバイスにも適用可能である。
【００７８】
上述の各種の実施形態を組み合わせて更なる実施形態を提供することができる。本明細書で参照した、および／または出願データシートに掲載されている全ての米国特許、米国特許出願公開、米国特許出願、外国特許、外国特許出願、および非特許文献の全文が本明細書に援用されている。すなわち以下の文献が含まれるがこれらに限定されない。２００７年４月１９日出願の米国仮特許出願第６０／９１２，９０４号「自動画像認識用のシステム、方法、および装置(Systems, Methods and Apparatus for Automatic Image Recognition)」、米国特許第６，８３８，６９４号、米国特許第７，３３５，９０９号、米国特許公開第２００６−０２２５１６５号、米国特許出願第１２／０１３，１９２号、２００７年１１月８日出願の米国仮特許出願第６０／９８６，５５４号「アナログ処理用のシステム、デバイス、および方法(Systems, Devices and Methods for Analog Processing)」、米国特許公開第２００６−０１４７１５４号、米国特許出願第１２／０１７，９９５号、米国特許第７，１３５，７０１号、米国特許出願第１１／９３２，２４８号、米国特許出願第１１／９３２，２６１号、米国特許出願第１１／３１７，８３８号、米国特許出願第１１／９５０，２７６号、および２００７年６月１２日出願の米国仮特許出願第６０／９４３，５１９号「再帰的量子計算アルゴリズムのシステム、方法、および装置(Systems, Methods, and Apparatus for Recursive Quantum Computing Algorithms)」。必要に応じて、各種の特許、出願および刊行物のシステム、回路および概念を採用すべく実施形態の態様を修正して更なる実施形態を提供することができる。
【００７９】
上で詳述された内容を考慮して実施形態に対し上記および他の変型を施すことができる。一般に、以下の特許請求の範囲において、使用する用語は、本明細書および特許請求の範囲に開示された特定の実施形態に特許請求の範囲が限定されると解釈すべきではなく、それらの特許請求の範囲が対応する等価物の完全な範囲に含まれる全ての可能な実施形態を含むものと解釈すべきである。従って、特許請求の範囲は本開示に限定されない。
【特許請求の範囲】
【請求項１】
画像データベース内のクエリー画像の特徴を識別するコンピュータに実装された方法であって、
クエリー画像の少なくとも１つの特徴のグラフ表現を、画像データベース内の複数のデータベース画像のうち少なくともいくつかの画像の各々の少なくとも一部の各グラフ表現と比較するステップであって、各々の比較が各連合グラフを生成するステップを含むステップと、
量子プロセッサを介して各連合グラフの少なくとも１つの特徴を決定するステップとを含み、各連合グラフの前記少なくとも１つの特徴が、前記クエリー画像の前記少なくとも１つの特徴と前記連合グラフが対応する各データベース画像の少なくとも一部との類似度を表す方法。
【請求項２】
各連合グラフの少なくとも１つの特徴を決定した結果を格納するステップと、
前記結果に対してランク付けをして、最高ランクの結果が前記クエリー画像の特徴と前記データベース画像のうち少なくとも１つとの間の最良の合致を表すようにするステップとを更に含んでいる、請求項１に記載の方法。
【請求項３】
前記複数のデータベース画像の少なくともいくつかが、各々少なくとも一人の人間の顔を表すデータを含み、クエリー画像の特徴が少なくとも一人の人間の顔を表すデータを含んでいる、請求項１に記載の方法。
【請求項４】
前記画像データベース内のデータベース画像のうち少なくともいくつかの画像の各々の少なくとも一部の各グラフ表現を生成するステップと、
前記クエリー画像の前記少なくとも１つの特徴のグラフ表現を生成するステップとを更に含んでいる、請求項１に記載の方法。
【請求項５】
前記データベース画像のうち少なくともいくつかの画像の各々の少なくとも一部のグラフ表現、および前記クエリー画像の前記少なくとも１つの特徴のグラフ表現を生成するステップが、弾性バンチグラフマッチングを実行するステップを含んでいる、請求項４に記載の方法。
【請求項６】
各データベース画像の前記少なくとも一部の各グラフ表現を生成するステップが、古典的デジタルプロセッサを用いて前記各グラフ表現を生成するステップを含んでいる、請求項４に記載の方法。
【請求項７】
前記クエリー画像の前記少なくとも１つの特徴のグラフ表現を生成するステップが、古典的デジタルプロセッサを用いて前記グラフ表現を生成するステップを含んでいる、請求項４に記載の方法。
【請求項８】
各連合グラフの少なくとも１つの特徴を決定するステップが、各連合グラフの最大独立集合を決定するステップを含んでいる、請求項１に記載の方法。
【請求項９】
各連合グラフの少なくとも１つの特徴を決定するステップが、各連合グラフの最大クリークを決定するステップを含んでいる、請求項１に記載の方法。
【請求項１０】
量子プロセッサを介して各連合グラフの少なくとも１つの特徴を決定するステップが、複数の超伝導量子ビット群を含む超伝導量子プロセッサを介して各連合グラフの少なくとも１つの特徴を決定するステップを含んでいる、請求項１に記載の方法。
【請求項１１】
古典的デジタルプロセッサを介して前記画像データベースにアクセスするステップを更に含んでいる、請求項１に記載の方法。
【請求項１２】
前記各連合グラフを生成するステップが、古典的デジタルプロセッサを用いて前記各連合グラフを生成するステップを含んでいる、請求項１に記載の方法。
【請求項１３】
前記各連合グラフを前記古典的デジタルプロセッサから前記量子プロセッサへ送信するステップを更に含んでいる、請求項１０に記載の方法。
【請求項１４】
前記量子プロセッサにより決定された各連合グラフの前記少なくとも１つの特徴を前記量子プロセッサから前記古典的デジタルプロセッサへ送信するステップを更に含んでいる、請求項１３に記載の方法。
【請求項１５】
前記クエリー画像のグラフ表現を前記データベース画像のグラフ表現と比較する前に前記クエリー画像の少なくとも一部を調べるステップと、
前記データベース画像の部分集合に共通する前記クエリー画像の態様を識別するステップとを含み、前記クエリー画像の前記少なくとも１つの特徴のグラフ表現を複数のデータベース画像のうち少なくともいくつかの画像の各々の各グラフ表現と比較するステップが、前記クエリー画像の前記少なくとも１つの特徴の前記グラフ表現を前記データベース画像の前記部分集合内のデータベース画像のグラフ表現のみと比較し、そのために対応する連合グラフを生成するステップを更に含んでいる、請求項１に記載の方法。
【請求項１６】
前記クエリー画像の前記少なくとも１つの特徴が、前記クエリー画像の大多数を表現する、請求項１に記載の方法。
【請求項１７】
前記クエリー画像の特徴と、前記連合グラフが対応する前記各データベース画像の少なくとも一部との間の類似度が、前記連合グラフが対応する前記各データベース画像内に前記クエリー画像の少なくとも１つの特徴が存在するか否かを示す、請求項１に記載の方法。
【請求項１８】
画像マッチング問題を解くコンピュータ実装された方法であって、
画像マッチング問題を２次無制約２値最適化問題として定式化するステップと、
前記２次無制約２値最適化問題を量子プロセッサにマッピングするステップと、
前記２次無制約２値最適化問題への解を与えるべく量子プロセッサを動作させるステップとを含む方法。
【請求項１９】
２つの物体を比較するコンピュータ実装された方法であって、
第１の物体の少なくとも一部のグラフ表現を第２の物体の少なくとも一部のグラフ表現と比較するステップであって、比較に際して連合グラフを生成するステップを含むステップと、
量子プロセッサを介して連合グラフの少なくとも１つの特徴を決定するステップであって、前記連合グラフの少なくとも１つの特徴が、前記第１の物体の少なくとも一部と前記第２の物体の少なくとも一部との間の類似度を表すようにするステップとを含む方法。
【請求項２０】
前記第１の物体および前記第２の物体が共に画像である、請求項１９に記載の方法。
【請求項２１】
前記連合グラフの少なくとも１つの特徴を決定するステップが、前記連合グラフの最大独立集合を決定するステップを含んでいる、請求項１９に記載の方法。
【請求項２２】
前記連合グラフの少なくとも１つの特徴を決定するステップが、前記連合グラフの最大クリークを決定するステップを含んでいる、請求項１９に記載の方法。
【請求項２３】
前記連合グラフの少なくとも１つの特徴を決定するステップの結果、前記量子プロセッサが、前記第１の物体の少なくとも一部と前記第２の物体の少なくとも一部との間の類似度を表す値を返す、請求項１９に記載の方法。
【請求項１】
画像データベース内のクエリー画像の特徴を識別するコンピュータに実装された方法であって、
クエリー画像の少なくとも１つの特徴のグラフ表現を、画像データベース内の複数のデータベース画像のうち少なくともいくつかの画像の各々の少なくとも一部の各グラフ表現と比較するステップであって、各々の比較が各連合グラフを生成するステップを含むステップと、
量子プロセッサを介して各連合グラフの少なくとも１つの特徴を決定するステップとを含み、各連合グラフの前記少なくとも１つの特徴が、前記クエリー画像の前記少なくとも１つの特徴と前記連合グラフが対応する各データベース画像の少なくとも一部との類似度を表す方法。
【請求項２】
各連合グラフの少なくとも１つの特徴を決定した結果を格納するステップと、
前記結果に対してランク付けをして、最高ランクの結果が前記クエリー画像の特徴と前記データベース画像のうち少なくとも１つとの間の最良の合致を表すようにするステップとを更に含んでいる、請求項１に記載の方法。
【請求項３】
前記複数のデータベース画像の少なくともいくつかが、各々少なくとも一人の人間の顔を表すデータを含み、クエリー画像の特徴が少なくとも一人の人間の顔を表すデータを含んでいる、請求項１に記載の方法。
【請求項４】
前記画像データベース内のデータベース画像のうち少なくともいくつかの画像の各々の少なくとも一部の各グラフ表現を生成するステップと、
前記クエリー画像の前記少なくとも１つの特徴のグラフ表現を生成するステップとを更に含んでいる、請求項１に記載の方法。
【請求項５】
前記データベース画像のうち少なくともいくつかの画像の各々の少なくとも一部のグラフ表現、および前記クエリー画像の前記少なくとも１つの特徴のグラフ表現を生成するステップが、弾性バンチグラフマッチングを実行するステップを含んでいる、請求項４に記載の方法。
【請求項６】
各データベース画像の前記少なくとも一部の各グラフ表現を生成するステップが、古典的デジタルプロセッサを用いて前記各グラフ表現を生成するステップを含んでいる、請求項４に記載の方法。
【請求項７】
前記クエリー画像の前記少なくとも１つの特徴のグラフ表現を生成するステップが、古典的デジタルプロセッサを用いて前記グラフ表現を生成するステップを含んでいる、請求項４に記載の方法。
【請求項８】
各連合グラフの少なくとも１つの特徴を決定するステップが、各連合グラフの最大独立集合を決定するステップを含んでいる、請求項１に記載の方法。
【請求項９】
各連合グラフの少なくとも１つの特徴を決定するステップが、各連合グラフの最大クリークを決定するステップを含んでいる、請求項１に記載の方法。
【請求項１０】
量子プロセッサを介して各連合グラフの少なくとも１つの特徴を決定するステップが、複数の超伝導量子ビット群を含む超伝導量子プロセッサを介して各連合グラフの少なくとも１つの特徴を決定するステップを含んでいる、請求項１に記載の方法。
【請求項１１】
古典的デジタルプロセッサを介して前記画像データベースにアクセスするステップを更に含んでいる、請求項１に記載の方法。
【請求項１２】
前記各連合グラフを生成するステップが、古典的デジタルプロセッサを用いて前記各連合グラフを生成するステップを含んでいる、請求項１に記載の方法。
【請求項１３】
前記各連合グラフを前記古典的デジタルプロセッサから前記量子プロセッサへ送信するステップを更に含んでいる、請求項１０に記載の方法。
【請求項１４】
前記量子プロセッサにより決定された各連合グラフの前記少なくとも１つの特徴を前記量子プロセッサから前記古典的デジタルプロセッサへ送信するステップを更に含んでいる、請求項１３に記載の方法。
【請求項１５】
前記クエリー画像のグラフ表現を前記データベース画像のグラフ表現と比較する前に前記クエリー画像の少なくとも一部を調べるステップと、
前記データベース画像の部分集合に共通する前記クエリー画像の態様を識別するステップとを含み、前記クエリー画像の前記少なくとも１つの特徴のグラフ表現を複数のデータベース画像のうち少なくともいくつかの画像の各々の各グラフ表現と比較するステップが、前記クエリー画像の前記少なくとも１つの特徴の前記グラフ表現を前記データベース画像の前記部分集合内のデータベース画像のグラフ表現のみと比較し、そのために対応する連合グラフを生成するステップを更に含んでいる、請求項１に記載の方法。
【請求項１６】
前記クエリー画像の前記少なくとも１つの特徴が、前記クエリー画像の大多数を表現する、請求項１に記載の方法。
【請求項１７】
前記クエリー画像の特徴と、前記連合グラフが対応する前記各データベース画像の少なくとも一部との間の類似度が、前記連合グラフが対応する前記各データベース画像内に前記クエリー画像の少なくとも１つの特徴が存在するか否かを示す、請求項１に記載の方法。
【請求項１８】
画像マッチング問題を解くコンピュータ実装された方法であって、
画像マッチング問題を２次無制約２値最適化問題として定式化するステップと、
前記２次無制約２値最適化問題を量子プロセッサにマッピングするステップと、
前記２次無制約２値最適化問題への解を与えるべく量子プロセッサを動作させるステップとを含む方法。
【請求項１９】
２つの物体を比較するコンピュータ実装された方法であって、
第１の物体の少なくとも一部のグラフ表現を第２の物体の少なくとも一部のグラフ表現と比較するステップであって、比較に際して連合グラフを生成するステップを含むステップと、
量子プロセッサを介して連合グラフの少なくとも１つの特徴を決定するステップであって、前記連合グラフの少なくとも１つの特徴が、前記第１の物体の少なくとも一部と前記第２の物体の少なくとも一部との間の類似度を表すようにするステップとを含む方法。
【請求項２０】
前記第１の物体および前記第２の物体が共に画像である、請求項１９に記載の方法。
【請求項２１】
前記連合グラフの少なくとも１つの特徴を決定するステップが、前記連合グラフの最大独立集合を決定するステップを含んでいる、請求項１９に記載の方法。
【請求項２２】
前記連合グラフの少なくとも１つの特徴を決定するステップが、前記連合グラフの最大クリークを決定するステップを含んでいる、請求項１９に記載の方法。
【請求項２３】
前記連合グラフの少なくとも１つの特徴を決定するステップの結果、前記量子プロセッサが、前記第１の物体の少なくとも一部と前記第２の物体の少なくとも一部との間の類似度を表す値を返す、請求項１９に記載の方法。
【図１】
【図２Ａ】
【図２Ｂ】
【図３】
【図４】
【図５】
【図２Ａ】
【図２Ｂ】
【図３】
【図４】
【図５】
【公表番号】特表２０１０−５２５４３１（Ｐ２０１０−５２５４３１Ａ）
【公表日】平成２２年７月２２日（２０１０．７．２２）
【国際特許分類】
【出願番号】特願２０１０−５０３３２４（Ｐ２０１０−５０３３２４）
【出願日】平成２０年４月１８日（２００８．４．１８）
【国際出願番号】ＰＣＴ／ＣＡ２００８／０００７２６
【国際公開番号】ＷＯ２００８／１２８３３８
【国際公開日】平成２０年１０月３０日（２００８．１０．３０）
【出願人】（５０７２０９２０７）ディー−ウェイブ システムズ，インコーポレイテッド (16)
【Ｆターム（参考）】
【公表日】平成２２年７月２２日（２０１０．７．２２）
【国際特許分類】
【出願日】平成２０年４月１８日（２００８．４．１８）
【国際出願番号】ＰＣＴ／ＣＡ２００８／０００７２６
【国際公開番号】ＷＯ２００８／１２８３３８
【国際公開日】平成２０年１０月３０日（２００８．１０．３０）
【出願人】（５０７２０９２０７）ディー−ウェイブ システムズ，インコーポレイテッド (16)
【Ｆターム（参考）】
[ Back to top ]