[go: up one dir, main page]

JP2018521382A - 古典的なプロセッサで量子類似計算をエミュレートするためのquanton表現 - Google Patents

古典的なプロセッサで量子類似計算をエミュレートするためのquanton表現 Download PDF

Info

Publication number
JP2018521382A
JP2018521382A JP2017557330A JP2017557330A JP2018521382A JP 2018521382 A JP2018521382 A JP 2018521382A JP 2017557330 A JP2017557330 A JP 2017557330A JP 2017557330 A JP2017557330 A JP 2017557330A JP 2018521382 A JP2018521382 A JP 2018521382A
Authority
JP
Japan
Prior art keywords
quanton
quantum
permutation
data
distribution
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
JP2017557330A
Other languages
English (en)
Other versions
JP6989387B2 (ja
Inventor
アルン、マジュムダール
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Kyndi Inc
Original Assignee
Kyndi Inc
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Kyndi Inc filed Critical Kyndi Inc
Publication of JP2018521382A publication Critical patent/JP2018521382A/ja
Application granted granted Critical
Publication of JP6989387B2 publication Critical patent/JP6989387B2/ja
Expired - Fee Related legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Classifications

    • GPHYSICS
    • G06COMPUTING OR CALCULATING; COUNTING
    • G06NCOMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N10/00Quantum computing, i.e. information processing based on quantum-mechanical phenomena
    • G06N10/80Quantum programming, e.g. interfaces, languages or software-development kits for creating or handling programs capable of running on quantum computers; Platforms for simulating or accessing quantum computers, e.g. cloud-based quantum computing
    • GPHYSICS
    • G06COMPUTING OR CALCULATING; COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00Arrangements for program control, e.g. control units
    • G06F9/06Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/44Arrangements for executing specific programs
    • G06F9/455Emulation; Interpretation; Software simulation, e.g. virtualisation or emulation of application or operating system execution engines
    • G06F9/45504Abstract machines for programme code execution, e.g. Java virtual machine [JVM], interpreters, emulators
    • GPHYSICS
    • G06COMPUTING OR CALCULATING; COUNTING
    • G06NCOMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N10/00Quantum computing, i.e. information processing based on quantum-mechanical phenomena
    • G06N10/20Models of quantum computing, e.g. quantum circuits or universal quantum computers
    • GPHYSICS
    • G06COMPUTING OR CALCULATING; COUNTING
    • G06NCOMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N10/00Quantum computing, i.e. information processing based on quantum-mechanical phenomena
    • G06N10/60Quantum algorithms, e.g. based on quantum optimisation, quantum Fourier or Hadamard transforms
    • GPHYSICS
    • G06COMPUTING OR CALCULATING; COUNTING
    • G06NCOMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N3/00Computing arrangements based on biological models
    • G06N3/12Computing arrangements based on biological models using genetic models
    • G06N3/126Evolutionary algorithms, e.g. genetic algorithms or genetic programming
    • BPERFORMING OPERATIONS; TRANSPORTING
    • B82NANOTECHNOLOGY
    • B82YSPECIFIC USES OR APPLICATIONS OF NANOSTRUCTURES; MEASUREMENT OR ANALYSIS OF NANOSTRUCTURES; MANUFACTURE OR TREATMENT OF NANOSTRUCTURES
    • B82Y10/00Nanotechnology for information processing, storage or transmission, e.g. quantum computing or single electron logic
    • GPHYSICS
    • G06COMPUTING OR CALCULATING; COUNTING
    • G06NCOMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N7/00Computing arrangements based on specific mathematical models
    • G06N7/01Probabilistic graphical models, e.g. probabilistic networks
    • GPHYSICS
    • G06COMPUTING OR CALCULATING; COUNTING
    • G06NCOMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N99/00Subject matter not provided for in other groups of this subclass

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Software Systems (AREA)
  • General Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • Data Mining & Analysis (AREA)
  • Mathematical Physics (AREA)
  • Evolutionary Computation (AREA)
  • Computing Systems (AREA)
  • Artificial Intelligence (AREA)
  • Life Sciences & Earth Sciences (AREA)
  • Health & Medical Sciences (AREA)
  • Biophysics (AREA)
  • Mathematical Analysis (AREA)
  • Pure & Applied Mathematics (AREA)
  • Mathematical Optimization (AREA)
  • Computational Mathematics (AREA)
  • Condensed Matter Physics & Semiconductors (AREA)
  • Bioinformatics & Cheminformatics (AREA)
  • Bioinformatics & Computational Biology (AREA)
  • Evolutionary Biology (AREA)
  • Physiology (AREA)
  • Genetics & Genomics (AREA)
  • Biomedical Technology (AREA)
  • Computational Linguistics (AREA)
  • General Health & Medical Sciences (AREA)
  • Molecular Biology (AREA)
  • Complex Calculations (AREA)
  • Image Analysis (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)
  • Error Detection And Correction (AREA)
  • Operations Research (AREA)
  • Probability & Statistics with Applications (AREA)
  • Algebra (AREA)
  • Databases & Information Systems (AREA)

Abstract

Quantonバーチャルマシンは、多項式時間における階乗空間においてNP困難問題の解を近似する。データ表現及び方法は、古典的ハードウェアでの量子計算をエミュレートするが、量子ハードウェアで実行される場合は量子計算をも実装する。Quantonは、量子ゲート及び量子演算を表現するためにLehmerコードによってインデックスを付けられた置換及び置換演算子を使用する。生成関数は効率的な圧縮表現のために幾何オブジェクトの中にインデックスを埋め込む。非線形方向性確率分布は多様体に埋め込まれ、さらに各インデックスポイントに対する接空間では線形確率分布である。分布に対する簡略なベクトル演算は量子ゲート演算に相当する。Quantonは量子計算の特徴、つまり重ね合わせ、量子化、及びエンタングルメント代用物を提供する。Quantonの母集団は問題を解決する局所発展ゲート演算として、または分布推定アルゴリズムにおける解の候補として進化する。Quantonは置換にモジュロ演算を使用し、したがって任意のハードウェアで完全に並列である。

Description

背景
関連出願の相互参照
本願は、全体の内容が参照により援用される、2015年5月5日に出願された米国仮出願第62/156,955号を基礎とし、米国仮出願第62/156,955号の利点を主張する。
開示の分野
本開示は、量子類似計算をエミュレートし、いくつかの実際的なデータ処理機能を実行する確率的多項式チューリングマシンコンピューティングモデルに関し、より詳細には、関数の計算を置換により再公式化し、これらを確率空間の中に埋め込み、トポロジカル量子計算の方法を組み込むことによる古典的な確率論的計算と量子計算または量子エミュレーションとの両方における表現及び計算方法のシステムに関する。
関連技術の説明
計算の普遍的モデルは従来チューリングマシンと呼ばれているバーチャルマシンであるということができ、チャーチ=チューリングテーゼに従って、バーチャルマシンは、その原型がラムダ計算である関数評価としての計算の基礎の上に構築されている。例えば基礎としてパイ算法を使用する、または確率的チューリングマシンを構築するために確率理論モデルもしくは量子チューリングマシンを構築するために量子理論を使用する等、チューリングマシンを設計する多くの他の方法がある。
多くのクラスの人工知能技法は、しばしば哲学、数理科学、物理科学、生物科学、及び経済学からインスピレーションを受ける。しかしながら、それは、当業者にとっては通常の知識である可能性があるが、互いに統合されるときに自明ではないこれらの異なる分野の部分を結合する新規性にある。したがって、矛盾する要件と対峙するときに優れた選択、及びどの分野のどの選択(例えば、生物学的に触発されたまたは経済的に触発されたモデル等)を行う方法の研究はすべてのデータ分析における根本的な問題である。つまり、これが、我々の技法が適用するところである。
優れたデータを選ぶことは、優れた決定を下す方法の問題の根底にある。加えて、矛盾するデータ、弱信号、または非常に高い組合せ的複雑さを取り扱う課題がある。矛盾するデータは、データが一貫性のない論理的推測結果を示すことを意味するだけである。弱信号は、ノイズから区別するのが困難である信号、または弱信号を隠す見かけは強力な信号のことである。頻度論的統計分析等の古典的な手法は、結果が見付けられるときに、結果が最善の解決法であることが保証されるように強力な信号または単純な複雑性クラスと連携する。しかしながら、弱信号または高複雑性クラスの場合、通常、正確な答えの代わりにある種の近似が使用されるため、達成しなければならないトレードオフのバランスがある。この場合、データ特性は、それが弱いまたは強いということではなく、それが非常に複雑であるということである。複雑さは計算上の複雑性クラス、またはデータ量もしくはデータの記述のサイズ、その高次元性、動態もしくは他のデータと結び付けられた関係性を定義する根本的なアルゴリズム構造に起因して生じる。要するに、これらの課題が、データを異なるクラスに分け、分析することを非常に複雑にしている。
訓練データサンプルは、(新しい医薬品の合成または材料設計等の)創造的な問題に対して新しい解決法を合成するための訓練データがない多くのときに存在すると仮定される。古典的な手法の同じ基本的な分布は問題解決データと同じ集合から訓練サンプルを引き出す。しかしながら、データ収集のスパース性及びノイズ、ならびに入力のときには大きい変動のため、訓練データと解決データの間の合同についての仮定は立てることができない、または以前は存在していなかった新規モデルを作成しなければならない。
(例えば、オントロジー、及び分類学、または他の層のデータ等の)層別データに基づいて決定を下す必要がある状況では、データが属する層に起因する応答に対する影響を予想できる。モデルフレームワークでは、層の帰属関係に起因するシフトが、共変量及びデータの特定の集合を所与としてなんらかの結果の分布の推定に著しく影響を及ぼすことがある。特定の層の中の帰属関係は、関心のある分布の値に影響を与えることがある。しかしながら、多くの場合これらの層レベルでの影響を明示的に推定することは望まれない。むしろ、層全体で観測され、推定での任意の非線形性を考慮する他の特徴と関連付けられた線形係数等の他の関心のあるパラメータを推定することが求められる。具体的な例のために、層内の観測のヒストグラムが条件付けられる古典的な条件付き尤度モデル手法のケースを検討する。この条件付き尤度は、あらゆる層レベルでの線形効果に対して不変であり、このようにして線形効果を本明細書で説明されるモデルの(尤度の)要因として取り除く。次いで、関心のある残りのパラメータを回復するために続けて最尤推定とともにモデルを使用する。例えば、心理学の臨床試験の分析において等、ケースコントロール研究における回答のヒストグラムに条件を付けると、層は回答ベクトルの全置換を検討することになる。この結果、組合せ的に、したがって階乗的にますます多くの条件の総和が生じる。計算はこの古典的な手法では実行不可能になる。
しかしながら、データで発見するのが困難であるパターンはいくつかの関連する特徴を有さなければならず、さもなければ人は純粋なノイズに対処することになるだろう。これらのパターンは多くの場合他のパターンと混同されるため、これらのパターンを識別するのは困難である。これらのパターンはノイズによって歪められているように見えることがあるが、いったん認識されると、ノイズに関わりなく復元され、分類されるだろう。パターンは、パターンモデルが以前に存在しなかった場合に、パターンモデル構造を推測的に仮定し、次いでこの構造と対照してデータ内のパターンの存在がないか試験することによって学習される必要がある場合がある。
19世紀後半には、「分布推定アルゴリズム(EDA:Estimation of Distribution Algorithm)」が紹介され、文献では「確率モデル構築型遺伝的アルゴリズム(PMBGA:Probabilistic Model-Building Genetic Algorithms)」または「反復密度推定アルゴリズム(Iterated Density Estimation Algorithms)」等のいくつかの他の名称で通っている。その新規な機能性のため、EDAは、進化、遺伝的アルゴリズムに類似する精神での生物学的に触発された計算による確率モデル学習に基づいた進化的アルゴリズムにおける主要なツールになった。
EDAは、問題の異なる変数間の相互関係をその確率分布を介して表現する訓練例の集合と関連付けられた同時確率分布を推定する。したがって、EDAは反復確率機械学習技法に理想的に適している。EDA推定サイクルの以前の生成で学習された確率モデルをサンプリングすると、解の新しい母集団が生じる。アルゴリズムは反復を停止し、例えば世代/評価の最大数、均質集団、及び解の改善の欠如等、特定の停止基準が満たされるときに世代全体で発見された最適解を返す。
階乗的に大きいデータ空間での推測、複雑なデータセットでオブジェクトにランクを付けること、及びデータ登録等のNP困難な問題に対する手法の大部分は、不正確であるが、決定解を密接に表す解に達するために、凸最適化、整数計画、緩和、及び関係する古典的な近似法技術に依存する。さらに、係る問題の解決の標準的な手法は線形目的関数を仮定する。しかしながら、多くの場合、これは非線形である場合がある現実的な問題の近似にすぎず、非線形関数を可能にするとはるかに幅広い表現力が生じる。しかしながら、線形構造と非線形構造の両方を同じモデルの中で結合するための方法は大いに場当たり的であった。
確率的推論は、例えばベイズ推論で通常使用されるデータ独立性の仮定とは対照的に、データ間の相関が考慮される必要があるので、扱いにくく且つ複雑になる。複雑に関連付けられたネットワークの中で推論する方法は、多くの場合データを連続的に且つヌル仮説の下で処理する必要性を強く主張する一方で、焼きなまし法及び多様な近似に依存する。例えばマルコフ確率場、マルコフ論理、ベイジアン信念ネットワーク、及び他の類似した構造等の方法は、まさに提示した処理のモデルに該当する。
機械学習アプリケーションは、多くの場合、性質で本質的に方向性であるデータからの深いパターンを学習することを伴う、またはデータは相互に関連付けられる、もしくは階層化される、もしくは潜在的に連続的に配列され、現実世界の場合、多くの場合データはクラスタサイズの先験的な知識なく連続的に配列され、階層化され、方向性であり、相互に関連付けられる。方向性データ分析のためのプロトタイプを構成する埋め込みを生成するためには、従来スペクトルクラスタリング技法が使用されてきたが、(元の構造に応じて)超球で異なる形状を生じさせ、解釈の難しさにつながることがある。係る方向データの例はテキスト、医療情報学、保険請求分析、及び方向性ベクトル場(風、天候、物理現象)を含む大部分の科学のいくつかの領域を含む。方向性データの多様な確率密度は、例えばグラフモデルにおいてのように、期待値最大化(EM)戦略または最大事後確率(MAP)推測のどちらかに基づいた優位点及び不利な点とともに存在する。おもな難しさは、通常不完全な知識(もしくは欠測データ)または問題の複雑さのために直接的にアクセスできない事後確率を学習することであり、したがって近似が使用されなければならない。学習の出力はある種のプロトタイプである。
所与のオブジェクトまたは観測されたオブジェクトの集合からプロトタイプを学習することは、画像理解、認知視覚、パターン認識、データマイニング、及びバイオインフォマティックスで多数の応用例を用いる機械学習における中核的な問題である。通常の手法は、多くの場合相対的に少ないよく理解されている現実世界の例からのスパースな入力である何らかのデータを有し、プロトタイプと呼ばれるパターンを学習することである。プロトタイプは(相違点が存在する場合)認識されている入力オブジェクト間の総合的な相違点を最小限に抑える。係る計算されたプロトタイプは、それらのプロトタイプの特性を考慮するだけでクエリーに効率的に答えることができるように、非常に大きいサイズの構造データについて推論する、分類する、またはインデックスを付けるために使用できる。他の重要な応用例は、プロトタイプが圧縮された知識または検知の形としていくつかの部分的な観測だけからオブジェクトを再構築する上で使用できる点である。プロトタイプは、異種データ項目の集合の中の、隠されているが一般的なパターンを識別し、このようにして非自明的な方法でデータ項目を関係付けるために使用できる。プロトタイプ学習及び表現のためのソフトウェアデータ構造は、例えばそのペアワイズ距離が剛体変換の下で不変のままとなる点の集合を構造マッチングするために使用できる。
プロトコル学習アルゴリズムの多くは、データの埋め込みであって、低粒度表現を作り出し、つねにではないが多くの場合、局所的に線形であり、願わくは検出漏れ及び誤検出を生じさせることなく手元の問題に計算上有用である可能性がある方法で顕著な特徴を取り込む低次元多様体の中へのデータの埋め込みを使用する。欠測データまたはデータが欠けていると推測することは、データの構造組成が埋め込みプロセスの間に失われる−したがって多様体は、その演算の部分として、欠けている構造をとるまたは欠けている構造を戻すことができない−ため、多様体埋め込み技法の多くでの主要な問題である。
本明細書に示される「背景」の説明は、本開示の文脈を概して提示するためである。それ以外の場合出願の時点で先行技術としての資格を与えないことがある本明細書の態様だけではなく、発明の背景の項にも説明される範囲まで、現在名前が挙げられている発明者の研究は明示的にも黙示的にも本開示に対する先行技術として認められない。
概要
Quantonバーチャルマシンは多項式時間で階乗空間におけるNP困難問題の解に近付く。データ表現及び方法は、古典的なハードウェアで量子計算をエミュレートするが、量子ハードウェアで実行される場合、さらに量子計算を実装する。Quantonは量子ゲート及び量子演算を表現するためにレーマーコード及び置換演算子によってインデックスを付けられた置換を使用する。生成関数は効率的な圧縮表現のために幾何オブジェクトの中にインデックスを埋め込む。非線形方向性確率分布は多様体に埋め込まれ、各インデックスポイントに対する接空間では線形確率分布でもある。分布に対する単純なベクトル演算は量子ゲート演算に相当する。Quantonは量子計算の特徴、つまり重ね合わせ、量子化、及びエンタングルメントの代用物を提供する。Quanton母集団は問題を解決する局所的な進化的ゲート演算として、または分布推定アルゴリズムにおける解の候補として進化する。Quantonは置換にモジュロ演算を使用し、したがって任意のハードウェアで完全に並列である。
上述の段落は概略紹介の目的で示され、以下の特許請求の範囲の範囲を制限することを意図していない。説明されている実施形態は、追加の優位点とともに、添付図面と併せて解釈される以下の発明を実施するための形態を参照することにより最もよく理解される。
本開示及び本開示の付随する優位点の多くのより完全な理解は、添付図面を併せて考慮すると、以下の実施形態の詳細な説明を参照することによって理解を深める際に容易に得られる。
システムの概要の例示的なフローチャートを示す。 ポリトープ(パームトリクス(Permutrix))の頂点での置換シーケンスの例示的な表現を示す。 ポリトープで頂点を生成するために使用される例示的なフィボナッチ格子を示す。 超球の表面での特定の確率密度分布の例示的な幾何学的形状を示す。 超球に対する接空間での分布の例示的な混合を示す。 Quantonの球状のフィボナッチ格子上の特定の接点及び接空間を示す。 Quantonのための分布アルゴリズムの推定のための反復フィードバックデータ処理の方式を示す。 Quantonのための古典的なビットに量子ビットを写像するためのルックアップテーブルを有する確率経路密度を示す。 Quantonのトポロジー構造と、球上のオービトープ(Orbitope)として置換状態空間を埋め込むこととの例を示す。 Quantonのための分布推定アルゴリズムのための運用モデルを示す。 Quanton構築のための例示的な較正演算及び分解能を示す。 Quanton較正構築処理の例示的な詳細を示す。 4置換オービトープの空間の例示的なトポロジー構造を示す。 5置換オービトープの空間の例示的なトポロジー構造を示す。 再帰的な進化及び推定を説明するフローチャートを示す。 いくつかのブレイド群及び置換オービトープ(ゾノトープ)の空間の多面体構造を示す。 量子化された多面体確率密度分布を示す多面体構造を示す。 単一の量子化された多面体確率密度の射影を示す多面体構造を示す。 量子ゲート(量子回路)の例を示す。 置換表現と量子回路との間の等値を示す。 古典的な不可逆全加算器回路及び可逆(量子)全加算器回路の例を示す。 計算の置換モデルのフローチャートを示す。 計算の置換モデルの別のフローチャートを示す。 計算の置換モデルの別のフローチャートを示す。 計算の置換モデルの別のフローチャートを示す。 ビトニック(Bitonic)整列ネットワークの多項式制約及び対応する実装の例を示す。 ビトニック整列ネットワークの演算及び設計の例を示す。 ポリトープ設計としてビトニック整列ネットワーク演算を示す。 整列ネットワークとして働くブレイディングの例を示す。 置換行列及び置換符号反転行列の例を示す。 置換行列及び置換パターン行列の例を示す。 点と、角度パラメータに対する点での点とタンジェントとの間の関係性を示す。 球(または超球)での特定の確率密度分布の幾何学的形状を示す。 確率密度を有するオービトープの上に置換を埋め込む例を示す。 超球のためのQuantonデータ構造構築のためのフローチャートを示す。 組合せパターンとして置換行列ゾノトープの頂点の再解釈を示す。 3置換オービトープパターンの例示的な列挙を示す。 レーマーインデックスを使用して等級序列付けされたインデックスの3置換オービトープパターンを符号化することを示す。 パターンベースのサンプリングによる信号の二値化、及び数値符号化の表示を示す。 球に写像されるパターンを示す。 表面が純粋である一方、球の中心でのパターンが混合状態であることを示す。 Quantonに写像されたパターンの例を示す。 入れ子にされたQuantonを有するQuanton階層構造を示す。 分布推定アルゴリズムにおけるQuantonのための例示的なフローチャートスキーマを示す。 システムオンチップ(SOC)でのQuantonのための例示的なハードウェア設計を示す。 Quanton PMBGAコンセンサス出力の全体的なマスタフローチャートを示す。 一実施形態に係るコンピュータの例示的な図を示す。
実施形態の詳細な説明
置換をモデル状態の表現として扱うことによって量子計算に対する近似を実行すると、すべての状態が反復によって同時に計算される旨の解釈が提供される。分散を密度汎関数の近似を求めることとして扱うこと、分布を推定すること、これらの分布を順列で表される状態空間に結合すること、これらの分布に基づいて計算すること、現在のQuantonモデルを使用して対称群及び構造学習に対してこれらの分布を用いて推論することは、本開示の実施形態により説明される中心的な考えである。
n個の項目の置換問題での解の探索空間はn階乗である。探索空間は、サイズnの対称群を参照し、通常Snとして示される。一般的に、置換問題はnが比較的小さい数を超えたときに非常に難しい問題として知られ、それらの計算の複雑性は典型的な置換問題の多くがNP困難であると立証されている。その複雑性を考慮して、最適解を計算することは一般的に解決困難である。この理由から、最悪で概算で、及び最善で特定の特別な場合正確に機能するように設計されたデータ構造を、探索空間の階乗サイズで適所に据えるためにQuantonを発明した。
さらに、量子計算が解決の可能性に関して非常に大きい空間を有し、Quantonのデータ構造及び方法が(置換量子計算の別名でも知られる)計算としての置換の考えを基に構築された本開示に説明される固有の効率的且つ計算可能なモデルを使用することに留意し、Quantonはバーチャルマシンとして量子計算をエミュレートするために本明細書で考案される。
ここで、Quantonの概要を提供する図1を参照すると、全体的な手順に対して2つの部分がある。第1に、(Quantonに対して)局所化された計算演算をエミュレートする際に使用するためにQuantonを作成するための局所的な手順があり、次いで入信データの問題について学習するためにQuantonまたはQuanton母集団を進化させるための大域的な手順がある。これは、確率モデル構築型遺伝的アルゴリズム(PMBGA)としても知られる分布推定(EDA)アルゴリズムの手順に基づいて最適解を生じさせるために行われる。
Quantonは、置換が(格子を使用することにより)それぞれ固有のインデックスを有することを可能にする特別な方法で置換を使用して連続確率空間の中に埋め込む。これは、それが量子ゲートを模倣できるようにする演算のための固有の符号化を生じさせる。したがって、量子ゲートは、高速ベクトル計算が複雑な量子ゲート演算の同等物を実行し、入力を出力に変換する、または同等に状態間の量子遷移を計算する連続確率ベクトル空間に埋め込まれる。すべての置換がQuantonでインデックスを付けられるとして同時に利用可能であるとすると、その結果、あらゆる連続ベクトル空間演算は、更新を実行しているのが確率密度分布であるため、すべての置換を同時に更新する。この意味で、Quantonはすべての潜在的な解の重ね合わせを表す。Quantonは、その格子のため量子化された離散構造を表し、エンタングルメントは、もつれ状態を入力クエリー状態(つまり、学習または解決されるデータ)に対する解集合として明らかにする進化プロセスの結果として現れる変数間の相関によって表される。
ステップ−1:Quantonを用いた計算のための主要な手順は、個々のQuantonがインスタンス化されているのか、それともQuanton母集団がインスタンス化されているのかに関わりなく、初期化及びセットアップである、項目1。問題のサイズは、既知または未知のどちらかである、項目1。問題のサイズが既知である、または外部ソースによって推定される場合、この数はQuantonのサイズを設定するために使用される。問題のサイズは多くの場合問題の複雑さといくらか相関し、これが既知である場合、Quantons母集団としての母集団のサイズが設定できる。これが未知である場合、次いで任意母集団サイズが設定される。
少なくとも図2及び表4に対応する本開示の項は、インスタンス化のためのQuantonの設計に関する追加の詳細を示す。
ステップ2−局所構造および大域構造の部分として、次の手順が局所構造及び大域的な分布母集団構造を割り当てる。局所的なQuanton構造はランダウ数を使用して、問題サイズに適合する最大置換群のサイズを生成する。一方、Quanton母集団の大域構造は分布関数を選ぶことによって設定される。置換を生じさせるためのランダウプロセスは、図20Aに対応する本開示の項に詳説される。
ステップ−3:「情報幾何学のナビゲーション」空間の概念、局所レベルと大域レベルの両方に深く根本的な概念がある。個々のQuantonの局所的なケースでは、これは規則正しいグリッドまたは格子を形作られた幾何学的形状の中に埋め込む方法を選ぶことに相当する。格子及び幾何学的形状の選択の詳細は、本開示の表1の中の本開示の項で示される。大域的なケースでは、情報幾何学は、母集団の探索空間を探求する、または別の言い方をすると、サンプリング関数が、空間が探索されるにつれ解の候補を選択するためにQuanton母集団の幾何学的形状の中を移動する、サンプリング手順である。
ステップ4−Quantonの局所モデルでは、本開示の表5に係る非線形方向性確率密度関数が、各置換を生じさせるQuantonに割り当てられ、次の置換に対する遷移確率を有する各格子点で埋め込まれる、またはユーザーの裁量で、確率は置換観測の尤度を表すこともある。これは、Quantonの演算でのL2ノルムの使用を可能にする。例えば、一般的なベイズ推論及び超球等の多様体での確率密度再分配の方法はベイズフィルタとして知られ、ケント分布またはフォンミーゼスフィッシャー分布及びそのより簡略なバージョン、カルマンフィルタ等の分布を使用して、なんらかの収束または固定点に達するまで分布を更新することがある。
ステップ−5:また、線形確率密度は、多様体の各格子点の接空間を関連付けることによってQuantonに関連付けられ、このことがQuantonの演算でのL1ノルムの使用を可能にする。したがって、Quantonは、各置換に関連付けられた線形成分と非線形成分の両方を結合する。Quantonの更新は、未知数の成分を扱うために異なる接空間のガウス分布のディリクレ過程混合モデルに基づいた古典的且つ柔軟な混合モデルを使用することによって進み、それはQuanton確率更新をその線形空間で実行するために容易に高次元データに拡張できる。
ステップ−6:本開示の最も独特な部分は、量子ゲートまたは量子回路に直接的に同等である置換ゲート演算子が、ランダウ数の割付けを使用して置換を生成するようにQuantonをセットアップし、Quanton上の置換関係性が量子演算の演算に一致するように置換に関連付けられる点である。この写像の追加の詳細は少なくとも図19に対応する本開示に示される。
ステップ−7:Quantonは量子エミュレータ(つまり、量子バーチャルマシン)として直接的に使用できる、またはQuantonは次いで、量子ゲート演算子が古典的な計算の通常のビット文字列に対するクロスオーバー演算及び変形演算の従来の概念を置き換えるQuanton母集団で使用できる。この意味では、Quantonは本開示の図39に対応する項でさらに詳説されるように、PMBGAを使用して問題解決量子回路を作り出す量子回路へ進化の経路を提供する。本開示の演算はすべて低い多項式コストで非常に高い効率を伴って発生し、したがってシステムは量子計算の新しいパラダイムを使用する問題解決のための超高速スケラブル量子エミュレータとして見ることができるため、これは重大である。Quantonが難しい問題を解決する際に使用される場合、Quantonは候補解を識別する反復母集団分布推定アルゴリズムでの確率多項式計算ステップによってNP困難な問題に対する解に近付く近似チューリングマシンとして機能する。
ステップ−8:進化のステップは、新しい個体が母集団の中で作成される主要なプロセスである。少なくとも図18Aに対応する本開示の項にさらに詳しく説明されるように、進化は、本開示の実施形態により説明されるように置換により表されるQuantonのゲート状態に作用する量子ゲート演算子の適用によって進む。本開示は置換形式の量子ゲート演算子を使用して量子ゲートを構築及び実行する非常に高速の演算に供されるシステム及び方法を有するため、問題解決システムとしての機能を果たす母集団内の量子計算回路を進化させるために、PMBGAのような古典的な枠組みの中でこの量子応用及び方法を結合することが効率的である。
ステップ−9:いったん量子ゲート演算子がステップ−8でのように選択されると、Quantonの量子回路は更新され、分布の推定が更新される。
ステップ−10:置換距離関数は、量子ゲートの解を測定するために使用される。距離が小さい場合には解は近い。距離が遠い場合には解は依然として見つけられなければならない。したがって、Quantonのきわめて重要な部分は、置換距離関数の選択である。例えばゲート演算の出力ビットストリング間のハミング距離またはゲート演算のビットストリング間の編集距離としてのレーベンシュタイン距離等の距離関数に対するいくつかの選択肢がある。ただし、本開示は、量子システムの確率的性質により密接につながっている置換距離を使用する。つまり、置換に対する距離測定はJ Ceberio, E Irurozki, A Mendiburu, JA Lozano , “A review of distances for the Mallows and Generalized Mallows estimation of distribution algorithms”, Computational Optimization and Applications 62 (2), 545-564の教示に従う一般化されたマローズ(generalized Mallows)モデルに基づき、本明細書にその全体として援用される。
距離測度はこの場合の距離測度を除き、ストリング間のレーベンシュタイン編集距離測度に対する類似物であり、レーベンシュタイン測度と同様にケンドールタウ距離を使用する距離に基づいた指数モデルであるザマローズ(The Mallows)モデルが使用される。2つの置換σ1及びσ2を所与とすると、測度は、σ1をσ2に変換するための隣接スワップの最小数に同等である、σ1とσ2との間のペアワイズ不一致の総数を数える。図39に対応する本開示の項に注記されるように、これは本開示に示される量子置換計算方法の量子ゲート演算子に同等である。したがって、この距離測度を使用する進化は、問題解決を実行する最適量子回路を求める。
ステップ−11:解を作り出すそれらのQuantonは、ビットストリングとしての出力解状態を計算することによって適合性について評価される、または適合性を測定する距離関数に基づいて母集団が当該母集団に単射されて戻るように解状態を計算しているかのどちらかである。適合が閾値に関して次善である場合、次いで母集団は単射されて戻され、親が削除され、より適合した子のQuantonを定位置に残す。システムが反復回数の間ユーザー定義の閾値を超える場合、またはQuantonが所望されるレベルの適合を達成した場合、次いで、Quantonsは活用される解として返される。
確率モデルは、Quantonの現在の母集団における最善の解の分布に従って構築される。したがって、Quanton母集団モデルから解をサンプリングすることは、高い確率を有する有望な領域に入る、または大域的最適に近くなるはずである。
概して、Quanton計算モデルを適用するQuantonバーチャルマシンは、元のチューリングマシンに基づいた計算のモデルに必要とされるすべての特性を有する。さらに、Quanton計算モデルは、置換により表される高次元表面(例えば、超球またはn−トーラス)での格子位置で確率分布関数を使用する多様な計算問題を表す。Quanton計算モデルにより提供される特徴の固有の組合せは、より多くの従来の計算モデル及び機械学習モデルを用いて上記に特定した課題の多くを克服する。
例えば、上記に特定されたように、機械学習の従来のモデルは、訓練データと解データの間の合同についての仮定を行うことができないとき、または以前は存在していなかった新しいモデルを作成しなければならないとき行き詰まることがある。これらの場合、従来の方法の素晴らしい線形特性を無視しなくても、入力データ空間の局所的な特徴及び固有の幾何学的構造は、非線形性も考慮に入れられるため合同の仮定の中に過剰に当てはめられることなく本発明の分類のためにより弁別的な力をもつようになるため、Quanton計算モデルは有利なことに従来の方法のこれらの制限を軽減できる。
さらに、EDAモデルは上述されたように多くの有利な特性を有しているが、Quanton計算モデルはこれらを改善できる。標準的なEDAモデルに比したQuantonとの唯一の相違点は、Quantonモデルが、置換の格子(状態空間)に基づいた構造の表現における方向性の(非可換の、幾何学的な、及び通常は複素数の)確率密度関数を、局所的に線形の接空間での確率密度と結合する点である。置換は、本開示に示されるように、任意の他のモデルまたはパターン構造に直接的にインデックスを付けるまたは表すことができる。有向の確率密度はデータの非線形成分を表し、接空間は線形成分を表す。したがって、Quantonモデルは方向の確率密度または複素数の確率密度と構造とを区別する。一方、従来のEDAモデルは等方性確率だけを使用し、いかなる種類の状態空間構造または格子も使用しない。
以下に詳しく説明されるように、置換は、多様体をテセレートする格子の上で生成され、埋め込まれる。つまり、格子等の例はフィボナッチ格子であり、格子の点に対する置換の対応する割当ての例は、置換多面体(Permutohedron)、または優先的に置換行列のバーコフポリトープとしてのそのより最適な表現である。構造の追加の詳細は、本開示のいくつかの実施形態に示される。しかしながら、Quantonにおいては、あらゆる離散構造が、それに関連付けられる線形確率密度空間だけではなく固有の非線形確率密度関数空間も有することに留意することが重要である。
Quantonに最も近い関係する概念は、例えばトピック分析のための自然言語処理で使用されてきた確率シンプレックスの概念である。確率シンプレックスの点はトピック分布を表す。2つの確率分布の差異がトピック類似性を生じさせる。確率分布差異は比較され、情報量に基づいた測定は、三角不等式に適合しないように使用される、例えばカルバック−ライブラー情報量及びジャンセン−シャノン情報量及びへリンガー距離等の情報理論類似性に基づいているので、距離測度は確率シンプレックスでは適切ではない。しかしながら、例えばトピック等のK個の項目での確率分布は、単一の確率分布が割り当てられる確率シンプレックスにあるベクトルにすぎない。したがって、大きいデータセットはシンプレックス内の点(つまりベクトル)による文書を表す。これらは、通常の最近隣法または潜在的意味インデキシングベースの手法で対応できない。文書がシンプレックスで表されるときに高速文書間類似度計算を実行できないことは、非常に大きな規模でこれらのトポロジー表現の探索及び可能性を制限してきた。
QuantonモデルとEDAモデルとの相違点をさらに示し、強調するために、一例として平易なユークリッド球が活用され、これが本開示において定義されるより一般的な超曲面の特別な場合にすぎないことを強調する。第1に、それ自体が非線形空間である球の表面上に割り当てることができる方向性確率密度があり、第2に、球の表面上の任意の点で、独自の確率密度関数を含むこともある線形部分空間である接点にある接空間が画定できる。Quantonはこのようにしてデータの構造に関して、(接空間の)線形成分と(球面空間の)非線形成分の両方を確率密度関数に結合する。データの構造はそれ自体インデックスを付けられるまたは置換により表される。
さらに、Quantonモデルは、計算を低多項式時間で達成できるように、確率シンプレックス及びEDA手法の考えの新しい高速符号化との混成である。符号化は幾何学的代数を使用することに依存して、Quantonを表し、さらに必要にされるときには、共形空間、つまり実際には最近傍でQuantonを再度表すことによって計算を簡略化し、比較探索は、関係する文書またはトピックをQuantonの非線形底空間の線形部分空間の中に符号化する、距離に敏感なハッシュ関数によって表されるようになる。
幾何学的代数(GA)は幾何学における対称性に基づいた、座標系を含まない代数である。GAでは、幾何オブジェクト及びこれらのオブジェクト上の演算子は単一代数で処理される。GAの特別な特徴はその幾何学的な直観力である。球及び円はともに幾何学的な意味を有する代数的対象である。分布手法は単純な仮説に基づいている。つまりオブジェクトの意味はその使用から推測できる。その考えのベクトル空間への適用は、オブジェクトが幾何学的部分空間の数学的点によって表されるコンテキスト空間の構築を可能にする。類似オブジェクトはこの空間で近くに表され、「使用」の定義は空間を構築するために使用されるコンテキストの定義に依存する。例えば、単語の場合、単語をオブジェクトとし、コンテキスト空間は文書全体、単語が発生する文、単語の固定されたウィンドウ、または特殊な統語的なコンテキストとなることがある。しかしながら、分布表現は多くの認知タスクで人間性能をシミュレーションすることができる(例えば、LSAモデル)が、分布表現は、理解力の認知理論における思考の原子単位と見なされるオブジェクト−関係−オブジェクトのトリプレット(または定理)を表さない。Quantonモデルでは、データは置換ベクトルとして扱われる。したがって、言語学の場合、単語は、それ自体一般的に段落及びテキストの置換である文章の置換である句に優る置換にすぎない。画像データの場合、置換はテクセルを作り出すためにピクセルに基づき、テクセルの置換は画像を生じさせる。
上述されたように、従来の計算モデルは、不正確であるが、決定解を密接に表す解に到達するために古典的な近似法技術を使用するため、従来の計算モデルは苦労することがある。このタイプ近似での課題は、実際の問題が非線形であることであり、非線形関数を可能にすると、はるかに幅広い表現力が生じる点である。しかしながら、線形構造と非線形構造の両方を同じモデルの中で結合するための従来の方法は大いに場当たり的である。Quantonモデルは両方の表現を結合するための一様な方法を提供し、したがって確率学習または確率的推測のための簡略な手順が使用される。さらに、上述されたように、例えば期待値最大化(EM)戦略または最大事後確率(MAP)推測等の学習方法はそれぞれ独自の一連の課題を有している。
Quantonモデルは、より高い次元性を処理できる点でより高い粒度の利点を利用し、誤検出または検出漏れを削減し、欠測データに対処しつつ、埋め込み手法も使用する。サンプリング点の適切な選択を所与として、ノイズの多い部分データはO(dNK)時間内に再構築することができ、ここでdは、フィルタが動作する空間の次元であり、KはN及びdとは関係のない値である。
例えば、高次元ガウスフィルタの加速に関する最近の研究は、サンプルの規則正しいグリッドを使用して高次元空間を点サンプルで明示的に表すことに焦点を当てている。空間がこのように明示的に表されるとき、フィルタリングは高次元サンプル上への入力データを再サンプリングし、サンプルに対して高次元ガウスぼかしを実行し、次いで入力空間の中に再サンプリングして戻すことによって実施される。このプロセスは、通常スプラッティング、ぼかし、及びスプライシングの3段階として文字どおりに定義される。さらに、他のシステムとは異なり、本システムはトレーニングデータ入力に基づいてフィルタ応答を生じさせるために機械学習で使用できる。サンプルの規則正しいグリッドだけを使用する代わりに、手法を拡大させ、均一なシンプライス(simplices)で高次元空間をテセレートする置換多面体(permutohedral)格子を使用できる。さらに、機械学習段階のこのテセレーションに確率密度速度を適用して推測のための事前確率で格子を構成できる。置換多面体のテセレーティングシンプライスは高次元4面体であり、したがって任意の所与の点の取り囲むシンプレックスは(量子化分解能に基づいた)簡略な丸めアルゴリズムによって見つけることができる。d次元にn個の値を有するデータの高次元のために置換多面体格子を使用することはO(d^2n)の時間複雑度及びO(dn)の空間複雑度を有するが、本発明の符号化を並べ替えオービトープとして用いて、この複雑度はk・log(d)まで縮小する。
いったん機械学習段階が完了し、アプリケーションが学習されたパターンの使用を始めると、これらの学習されたパターンが、大規模オンラインリアルタイム知識処理の目標において高速、高データスループットで実行できるだけではなく、ノイズに対してロバスト且つ回復力があることが重要である。重要な学習問題は、観測されるデータの集合を表す最適構造を見つける構造同定の問題である。問題は一般にNP困難であるが、本開示で提供されるデータ表現技法は解としての高速近似のための手段を提供する。
Quantonは予測計算、及び特に状況の妥当と思われる、原因となる状態を仮説推論すること、または潜在的にありそうな驚きの結果を予測することに適用できる。Quantonは、その多様体の上の学習された軌跡によって定義される到達可能な状態の集合を計算するために使用できる。この集合が仮説上の(つまり、おそらく事実に反する)状態の指定された集合と交差しない場合、Quantonはありそうな驚きの結果を予測しない−ただし、集合が交差する場合、結果はもっともらしく、軌跡によって示される驚きを構成することがあるだろう。
一般的に、古典的な確率計算だけではなく量子計算、機械学習、及び人工知能も可逆回路及び高速、高効率、コンパクトな計算表現、ならびに超指数(エクサスケールを超えた)推測及びデータ空間サイズに拡大縮小できるアルゴリズムの恩恵を受けることがある。可逆性は、ソフトウェア設計とハードウェア設計の両方のための現在の技術に比較して、実質的に改善されたより低電力消費につながる。可逆論理回路の表現及び合成は、量子計算のための重要なステップである。それは、新しいタイプの暗号化及び計算においても重要である。一般的な計算、機械学習、及び推測を実施する一般的なタイプの確率可逆回路を合成する上での主要な課題は、入力数の増加に伴い状態空間が指数関数的に大きくなる点である。本開示の実施形態は、高速で効率的であり、きわめてコンパクトな表現を使用する古典的なコンピュータでの古典的な確率計算及び量子計算または量子エミュレーションの両方での表現及び計算方法のシステムを説明する。任意の計算可能な関数は可逆関数に埋め込むことができる。つまり、それは置換として表現できる。本開示の態様は置換により関数の計算を再公式化し、これらを、量子類似計算をエミュレートしていくつかの実際のデータ処理機能を実行する確率多項式チューリングマシンコンピューティングモデルの実現のための確率空間の中に埋め込む。
本開示は、多様な決定または論理ゲートプロセスをシミュレーションする計算ステップが、複雑な演算シーケンスを1つの中に任意でショートカットすることによって計算できるように、離散データ表現または象徴データ表現を、特別な確率的に構成された空間の中に埋め込まれた置換表現の上に可逆に写像する技法を提供する。空間は量子化され、各量子化は、可逆写像を効率的に計算できるようにするインデックスを提供する。量子化は、格子を構築する構造によって実行される。量子化された空間及び空間埋め込み演算に対する可逆部分品は、適切な機械学習及び近似計算のためのデータ構造を提供する。計算は正確であることもあれば、近似であることもある。近似の場合、量子化は、理想的な解析結果とその近似との間の相違をごくわずかにすることができるほど十分に細かくすることができる。データ構造とアルゴリズムとが合わさって、本明細書でQuantonまたはQuantonバーチャルマシン(QVM:Quanton Virtual Machine)と呼ばれるバーチャルマシンを定義する。
以下では、非常に高次元且つ結合により複合したドメインでインデックス付け、クラスタ化、及び推測を実行するための量子触発データ表現、計算モデル、及びアルゴリズムとしてのQVMの説明が提供される。Quantonは、本明細書に指定されるアルゴリズムが効率的な量子類似計算を任意のデータに対して実行するように、データを符号化する。Quantonの作用は、本開示の態様によって定義されるようにQuantonのバーチャルマシン動作の単一のバーチャルクロックサイクルの中のすべての考えられる解経路に作用することであるため、用語量子類似が本明細書で使用されることが理解されなければならない。
Quantonは、高次元並列性を単一計算ステップの中に符号化することによって量子類似計算をエミュレートする。Quantonは、スパースなトレーニングサンプルを使用しながら、高品質、高次元、推測、欠測データ補間、合成、及びフィルタリングを効率的に実行するための新しい手法を提供する。Quantonは、主流の技法で発見された短所を回避する。Quantonは、ハードウェアチップ技術(例えば、フィールドプログラマブルゲートアレイ(FPGA)、超大規模集積(VLSI)回路)だけではなく現在のソフトウェアチップ技術ででも製作することができ、Quantonのための本開示はハードウェア仕様だけではなくソフトウェア仕様の好ましい実施形態も含む。
Quantonモデルは、以下に列挙されるように続く例の応用例でユーザー定義の確度の任意の程度まで効率的な近似を提供する。
1.学習傾向及びランク付け優先傾向
2.認知画像理解
3.コンピュータ音楽(例えば、自動伴奏または音楽フレーズ合成)、大型で複雑な航空管制
4.自動目標認識及び目標追跡
5.高次元階乗ビッグデータ推測、レーダ、及び他の信号追跡アイデンティティ割当て
6.コンピュータグラフィックス及びビデオ分析
7.密にコード化された点集合登録(ピクセル、ボクセル、または量子格子構造)
8.ロボット工学、バイオメトリクス、例えばクラスタ化、実験設計、センサ設置、グラフィックモデル構造学習、部分集合選択、データ圧縮、リソース割当て、オブジェクト追跡または目標追跡その他の階乗的に大きい(状態)空間を有する問題、剛性物体の位置合わせ問題、及び多次元点集合間での類似度の検出等の機械学習
9.例えば、類似したトピックを共有する異なる文書にわたって言い換えられた段落の発見等の意味論的な応用例またはテキスト応用例
10.暗号作成法(つまり、隠れたコードにおけるパターンの発見)
Quantonモデルは、条件付き尤度の下で相互に関連付けられた変数の集合を所与として、グルーピングまたは層として自然に観測されるデータからなんらかの結果(つまり、確率測度)の分布を推定するために線形相関と非線形相関の両方を処理できる。例えば、ケースコントロール臨床研究では、条件付けは、ケースコントロール応答ベクトルの固有の要素のすべての置換を検討することに同等である、層の観測のヒストグラムに対して実行される。これは、古典的なコンピュータでは実行不可能である、階乗的に増え続ける数の項に対して足し算を実行する必要を生じさせる。Quantonは、幾何学的近似によってこれらの問題を解決する。つまり、Quantonはこの階層化された条件尤度の置換オービトープの中に、超球または超トーラスの上への埋め込みを実行することができ、このことが究極的に面倒で非常に長い組合せの総和を、(階乗nの代わりに)(n)log(n)ステップで解を作り出す単一で簡略なベクトル項で置き換える。
Quantonは、「情報を記憶するために亜原子粒子の量子状態を利用するコンピュータ」(Oxford English Dictionary)である、通常定義されるような量子計算の純粋に技術的な意味での量子コンピュータではないが、量子システムの特性及び概念によって触発されている。本開示は、実数または複素数の分布推定アルゴリズム(EDA)のどちらかを使用する連続体表現を有する置換を使用して符号化された離散状態表現に基づいた確率(幾何学)的チューリングマシンの観点からQuantonを定義する。Quantonモデルは、トポロジカル量子コンピュータ(TQC:Topological Quantum Computer)で達成可能であるだろう結果の種類をエミュレートする量子類似計算の近似モデルを表す。TQCモデルでは、参照によりその全体として本明細書に援用される、「Permutational quantum computing」、Quantum Info.Comput.10、5(2010年5月)、470〜497の中でStephen P. Jordanによって説明されるように、任意の計算は置換によってのみ定義できる(つまり、その置換だけがQuantonベースのバーチャルマシンで計算を定義する)。
Quantonバーチャルマシンは、古典的なコンピュータが、真の量子計算によって(つまり、亜原子粒子の状態を使用する)以外、実行不可能である可能性がある、または任意の他の手法によって達成するには確かにきわめて明白ではない可能性がある問題に対する解を近似できるようにする。Quantonは、任意の状態表示が置換によって表される状態に写像される、つまり、各計算ステップが、遷移がある状態表現(または状態空間)と別の状態表現との間の遷移と等価となる、ある置換から別の置換への有向確率である置換遷移モデルによって表される、近似チューリングマシンとして最もうまく説明される。
Quantonの連続モデルは、例えばフィボナッチ数等の数、またはチャンパーノウン数から等の他の数列からのサンプリングを使用して準結晶(準格子)を構築すること、または参照によりその全体として本明細書に援用される、2004年4月8日に出版された、「A granular permutation−based representation of complex numbers and quaternions:elements of a possible realistic quantum theory、Proc.R.Soc.Lond.A 2004 460 1039〜1055、DOI:10.1098/rspa.2003.1189」の中でT.N.Palmerによって説明される技法を活用することによって、確率密度分布または確率密度の混合モデルに置換を埋め込むことによって作成される。
一般的な考えは、(フィボナッチまたはチャンパーノウン等の)数列等の番号付けのモデルから導出された(置換からの)数を関連付けて、リーマン球面等の幾何オブジェクトの量子化された(つまり粒度の細かい)バージョンを埋め込み、確率密度をその上に割り当てることができる準結晶格子を作成することである。より詳細には、格子点は、本明細書に説明されるなんらかのタイプの状態またはデータ構造を表す置換に関連付けられる。さらに、確率密度は、複雑であることがあるn球等の幾何オブジェクトに埋め込むことができるが、その実際の出力は考えられる状態のパターンを置換の関数として表すオブジェクトの多様体での方向性確率分布である。
置換は状態モデルを表す。置換演算の選択は、Quantonを最適に適用できるモデルのクラスを定義するので、特に重要なのは置換演算のタイプ(つまり、要素の置換がアルゴリズム的にどのように実行されるのか)である。球の上の特定の位置の値は、量子粒子状態の代用物を表す状態を定義する。したがって、幾何オブジェクト(例えばn−球)の多様体上の経路の可算集合でのすべての値のアンサンブルが、ヒルベルト空間量子波動関数の代用物である。
一実施形態によって、Quantonは、確率密度空間(多様体)の中への埋め込みと、本開示の態様に指定されるアルゴリズムと結合された置換表現を使用して任意のデータ構造を表してよいソフトウェア要素である。Quantonは、古典的なプロセッサでの量子類似計算を近似するための代用物モデルを形成し、未来の量子プロセッサにおいては、Quantonは高次元空間での複雑な推測のための正確なモデルである。
古典的なプロセッサ上のQuantonは、データサイクルの機械学習における反復(つまり、確率多様体における母集団進化ステップ及びカルマンのような反復ステップの生成)を多くの場合単一のパスで実行できる最小の反復で非常に高速の結果を生じさせる。Quantonデータ表現は、きわめて高度に複雑なデータの空間的且つ時間的に効率のよい表現を可能にする。つまり、Quantonデータ表現は、遺伝的アルゴリズム、中でも注目すべきは確率モデル遺伝的アルゴリズム(PMBGA)としても知られる分布推定アルゴリズム(EDA)に基づいて量子シミュレーションの計算の空間及び時間を削減するための、本明細書に提示されるアルゴリズムも可能にする。
一実施形態によって、Quantonは以下の固有の埋め込み、つまり置換オービトープまたは関連付けオービトープ、確率密度関数を有する非線形多様体、オービトープの点に対応する多様体の点にインデックスを付けるための格子、及び線形部分空間を表すためのインデックスを付けられた点での接空間を使用する。Quantonの特定のインスタンスの一例として、球状のフィボナッチ格子を使用して構築されたQuantonを検討する。フィボナッチ格子は置換多面体の点に対応するインデックスが付けられた点を定義する。これらの点は超球の連続多様体内で内接させられる。超球の多様体は、例えばフォンミーゼスフィッシャー関数等の幾何学的な方向性確率密度関数と関連付けられる。また、格子点での接空間は、ガウシアン等のその線形部分空間及び確率分布とも関連付けられる。
Quantonは、Quantonの中にQuantonを埋め込む、またはQuantonのネットワークを形成することによって階層的にアセンブルできる。ネットワークの場合、Quantonは、「学習された」Quantonの確率密度関数及び置換関数が構造予測機能を提供するため、データがネットワークに進入する際に、接続性が予測される経路予測進化(path−anticipation−evolution)(PAE)を提供する。リアルタイム追跡及び衝突回避で使用される経路予測の例は、参照によりその全体として本明細書に援用される「Deteccting collisions in an unstructured environment through path anticipation」、2006 International Conference on Hybrid Information Technology、済州島、2006年、115〜119ページにJ.Park、S.Kang、N.Ahmad、及びG.Kangによって提供される。
Quantonは、データ空間が入力のサイズで階乗であることがある困難な組合せ最適化問題においてだけではなくマルチメディアまたは多感覚応用データにおけるきわめて大量の高次元の複雑なドメインで推測を扱うために開発される。膨大な数のこれらのデータ及びその高次元のため、従来の推測手順だけではなく、従来の古典的なインデックス付け方法または探索方法もはるかに非効率的過ぎて、最新のスーパーコンピュータのパワーをもってしても役立たない。最適化問題を含むが、これに限定されるものではないこれらの種類の問題のために、EDAモデル等の多様な他の発見的な近似モデルだけではなく、Quantonコンピューティングも提案されてきた。
EDAモデルの2つのバージョンは最適化問題のための粒子群れ及びアリの巣である。しかしながら、これらの多様な異種の手法のいずれも、確率演算子、変形演算子、クロスオーバー演算子、及び他の進化演算子が機能する基本データ構造としてビットベクトルを越えてロバストで柔軟なソフトウェアデータ表現を統合してこなかった。
Quantonは、離散基礎構造がオービトープの頂点から構成される、連続方向性確率分布から構成される。この幾何学的な形状は超球(多様体)、及び有向確率空間上の非方向性確率空間の代用物であるその関連付けられた局所的に線形の接空間の中で内接させられる。状態は対応する量子状態の結果に対する代用物を形成する。係る結果の例は、確率密度の混合物としてのデータクラスタ化、データ分析、及びデータ推論の応用例での結果、推測、または構成を含む。
また、理想的には、本システムのデータ表現及び方法は、古典的なコンピュータアーキテクチャ(つまり、フォンノイマンモデル)での実装からアナログコンピュータ、ハイブリッドアナログ/デジタルモデル、及び完全量子コンピュータモデルへの懸け橋として適している。
重要な考えの1つは、(本開示の格子によって提供されるような)効率的なインデックス付け方法を同時に提供しつつ、例えば置換多面体及び関連付けられたゾノイド等のオービトープ(つまり、組合せポリトープ)を、オービトープを超球または超トーラスまたは他の幾何オブジェクトの表面の中に埋め込むことによってコンパイルできる方法を、データ挙動を表す方法で配向される確率分布と接続することである。
一実施形態によって、本開示のQuantonは5つの重要な考え、つまり(i)組合せポリトープ、(ii)多様体埋め込み、及び(iii)方向性確率密度、(iv)格子、及び(v)接空間を結合する。Quantonは、(例えば、ここで置換構造を、新規且つ自明ではない結果が、さまざまな(ノンパラメトリック)推測プロセスが代用物量子計算近似器として適用できることである、本開示の上述されたPalmerの教示で細かく調べることによって量子代用物データ表現を提供する。これらの近似器は、真の量子コンピュータの忠実性に近いが、真の量子コンピュータの忠実性に完全に一致せず、しかし(当該技術分野では量子人工知能としても知られる)人工知能向けの量子コンピュータに容易に対応できる、結果を生じさせる近似の程度を提供する。
本開示を簡略化する目的で、本開示の中心的に働くアルゴリズム及び方法を示す、開示する、及び説明するために我々の幾何オブジェクトとしてn球(つまり、超球)を使用する。しかしながら、他の幾何オブジェクト(例えば、超トーラス)が等しく適用可能であることが理解されなければならない。
データオブジェクトの係る大きい集合を使用する選択、ランク付け、及び推測は、データオブジェクトの置換、したがって規則または推測の考えられる連鎖の数がエンティティの数の階乗(n!)になる規則構造につながる。
Quantonデータ表現及びアルゴリズムは、任意のオブジェクト集合のすべてのn!置換の埋め込みを提供し、組合せ超級の表面での所与の数のオブジェクト(エンティティ)の場合、R(n+1)における空間のR(n−1)において定義される。Quantonは、組合せ超級表現と、量子計算代用物データ表現と、推測で必要とされる簡略な多項式に削減されるn!要素組合せ時間及び空間複雑度との間でn(log(n))時間アルゴリズム、最悪の場合でも、kn(log(n))を提供する。本開示の態様は、方向確率密度に関連付けることができる連続モートンコードを使用する方法、及び本明細書に説明されるアルゴリズムを使用して置換として表すことができる任意の状態または構造に対して確率密度を確立するための他の方法を提供する。
方法は、多数のオブジェクトを扱い、従来の確率データ関連付けアルゴリズムの結果をエミュレートし、高ノイズの状態での弱信号を弁別し、キラリティを扱うことができ、当業者に既知の当該技術分野主流の推測方法の状態によってではないデータサイズに拡大縮小できる。理想的には、Quantonは量子コンピュータと古典的なコンピュータの両方での実装に適している。
ここで同様の参照番号がいくつかの図を通して同一の部分または対応する部分を示す図面を参照する。実施形態を詳細に説明する際に、上記に定義されるなんらかの従来の表記が使用される。
nは置換の長さである。
πln=(1,2,3,...,n)は、アイデンティティ置換である。
は長さnのすべての置換ベクトルの集合である。
π∈Pは任意の置換である。
は置換ベクトルpのi番目のインデックスが付けられた要素である。
π1(n)は、エントリがすべて1に設定される長さnのベクトルである。
は、1及びゼロを含むnxn置換行列の集合であり、各行及び各列に単一の1を有する。
nxn置換行列の集合の凸包は、Bと示されるバーコフポリトープである。すべての二重確率nxn行列の集合は以下の通りである。
置換多面体PHは置換Pの凸包であり、2−2のファセットを有し、以下の通りに定義される。
置換多面体は、以下によるRn×nからR(R:実数体)へのバーコフポリトープの射影である。
=(v,v,...,v)及びu=(u,u,...,u)を置換多面体の頂点を指す2つのベクトルとし、uとvとの間の距離をd(u,v)とする。
さらに、uのε−近傍を以下として定義し、
例えば、
0≦ε<√2の場合、ε−近傍はN(1324,ε)={1324}であり、
√2≦ε<√4の場合、ε−近傍はN(1324,ε)={1324,1234,2314,1423}である。
頂点が隣接しているとき、次いで(u,v)=√2であり、置換多面体の各点に(n−1)の隣接する頂点がある。
さらに、実数の集合をX=(x,x,x,...,x)として示させる。置換は以下の通り定義される。
置換は劣モジュラ多面体である。置換多面体は単純なゾノトープである。ゾノトープ理論は、ベクトル構成、つまり実現可能な配向マトロイドの理論及び超平面配置の理論と同等である。各次元vの超平面は以下によって与えられる。
置換多面体の点はn次元空間の(n−1)球(超球)上にあり、以下により与えられる。
バーコフポリトープでは、2つの隣接する頂点は、以下の記号、
の単一の互換により異なる。
解xでの確率分布の連続空間の結果を強制的に置換、すなわち置換多面体の頂点により近くするためにペナルティを導入することも役に立つ。この目的を達成するために、以下に示すことは、以下の規則により定義されるベクトルをベースにした規則化方式である。
規則1:v∈R、及びvのすべての置換の凸包から成る集合Xとする。vの置換として、1<p<∞のために最高のlノルムでXの点を定義する。
規則2:Rn^2(n次元の実数体)のすべてのn×n置換行列は、すべての二重確率(bistochastic)行列の凸包である凸(n−1)次元ポリトープの端点である。
n!要素を(n−1)次元超球の表面に埋め込む。
規則4:バーコフポリトープ及び任意の二重確率行列のための置換行列の端点を、すべてのn!置換、つまりRn^2のすべてのマスの中心の回りにクラスタ化される半径√(n−1)の超球の表面に設定する。
置換行列をMとして示し、特定の置換行列をMとして示し、行列のセルでの特定の要素をM(i,j)として示す。
規則5:2n−1超平面の垂線との交差により、規則4の超平面だけではなくすべての置換Mも含むために、Rn^2に(n−1)次元のアファイン部分空間を設定する。
は、次元d=(n−1)−1とする、Rd+1上におけるd次元の超球である。
n個のオブジェクト上のすべての置換行列Mは、上記規則を使用してR(n−1)^2の半径√(n−1)の超球Sの表面上になるように設定される。したがって、例えば3つの置換は4次元空間にある。等角モデルでは、等角モデルは無限遠点を加えるので、3つの置換は5次元空間にある。
規則6:原点で中心に置かれたSを定義する。要件は、Rn^2の空間とR(n−1)^2の空間との間の基底間の変換である。
で確率密度関数を定義し、それを使用して離散n!置換区間を参照する。この特徴は、それが一方の空間、つまり確率の連続空間の要素を他方の空間、つまりその構造が置換によって表される量子化された離散状態空間に効率的に変換するための方法を説明するので、本開示で有用である。
規則7:離散n!置換空間と、極座標の半径√(n−1)の原点を中心とした凸(n-1)次元の超球の表面と、単位元に正規化される超球の半径との間の変換を定義する。
規則8:置換に対するインデックスとしてそのレーマーコード(Lehmer code)を使用してすべての置換を参照し、レーマーコードと極角の座標との間の超球の座標上に規則正しい原点を設定する。
規則9:n番目のレーマーコードを、次元性の原点、d>2からフィボナッチ螺旋格子(それぞれ、球及び超球)上のn番目のフィボナッチ点となるように定義する。したがって、あらゆる置換は格子上の点であり、規則6によって、(格子によって連続多様体上での量子化された誘導されたによって囲まれる)確率密度の有界領域でもある。
規則10:Sで線形部分空間Tとなるために、n番目のレーマーコードに対応するn番目のフィボナッチ球状格子点Sで接空間を定義する。
規則11:例えば置換多面体、カラビヤウポリトープ(Calabi-Yau Polytope)、または任意の準結晶生成関数等のポリトープの逆格子は、(超)球もしくは(超)トーラス等の所与の多様体またはカラビヤウ多様体(Calabi-Yau manifolds)等の他の連続多様体構造の連続体を量子化するために格子の代わりに使用できる。
規則12:接触の空間に対する正しい最も近い格子点を選ぶ不確実性に相当する、エプシロンの不確実性の中で逆格子に線形的に依存すために接空間を定義する。
次元dの単位ベクトルは、その確率密度関数が以下として示される場合、多変量のワトソン分布を有すると言われ、
上式では、
はクンマー関数(Kummer Function)としても知られる合流型超幾何関数である。
定義1:情報搬送自由度は、本明細書ではoとして示される可観測と呼ばれ、仮想情報を搬送してよいシステムの他の自由度はhとして示される隠れていると呼ばれる。量子状態トモグラフィー手順から生じる状態の説明は、密度行列Dによって示される。
重要な手法は状態を観測可能な部分及び隠された部分に明示的に分離し、状態全体の量子統計ニーズを使用して観測可能な部分及びその制約を計算することである。
定義2:パーミュタント(permutant)と呼ぶ特定の順序の記号のシーケンス、及びパーミュトン(permuton)と呼ぶこととする(おそらく固定された制約として働く)記号の別の隠れたシーケンスを含む実際の観測可能な置換。パーミュトンをパーミュタントに適用する演算は、パームトリクス(permutrix)を生じさせる。
定義3:確率測度は格子(例えば、フィボナッチ格子)の頂点で可観測であり、格子点で囲まれた部分区間の中の点は定義されていない。言い換えると、格子点が可観測を提供する量子プシー認識理論に類似して空間を解釈する。一方、介在する領域は遷移空間であり、定義されないまままである。
定義4:Quanton
Quantonは以下のデータ要素を含む。
(1)対称的であり、連続多様体の形をとる幾何学形状、
(2)多様体に埋め込まれた線形部分空間を提供する格子の点で、多様体の対称性群及び任意選択の接平面を区切る格子(したがってトポロジー)、
(3)整数の置換をそれぞれに関連付ける格子の点に対するインデックス、
(4)ある置換から、格子点の間の別の置換への遷移のための規則、及び
(5)格子の点の間の遷移確率を関連付ける確率密度関数。
Quantonの該要素を所与として、QVMがその機能を実行するために動作する特定の操作規則を識別できる。本開示の方法の説明を簡略且つ明確にするために、n球の形をとる球状幾何学形状が、正確なアルゴリズム及びプロセスを示すために全体を通して使用され、これらが他の幾何学形状に適用するために明らかになることに留意する。
定義5:Quanton言語は、本明細書では、置換の間の移動に対応する演算の可逆言語として定義され、これらの移動は格子点の間で可逆である。
n球は、Quantonデータ構造のための例示的な幾何学形状及びトポロジーである。例えばnトーラスまたはカラビヤウ等の他の多様体構造等の他の幾何学形状も使用できる。Quantonは、軽く接触する頂点が置換だけではなくフィボナッチ球状格子上の点にも対応するように、その軽く接触する頂点が超球を内接させるポリトープから構成されるオブジェクトである。
Quantonの表面は通常確率分布、または例えばフォンミーゼスフィッシャー、ワトソン、ガウス、または混合物等のそれと関連付けられた確率分布関数(PDF:Probability Density Function)、及び複素n球上の複素ビンガム分布または複素ワトソン分布等のこれらの確率分布関数の複素バージョンを有する。したがって、Quantonは一実施形態によって、少なくともPDF、離散格子、及び計算または複素データでの深いパターン学習のために本明細書に提示される特定のアルゴリズムから構成されるソフトウェアデータ構造である。
Quantonは、軽く接触する頂点が置換にだけではなく、フィボナッチ球状格子上の点にも対応するように軽く接触する頂点が超球を内接させるポリトープから構成されるオブジェクトであってよい。Quantonの表面は通常、例えばフォンミーゼスフィッシャー、ワトソン、ガウス、または混合物等のそれと関連付けられた確率分布、及び本開示がソフトウェアデータ構造及び複素データの深いパターンを学習するための関連付けられた量子触発アルゴリズムとして定義するこれらの確率密度関数の複素バージョンも有する。一例は、頂点の1つに対する接平面、点での通常のベクトル、及び例えば接空間上の点の回りの、ガウス分布に制限されない確率分布である。この構造は、さまざまな混合物が表されるために、表面と表面上の点への接空間のどちらかまたは両方での確率分布の混合を可能にする。
フィボナッチ螺旋格子は、超球の表面上の座標として点の分布に対する完全に解析解を可能にし、これらの点は置換シーケンスと同じ量に達する。本開示に説明される置換シーケンス、フィボナッチ格子の間の関係性は、置換ポリトープの頂点がフィボナッチ格子を交差するほどであり、これにより置換に対する超曲面上のすべての点及びその逆は、ヒルベルト曲線等の空間充填曲線インデックス付けと類似して、フィボナッチ格子のインデックスとなる。また、頂点の配置は、頂点対頂点の関係が無作為ではないように重要である。例えば、4つの整数(1、2、3、4)の集合を所与として、整数を配置する4!=24の方法があるが、これらの24の数がそれによって書き留められてよい幾何学形状、つまり、その順序付けはそれ自体24!である。したがって、Quantonは、順序付け規則を使用し、ある種の規則正しい順序付けを必要とする。これらの規則は、Quantonを特徴付けるオービトープの例示的なトポロジーについて図13A及び図13Bの下で実施形態でさらに規定される。
図2はパームトリクス 15と呼ばれる頂点12の置換シーケンス16の固有の方法論及び表現を示す。パームトリクス15は、置換パターン、置換パターンの可視部分であるパーミュタント13、及び目的が置換パターンの非可視部分としての機能を果たすことであるパーミュトン14と呼ばれる他のエントリから構成される。パーミュトン14は、その位置を他の要素、つまりパーミュタント13の置換に対して不変にすることによって制約システムとしての機能を果たすことがある。1つの類似性は、なんらかのゲームで許された動きとしてパーミュタントを考え、阻止された(許されていない)動きとしてパーミュトンを考えることである。2次元では、ゲームは多くの内の一例として、チェスであることがある。
また、パームトリクスは、Quantonについての上述の説明のようにn-パーミュタント及びd-パーミュトン(n+d)!について、((n+d)!)!幾何学順序の配列の順序付けの数を生成することがある。順序付けは任意のインデックスのための開始シーケンスを決定するので、この点はなんらかの重要性を帯び、順序自体が、インデックスがどのように動作するのかを支配する関係性を決定する。d-パーミュトン(多くの内の1つの考えられる規則として)「ダミー」変数として働くことを所与として、及び削除される場合、いくつかのシーケンスの結果が繰り返す。パーミュトンの役割は上記で明らかになるが、パーミュトンは、他の演算及び関係性がパーミュタントの関係に応じてパーミュタント及び因数を制御できるようにする仮想粒子の役割を果たすこともできる。1つの具体例として、パーミュタントは自然整数(1、2、3...N)によってインデックスを付けることができる。一方、パーミュトンは、他の演算が特定の方法(例えば、複素共役)でパーミュタント及びパーミュトンを結合することによってインデックスを出力させることができるように、虚数値の自然整数(i1、i2、i3、...iN)によってインデックスを付けることができる。重要なのは、1、異なる反転の数がSteinhaus-ジョンソン-トロッターアルゴリズムからレーマーコード(階乗番号システム)に基づいてグレイコードを形成する連続置換である。したがって、レーマーコードを使用してn番目の反転が決定的に計算可能である。
任意の種類の任意のデータ構造は置換により表すことができ、置換はシーケンス、集合、及び多重集合を表すことができる。したがって、置換は、以下に表現される方法及びアルゴリズムによるデータ表現と計算の両方にとって最も基本的なビルディングブロックとして使用できる。
階乗番号システムは、基数nの累乗で乗算される数字を、nの階乗の連続値を乗算する数字で置換する。階乗番号システムの数列であるレーマーコードは置換を一意に表し、自然数を使用して表すこともできる。自然数は、最初にそのレーマーコードを計算することによってゼロより大きいサイズの置換のためのランクを最初に計算し、次いで固有の自然数を、それをその階乗番号システム表現から10進数に変換することによってそれに関連付けることによって計算される。このようにして、同様に置換の階乗番号システム表現から計算されるそのレーマーコードから任意の置換を再構築することは容易である。
したがって、上述を所与として、任意のリスト、数列、集合、及び多重集合の間で置換に変換するためのプロシージャは指数(つまり、置換、及びその後多重集合等のソースデータ構造が損失なく回復可能である自然数)として表される。データ構造と置換と簡潔な整数表現の間の符号化及び復号のプロシージャは他のすべての場合(数列、集合、及びリスト)をカバーし、以下の変換規則の集合によって示される。
Knuthによって説明される階乗番号システムは、基数nの累乗で乗算される数字を、nの階乗の連続値を乗算する数字で置換する。増加する順序確率変数frでは、第1の数字dは0であり、第2はd∈{0,1}であり、n番目はd∈[0..n]である。例えば、fr(42)→[0,0,0,3,1]→0*0!+0*1!+0*2!+3*3!+1*4!である。
左から右へ減少する順序確率変数flは、frの数字を逆にすることによって得られる。例えば、fr(42)=[0,0,0,3,1]であり、したがってfl(42)=[1,3,0,0,0]である。階乗番号システムを数のリストに変換するプロシージャfrの逆数は、数のリストを階乗番号システムに変換するrfとして示される。同様に、flの逆数はlfである。
例:
fr:42 →[0,0,0,3,1];
rf:[0,0,0,3,1] →42;
fl:42 →[1,3,0,0,0]、及び
lf:[1,3,0,0,0]→42
置換のランク及びアンランキングは、レーマーコード及びその階乗番号システムを使用して実行される。関数perm2nthは、所与のサイズのn番目の置換を生成し、したがって当然、ゼロよりも大きいサイズの任意の置換のランクを表す。それは、最初にそのレーマーコードLhをperm2lehmerを用いて計算することによって開始する。次いで、それは、それを階乗番号システムから10進数に関数lfを用いて変換することによって固有の自然数nをLhに関連付ける。本開示について特に留意するのは、レーマーコードLhが階乗番号システム表現における数字のリストとして使用されることである。
関数nth2permはperm2nthの逆数であり、置換を(ゼロよりも大きい)所与のサイズ及び自然数Nに関連付ける一致するアンランキングを実現する。したがって、置換は、同様に階乗番号システムとして置換の表現から計算できるそのレーマーコードから再構築できる。
全単射写像の例が以下に続く。
nth2perm(5,42) →[1,4,0,2,3]
perm2nth[1,4,0,2,3] →(5,42)
nth2perm(8,2008) →[0,3,6,5,4,7,1,2]
perm2nth[0,3,6,5,4,7,1,2]→(8,2008)
レーマーコード及び階乗番号システムに関して置換及び数を符号化することの方法の上述のプロセス及び応用例を所与として、本開示はこれらの事実を使用して、自然数のリスト、任意のリスト、集合、及び多重集合等のデータ構造の簡潔な整数表現を構築する。
プロシージャ−1:自然数のリストの符号化
(1)任意の入力多重集合の場合、最初に多重集合を並べ替え、次いで連続要素間の差異を計算する。つまり、[x...x,xi+1...]→[x...xi+1−x...]例として:多重集合[4、4,1,3,3,3]を所与として、[1,3,3,3,4,4]に並べ替え、[1,2,0,0,1,0]として一対差異リストを計算する。
(2)ステップ(1)の結果を所与として、そのプロセッサで置換されるインクリメントの数列の要素によって差異リストを再符号化する。したがって、数列中の数のサクセッサのインクリメント和のプレデセッサは並べ替えられた形式で元の集合を返す。例えば、[1,2,0,0,1,0]の第1の要素は数1であり、リスト[2,0,0,1,0]としてそのサクセッサが後に続く。数列中の数のプレフィックス和は、並べ替えられた形式で元の集合を返す。もう1つのより明白な例の場合、[1,2,3,4,5]を所与として、結果として生じる差異リストは[1,1,1,1,1]である。
(3)例えば{7,1,4,3}等の自然数の任意の集合を所与として、先行する第1の2つの演算の適用は並べ替え{1,3,4,7}を生じさせ、次いで連続要素間の差異を計算することは、第1の要素1にインクリメント[2,1,3]が後に続く[1,2,1,3]を示し、インクリメントの数列中の要素を採取し、[1,1,0,2]を生じさせるためにそのプレデセッサで置換することによって、それを、数列の考えられる要素として0を含む全単射に変換し、したがってこれはレーマーまたは階乗番号システムを使用して復号できる。
(4)(3)の出力をとると、係る数列中の数のサクセッサのインクリメント和のプレデセッサは、並べ替えられた形式で元の集合を返す。
任意の自然数の(ビックエンディアン)バイナリ表現は、以下の形式のバイナリ数字の連結として作成することができ、
∈{0,1}、b≠bi+1及び、最高の数字b=1である。
したがって、一実施形態によって、プロセスは定義され、
形式0 の偶数は演算2 に相当し、形式1 の奇数は演算2(j+1)−1に相当する。したがって、以下の方程式が当てはまる。
したがって、表現(l)の中で1 として示されるnの中の各ブロック1は、i回の、fの反復される適用に相当し、n=f(j)である。
この事実から、最上位の桁(したがってビックエンディアン表現の最後のブロック)は1であり、ブロックのパリティが交互になるという事実から、数nは方程式(1)の形式b k_i(k_iは、kを表す)の偶数のブロックを含むとき且つそのときに限り、数nは偶数であるという結果となる。数nは、数nが方程式(1)の形式b k_iの奇数のブロックを含むとき且つそのときに限り奇数である。
以下の通りに、2つの別々の入力自然数を所与として、単一の自然数Nを出力するプロシージャcompose(i,j,N)を構成する。
したがって、一般的にプロシージャを定義する。
具体的には、本明細書で定義されるのは、カウントは本明細書で0を開始するために定義されるので、指数はiの代わりにi+1である点である。また、jが奇数であるときcompose(i,j)が偶数となり、jが偶数のとき奇数となることにも留意されたい。演算compose(i,j)は可逆であり、数のリストを単一の数に繰り返し変換するために使用できる、または単一の数から数の元のリストに逆転できる。
入力として単一の自然数を受け入れ、それを構成した2つの数i及びjを出力するプロシージャuncompose(N)=[i,j]を定義する。uncomposeの定義はcomposeの逆数であり、Nを除算する2の最大指数を識別するために、ヘルパーサブルーチンdivine(N,i,j)を活用する。それは、記号「//」が整数除算を意味することに留意し、以下の通りに計算される。
したがって、一般的に、自然数を他の2つの自然数に可逆的にuncomposeするためにプロシージャを定義する。
上記のプロシージャは規則を定義するために使用され、表3に要約される。数が、グラフまたはフラグメント等の構造を指す、または他のオブジェクトに対するハッシュのような任意の他の写像を有するならば、次いでこれらは表3の方法を使用して、符号化、復号、及び表すことができる。この特徴は、Quantonの構造を写像する上で重要です。
プロシージャ2:Quantonの組合せ設計は、置換の間に遷移モデルを提供して、結果として生じる置換を出力として生じさせるためにデータ構造と置換との間で確立される関係性に基づく。組合せ設計には以下のいくつかの要素がある。
(i)置換をサクセッサ及びプレデセッサに関係付ける整数数列の選択肢に関するQuantonの置換の設計、
(ii)先行するステップ(i)により生じる設計の置換の間の置換遷移演算子の設計、及び
(iii)ステップ(ii)からの置換遷移演算子を操作意味論に関連付けること。
最初に、Quantonの構造の設計、順序付け、及びサイズは、計算のサイズ、演算のタイプ、及び必要とされるデータ表現におけるユーザー定義要件に基づいている。例えば、及び従来のCPUに類似して、4要素のQuantonは2ビットを表すことができ、10要素のQuantonは221ビット(例えば、10!)を表すことができる。問題は、最適性を提供するSnの対称群の適切な設計の観点から置換の正しいサイズ及び設計を選ぶための方法を有することである。答えは、置換の観点からランダウ数を決定することによって与えられる。つまり、これらは、本開示の後の項に示されるように、置換演算子設計の設計により、置換を変換する操作意味論が全単射且つ可逆であることを保証する。
整数数列の選択は明白ではなく、Gian−Carlo Roteによって最初に設計され、参照によりその全体として本明細書に援用される参考資料、Richard P.Stanley(1997年)、Enumerative Combinatorics、第1巻、 Cambridge University Press.ISBN 0−521−66351−2.P41に説明される12要素のある方法から続く。Quantonの組合せ設計のための好ましい数列は表4に示す。しかしながら、なんらかの級数または演算の集合の規則正しいパターンに分解可能である任意の置換が、置換格子を構築するために役立つことがあることが理解されなければならない。例えば、パターン演算子はカタラン自己同形、シグナチャ置換等であってよい。
ランダウ数に基づいたランダウ数列は、置換をSnの巡回部分群の自然な順序付けで自然に構造化できる最大のサイクルを提供する。この場合、例えば、通常の算術加算演算は、示されるようにまさに置換の適用になる。Quantanは、置換がそれによってインデックスを付けられる格子点の間の遷移(つまり移動)を使用することによって表し、計算できるために置換の設計に依存するため、これは重要である。
超球の表面上へのポリトープの頂点の分布で使用される主要なツールは図3:フィボナッチ格子に示される。フィボナッチ格子及びフェルマー格子(やはり螺旋)は分析的であり、可変幾何学形状を用いて点の高速生成を可能にする。また、他の格子も使用できるだろう。例えば、図3、項目17は均等に分布されるフィボナッチ格子によって生成される幾何学形状を示す。一方、図3、項目18は、格子ジェネレータが赤道で生成された点の密度を増加させるためにどのようにして変調されたのかを示す。
任意の次元のためのフィボナッチ格子の表現は角度パラメータの形で示され、n次元表面上の点ごとに1つの角度方向がある。πラジアンの期間で角度を使用する回転操作の対称性のため、角度パラメータの使用は好ましい。この表現を所与として、超球座標では、次いである置換から別の置換へのいかなる移動も簡略に且つ分析的に、フィボナッチ超螺旋(hyperspiral)に沿ってまたはフィボナッチ超螺旋の巻線の間のどちらかの移動によって示される。
置換の頂点を生成する場合では、n番目の置換はレーマーコードによって示され、n番目のフィボナッチ数はビネの公式によって示される。したがって、フィボナッチ格子上の置換と座標との間には分析的な一致がある。これらをどのようにしてさらに点に分布できるのかに関する例示的なオプションは、図13A及び図13Bについてさらに説明される。2球の場合、球状フィボナッチ点集合は、角度を使用して直接的に定義される(これらは単純な置換によって超球座標について上述されたようにn球に汎用化できる)。
底角θごとに、点は垂直線(z軸)上に分布される。
及び、回転の角度φはフィボナッチ率によって示される。
フィボナッチ反比の制限は、mが増加するにつれ黄金比になる。1/Nをz座標に追加することによって、極で均一性を達成し、したがって以下となる。
上述の説明から、円を単一の置換を表す点の数に相当する点に均等に分割できること、または2次元フィボナッチ螺旋、つまりオイラー螺旋も使用できることが理解されなければならない。例えば、3つの置換を用いると、円の上に六角形に相当する6つの点があることになる。集合{1,2,3}を使用してインデックスが付けられた3つのオブジェクトの置換の場合、及びベクトル空間で座標として整数を処理すると、次いで6つのベクトルは3つの空間の座標である(1,2,3)、(2,1,3)、…(3,2,1)となる。しかしながら、このことから、高次元座標系から低次元座標系へ写像する多様な方法は、高次元番号付けを1次元番号付けに全単射的に変換するためにZ-オーダー(モートンコード)等の情報を失うことなく使用できることに留意しなければならない。したがって、例えば、4オブジェクト、{1,2,3,4}の置換のための置換の座標は、4次元空間を生じさせるだろうが、これらはモートンコードを使用してフィボナッチ螺旋上にインデックスとして射影し、3球の上に分散することができる。参照によりその全体として本明細書に援用される、「Spherical fibonacci mapping」、ACM Trans.Graph.34,6,Article 193(2015年10月)の中のBenjamin Keinert、Matthias Innmann、Michael Sanger、及びMarc Stammingerの教示は、置換を点として、フィボナッチ級数を使用する球を含む多様な所望される多様体に関連付けるための手段として球に対する点の写像を説明する。
選択肢が、置換が空間内の座標を表すということである場合、次いでこれらの離散座標はゾノトープ、つまりポリトープまたは超立方体を表す。3つの点の場合、これらは3次元での球の表面の軽く接触する頂点である六角形の頂点を形成するだろう。したがって、一般的に、置換の任意の部分集合は、置換要素がそれぞれ次元として解釈されるならば必要とされる次元よりも低い次元で表すことができる。
置換自体を生成する際に、及び特に0が選ばれたのか、それとも1が選ばれたのかに関わりなく、0(置換無し)で開始して、または1(第1の置換)で開始してインデックスを付けることができる数列に置換を生じさせるジェネレータを提供する際には、最も簡略なジェネレータは、John R.Howel、「Generator Of Permutations By Addition」−Mathematics of Computation−第16巻−第78刷−1962年、243ページの教示から以下に続き、参照によりその全体として本明細書に援用される、整数を使用する加法置換ジェネレータである。K!置換は、置換生成演算子に対する定数Cの加算によって生成できる。整数{0,1,2,...,(K−1)}または{1,2,3,...K}は、基数K整数の「数字」を形成するために連結できる。1の繰り返される加算は、基数K整数を使用してその「数字」が長さKの置換を表す整数を生成する。
このプロセスは、置換ではない数も生成する。この整数に加算するための1よりも大きい正しい数Cは、C=(K−1)基数Kの倍数である。相互に似ていない数字から構成される整数と同じ数字の置換から構成される別の整数との間の算術差異基数Kは、(K−1)の倍数となる。このアルゴリズムが辞書準配列でK!置換を生成する、または2つの所与の置換の「間の」そのあらゆる置換を直接的に計算できる。例えば、K=4の4!置換の場合、数字の集合、D={0,1,2,3}を使用すると、次いでC=3基数4となる。第1にDを連結して数字「0123」を得る。第2に、Cを加算し、「0123」の第1の置換である「0132」を得る。これは、置換が「0123」に循環して戻るまで繰り返すことができる。
順序正しく生成された各置換の場合、それは格子生成関数(つまり、フィボナッチ数列)のインデックス(0,1,2,3...N)に関連付けることができることに留意しなければならない。このようにして、置換は格子上の任意の点と関連付けることができる。
図4で、項目19及び20は、それぞれフォンミーゼスフィッシャー円形方向統計モデル及びサンプル方向データセットからの多変量ワトソン分布の混合モデルを示す。ただし、ガウスまたは汎用マローズ分布等の他の分布も示すことができるだろう。
図4は、内接相関ポリトープ(例えば、置換多面体、アソシアヘドロン)の頂点のない球を示しているが、ソフトウェアQuantonの基本的な内在する実装及び設計がn球上またはnトーラス上での確率密度関数(PDF)の使用に集中していることを強調するために役立つ。正式には、描画は、生成データの個々の確率分布の加重和としてモデル化される、項目19の円及び項目20の軌跡等のデータの分布を表す混合モデルである。
言い換えると、観測されたデータは、確率分布の数の混合物Mであり、以下の公式で定義され、
上式では、vはd次元ベクトル(データ)であり、Mは、それぞれwをエビデンス(重量)として、ρをk番目の成分の確率密度として有する混合成分の数である。
したがって、Quantonは例えばオブジェクトの置換として離散構造と結合されたリーマン多様体上のQuanton等、複素空間上に構築できる。既知のリーマン多様体上にある潜在的に大きいデータセットの確率密度関数(PDF)は、本開示の方法によって近似値を求められる。このようにして構造化されたQuantonデータは、完全にデータ駆動型表現を提供し、多様体上で排他的に定義されるPDFを生み出すデータ駆動型アルゴリズムを可能にする。
ここで図5を参照し、接空間、非線形多様体空間21、確率の関係性、その後置換に対するその関係性、最後にチューリングマシンの意味での状態空間22から状態空間23への遷移の計算でQuantonを定義するための置換の使用を説明する。
図5は、特に点が内接オービトープの頂点を表す内接フィボナッチ球状格子の頂点での接空間を示す。図は、Quantonが多様体の点での接空間内に常駐する線形PDFだけではなく非線形PDFも表すというQuantonについての重要な点を説明しているため重要である。代替表現は、入力データが多様体上で広く広げられるときに代替表現に重大な確度誤差を持たせることになる、またはデータサイズが非常に大きいとき、例えばガウスプロセスを使用することの関連するアルゴリズムの複雑さが代替表現を大きいデータセットに対して実現不可能にする、測地手段に位置する単一の接空間を使用する。
本開示の一実施形態によって、対数写像は、線形ユークリッド接空間でのメッセージ長コストを最小限に抑えるモデル成分の数を自動的に計算する教師なきアルゴリズムを使用して複数の入力データ点を射影するために活用される。データ入力は最も近い頂点の点に量子化される対応する平均点での接空間上の分布によって表される(これは、小さい誤差のある近似を生じさせる)。複数の接空間に対して、単一の接空間を使用して生じる確度損失は多様体の頂点での量子化誤差のコストを克服する。しかしながら、量子化誤差は本明細書では、非線形補正成分、また多様体の表面のPDFである、それ自体別個の条件として対応される。このPDFはQuantonの総合モデルの事後確率の非線形部分の役割を果たすので、該PDFはそれ自体近似値を求められる。
接空間統計は計算され、指数マップを使用して多様体に射影し直される。このプロセスは、統計の集束まで繰り返した。Quantonは、複雑性がトレーニング集合サイズとともに大きくなる既存のノンパラメトリック手法とは対照的に、任意に多数のサンプルを扱うことができる。Quanton多様体混合モデルは、特定のトレーニングなしに欠測成分の部分集合を推測するための回帰だけではなく非線形データモデリングも扱う(つまり、欠測データギャップ識別解決策)。言い換えると、Quantonはつねに需要に応えて仮説を作り出すことができる。
最小メッセージ長(MML:Minimum Message Length)原則を使用する、完全共分散行列を有する多変量ガウス分布のパラメータの分析推定は、接空間を使用してガウスPDFの近似値を求める際に好まれる。多様体上の「ケルヒャー平均(Karcher Mean)」とも呼ばれることがあるN個の点xのマスのリーマン中心(Riemannian Center of Mass)は以下の通りである。
これは、
まで反復される。
値εは閾値であり、値δは多様体を構築するために使用されるフィボナッチ格子(または他の準結晶構造)の量子化(分解能またはステップサイズ)である。本来、方向性PDFはR上でベクトルフィールドを定義し、これは任意の点x∈Rから質点pまでのベクトルを平均するとして解釈できる。
このようにして、点pの回りの接空間の単一のゼロ平均ガウスは、それがこのクラスタのマスのリーマン中心であるならば、pからのクラスタ内偏差に効果的なモデルを提供する。
d次元球上の任意のd次元vMF分布の濃度パラメータk及び平均ベクトルuを推測するための式のための公式は以下として示される。
最小メッセージ長(MML)は事前分布または事前分布が容易に利用できない場合には少なくとも1つの近似を必要とする。前提として使用可能な最も容易な事前確率は一様であり、kとは無関係に単に以下として作成される。
MML推定値は、3次元フォンミーゼスフィッシャー分布のメッセージ長式(MLE)を最小にする(α,β,κ)の値であり、Dはデータを表し、hは仮説を表す。
ここで、Cは定数である。
式det(F(α,β,κ))は、予想されるフィッシャー情報行列の行列式である。それに対して式hα,β,κ(α,β,κ)は3次元での事前確率である。
最後に、式f(D|α,β,κ)は以下からのvMF分布に従って3次元で示される。
したがって、n個のデータ要素Dの場合、以下となる。
混合コンポーネント及び観測データを説明するその対応するパラメータの最適数を推測するための最小メッセージ長の汎用探索発見的手法が使用され、Quantaonのための好ましい実施形態として『Snob』分類プログラムの多様なバージョンで使用される探索に基づく。
図5:接空間から超球への分布の混合に示される状況は、Quanton混合モデルに、両方の線形接空間を球に表すその能力を提供し、図4の球状フォンミーゼスフィッシャー(vMF:von−Mises−Fisher)分布と関連付けられた等方性共分散だけではなく完全共分散行列も提供する。
最終結果として、Quantonを粒子として、及び分布の推定量との関連ではモデルとして関与させる本開示の推論プロセスでのQuantonモデルは、平行化可能であり、観測に対する適応モデル複雑性を有する異方性分布だけではなく等方性分布も扱う。示されるように、各接点は置換の上に構築された相関ポリトープの頂点である。この空間はT と示され、点pの近傍で球の領域を最もよく近似し、方向導関数として考えることができる線形部分空間である。この空間でのベクトルはpでの接線ベクトルと呼ばれる。
該接点での球上のあらゆる接点は、以下の通りにリーマン変換を使用してその線形接空間に写像するために定められる。
を球上の点、T を球上の接点とし、pを球が次元D−1にある任意の接点とする。したがって、T∈SD−1である。接点はT S^(D−1)にあり、p∈T S^(D−1)となる。
そして、リーマンノルム(Riemannian Norm)、リーマン内積(Riemannian inner product)は、以下のように定義される。
リーマン対数写像としての球上の点から接空間への写像は以下の通りであり、
上式では、d(p,T)は任意の点と関心のある点との間の測地的距離である。
逆変換は、本明細書では以下の通りに定義される。
上式ではlノルムは、Tとp(接点)との間の測地的距離である、T S^(D−1)のためのリーマンノルム||T ||である。この表現では、各確率混合成分は独自の固有の接空間にある。
測地的距離変換は、
である。
図6は、Quantonの球状フィボナッチ格子上の特有接点及び接空間を示す−この図は、項目26によって示されるその線形部分空間だけではなく、項目25によって示される接点の、項目24によって示される近傍を示す。線形空間上の点は項目26でσ(1)、σ(2)、σ(3)、及びσ(4)として示され、球の多様体上のその対応する点はσ (1)、σ (2)、σ (3)、及びσ (4)として示される。これらのシグマ点は共分散である楕円を形成し、これは接空間に関する統計が、非線形であるn球上に埋め込まれているが、線形であることを意味する。線形性と非線形性との間のこの架け橋は、計算負担を削減し、一部データセットを所与として、精度だけではく速度も推定量にするために本開示で特に利用される。
上述の図の使用の全体的なモデルは、図7:分布推定アルゴリズムのための反復フィードバックデータ処理のQuantonスキーマに示される全体的なスキーマによって要約される。図7の項目27で、P(λ|x)として表される一部観測データをモデル化する仮説があり、上式ではλは仮説を表し、xは観測可能なデータを表す。項目28のデータxはQuantonに写像される。これは、多様なP(λ|x)のいくつかの、または混合物のために実行できる。
いくつかの重要な点は順序正しい。第1に、基本的な手法は、データxの置換σのなんらかの位置nであるなんらかの項目eの確率を表す一次周辺に対する情報を維持することから構成される。Quanton、接点で接続されたΩ及びΩとして示される項目29の場合、ともにパームトリクスを形成するパーミュタント及びパーミュトンの概念を示し、したがってQuanton拡張は、特定の位置(σ 1, σ 2, ..., σ k)にあるパームトリクス(e,e,...e)の項目の特定の集合の確率に相当する、パームトリクス、Π、図7の項目30での高次周辺から構成される。
したがって、パームトリクスを使用して、Quantonは正確な位置を指定しなくても別の要素に続く位置にある要素の確率を維持でき、このようにして絶対情報なしの相対情報が取り込まれる。したがって、パームトリクスはQuantonの中にあるx個のデータ項目を表す。計算モデルが実行された後のQuantonの出力、図7の項目31は、調和する仮説及びデータ、P(Π|λ,x)だけではなくパームトリクス、Πのモデルである。言い換えると、未処理データ及びその基本的なモデル及び結果は、出力として確率的に引き出される。
大きいxでの任意の分布を表すために、xがサイズの階乗であることを考慮すると、xの置換は、フィボナッチ球状格子上のインデックス、及び格子のその点でのn番目のインデックス置換を表すレーマーコードにより示される分析関係によって、記憶されるのではなく、参照される。このようにして、x個のデータ項目での一様の分布は、xの任意のサイズについて表すことができ、σは置換であり、U(σ)はσでの一様の分布である。
Quantonの構造は、スワップ演算または加算演算等であるが、これに限定されるものではない特定の原始的演算に関して置換及び互いに対するその関係を符号化する。各置換は、したがって暗示的には置換に対する分布である確率分布が割り当てられる基本的な多様体を充填する格子によってインデックスを付けられる。
分布は複雑な方向統計であることがあり、本開示ではそれ自体、量子波動関数の近似代用物として使用される密度汎関数のプロキシとしての機能を果たすことがあり、その場合各置換は状態空間構成を表す。
この状況は図8:量子ビットを古典的なビットに写像するためのルックアップテーブル付きの量子確率経路−密度に示される。図8、項目32で、ポアンカレ−ブロッホ球を示し、α及びβの基底の重ねられた構成のそれぞれに開放端点及び閉鎖端点を有する線分の観点から特別な表現を使用する。図8の項目33で、角度パラメータの観点から通常の量子ビットモデルを示す。球の接点であるパームトリクスが、その近傍の近傍無作為軸整列超平面の近似だけではなく、サンプルを選択できる線形接超平面を指定することに留意すること。
図8の項目34は、接点T 、及び別の点に対するθに関する測地的距離を表す配向セグメントlを示し、点の間隔は端点での塗りつぶされた円及び塗りつぶされていない円により示される向きを有する0と1との間のどこかであることを示す。最後に、項目35はθに基づいた線分が古典的ビット0または1に写像すると見なされるかどうかを判断するために定義される規則を示す。線分は、重ね合わせの部分空間を表すために、及びQuantanの幾何学的仕様及び量子ビットに対するその関係性を強調するために描画される。
言い換えると、量子ビットが確率密度を表すように、Quantonも確率密度を表す。例示的な目的のために、球及び円はより低次元のケースを示すために描画されているが、Quantonの幾何学形状は超球である。しかしながら、量子ビットとは異なるが、量子ビットと同様に、Quantonは、各パームトリクスが、効率のために座標と位置合わせされた整数によってラベル付与された独立した、相互に直交するk次元の部分空間の集合である部分空間の集合を表す。最も簡略な場合、k次元部分集合は1であるが、より複雑な状況では、Quantonは1よりも大きい部分空間を表す。パームトリクスがバイナリ空間[0,1]を表す部分空間の場合、次いで空間は、通常の解釈のように、次元の数のバイナリ指数に比例している。
これを明確にするために、及びQuantonが固有の設計の複雑なデータオブジェクトであることを示すために、「図9:Quantonのトポロジー構造、及び球上のオービトープとして置換状態空間を埋め込むこと」は、部分空間及び写像を示す。図9、36で、4個の量子ビットの簡略な数列が示され、図8の33の円線図は状態を表す。量子置換レジスタの構造は、量子ビットの集合を採取することによって定義及び構築され、4組の量子ビットの4次量子ビットレジスタでの時間で2量子ビットの対を有するレジスタの例が、図9の37でそのそれぞれのベクトル部分空間とともに示される。最終的に、4組の集合(つまり、4量子ビット)の場合、置換の24階乗可能順序付けを有する、考えられる4階乗数列(4!=24)がある。
置換は、部分空間を表す整数によって表され、整数は38に示されるように置換多面体、置換ゾノトープを定義する座標に写像される。しかしながら、本開示の実施形態によって説明されるように、バーコフポリトープ、つまり置換多面体の同等な表現から導出される並べ替えオービトープとして置換ポリトープの拡張されたコンパクト表現があるが、バーコフポリトープは、バーコフポリトープのn複雑度と対照的に、n(log(n))計算複雑度を提供する並べ替えオービトープにさらに拡張される。Quantonのための最終的なオービトープは、図9の39に出力として概略で示され、その構造の詳細は本開示で後述される。
操作モデルは、Quantonの構造、特にトレーニングデータ41から発することもあれば、発しないこともある置換サイズとしてのパームトリクスのサイズ、次元の数、フィボナッチ球状グリッド、及び確率密度モデル42の選択肢によって必要とされる制御パラメータの選択肢を決定するパラメータの集合40を有する図10:分布推定アルゴリズムのためのQuanton操作モデルに完全に示されている。必要に応じて他が選ばれてよく、その任意の混合が選ばれてよいが、確率分布の選択肢はフォンミーゼスフィッシャー分布、ワトソン分布、マローズ分布、及びガウス分布に限定されるものではないが、好ましくはこれらを含む。
確率モデル43の選択肢は、正式の量子波動関数の代わりに擬ポテンシャルを使用する時間依存密度汎関数(TDDF:Time Dependent Density Functional)または方向依存密度汎関数(DDDF:Direction Dependent Density Functional)の優先的な使用を伴うベイズモデル、カルマンモデル、及び量子モデルを含む。TDDFは当業者に既知であることがあるが、DDDFは方向統計の使用に関し、TDDFでは時間が方向性を提供するのに対し、DDDFは遷移にベクトル方向を提供するので既知ではない。
Quantonデータマッピング44は選ばれた確率モデル43に依存し、表5は好ましい写像モデルを示す。
量子計算のために開発された1つのモデルはトポロジーモデルの観点から量子回路網を定義する。これらのトポロジー量子コンピューティングモデルは、1つのインスタンスでは、計算を実行するために「ブレイド」と呼ばれる演算で置換を使用する。Braid演算は、量子ゲートの論理演算を実行するために量子空間に作用する、ジェネレータと呼ばれる行列によって表すことができる。ブレイドは個々のブレイド演算を符号化するジェネレータの積を表すことがある。
したがって、Quantonの置換表現を使用すると、ブレイド演算は、確率の分布の推定の進化を使用して学習することによる解決路へ動かされる置換空間を通る経路である。詳細は上記に示される。
図10、46は、画像データ、方向データ、確率的に関連付けられたデータ、部分グラフデータ、時系列、及び状態表現データを含むことがあるノイズが多い部分データを受け取る。45として構築され、図11でさらに説明されるQuantonデータ構造での計算は、推定される分布の形をとるデータ関係性47のトモグラフィー、及び求められた結果、項目48のトモグラフからの出力に対する解を生じさせる。したがって、データベースが利用できない場合にはシステムは近似解に収束することが示されるが、原則成分はパラメータの集合を有する密度モデル、及び有効な観測のデータベースである。
上述の図10で、図10、45のQuantonを参照し、高レベルモデル説明を示し、ここでは「図11:Quantonデータ構造の構築のためのフローチャート」で、操作ステップ及びQuantonを構築するための操作ステップの説明が細かい粒度をもって示される。
ここで図11を参照すると、訓練データ、項目49は本開示の表3の方法によって置換として表され、これらの結果的に生じる置換パターンは、例えば置換(パターン)、項目50を表すk番目のレーマーコードであるフィボナッチ級数のk番目のインデックスとしてQuanton上のそのインデックス場所に分解される。オービトープ、項目51は、本開示の表1の方法に従って、及び最適には、図23のための説明で後に示されるように並べ替えポリトープとして構築される。確率密度、項目52は表5の方法、ならびに訓練集合の最大事後確率(MAP)分布の推定(例えば、ベイズ回帰フィルタリグプロセスを使用する)、項目61だけではなく、一次キーとしてインデックスも使用し、関係述語の集合または標準的なリレーショナルデータベースシステム等の基本データ構造、項目53にビネの公式及びそのインデックスのリストを書き込むことを含むコンパイルのステップを使用して選ばれる。いったんこれが図5の方法に従って固定点に達すると、次いで較正されたQuantonが返される。
ここで、結果を生じさせるためにノイズの多い部分データを使用するQuantonの一般化である分解を用いて、ノイズの多いデータ、項目56は本開示の表3の方法により置換として表される。しかしながら、この場合、フィルタリングプロセスは、さまざまなユーザーによって選ばれた方法を使用してデータを拒絶してQuanton、項目57のために提示されるデータを削減するために適用されてよい。球状の幾何学形状が埋め込み幾何学形状、項目60として選ばれている場合に、球の上に射影することによってノイズの多いデータのQuantonへの分布を割り当てるために、カルマンフィルタとして、例えばガウシアンを使用し、削減できる出力を生じさせるための、反復ベイズフィルタリングプロセス等の推定関数、項目58。推定は更新されてよく、次いで格子上の最も近い量子化された点は、表3の方法によるその置換表現からデータへ戻す変換を用いて候補の解として返されてよい。
この一般的なプロセスは、訓練データの集合に関してQuanton確率分布を局所的に更新するために使用され、確率的方法及びMAP計算を用いる機械学習の技術の当業者にとっては典型的な十分に理解された慣用法である。
超球の構築は以下の通り説明できる。
はRd+1に埋め込まれており、次元dは、
であり、
である。
超球Sn−1は、以下の通りにn次元の超球状の極座標によって表される。
={x,x,x...x}をn次元のデカルト座標とする。したがって、
である。
変換を所与として及び説明のために、単にnの次元のすべての超球への直接的な一般化による表記の便宜のためにn=3が使用される。
また、半径はより高い次元のケースに対する一般性を失うことなく上記を簡略化するために、単位超球のための単位元となると仮定される。
ここでは、(n=3次元の場合)円弧セグメントは以下により与えられる。
したがって、
である。
球上の螺旋曲線の傾きは、
として示される定数となるために定義される。
したがって、
である。
超球の表面の中への置換埋め込み:
次元d:
空間:
次元の超球への置換埋め込み:
超球の半径:
n個のオブジェクト上のすべての置換行列は、Rn^2−2n+1の中の超球Sn^2−2nの半径√(n−1)に属する。
置換空間:
すべての置換ベクトルのマスの中心:
インデックスをq,rとし、したがって位置qが値を有する場合、それはrとなる。一例に、P(q,r)=P(1,1)は、置換ベクトルの第1の位置が値1に設定されることを意味する。したがって、n個のベクトルの場合、(1,1)置換を有する(n−1)個のベクトルがある。
したがって、
である。超球の半径は、
である。
n番目のフィボナッチ数は、ビネの公式によって示される。
モチベーションは、任意の次元のデータに対する確率密度推定量の設計から、より一般的にはソースコーディングから引き出される。以下の手順は、(n−1)次元のサンプルをSn−1の上に写像するPDF推定モデルを定義する。PDF推定は、カーネル密度導出推定技法を使用して新しいドメインで実行される。平滑化カーネル関数は各サンプルをその場所で表し、そのコントリビューションを合計する。
これはカーネルとデータとの間のコンボリューションに同等である。したがって、導出されたコンボリューションの結果は推定を表す。コンボリューションが依存性を扱うためではなく、推定値を計算するためにだけ使用されることに留意されたい。vMF遷移モデルでは、vMFは角度ガウスによって、及びvMF空間に以後に射影して戻る角度ガウスの分析コンボリューションを実行することによって近似値を求めることができる(Mardia及びJupp)という事実を使用して周辺化が実行できる。
関連する研究では、S.M.Plis、T.Lane、及びV.D.Calhoun「Permutations as Angular Data:Efficient Interference in Factorial Spaces」、2010 IEEE International Conference on Data Mining、シドニー、NSW、2010年、403〜410ページの教示が参照によりその全体としてここに援用される。しかしながら、Plisらの教示はn球の中に離散置換構造を埋め込む方法を示しているが、該教示は、例えば本発明の方法等、インデックスが付けられた準結晶格子を使用することによってプロセスを効率的且つ一般的にする方法を示していない。本開示は、インデックスが付けられた埋め込み空間を、単にn球ではなくnトーラス等の他の種類の幾何学形状に一般化できる多様体の上に構築するために、概して例えばフィボナッチ級数等の数系列を使用するすべてを除き、いくつかの方法の内の1つの方法を提供する。
置換ポリトープから超球へのアルゴリズム:
ポリトープの頂点から球の表面へ写像するための一般的なアルゴリズムは、以下の3つの簡略な一般的なステップによって示される。
1.ポリトープPを所与として整数座標を原点に変換する。
2.ベクトルをRn−1の球座標に変換することによって基底を変更する。
3.単位ベクトルを得るために半径により縮尺を変更する。
ここで、以下に示されるこの一般的な手順の好ましい実施形態は、縮尺の変更及びそれ以外の場合Plisらにより示される多くの他の計算を回避する。
1.0...nからの任意のコードが置換、P番目のインデックスを提供するように、置換ポリトープPをレーマーコードインデックスに変換する。
2.各レーマーコードを1からNからの固有インデックスに関連付ける。
3.このp番目のインデックスを超球の超曲面上のフィボナッチ超曲線(hypercurve)上の点にする。ビネの公式を使用してこのP番目の整数を計算する。
4.フォンミーゼスまたは他の(マローズ、ワトソン)確率モデルを、超曲線が埋め込まれる超曲面に適用する。
5.したがって、その点にあるフィボナッチ数により示される超球上の各インデックスはそれぞれの置換、したがって点の回りの領域パッチによりインデックスを付けられる、インデックス付き方向分布を有するロケールも表す。
6.Rn−1の単位球座標を使用する。
7.インデックスをフィボナッチ球面写像のインデックス項に関連付ける。
超球から置換ポリトープへ戻るアルゴリズム:
n^2での(超球の表面上または近くの)任意の点を所与として、置換である最も近い点を見つける。Plisらの教示に従って、超球上の任意の点は、入力点とその最近傍との間のコスト行列が、最善の最近傍の選択を生じさせるために最小限に抑えられる最小重み付き二分マッチングアルゴリズムを使用することによって最も近い置換点に適合できる。
しかしながら、本開示では状況はより簡単である。なぜならば、Quantonジェネレータは分析的であり、フィボナッチ格子は任意の擬似セルでのいかなる任意の点も最善の格子(つまり置換)点を選ぶために、識別し、距離を計算するのが容易であるように規則正しいインデックスで空間をテセレートする(つまり量子化する)ためである。言い換えると、フィボナッチ格子ポリトープのインデックス点は空間を量子化し、したがってフィボナッチ曲線上の任意の点に最も近い点は任意の点までの曲線に沿った最小距離を使用して見付けられる。任意の点が(例えば、2つの格子点の間の)完全な中点二等分である場合、次いで最近傍格子点を無作為に選択する。曲線への距離の値を求めるための手順は以下の通りである。
(1)フィボナッチ曲線は北極から南極まで球をらせん状に下がる。フィボナッチ曲線はz(南極での−1から北極での+1)について近傍の巻線から一定の距離のままである。
n=所与の螺旋を定義する定数
それは隣接する巻線からの各巻線√(4π/n)で球の回りでk/2回転する。一方、傾きdz/d(x,y)は1/kである。
(2)巻線間距離が球上の最大のタイルをカバーするようにkを設定する。
(3)主要な集合の各点について、曲線上の最も近い点のシータを計算し、それらの数で点のリストにインデックスを付ける。所与の試験点の場合、最近傍距離限度である曲線上の最も近い点のそのシータを計算し、インデックスの中でその点を見つける。
(4)線形走査を使用して、そこから(つまりインデックスから)現在の最近傍と同程度に遠く離れているシータ値まで(両方向で)外向きに探索する。その限度に到達後、その近傍までの距離が試験点から次の隣接する巻線までの距離未満である場合、最近傍が得られた。得られなかった場合、2pi、シータ値をジャンプし、同様にその巻線を探索する。
(5)次いで、n球上のアーク長さsは以下の通りに計算される。
(6)最も近い格子点のインデックスがその点での置換のためのレーマーコードを生じさせる関係を使用して、超球の表面上の点から最も近い置換への最も近い格子点に変換し直す。ただし、
(7)表面上の点が複数の格子点から等距離である場合、無作為に最も近い点を選び、その点で置換を返す。
Quantonジャストインタイム較正アルゴリズム。ここで、置換がどのようにして生成されるのかを定義する構造モデルで開始する、図12:Quanton較正構築処理64の詳細を参照する。置換構造は置換のタイプ、及び1つの置換がどのようにして次の置換につながるのかだけではなく、それが所与の問題をどのようにして表すのか、またはそれが一部のデータをどのようにして表すのかという観点からも定義される。要素65、状態遷移モデルは、置換の間の確率遷移のタイプを指定し、データから学習されてよい、または推測的に提供されてよい。つまり、モデルが実際に遷移状態ベクトルを説明する。時間モデル66は、置換またはそれらの多様体への割当てがどのようにして経時的に変化するのかを決定する関数を指定する。測定モデル67は、重み付け係数または換算係数、及び置換の間の距離を測定するための関数を提供する。実際には、それは状態ベクトルでの観測よりも低い次元性の測定ベクトルを提供する。例えば、ハミング距離が使用できるだろう。
アルゴリズムパラメータ68は、確率密度関数69の選択によって示されるように、あらゆる定数または発見的手法または濃度または確率モデルによって必要とされる他のパラメータを含む。
確率モデルは、例えばベイズ推論等、当業者にとって標準的な定義に従って観測確率、推移確率、及び事後70確率から構成される。
ここで、図12において71、72、73、74、及び75と参照される項目は、集合的に機械学習としても知られる較正のプロセスを構成する。Quantonは、観測としてなんらかの既知の参照データを使用して較正される。較正は、置換が、観測された訓練データが満たされる許容閾値に対応するまで多様体上の置換の間の確率密度分布の反復推定に基づく。周辺化ステップ、項目71は、新しい分布を生じさせ、これは従来のケースでのように、データが学習される、項目72まで(再帰的ベイズ推定のように)再帰的である更新推定プロセス、項目73で使用され、較正は完了される、74、75。
ここで、図13A:トポロジー構造4置換オービトープの空間を参照する。置換を定義する数の移動としての置換の構造は特定の構成を形成することに留意する。本明細書に示される1つの例では、4つの置換は76で開始してよく、77で結果を生じさせる。
図13Bは、5置換オービトープの空間のトポロジー構造を示す。一例では、5置換は78で開始し、79で終了する。
図14は再帰的進化及び推定のフローチャートを示す。
モデルは2つの主要な部分を有する。
は、隠れた置換の確率的進化を説明する
は、上式ではoは隠れた置換
のノイズの多い観測であり、この式に対する周辺化は角度ガウシアンでvMFの近似値を求め、分析的にコンボリューションし、vMF空間に射影し直すことによって計算できる。
すべての推論ステップは置換のS表現に対してだけ作用し、不必要な変換オーバヘッドを回避する。
遷移モデルは置換h(σ(t)|σ(t−1))に対するおそらく混合された条件付きの確率分布によって定義され、2つの異なるデータに属する要素は混合イベントによりなんらかの確率と交換される可能性がある。観測モデルは、例えば各データ要素について観測可能である特定のデータ特徴に対する分布を捕捉する可能性がある分布P(h(t)|σ(t))により定義される。
分布h(σ(t)|z(1),…,z(t))を所与として、2つのステップ、つまり予測/ロールアップステップ及び条件付けステップで時間t+1での事後確率h(σ(t+1)|z(1),…,z(t+1))を再帰的に計算する。総合すれば、これらの2つのステップが前向きアルゴリズムを形成する。予測(数学的帰納法)/ロールアップステップは遷移モデルで分布を乗算し、以前のタイムステップを除外する。
密接に関係している置換はより多くの共通の情報を有し、したがって不十分に関係している置換よりもより圧縮可能である。この情報理論的枠組はそれらの設定におけるランク付けについての事前の知識を調整することによって個々の状況に適応できる。行うことが可能である特定のタイプの測定は以下の通りである。
(1)2つのパームトリクスの非オーバラップの範囲の測定
(2)パームトリクスのその重複する要素の混乱の測定
(3)パーミュタントでのこれらの要素の位置(ランク)の変位、及び
(4)パーミュトンのサイズ、及びそれらの部分列回避パターンまたはそれらの部分列同型との間のアライメントに基づいたエンタングルメントの代用物
(n球に対する射影である)連続パラメータは(フィボナッチ格子構造及び置換のために)必ず有限精度までしか記載できない。MMLは、パラメータが位置する不確実性の領域を決定することによって枠組みの中にこれを取り込む。値、
は、中心にあるパラメータΘの不確実性の領域の体積の測度を与える。
Θが確率密度で乗算されると、h(Θ)は特定のΘの確率を与え、以下に比例する。
この確率は、連続値パラメータを(有限精度まで)符号化することと関連付けられたメッセージ長を計算するために使用される。
データDを所与とする任意の分布のパラメータΘのベクトル。仮説h(Θ)に対する事前確率が選ばれる(例えばガウシアン)。フィッシャー情報行列の行列式も以下、つまり対数尤度関数
の予測される二次偏微分係数の
を評価するために必要である。
pがモデルの自由パラメータの数であることに留意されたい。
置換問題のための凸緩和
所与:n個の変数に対する対類似性Aij情報
πを連続的に配置された置換順序付け(半順序集合)とする。次いでAπ(i)π(j)は、(R行列としても知られる)|i−j|で減少する。
Aのラプラシアンを
として定義する。
Aのフィードラベクトルは以下の通りである。
点zがxの座標全体の値を降順で並べ替えることによって得られ、以下の方程式を満たすとき且つそのときに限り、x∈RはPHにある。
vMFの例:
(要素81を参照すること。)
(要素81を参照すること。)
;事後確率モデル(要素82を参照すること。)
観測モデルにより推定を更新するために新しい観測を使用する(要素86を参照すること)。
遷移モデル、観測モデル、及び事後確率モデルのために確率分布を使用する。
o個のオブジェクトの部分的な観測が利用可能になるとき、観測された置換行列Oの未知の部分はnから(n‐o)に削減される。したがって、アルゴリズムはそのノイズが多い部分的な可観測から隠れた置換の仮説形成(推論)を提供する。
図14は、方法1400 Quantonモデルシミュレーションの1つの実装のフローチャートを示す。
方法1400のステップ80では、多様な入力パラメータを初期化する。例えば、初期化されたパラメータは最大値、停止基準(例えば、反復の最大数)、次元、構造モデル、状態遷移モデル、方向性確率密度関数(例えば、ガウス分布の平均及び分散、及びフォンミーゼスフィッシャー分布の場合、平均及びκの値)を含むことがある。多くの方向性確率密度関数を使用できるが、方法1400はフォンミーゼスフィッシャー分布を使用して本明細書に例示される。さらに、初期化されたパラメータは隠れた置換の相対パーセンテージを含むことがある。Quantonは、バーコフポリトープとして及び/または超球として表すことができる。
方法1400のステップ81で、観測モード及び遷移モードを定義する。遷移モデルは、遷移モデルは置換h(σ(t)|σ(t−1))に対するおそらく混合された条件付きの確率分布によって定義され、2つの異なるデータに属する要素は混合イベントによりなんらかの確率と交換される可能性がある。観測モデルは、例えば各データ要素について観測可能である特定のデータ特徴に対する分布を捕捉する可能性がある分布P(h(t)|σ(t))により定義される。
分布h(σ(t)|z(1),…,z(t))を所与として、2つのステップ、つまり予測/ロールアップステップ及び条件付けステップで時間t+1での事後確率h(σ(t+1)|z(1),…,z(t+1))を再帰的に計算する。総合すれば、これらの2つのステップが前向きアルゴリズムを形成する。予測(数学的帰納法)/ロールアップステップは遷移モデルで分布を乗算し、以前のタイムステップを除外する。
方法1400のステップ82で、状態の事後確率を生成する。
方法1400のステップ83で、隠れた置換の確率的進化のための周縁化を計算する。フォンミーゼスフィッシャー分布の場合、これは2つのフォンミーゼスフィッシャー分布間のコンボリューションが周縁化を表す近似を使用して計算できる。
方法1400のステップ84で、観測を生成する。観測は、最初に置換をその行列演算子表現に変換することによって生成できる。次に、行列演算子表現を使用して、分布の平均ベクトルを生成するためにバーコフポリトープの部分空間を表す直交基底ベクトルが及ぶ部分空間の超球の表面上に行列演算子表現を射影することができる。
ステップ84の特定の実装では、分布の平均ベクトルを使用することによりフォンミーゼスフィッシャー分布からのランダムドローを生成して統計サンプルを生成し、バーコフポリトープ上で修正された置換分布を生成する。
ステップ84の特定の他の実装では、分布の平均ベクトルを使用して多様なオブジェクトの場所のためにフリップ確率行列を計算する。次いでフリップ確率行列を確率モデルとして使用して、超球上で表される置換に対する変更を決定して、修正された置換を生成する。修正された置換は次いでバーコフポリトープ上の修正された置換分布に変換できる。
バーコフポリトープでの修正された置換分布は、次いで置換行列の最も近い頂点の値を求めるためにバーコフポリトープの部分空間を表す直交基底ベクトルの逆数を使用して超球の最も近い頂点の上に写像でき、最も近いことはユークリッド距離を使用して決定される。
方法1400のステップ85で、新しい観測を生成するために部分観測を実行する。
方法1400のステップ86で、新しい観測を使用して、観測モデルを通して推定を更新する。
方法1400のステップ87で、停止基準に達しているかどうかの照会を実行する。停止基準に達していない場合、方法1400はステップ87からステップ83に進む。それ以外の場合、方法1400は完了する。
n^2の任意の点は超球上の点に、したがって置換に相当する。TをRn^2の任意の点にし、したがってこの点はS上、つまりS(n−1)^2−1上の点に相当しなければならない。
置換に関するPDFの観点から、vMFは距離をベースにしたモデルを確立し、距離はSd上の測地線である。しかしながら、VMFは等方性分布のために役立つが、vMF分布の濃度パラメータのための閉鎖形式の共役事前確率の欠如が事後確率推測を複雑化し、濃度は通常パラメータであり、任意に固定され、データから推測されない。
接空間モデルの追加は異方性分布を可能にし、データによって動かされるように、データにモデル複雑度を適応させながら、球上の他の分布に対する補正の機能を果たすことがある。推測アルゴリズムは、球の幾何学形状及びフィボナッチ格子を利用しながら平行化可能である。
本開示では、接空間モデルで、各混合成分は独自の接空間に存在し、各接空間は一意である。
ここで図15:多面体構造を参照すると、ある置換から別の置換に遷移する際の経路または関係を識別する、いくつかのブレイド群及び置換オービトープ(ゾノトープ)の空間、つまり異なる置換レイアウトが示される。図15の目的は、置換の順序付けに関して幾何学形状の構造に注意を引くことである。Quantonモデルでの置換順序付けは状態空間の間の遷移順序付けを提供するため、これは重要である。例えば、88で、ラベルaは置換の「正方形の」配置にあり、置換の六角形の配置に隣接している。しかしながら、89で、ラベルaは置換の「正方形の」配置にあり、ラベルbで置換の八角形の配置に隣接している。90で、Quantonの表面をタイル表示させるいくつかの異なる多角形のロケールが示される。
ここで図16:量子化された多面体確率密度分布を示す多面体構造を参照すると、等しい確率密度91のより明るい陰影が付けられたパッチが、カバーされているすべての置換が可観測としての外部セマンティックスを置換としての状態空間に関連付けることを意味すると解釈されることが分かる。本開示に示されるように、これは、ベイズのような手法を使用し、Quantonによって学習できる。
図17:単一の量子化された多面体確率密度の射影を示す多面体構造。学習された状態が軌跡またはQuanton92の因果関係を示す状態の数列を表す場合、これらの状態は数列に展開する93ことができ、状態及びその遷移の集合が標準的な確率ベースの学習方法によって学習される因果関係のモデルを構成する。
図13、図14、図15、及び図16は、置換が置換パターン数列に従ってパターンに埋め込まれる、及びこれが準格子生成手順によって示される幾何学形状及びトポロジーに関連付けられる旨の一般的な考えを示す。この時点で、任意の量子ゲート及び回路を置換パターンによってどのようにして表すことができるのか、ならびに任意の量子ゲートプロセス(つまり量子ゲートの複雑な集合の演算)がQuantonの経路によって直接的にエミュレートできることをここで示す。具体的には、計算不可能な数と計算可能な数の両方とも仮説形成的な仮説及び演繹的な計算を生じさせ、一方、確率遷移を調整する機械学習は帰納的学習を生じさせる、という事実に対処する。
参照によりその全体として本明細書に含まれるのは、Michael A.Nielsen及びIsaac L.Chuang、2011 Quantum Computation and Quantum Information: 10th Anniversary Edition(第10版)、Cambridge University Press、米国NY、ニューヨークの教示である。
n個のビットのグループ(レジスタ)は所与のときに2個の異なる数字の1つしか含むことができず、任意の定数k>1及び任意の自然数nの場合も、以下、つまりk≦n!≦nが当てはまることが理解されなければならない。したがって、例えば、置換に含まれるように2=16の可能性を含む4量子ビット状態、つまり4!=24の可能性状態を考慮する。したがって、置換の状態空間が従来の量子ビットに比較して驚くほど迅速に拡縮し、最後に量子ビットが単純ビット(または当業者に既知のpbit等の一様な確率のビット)の状態空間よりも速く拡縮することが明らかに分かる。
実数を複素数の部分集合として見ることができるように、量子ビットを、計算基底を用いて、実数のエントリを有する密度行列を有する量子ビットの量子状態の部分集合としての、実数とされるRebitとして書き換えることが可能である。Rudolph、T及びGrover,L、「量子計算にとって汎用の2rebitゲート」の教示に基づいて、n+1個のRebit(実数ビット)は実数部及び虚数部ならびにn量子ビット状態の初期状態に対する追加のコーディングを用いて、任意の状態を表すことができると言うことができる。
対応する符号化された状態は、│R〉=│0〉及び│I〉=│1〉を符号化において実数部及び虚数部を明示する単なる記法であるとして、
である。
大域的な位相だけ量子ビット状態を変更することは、同じ量子ビット状態を符号化する無限に多くのRebit状態の存在によって反映される。簡略に言えば、結果として生じる公式は、全体的な絶対値符号が欠けていることを除き、複素数の場合に類似している。したがって、2量子ビット状態は、ルドルフ及びショア(Shor)モデルの3Rebit状態として書き換えることができる。Quantonは量子理論の実数振幅変形による量子システムの近似モデルであるため、これは重要である。
任意の所与の量子モデル状態は、量子状態の標準形として機能する固有のQuantonに変換されてよい。標準形は、Quantonでの確率の下での等価なグループである、代数的に独立した確率的な局所的操作及び古典通信(SLOCC:Stochastic Local Operations and Classical Communication)に依存する。したがって、これらの不変式は、これらの確率によってパラメータ化される電子軌道の族を構成する。一実施形態によって、この考えは、例えば、共有されるパターン回避順列として、または共有されるパターン適合順列として既知でもある、少なくとも1つの群(つまり電子軌道)が共有されなければならないとした場合に、N量子ビットエンタングルメント状態が(N−1)!の量子もつれ状態の族として定義されるように、等価な群共有のモデルによるエンタングルメント表現の土台を作ると解釈される。したがって、N=4の場合、3!=6族があり、N=3の場合、2族(つまり2つの非同型のパターン)がある。
量子論理回路を置換表現に写像するための手順:
上記に引用され、本明細書に援用されるNielsen及びChuangに従う量子回路は、nビット可逆論理ゲートとして見ることができる。これらの論理ゲートは複雑な関数回路を形成する。しかしながら、それらはすべてそれらを通過するビットの2の考えられる状態に作用する置換と等価である。したがって、可逆論理回路を指定することは、それが置換として動作する写像を指定することとして定義される。量子計算では、これらの計算状態は量子機械状態によって表される。
明確に定義された量子機械状態であるn個の要素を有する有限集合Sを定義する。したがって、任意の可逆論理は置換演算子σ∈Sを導入することによって表現され、σはそれ自体の上へのSの1対1の写像である(つまり、置換)。
ビットの集合を以下、つまりa,b∈(1,0)のように小文字で表し、集合の内の集合は測定ゲートの2つの入力ビットによって表現される4つの計算状態として解釈されるiによって(i=0、1、2、3となるように)表すこととする。したがって、以下のように論理の詳述を作成できる。
この表現は置換群Sの要素として本開示で解釈される。ここで、重要な考えは、C−NOTゲート等の任意の汎用ゲートが、上記表を置換によってのみ表現できるようにSの1対1写像として表現できる点である。Sは、4状態システムのための24の異なった論理ゲートを意味する4!の置換を含む。本開示で上述されたように、任意のNレベルの量子システムはN!の計算上別個の論理集合で置換できる。つまり、次数Nのこれらの置換は置換の合成演算の下で階数N!の群を形成する。
したがって、以下では、本開示が(置換による計算としても知られる)(確率)置換による量子計算のためのバーチャルマシンをどのようにして表すのかが示されている。
任意の置換群Sは、σに対する群演算としての組成写像φを用いる、間隔S={1,2,3,...N}の置換
の集合のすべての全単射写像の集合体である。
互換が長さ2の巡回置換であるため、任意の置換は互換の積として作成することができ、したがって任意の置換は互いに素な巡回置換の積として作成することができることを思い起こすと、各巡回置換を以下のように互換の積として作成すれば十分である。
所与の置換を互換の積として作成するいくつかの方法があることに留意されたい。例えば、P=(3,5,4)(1,2,3,4)とする。次いで上記公式[00183]を巡回置換(3,5,4)及び(1,2,3,4)のそれぞれに適用すると、P=(3,4)(3,5)(1,4)(1,3)(1,2)が得られ、したがってPは5つの互換の積である。他方、最初に互いに素な巡回置換(この場合、ただ1つの巡回置換しかない)の積としてPを作成し、次いで(T)を使用する。これによりP=(3,5,4)(1,2,3,4)=(1,2,5,4)=(1,4)(1,5)(1,2)が与えられ、したがってここではPは3つの互換の積である。
C−NOTゲート94は、Nielsen及びChuangに説明されるように汎用量子ゲートである。図18Aは、置換巡回表記で作成される置換へのC−NOT回路の写像を示す。置換の巡回の積は可逆論理と等価である。nビットのCNOTゲート(つまり、制御されたNOTまたはC−NOT)はnの任意の1ビットに対して作用する。一方、制御ビットは他の(n‐1)ビットまたは(n‐2)ビット等である。n=3の場合、図18Bに示されるように、9つの考えられるC−NOTゲート100があり、入力と出力との間の各置換演算は互換の固有の積によって顕在化される。
量子計算の場合、汎用可逆ゲートが必要である。係るゲートの1つはトフォリゲート95であり、3つの入力(a、b、c)及び対応する出力(a’、b’、c’)を有する3ビットゲートである。入力と出力との関係性は以下の通りである。
ここでは、
は排他的論理和(つまり、2を法とする加算)を示し、・は論理積関数を示す。変数a及びbは制御ビットであり、cは目標ビットと呼ばれる。論理から分かるように、制御ビットはゲートを通過中、変更を有さない。しかしながら、両方の制御ビットが論理1である場合、目標ビットは反転する。トフォリゲートゲートに対応する置換は以下の通りである。
2進数での互換表現は、10進数が(6,7)である(110,111)である。
Peresゲート96はトフォリ及びC−NOTゲートの動作の組合せであり、図18Aに示されるように、97が98に加算されて99を生じさせる。したがって、それは、加算、減算等のより複雑な論理を実現できる。Peresゲートは、以下のように入力と出力との関係性を維持する3ビットゲートである。
このゲートに対応する置換は以下の通りである。
10進数では、対応する巡回置換は4の長さを有し、以下
として3つの互換に分解できる。
任意の可逆論理は置換群として書き換えることができる。したがって、置換巡回の概念が可逆ゲートの基礎的要素を生じることを使用する。nビットの可逆論理ごとに、次数2の固有の置換が存在する。したがって、置換群に関するすべての特性及び演算は可逆論理演算を適用または実施する。したがって、例えば制御交換ゲートとしても知られるフレドキンゲート等の他の有用なゲート等すべてのゲートは置換によって定義できる。さらに、n個の入力及びn個の出力を有する可逆ゲートであるマルチプル・コントロール・トフォリ(Multiple Control Toffoli)(MCT)としても知られるnビットのトフォリゲート等、すべてのゲートは、それらがnビット演算を表すことができるという点で一般的である。
したがって置換は可逆論理を模倣するので、任意の可逆ゲートが対応する置換によって表現できることを所与とし、置換の構成を用いて、可逆ゲートまたは可逆ゲートから構成される量子回路によって実行される演算を定義する。したがって任意の量子回路は互いに素な巡回置換の積にすぎず、必然的に互換の積となる。本開示では、全加算器量子回路の原始的な演算の場合、その特定のノウハウが、回路に対応する置換演算子によって量子回路を構築するために必要とされることを示す。単に互換の積を構成する単純な手法は一般的に効率的で単純な計算演算子をQuantonで構築する基礎である。
任意の不可逆関数は、一定入力及び不要データ出力を追加するだけで可逆関数に写像される。しかしながら、一定入力は出力で機能性を実現するために特定の値を有さなければならず、不要データ出力は最終計算に影響を及ぼしてはならない。不可逆関数を可逆関数に変換するために必要とされる不要データ出力の最小数はlog(Q)であり、Qは出力ビットパターンが不可逆関数を表す真理値表で繰り返される回数である。全加算器101の場合、図19に示されるように、出力ビットパターン01及び10が3回繰り返され、発生の最高数を有することは当業者にとって明らかである。したがって、Q=3の場合、全加算器関数を図19に示すように可逆にするためには、少なくともlog2(3)=2回の不要データ出力及び1回の一定入力が必要とされる。
置換表現での計算のための手順
Deleglise、Marc、Nicolas、Jean−Louis、及びZimmermann,Paul「Landau’s function for one million billions.」、Jounral de Theorie des Nombres de Bordeaux 20.3(2008):625〜671の教示を含み、拡張する、置換表現での計算のためのQuantonの設計及び手順が提示される。米国第6256656 B1号に参照される、Carroll Philip Gossett、Nancy Cam Wingetの彼らの特許「Apparatus and method for extending computational precision of a computer system having a modular arithmetic processing unit」の教示における先行技術は、基本的な不可逆コンピュータ演算を計算することを強化するためにモジュラ整数表現をどのように生産的に使用できるのかを示している。モジュラ整数表現の類似した概念の本開示での我々による使用との相違点は、我々は置換演算のための番号付け数列を作成するためにランダウ関数を使用する点、及び図19の102に見られるようにやはり完全に平行化可能である基本的な完全に可逆なコンピュータ演算を計算することを強化することがこれらの置換演算による点である。さらに、置換演算によるこれらの可逆演算は量子計算回路の高速エミュレーションを可能にし、確率モデルと結合されたときに、非常に高速の近似の量子類似計算を、一般的な近似確率的チューリングマシンモデルとして可能にする。
図20Aは、最適性を提供するSの対称群の置換のサイズ及び設計を選ぶ方法のフローチャートを示す。すべてのステップは完全に平行化可能である。本方法は、置換演算子設計の対応する設計とともに結合されるときに、変換する置換が全単射且つ可逆であることを確実にするために変換する置換の操作意味論を提供するランダウ数を使用する。例えば、置換を設計するためにランダウ番号付けを使用することによって、加算演算子は、数がランダウ番号付けの中で適合しなければならない置換間の演算として作成することができる。結果として、Quantonは、設計における移動及び演算の観点から、加算及び減算等のすべての従来の命令を実行することができる。この設計を使用し、Quantonは、最小のチューリングコンピューティングモデルを表すことができる、命令に対する計算のモデルを提供する。
方法のステップ103で、区切りは対称群Sの次元nについて決定される。区切りは正の自然数の合計として決定される。このステップ及び方法の残りのステップを、ハスケルコードで作成された関数を使用して以下に例示する。図20Aに示されるような方法は、対称群Sの置換の部分集合で算術を実行することを可能にする。その目的を達成するために、ランダウ数を使用して、Sの最大巡回部分群の順序に対する理想的な候補を得ることができる。相対的に、及び図20Bに示される方法により説明されるように、巡回群は、部分群の積として分解できるZnと同型である。部分群のこれらの積はそれぞれ順位p を有し、pはnの素因数であり、部分群は、これらの計算を平行化及び高速実行するためにモジュラ演算を使用してこれらの置換を伴う演算をエミュレートするために使用できる。
図20Aの方法を初期化するために、最大整数サイズを設定できる(例えば、最大整数は100に設定できる)。
ステップ103で、ランダウ数は決定された区切りを使用して計算される。ランダウ数は正の自然数の合計としてのnの区切りを使用して計算できる。ランダウ数は区切りの要素の最小公倍数(LCM)を使用して決定できる。ここではLCM(a、b)によって示すことができる2つの整数a及びbの最小公倍数はa及びbの両方によって除算可能である最小の正の整数である。
ステップ103及び104の区切り及びランダウ数は、一例ではハスケルコードで定義できる。また任意の他のプログラミング言語も使用できるだろう。また、以下に関数呼び出し及び関数呼び出しによって生成される出力の例を示す。
例:
図20Aの方法ステップ103で、ジェネレータ及びテンプレートは、nよりも大きいランダウ数を有する第1の区切りを使用して、ランダウ数によって与えられる順位の巡回群に対して定義される。ジェネレータは、ランダウ数がnを超えている第1の区切りを使用する。以下に示すように、ステップ1230のジェネレータ及びテンプレートはコードで定義できる。また、以下に、関数呼び出し及び当該関数呼び出しによって生成される出力の例を示す。
例:
ステップ106で、巡回形式の置換のためにサクセッサ演算子及びプレデセッサ演算子が決定される。巡回形式の置換のためのサクセッサ演算子は右回転として表すことができる。同様に、巡回形式の置換のためのプレデセッサ演算子は左回転として表すことができる。
ステップ107で、自然数と置換との間の変換は巡回形式で決定される。
以下に示すように、ステップ107の自然数と置換との間の変換だけではなく、ステップ106のサクセッサ演算子及びプレデセッサ演算子も例えばコードで定義できる。また、以下に関数呼び出し及び当該関数呼び出しによって生成される出力の例を示す。
例:
また、上記のハスケルコードに含まれるのは、サクセッサ算術計算の定義である。
ステップ108で、巡回形式の置換の軌道はサクセッサ演算子を使用して計算される。以下に示すように、ステップ108の軌道はコードで定義できる。また、関数呼び出し及び当該関数呼び出しによって生成される出力の例を以下に示す。
例:
最終的に、ステップ109で、計算は、古典的計算及びモジュラ演算を使用して、または量子計算フレームワークまたは可逆計算フレームワークで置換演算を使用して、対称群Sの巡回部分群で実行される。
図20Bは、Sの対称群のエミュレーションを使用して置換のサイズ及び設計を選ぶための方法のフローチャートを示す。図20Bに示される方法は、Zが積である各部分群でモジュラ演算が独立して起こるために方法(図20B)がより高速であって平行化できることを除き、図20Aの方法と類似した機能を実行する。
図20Bに示される方法のステップ110で、対称群Sの次元nの区切りを素数積の因数を使用してエミュレートする。このエミュレーションは、Sの巡回部分群の、Zとの同型に基づいている。上述されたように、巡回群は、部分群の積として分解できるZと同型である。部分群のこれらの積はそれぞれ順位P を有し、pはnの素因数であり、部分群は、これらの計算の性能を平行化及び加速するためにモジュラ演算を使用してこれらの置換を伴う演算をエミュレートするために使用できる。
ステップ110の区切り及び素数積はコードで定義できる。また、関数呼び出し及び当該関数呼び出しによって生成される出力の例を以下に示す。
例:
関数「区切り関数」は、素数積の2倍がnを超えるように第1の区切りを返す。
さらに、ステップ111で、ジェネレータ及びテンプレートを巡回群のエミュレーションに対して定義する。ジェネレータ及びテンプレートは、nよりも大きい積により与えられる順位の巡回群用であり、積は素数積の2倍である。以下に示されるように、ステップ111のジェネレータ及びテンプレートはコードで定義できる。また、関数呼び出し及び当該関数呼び出しによって生成される出力の例を以下に示す。
例:
ステップ112で、サクセッサ(z)演算子及びプレデセッサ(z’)演算子を巡回形式の置換のエミュレーションに対して決定する。例えば、置換の巡回の各回転はこれらの部分群で1による対応するモジュール加算に写像できる。以下のハスケルコードでは、関数zはサクセッサを実装し、関数z’はプレデセッサを実装する。
ステップ113で、自然数と置換のエミュレーションとの間の変換を巡回形式で決定する。
以下に示されるように、ステップ112のサクセッサ演算子及びプレデセッサ演算子、ならびにステップ113の自然数と置換のエミュレーションとの間の変換はコードで定義できる。また、関数呼び出し及び当該関数呼び出しにより生成される出力の例を以下に示す。
例:
ステップ114で、巡回形式の置換に対する軌道をサクセッサ演算子を使用して計算する。以下に示されるように、ステップ108(図20A)の軌道はコードで定義できる。また、関数呼び出し及び当該関数呼び出しによって生成される出力の例を以下に示す。
例:
最終的にステップ115で、計算はモジュラ演算としての素数積ベースの近似を使用して、対称群Sの巡回部分群で実行される。
置換を決定するための上記方法は、それぞれ、変換する置換が全単射且つ可逆であることを確実にするために、変換する置換の操作意味論を決定する関数を実行する。しかしながら、サクセッサ関数及びプレデセッサ関数に依存する上述の方法よりむしろ、より高速の変換機構を実現できるかどうかに関する未解決の問題が存在する。答えは肯定であり、より高速の変換機構は、図20Cの方法に示されるように剰余から効率的に数を回復できるようにする中国の剰余定理を使用して実現できる。したがって、モジュラ剰余のリストへの高速変換は、剰余から自然数を回復することによって達成できる。
図20Cを参照すると、ステップ116Aで、自然数は中国の剰余定理を使用して剰余から回復される。以下に示すように、高速変換関数はコードで定義できる。また、関数呼び出し及び当該関数呼び出しによって生成される出力の例を以下に示す。逆数n2zs’が、素数積因数(またはランダウ数同等物)の要素のそれぞれにモジュール関数を適用するだけで剰余のリストを見つけ出すことに留意されたい。
例:
さらに、中国の剰余定理のための拡張されたgcdベースのアルゴリズムはコードで表現できる。
ステップ116Bで、全単射は各巡回を回転するように剰余を写像することによって剰余のリストと置換との間で定義される。上記関数の全単射写像は、巡回形式の実際の置換に拡張できる。これを達成するために、全単射は各巡回を回転するように剰余を写像することによって剰余のリストと置換との間で定義される。以下に示されるように、これはコードで定義することができ、関数zs2cpは剰余のリストに対応する巡回置換を生成し、逆関数zs2cpは巡回置換に対応する剰余のリストを生成する。置換が巡回を有する基準形式をとり、それぞれが[から..への]スライスの回転として表されるという仮定がなされることに留意されたい。また、関数呼び出し及び当該関数呼び出しによって生成される出力の例を以下に示す。
例:
ステップ116Cで全単射を定義する。上記の定義を行い、ここで自然数と巡回形式の置換との間の全単射を表現できる。以下に示されるように、自然数と巡回形式の置換との間の全単射はコードで定義できる。また、関数呼び出し及び当該関数呼び出しによって生成される出力の例を以下に示す。
例:
ステップ116Dで、上述されたより高速の全単射は、多様な算術演算を定義することに適用される。自然数と巡回形式の置換との間のより高速の全単射を使用して、巡回形式の置換に対して多様な算術演算を定義し、及び効率的に実行できる。これらの算術演算は、例えば加算演算及び乗算演算を含むことがある。以下に示されるように、これらの算術演算はコードで定義できる。また、関数呼び出し及び当該関数呼び出しによって生成される出力の例を以下に示す。第1に、高階関数zsOpを定義できる。高階関数は次いで算術演算ごとに特殊化できる。例えば、加算演算及び乗算演算はハスケルコードで定義できる。
例:
次いで、これらの演算は、ハスケルコードで以下に示されるように巡回形式の置換に対して作用するように、同型剰余リストから適用できる。
例:
自然数と巡回形式の置換との間の全単射写像のための上記方法に対する代替策として、辞書順配列された表現を生成する別の方法を使用できる。例えば、図20Dの方法に示されるように、変換器が逆辞書順配列で剰余を列挙するように、辞書順配列された表現への変換器を定義できる。
ステップ116Eで、方法の結果を達成するために、数nから1つの全単射の基数bの桁を抽出する関数を定義する。したがって、「get base number digit」関数は、0とb−1との間の桁の選択をするために消費される情報分だけ、nに記憶される情報を削減する効果的な結果を達成する。相対的に、ステップ116Eは、0からb−1の桁bに記憶される情報をmに追加する結果を達成する関数「put base number digit」も定義する。以下に示されるように、ステップ1410の関数はコードで定義できる。
ステップ116Fで、単一の基数bの代わりに基数bのリストを使用してnからの桁の抽出を反復する基数リストに対する関数を定義する。また、基数リストに対する関数は、正確にbの長さに一致する長さの「ベクトル」が抽出されることを確実にするために、まさに最後のものよりも短い桁のリストの数のスキップによりnをインクリメントする。さらに、ステップ116Fで、基数リストに対する補関数が定義される。この関数は基数リストからそのまま参照することができ、基数リストからの関数は、複数のbによる基数により境界付けられるとすべて仮定される桁のリスト「数リスト」を単一の自然数nに変換することによって上述されたプロセスを逆転する。
所与の基数リストの場合、ステップ116Fの2つの関数が、リストと同じ長さであって基数リストの要素bごとに0とb‐1との間の要素を有するタプルへの全単射を定義する。さらに、これらの関数は(最も右の桁が最上位の)辞書順配列で要素タプルを列挙し、他方、これは、サクセッサを繰り返し適用することによって生じる順位と異なる場合、中国の剰余定理によって与えられる高速変換に一致する。
以下に示されるように、ステップ116Fの関数はコードで定義できる。また、関数呼び出し及び当該関数呼び出しによって生成される出力の例を以下に示す。
例:
置換を最小オービトープとしてQuantonの中に埋め込むための手順
表6(上記参照)による置換の間の遷移関係の置換オービトープは、サイズnのデータについて、nのサイズの階乗のデータ点数を必要とする。メモリ要件の効率を改善するために、データ点の数をnの変数及び制約に削減するバーコフポリトープを使用できるが、これはベクトルとしてまたは本開示に示される巡回形式で置換を表すために使用できるだろうn個の変数よりも依然としてはるかに多い。
しかしながら、Michel X.Goemans、「Smallest compact formulation for the permutahedron」、Mathematical Programming、2015年10月、第153巻、第1号、5〜11ページ、Springer Publishingの最新の教示を結合することによって、簡約表示を作り出すために、フィボナッチ格子の我々による使用と、Advances in Neural Information Processing Systems、第27巻、MIT Press、マサチューセッツ州ケンブリッジ、2014年、2168〜2176ページのC.H.Lim及びS.Wright、Beyond the Birkhoff polytope:「Convex relaxations for vector permutation problems」の中のGoemansに基づいた教示とを結合する。本開示の表現は、n.log(n)置換ベクトルのみがGoemans及びLimらの研究で置換多面体を表す場合にn個の点に対する埋め込みが必要されるように、置換を表すレーマーコードに対する、フィボナッチ格子とそのインデックスとの間の写像を活用することによってさらに削減され、圧縮される。したがって、これはQuantonとしての置換の埋め込みの最小表現を形成する。これは、置換を、好ましい実施形態としてのフィボナッチ格子のインデックスと置換多面体に対するそれらの等価物として表すための、著しくより効率的且つ削減されたメモリ表現である。しかしながら、フィボルッチ写像を所与として、レビューのいくつかの点は整列ネットワークに基づいた順序となり、それは、置換へのそれらの接続がただちに明白にならず、したがってデータ及び可逆回路エミュレーションの表現でのその使用もただちに明白にならないことがあるためである。
図21:ビトニック整列ネットワークの多項式の制約及び実装
任意の整列ネットワークは、項目117において、Goemanに従ってm個のコンパレータにn個の入力を与えられ、項目118において、コンパレータk=1,2,3..mごとに制約の集合を使用して各コンパレータの2つの入力と2つの出力との間の関係性を示すことに基づいて、0(m)の複雑性を有する置換多面体の変数及び制約を表現する。
図22:ビトニック整列ネットワークの演算及び設計
一般的な関係性は、項目120に示されるように、入力と出力との間の置換として見ることができ、一般的な場合、コンパレータ方向がそれ自体置換できるとき、これらは簡単な整列ネットワークまたは、項目121に示される、入力と出力との間の任意の一般的な置換を表すことがある。
図23:ポリトープ設計してのビトニック整列ネットワーク演算
コンパレータの視点からさらに一般化し、任意の次元の視点を取ることによって、概念は項目122に示されるSの並べ替えオービトープに拡張される。係るコンパレータ演算子は、P.S.Phaeendra、C.Vudadha、V.Sreehari、及びM.B.Srinivas、「An Optimized Design of Reversible Quantum Comparator」、2014年、第27回International Conference on VLSI Design及び2014年第13回International Conference on Embedded Systems、ムンバイ、2014年、557〜562ページの教示に示されるように可逆に実装できる。
図24は、ビトニック整列ネットワークを介して見られるブレイドを示す。一実施形態によると、本開示で上記に参照されたStephen Jordanの教示により示される置換量子計算間の関係性は、項目124における置換演算と等価である、項目123におけるブレイドの演算の観点で示される。したがって、これらは、可逆計算がすでに本明細書に提示されている図22、項目122の並べ替えオービトープ設計に直接的に同等である。
図25:置換行列及び置換符号反転行列
Quantonの追加の特性は、値が負から正に及ぶことがある点、及び置換巡回表現が、項目125における置換行列としてのその表現の観点から見ることができる点、及びQuantonでの置換が、該置換が、それらが作用する、項目126で示される入力の符号を変更できる追加特性を有する点である。
図26:置換行列及び置換パターン行列
上述されたように、パーミュトン及びパームトリクスの概念が導入されて、項目127及び128の目的は、行列内の2つの異なるパターンが、パターンを回避または節約するように、パーミュトン及びパームトリクスの合成物である概念を示すことである。項目130によって示されるブロックは、任意のパターン置換演算をどのようにして表すことができるのかをも示す。
図27:点と角度パラメータに対する点でのタンジェントとの関係
この図は、Quantonデータ構造130及び131の例示的な幾何学形状及びトポロジーを示す。要素134は、頂点133の1つに対する接平面である。要素132は、接空間での点の回りの確率分布を示す。
図28:確率密度分布のクラスの幾何学形状
移動の任意のパターンの場合、136に示される経路は分布推定アルゴリズム(EDA)を使用する反復プロセスによって入信データから学習されるのに対し、可逆量子回路を置換回路として表す規則正しいパターンが項目135に示されている。Quantonの場合、学習された経路を記録することは、フィボナッチ格子の点に相当するところにその制御点が記憶されるn次元(例えば、スプラインまたはベジエ曲線)の集合を使用して実行される。
ここで図29:確率密度を有するオービトープに置換を埋め込むことを参照すると、両方の定義された回路、項目137または学習された経路138の組合せは、確率密度経路140の混合として結合できる。フィボナッチ格子139を埋め込むことによって、次いで確率は量子化され、置換(つまり、格子点での状態空間)141に対応して、最終的なQuanton構造142を作り出すことができる。
図29、項目142のQuanton構造を構築する際に、図30のフローチャート、すなわちQuantonデータ構造構築のためのフローチャートが使用される。一般的に、及び上述された表6に続き、超立方体及び一般的なアソシアヘドロンは、本明細書で上記に詳説された手順を使用する好ましい実施形態で置換多面体の簡約表現で表される。したがって、項目143、または144、または145の1つを選ぶと、項目146での置換多面体の表現は147のポリトープに縮小され、並べ替えオービトープは、項目148のGoemansの方法を使用してポリトープから生成される。最後に、フィボナッチ格子を使用して超球の中に埋め込むことは、結果として生じるQuanton構造157を作り出すために項目149で実行される。上記に詳説されるように、訓練データは項目150で提示され、このデータは、項目151に従ってフィルタリングされ、図32、図36、及び図37で後に提示される詳細から得られる項目152に従ってパターンに量子化される。確率密度関数153は上記に定義されるように表5に従って選択され、これは上記図14に示されるプロセスによってQuantonに写像される。この時点でQuantonは分布を学習しており、フィルタ155を使用して、そして必要に応じて欠測データ(部分的にノイズが多いデータが存在している場合)を演繹できる射影アルゴリズム156を使用して、項目154におけるノイズの多いデータに対する各演繹的推論を実行できる。
パターンの仕様を置換として明確にするために、図31:置換行列ゾノトープの頂点の組合せパターンとしての再解釈は、2進行列の場合どのようにしてパターンを二値化できるのかを示す。より高い次元の同等物は行列の代わりにテンソルである。しかしながら、本目的のために、行列は本開示の本質的な方法を示す。例えば、項目158における行列のパターンは、例えば画像平面の白黒ピクセルの3×3集合からなり得る、項目159におけるバイナリパターンに対応する。
すべてのパターンの完全な集合は図32:3置換オービトープパターンのための列挙に示される。パターンのこの集合に対し、各パターンは単に整数として示される置換ベクトルに関連付けられる。したがって、例えば、164は、置換P=(3,1,2)を表す対応する整数312を有する置換の行列を示す。要素160、161、162、163、及び165は他の例を示す。
図33:レーマーインデックスを使用して等級序列付けされたインデックスの3置換オービトープパターンを符号化することの、項目166における各パターンは、階乗番号付けシステムを使用するレーマーコード167に変換される。当業者は、これがインデックスとしてのレーマーコードによるパターンの順序付けを生じさせることをよく知っている。
したがって、選ばれた置換(つまり、この場合、6パターンの3要素置換行列)の分解能で任意の入力をサンプリングするとき、図34:パターンベースのサンプリングによる信号の二値化及び数値符号化を示すこと、に示される順位付けられたパターンインデックスの数列を生じさせるために、任意の信号はなんらかのクロックまたは論理ランポートクロックに関してサンプリングできる。図34の重要な部分は、パターンが、信号ストリームで示される項目168、169、170、及び171におけるように入るときに、これらが行列パターン172に対するインデックスを表し、したがって入力の近似値を最もよく求めるパターンごとのコード173が作成されることに留意することである。したがって、パターンの数による入力信号の圧縮は、置換のサイズ及びサンプリングレートに従って比例して圧縮される。パターンの数列は、ビデオにおけるように経時的に変化する白黒画面でのピクセルとしての代わりに、CPUにおけるようにバイナリコンピュータレジスタの遷移の数列を表すことがあることに留意されたい。
本開示の態様は、図35:球に写像されたパターン、においては例として球をなす多様体の表面においてQuanton178の表面ではゼロノイズであるがQuanton178の重心ではゼロではなく純粋なノイズであるノイズ関数を提供する。つまり、その値がQuantonの表面に正確に位置しない測定は、表面上の最も近い候補点に、ノイズの閾値内で外挿できる。この場合、Quantonは、真の解に対する最善の最も近い仮説を作り出そうとノイズの多いデータ環境で機能している。多様なノイズ関数が使用でき、表面でのゼロから中心での1へとノイズの重み付けを変える簡略なシェパード外挿機能が使用されるユーザー定義選択肢として残されるのが最良である。このようにして、ノイズが多い回路のノイズが多い類似性またはパターンを有するノイズが多い画像をエミュレートすることができ、答えを生じさせるために高速に候補を生成できる。統計的に答えを反復することにより、弱信号バイアスがk回のトライアルにおける成功の頻度を観測するだけで最善の候補を選択すると予想される。最後に、ノイズは、Quanton機械学習プロセスの一体部分として、本開示において後で示されるように分布推定アルゴリズム(EDA)を使用することによって説明できる。
図36:表面が純粋である一方、球の中心でのパターンが混合状態である、は、量子回路が、表面179でのノイズは純粋状態としてのゼロである一方、中心180により近いところでは状態はノイズに似た十分に混合した状態であると説明することを目的としており、この場合、ノイズ関数は、データに関する不確定測定から導入されるある程度のガウシアンノイズを伴って置換的に生成される。ノイズを選ぶための手順は、(分散等の)統計モーメントを選択して、例えばMichael Mascagrni及びHaohai Yu、「Scrambled Sobol Sequences via Permutation」、Monte Carlo Methods and Applications、第15巻、第4号、311〜332ページ、ISSN(オンライン)1569〜3961、ISSN(印刷)0929〜9629、DOI:10.1515/MCMA.2009.017、2010年1月の教示に従い、置換を介して生成されるスクランブルがかけられたSobolシーケンスに加算することである。
全体的な状況は、図37:Quantonに写像されたパターン、に示され、ここでは要素181が、確率分布及びノイズ182とともに表面に写像されたパターン、すなわちQuantonを表す。
より大きい置換がより小さい置換のパターンを含むこと、及びパターンが入れ子の各レベルで確率測度の選択の多様性を提供するためにパターンが入れ子構造の中に分離されるときによりよく関連付けられることに留意されたい。入れ子は、図38:入れ子にされたQuantonを有するQuanton階層構造、に示され、ここでは超球が説明に使用されているが、当該状況は(超トーラス等の)規則正しい多様体の他の選択肢のいずれにも当てはまる。Quanton183及び184の階層または母集団を作成するための洞察及び判断は、Quantonを生成する最善の解を進化させるように分布の推定を使用することである。最低レベルのQuantonは、状態遷移関数に結合されるQuantonに相当し、したがって確率密度関数はより高いレベルでの確率密度関数と比較して異なることがある。世代tのQuanton QはQn(t)と注記され、量子ビット(それぞれRebit)を表す、λ置換状態に対して方向性確率密度を有するオービトープに相当する。したがって、各Quantonは、確率密度関数分布を有する置換として表現される、長さλのビットストリングの分布として見ることができる。モデルの遺伝的進化タイプであるこのモデルでは、Quantonは、確率密度に従って優性表現型である置換を発現させる遺伝子型である。したがって、各Quantonは究極的には所与の入力データ問題に対する解を表す2進列を作り出す。
図39:量子類似計算のためのQuantonに基づいた分布推定アルゴリズム。Quantonの上述のモデルを所与として、次いで分布推定アルゴリズムの変形である確率密度分布の推定を、入力データを所与とする機械学習でQuantonを調整するために適用する。
Quantonの母集団及び階層は量子多重集合に相当する。項目185においてQuanton母集団はm個の部分集合に分割され、項目186においてそれぞれが群あたりn個のQuantonを含み、当該Quaontonはそれらの状態遷移関数を同期させる能力を有する(つまり、全く同じ関数及びパラメータを単に使用することによる)。ステップ187及び188で、分布のQuanton推定は、第1にパート−Aと呼ばれる項目185から191に列挙される母集団進化ステップで与えられ、第2にパートBと呼ばれる項目192から198のステップで個々のQuantonのレベルで与えられる以下の対結合されたやり方で進化する。つまり、この結合された進化の固有の態様は、局所的なQuantonの状態が量子もつれ状態になるまたは大域的な状態と相関することになる点である。EDAアルゴリズムは以下の通り進み、パートA及びパートBは縦一列になって進化する。
項目185から191を参照すると、パートAとして
(1)第1の初期化世代が第2の世代に対して反復され、
(2)あらゆるQuanton Qnは、上記に示された置換表現の方法を使用してデータ入力ストリングAnに関連付けられ、
(3)項目187において、このデータセットを用いて初期の確率分布を構築し、次いで、
(4)項目188において確率分布をサンプリングし、及び、
(5)AnとQnとの間のビットストリングの値を比較して適合性189を求め、
(6)Anが以前の世代よりも優れている場合、及びそれらのビット値が異なる場合、量子ゲート演算子を、上述された置換方法を使用してQnの対応する量子ビットに適用し、
(7)したがって、項目190において、ゲート演算後、分布Qnは全体的解空間の所与の解Anに向かってわずかに移動し、
(8)項目186からのステップは、反復数または適合性のどちらかで閾値に達するときの終端である項目191まで繰り返される。
Quantonの初期セットアップは、X=(Xl,...,Xn)が長さnの置換(それぞれブレイド)を表す場合にX=(Xl,...,Xn)が離散ランダム変数のベクトルを表記することである。変数に対する値の割当てを表記するには(小文字)x=(x1,...,xn)を使用する。最後に、置換として{1,...,n}のインデックスの集合を表記するK、及びKのインデックスによって決定されるX(それぞれx)の変数の部分集合であるXk(それぞれxk)を定義する。したがって、各Xは{0,1,...,2g‐1}の値をとり、ここでgは値に対するジェネレータの数である(及びこれらは訓練データを起源とすることがある)。
ボルツマン確率分布は、確率とシステム状態とをシステム状態のエネルギーに従って関連付けるために統計物理学で使用される。このプロセスは、計算を駆動するために、またはQuantonのための分布の推定の代用物として使用できる。計算を駆動する際に、エネルギーは情報を持ち去り、設計は、パーミュタントが情報源になる一方でパーミュトンが情報シンクの役割を果たすというものである。したがって、Quanton構造はその計算進化モードでボルツマン分布pB(x)を使用し、これによりブレイド(それぞれ置換ゲート)演算子をモデル化し、ブレイドに目標ゲートにより正確な近似を与えるより高い確率を割り当て、このようにして量子ゲート自体をモデル化する。
ボルツマン分布p(x)をQuantonに対して、
と定義する。
ここでは、g(x)は目的関数であり、Tは確率を平滑化するためのシステム温度である。
分布推定アルゴリズムからの最高の確率を有するQuantonは、目的関数を最大化するブレイドに相当する。Quantonは、目標ゲートを表すブレイドに対するジェネレータ行列の積を見つける問題を解いており、以下のようなブレイド長さの目的関数を使用する。
ここでパートBとしての項目192から198を参照すると、
(1)項目192において、本開示の上述された方法を使用して、置換のサイズが変化するQuantonのランダム母集団を構築し、
(2)項目193において、置換を表すオービトープを、個々のQuantonをQuanton母集団の一部として表すようにインスタンス化し、
(3)項目194において、通常置換空間のサイズ未満の選ばれた次元を使用して、置換ベクトルを多様体(例えば、超球または表1の幾何学形状のいずれか)の中に埋め込む。例えば、3要素の置換ベクトル{1,2,3}は通常のユークリッド3空間で点を作り出す。しかし4要素の置換{1,2,3,4}は置換変異体のより高い次元の点を作り出す。したがって、例えば円が埋め込み空間として選ばれる場合、3要素には円の6つの分割、または4要素には円の24の分割があり、隣接関係は、例えば置換における隣接要素の互換であることがある。したがって、埋め込みの空間は置換空間自体と同じサイズである必要はなく、
(4)混合モデル195は、上述された方法により進化及び調整でき、
(5)確率を変更する量子ゲート演算子の作用により調整される確率モデルは、項目196で(ゲート演算として)置換の間で遷移する。古典的な進化的アルゴリズムでは、ビットストリングクロスオーバーまたは変形等の演算子が探索空間を探索するために使用される。一方、これらの演算子に対するQuantonの量子類似物は量子ゲートであり、次いで、
(6)197において適合性が評価される。効果は、局所的なQuantonが、それらが局所状態から大域状態に同期するようになり、集合的に解に向かってより近くに移動するように進化する点であり、最後には、
(7)項目198において、適合性または反復数のどちらかの解閾値が達成される。
最善の最も適合する状態遷移関数をあらゆる世代で記憶し、局所的な同期を表す間欠した間隔で群関数に分散する。次いで、Quantonの群のすべての母集団の集合、つまり合計でn×mのQuantonから、すべてのQuanton多重集合の中の最善の最も適合する推移関数を世代ごとに記憶し、さらに群関数に周期的に分散する。これは事実上大域同期の一段階である。すべてのQuantonは、それらの確率分布が|α|=|β|=1/2に相当して2つの状態「0」及び「1」がバイナリ値の観測論理の場合に同程度の確率となるように、初期母集団で開始する。
Quantonモデルは2量子ビット状態モデルを任意の有限数の状態に一般化する。ここでは情報の最小単位は、n!であるサイズnのタプルで定義されるQuantonであり、考えられる異なるS状態の総数は、その値が量子ビット(量子ビット)に対する類似物である確率ビットの集合の順序付けに関して定義される。
∈{0,1}の場合に、2パターンがあるように状態S={s,s,s,s}とするが、SがQuantonである場合に表される(4)=64の組合せ解集合があり、置換の間の経路はその多様な起源に戻ることがある(つまり、置換はそれ自体に戻る経路を有することがある)。この混合状態確率分布は純粋状態とラベル付与される個別状態αを有する。
Quantonは、以下の通りに、各状態の各確率の全確率保存式に従う。
Quanton母集団は、Quantonの母集団の観点からだけではなく、個々のQuantonでの経路の観点からも確率的に状態の線形重ね合わせの概念を表す。したがって、状態の分布を学習することにおいて、好ましい実施形態のアルゴリズムは、確率モデル遺伝的アルゴリズム(PMBGA)として文献でさまざまに知られてもいる分布推定アルゴリズム(EDA)である。両方の用語とも本開示中区別なく交互に用いられる。
Quantonは、置換での分布によって、及び置換間の確率遷移経路によって表される。これらは、上記に注記されたように量子ビットまたはRebitのストリングに対応し、したがってすべての置換(つまり状態)は単一のQuantonで利用可能であるので、任意の量子ビット(それぞれRebit)は解の線形重ね合わせを表すこともある。可観測に対する真理値が2進である場合に解は2進集合の重ね合わせとなり、そうではなく別の論理が使用される場合、重ね合わせは論理の階数(例えば、3値論理)での解である。
ビットが2つの考えられる状態(0または1)の一方だけしか有さないビットストリングに基づいた従来の遺伝的アルゴリズムは、非常に高いスケールで、次元性の大量の増加、長い収束時間、弱信号混乱、数値不正確、及び複雑なコード等の重大且つ深刻な不利な点を有する。対照的に、個体として及び母集団としてのQuantonはすべての組合せ解の重ね合わせを表す。これは、Quanton/量子表現モデルの自然な一部である一方、Quantonを使用する遺伝的アルゴリズムによって組合せ最適化における多大な効率及び性能の向上を提供する。
ここで図39:分布推定アルゴリズムでのQuantonのためのフローチャートスキーマ、を参照すると、本開示に対する特に重要ないくつかの注釈が整理されている。第1に、分布推定アルゴリズム(EDA)が問題空間へのより良い候補解の確率分布を推定することに基づくタイプの進化モデルであることは当業者に周知である。上述されたように、Quantonは局所的な(Quantonのレベルでの)及び大域的な(Quantonの母集団のレベルでの)進化のタンデムモデルを使用する。したがって、Quantonに基づいたPMBGAの主要ステップは、以下の通りに、基準PMBGA(それぞれEDA)から大幅に分岐する。
(i)Quantonの初期母集団は無作為に生成され、各Quantonは、それ自体、大局確率密度関数とは異なる独自の局所確率密度関数を大域確率密度関数とともに、すなわち混合物を有することができ、
(ii)すべての許容可能な解に亘る一様分布により生成される母集団から開始して、個体群からなる局所的に量子がもつれた部分母集団を、ダイバーシティとの同期を確保するように置換パターン回避制約及び他の強力な相関関係を設定することによって作成できる。
(iii)Quantonを、その母集団だけではなく個別に、母集団の中の個体ごとに、数が高いほどよくなる数値ランクを与える適合度関数に基づいた方法でモデルを使用して採点する。このランク付けされた母集団から、最も見込みがある解の部分集合を選択演算子によって選択する。
(iv)アルゴリズムは次いで、選択された解の確率分布を推定しようと試みる確率モデルを構築する。新しい解(子孫)を、このモデルによって符号化された分布をサンプリングすることによって生成する。これらの新しい解は、次いで古い母集団の中に組み込み直され、場合によっては古い母集団を完全に置き換える。最後に、これらのステップの反復を、予想されるまたは所定の基準に達するまで連続サイクルで繰り返す。このモデルは、量子ゲート演算を使用して無作為選択による個体を入信データに照合して試験するため、量子類似計算をモデル化する通常の進化モデルから逸脱し、したがって個体を無作為プロセスとは対照的に機械学習プロセスから作り出してもよい。
(v)最後に、大部分の実装は、すべての問題変数は独立しているという仮定を主に理由として高速且つ効率的なモデルを提供する確率ベクトルに基づく。Quantonは、変数が独立しておらず(つまり、なんらかの点でもつれ)、古典的な場合にはいくつかの予測できない隠れた変数によって関係付けられるケース(つまり、パーミュトン及びパームトリクス相互関係)だけではなく、このケースも処理できる。
推定された確率モデルは、現在の最善の解を選択することから構築され、サンプルを作り出す際にこれを用いて探索プロセスを誘導するとともに誘導されたモデルを更新する。Quantonが解こうとしている主要なプロセスは、きわめて複雑なデータ空間での変数間の同時確率を取り込むことである。したがって、おもなボトルネックはデータと関連付けられた同時確率分布を推定することにある。
Quantonモデルは、ボトルネックを緩和するために、以下の経験的規則の集合を使用する。
(a)独立分布発見的手法:問題の変数間に依存性はないと仮定する。同時確率分布をn個の独立した一変量の確率分布として因数分解し、H.Muhlenbein、「The equation for response to selection and its use for prediction」、Evolutionary Computation、1977年の教示を使用して、単変量周辺分布アルゴリズム(UMDA)を使用する。同じ発見的手法による他の選択肢は、例えばProceedings of the International Conference on Genetic Algorithm Mendel、1998年のM.Pelikan及びH.Muhlenbein、「Marginal distributions in evolutionary algorithms」等の当業者に対する文献で参照される母集団ベースの増加学習(Population Based Incremental Learning)(PBIL)及びコンパクト遺伝的アルゴリズム(compact genetic algorithm)(cGA)を含む。
(b)対依存性発見的手法:変数の対の間の依存性を仮定する。したがって、変数の同時確率分布は、変数間の置換を所与として、単変量密度関数及び(n‐1)対の条件密度関数の積として因数分解される。例えば、Advances in Soft Computing:Engineering Design and Manufacturing、521〜535ページ、Springer、1999年のM.Pelikan及びH.Muhlenbein「The Bivariate Marginal Distribution Algorithm」、及びRomero、Leoncio A.等「A Comparison between Metaheuristics as Strategies for Minimizing Cyclic Instability in Ambient Intelligence」、Sensors(スイス、バーゼル)12.8(2012年):10990〜11012、PMC、Web、2016年5月5日で参照されるような入力クラスタ化のための相互情報最大化(Mutual Information Maximization for Input Clustering)(MIMIC)、またはS.Baluja及びS.Daviesの教示による相互情報ツリーとの最適化プログラムの結合(Combining Optimizers with Mutual Information Trees)(COMIT)アルゴリズム。複数の最適化の結合は、最適依存性ツリーを用いて動作する。Technical Report CMU−CS−97−157。
(c)多重依存性:複数の変数間の依存性(強力な相関またはエンタングルメント)を仮定する。この場合、本開示による局所的及び大域的なQuanton進化及び母集団進化は、好ましい実施形態の1つである。
多重依存性の場合、Quantonは他の方法に優る特別の優位点及び多項式効率を有する。Quantonの根本にあるのは、通常クエリーレジスタ、|q>、及びヒルベルト空間に作用する回答レジスタ、|a>から構成される量子システムの概念である。
Quantonでは、クエリーレジスタ及び回答レジスタはともに、特定の問題インスタンスの変数に対して考えられる値が変数に対する値の割当ての置換の空間に存在するn量子ビットレジスタである。例えば、NP完了に既知であるSAT問題は、通常、多重柔軟性を有する。簡単な古典的な計算に優るQuanton量子効率は、|q>が、初期化n量子ビット状態|0>に合計n回のアダマール変換Hを適用することにより計算基底の一様な重ね合わせで配置される点である。つまり、
これは、指数関数的な数の状態の重ね合わせを生じ、それぞれはQuantonで考えられる経路を表すが、Quantonの置換表現に起因して多項式数のゲートだけを利用する。単一の量子ビットは、状態|0>に初期化され、これが回答レジスタである。システムの状態は以下の通りである。
これから、クエリー式及び回答式を以下の通り導出できる。
そして、エンタングルメントを以下として表し、
が各純粋状態|Ψ>のアンサンブルの分数である
として定義される密度行列を所与とすると、
単純に以下として書かれる。
そして、回答は
である。
したがって、kに解の総数を示させ、次いで
は以下の式に示される形式をとる。
総合的な状態は、k=0、つまり解が存在しないときだけ、またはk=2nであり、[0,2‐1]に属する各値が解であるときに分離可能である。それ以外の場合、システムはもつれている。したがって、問題に対する解が存在するかどうかを判断する問題は、状態が分離可能であるのか、それとももつれているのかを判断する問題に還元できる。状態がもつれているかどうかを判断するために、以下の決定方程式が使用され、
これは
に対して補助関数を利用する。
このプロセスは量子レジスタをもつれさせ、補助関数を使用して、エンタングルメントを所与の範囲について解の状態の存在下で確認できる。対照的に、解の不在は、特定の範囲が探索手順から除去されることを意味する。
図40:システムオンチップ(SOC)のためのQuantonのハードウェア設計
上述の情報が与えられると、Quantonはさらに、量子ハードウェアがいつ利用可能になるかに関わらず、古典的ハードウェアと量子ハードウェアとの両方での実装に適する。古典的ハードウェアでの実施形態では、項目99のデータサンプラは、項目Gの確率分布を使用してプロセッサへの供給を行う。項目200において、プロセッサは、GPU(グラフィックスプロセッシングユニットコプロセッサ)またはDSP(デジタル信号処理)装置のどちらかを使用して事後確率分布を計算する。これを、信号符号化のために上述された圧縮された符号化を使用して、加算器及びバッファとして動作して項目202の最終出力コードを生じさせるレーマーコード「リバイザ(reviser)」項目201の形をとる量子ゲートの置換表現と結合する。
図41:Quanton PMBGAコンセンサス出力の全体的なマスタフローチャート
Quantonの母集団は、項目204から211まで、異なる進化的方法に従って進化することができ、これらは項目203における親Quantonの確率密度分布を学習する分布のメタヒューリスティック推定器としての機能を果たす。このようにして、非常に複雑なパターンまたは時間イベントを、所与のドメインでの問題解決におけるリコール及び使用に向けて、、または他のドメインでの解に対する類似物として、項目212では確率のコンセンサス(つまり混合モデル)として、単一のマスタQuantonにおいて学習し、記憶できる。
したがって、上記説明は、本発明の単に例示的な実施形態を開示し、説明する。当業者によって理解されるように、本発明はその精神または必須特徴から逸脱することなく、他の特定の形式で実施されてよい。したがって、本発明の開示は、他の請求の範囲と同様に、例示的であって本発明の範囲を限定するものではないことが意図される。本開示は、任意の容易に識別可能な本明細書の教示の変形を含み、発明の主題が公知のものに特定されないように、先行する請求の範囲の用語の範囲を部分的に定義する。
本開示の特徴は、なんらかの形のコンピュータプロセッサを使用して実装できる。上述されたように、上述された実施形態の機能のそれぞれは1つまたは複数の処理回路によって実装されてよい。プロセッサが回路を含むように、処理回路は、プログラムされたプロセッサ(例えば、図42のプロセッサ1004)を含む。また、処理回路は、特定用途向け集積回路(ASIC)及び列挙されている機能を実行するように配置された従来の回路構成要素等の装置も含む。回路は、回路の処理を改善し、データを人間、またはさらには本実施形態の特徴を欠いた汎用コンピュータによって可能ではない方法で処理できるようにする、上述の機能及び特徴を実装するように特に設計またはプログラムされてよい。
本実施形態は、回路を有するデジタル計算装置で量子計算をエミュレートできる、または量子コンピュータ等で実装できる。
当業者であれば認識するように、コンピュータプロセッサは、特定用途向け集積回路(ASIC)、フィールドプログラマブルゲートアレイ(FPGA)、または他の結合プログラム可能論理回路(CPLD)のようにディスクリートの論理ゲートとして実装できる。FPGAまたはCPLDの実装は、VHDL、Verilog、または任意の他のハードウェア記述言語でコード化されてよく、コードはFPGAまたはCPLD内で直接的に電子メモリに、または別個の電子メモリに記憶されてよい。さらに、電子メモリは、ROM、EPROM、EEPROM、またはFLASHメモリ等、不揮発性であってよい。また、電子メモリは、スタティックRAMまたはダイナミックRAM等の揮発性であってよく、マイクロコントローラまたはマイクロプロセッサ等のプロセッサは、FPGAまたはCPLDと電子メモリとの間の対話だけではなく電子メモリも管理するように提供されてよい。
代わりに、コンピュータプロセッサは、本明細書に説明される機能を実行するコンピュータ可読命令の集合を含むコンピュータプログラムを実行してよく、プログラムは上述された非一過性電子メモリ及び/またはハードディスクドライブ、CD、DVD、FLASHドライブもしくは任意の他の既知のストレージメディアのいずれかに記憶されている。さらに、コンピュータ可読命令は、アメリカのIntelのXenonプロセッサ、またはアメリカのAMDのOpteronプロセッサ等のプロセッサ、ならびにMicrosoft VISTA、UNIX、Solaris、LINUX、Apple、MAC−OSX、及び当業者にとって既知の他のオペレーティングシステム等のオペレーティングシステムと連動して実行しているユーティリティアプリケーション、バックグラウンドデーモン、またはオペレーティングシステムの構成要素、またはその組合せとして提供されてよい。ONE CPUマシン上でも、それは置換符号化のために「並行して」動作する。
さらに、本発明は、図42に示されるコンピュータベースのシステム1000を使用して実装できる。コンピュータ1000は、情報を通信するためのバスBまたは他の通信機構、及び情報を処理するためにバスBと結合されるプロセッサ/CPU1004を含む。また、コンピュータ1000は、プロセッサ/CPU1004によって実行される情報及び命令を記憶するためにバスBに結合された、ランダムアクセスメモリ(RAM)または他の動的記憶装置(例えば、ダイナミックRAM(DRAM)、スタティックRAM(SRAM)、及び同期DRAM(SDRAM))等のメインメモリ/メモリユニット1003も含む。さらに、メモリ装置1003は、CPU1004による命令の実行中に一時変数または他の中間情報を記憶するために使用されてよい。また、コンピュータ1000はさらに、CPU1004のために静的情報及び命令を記憶するためにバスBに結合される、読出し専用メモリ(ROM)または他の静的記憶装置(例えば、プログラマブルROM(PROM)、消去可能PROM(EPROM)、及び電気的消去可能PROM(EEPROM))をさらに含んでよい。
また、コンピュータ1000は、例えば大量記憶装置1002等の情報及び命令を記憶する1つまたは複数の記憶装置を制御するようにバスBに結合されたディスクコントローラ、及び駆動装置1006(例えば、フロッピーディスクドライブ、読取り専用コンパクトディスクドライブ、読書きコンパクトディスクドライブ、コンパクトディスクジュークボックス、テープドライブ、及び取外し自在の光磁気ドライブ)を含んでもよい。記憶装置は、適切なデバイスインタフェース(例えば、小型コンピュータシステムインタフェース(SCSI)、統合デバイスエレクトロニクス(IDE)、拡張IDE(E−IDE)、ダイレクトメモリアクセス(DMA)、または超DMA)を使用してコンピュータ1000に追加されてよい。
また、コンピュータ1000は専用論理装置(例えば、特定用途向け集積回路(ASIC))または構成可能な論理装置(例えば、単純プログラム可能論理デバイス(SPLD)、結合プログラム可能論理回路(CPLD)、及びフィールドプログラマブルゲートアレイ(FPGA))も含んでよい。
また、コンピュータ1000は、コンピュータユーザーに情報を表示するために、陰極線管(CRT)等のディスプレイを制御するようにバスBに結合されたディスプレイ制御装置を含んでもよい。コンピュータシステムは、コンピュータユーザーと対話し、情報をプロセッサに提供するために、キーボード及びポインティングデバイス等の入力装置を含む。ポインティングデバイスは、方向情報及びコマンド選択をプロセッサに通信するため、及びディスプレイ上のカーソルの移動を制御するための、例えばマウス、トラックボール、またはポインティングスティックであってよい。さらに、プリンタはコンピュータシステムによって記憶及び/または生成されたデータの印刷されたリストを提供してよい。
コンピュータ1000は、CPU1004がメモリ装置1003等のメモリに含まれる1つまたは複数の命令の1つまたは複数のシーケンスを実行することに応答して、本発明の処理ステップの少なくとも一部を実行する。係る命令は、例えば大容量記憶装置1002またはリムーバブルメディア1001等の別のコンピュータ可読媒体からメモリ装置の中に読み込まれてよい。また、マルチプロセッシング構成をなす1つまたは複数のプロセッサを利用して、メモリ装置1003に含まれる命令のシーケンスを実行してもよい。代替実施形態では、ハードワイヤード回路網を、ソフトウェア命令の代わりにまたはソフトウェア命令と組み合わせて使用してよい。したがって、実施形態は、ハードウェア回路網及びソフトウェアの任意の特定の組合せに限定されない。
上述されたように、コンピュータ1000は、本発明の教示に従ってプログラムされた命令を保持するために、及び本明細書に説明されるデータ構造、テーブル、レコード、または他のデータを含むために少なくとも1つのコンピュータ可読媒体1001またはメモリを含む。コンピュータ可読媒体の例はコンパクトディスク、ハードディスク、フロッピーディスク、テープ、光磁気ディスク、PROM(EPROM、EEPROM、フラッシュEPROM)、DRAM、SRAM、SDRAM、または任意の他の磁気媒体、コンパクトディスク(例えば、CD−ROM)、またはコンピュータが読み取ることができる任意の他の媒体である。
コンピュータ可読媒体の任意の1つ上または組合せ上に記憶され、本発明は、メイン処理装置を制御し、本発明を実施するための1つまたは複数の装置を駆動し、及びメイン処理ユニットが人間のユーザーと対話できるようにするソフトウェアを含む。係るソフトウェアは、デバイスドライバ、オペレーティングシステム、開発ツール、及びアプリケーションソフトウェアを含んでよいが、これに限定されるものではない。係るコンピュータ可読媒体はさらに、(処理が分散される場合)本発明を実施する上で実行される処理のすべてまたは一部を実行するために本発明のコンピュータプログラム製品を含む。
本発明の媒体上でのコンピュータコード要素は、スクリプト、解釈可能なプログラム、ダイナミックリンクライブラリ(DLL)、Javaクラス、及び完全実行可能プログラムを含むが、これに限定されるものではない任意の解釈可能または実行可能なコード機構であってよい。さらに、本発明の処理の部分はより優れた性能、信頼性、及び/またはコストのために分散されてよい。
本明細書に使用される用語「コンピュータ可読媒体」は、実行のためにCPU1004に命令を提供することに関与する任意の媒体を指す。コンピュータ可読媒体は多くの形式をとってよく、不揮発性媒体、及び揮発性媒体を含むが、これに限定されるものではない。不揮発性媒体は、例えば、大容量記憶装置1002またはリムーバブルメディア1001等の光ディスク、磁気ディスク、及び光磁気ディスクを含む。揮発性媒体は、メモリユニット1003等のダイナミックメモリを含む。
多様な形式のコンピュータ可読媒体は実行に供されるCPU1004への1つまたは複数の命令の1つまたは複数のシーケンスを実行することに関与してよい。例えば、命令は当初リモートコンピュータの磁気ディスク上に保持されてよい。バスBに結合された入力はデータを受け取り、バスBにデータを格納することができる。バスBはデータをメモリユニット1003に搬送し、CPU1004はメモリユニット1003から命令を取り出し、実行する。メモリユニット1003によって受け取られた命令は、任意選択で、CPU1004による実行の前または後のどちらかに大容量記憶装置1002に記憶されてよい。
また、コンピュータ1000は、バスBに結合された通信インタフェース1005を含む。通信インタフェース1004は、例えばローカルエリアネットワーク(LAN)にまたはインターネット等の別の通信ネットワークに接続されるネットワークに結合する双方向データ通信を提供する。例えば、通信インタフェース1005は、任意のパケット交換方式のLANに取り付けるネットワークインタフェースカードであってよい。別の例として、通信インタフェース1005は、データ通信接続を対応するタイプの通信回線に提供する非対称デジタル加入者線(ADSL)カード、総合デジタル通信網(ISDN)カード、またはモデムであってよい。また、無線リンクも実装されてよい。任意の係る実装では、通信インタフェース1005は、多様なタイプの情報を表すデジタルデータストリームを搬送する電気信号、電磁信号、または光信号を送受する。
ネットワークは、通常、データ通信を1つまたは複数のネットワークを通して他のデータ装置に提供する。例えば、ネットワークは、ローカルネットワーク(例えばLAN)を通して、または通信ネットワークを通して通信サービスを提供するサービスプロバイダによって運用される設備を通して、別のコンピュータに接続を提供してよい。ローカルネットワーク及び通信ネットワークは、例えば、デジタルデータストリームを搬送する電気信号、電磁信号、または光信号、及び関連付けられた物理層(例えば、CAT5ケーブル、同軸ケーブル、光ファイバ等)を使用する。さらに、ネットワークは、パーソナルデジタルアシスタント(PDA)ラップトップコンピュータ、またはセルラー電話等のモバイル機器に接続を提供して良く、コンピュータ1000はパーソナルデジタルアシスタント(PDA)ラップトップコンピュータ、またはセルラー電話等のモバイル機器であってよい。
要約すれば、量子の方法及び装置は、Quantonと呼ばれる、量子触発計算データ表現及びアルゴリズムを使用する。Quantonは、Quantonに対して作用して、学習または推測を実行して結果を生じさせるための混合状態表現及びアルゴリズムの代用物である。Quantonは、確率密度関数と、連続空間を量子化する格子と、各格子インデックスにおいて状態空間を表す置換符号化とを選ぶことによって、古典類似挙動と量子類似挙動との間で等級分けすることができる特性を有する、架空の、仮想の(例えば音量子)または現実の(例えば原子の)物理的粒子のための符号化として使用できる。
Quantonは、例えばボレル正規実数の実数の二進展開によって量子複素空間を表すための上述されたPalmerによって提案されている置換モデル等の、任意の数の桁及び場所に作用する自己相似置換演算子の任意の集合によって定義できる。
実施形態を説明するために、フィボナッチ格子及び単純な互換置換演算子を使用して置換を生成することとする。単純な確率密度関数、フォンミーゼスビンガム分布を使用することとし、フィボナッチ格子に割り当てる。置換に関連付けられるフィボナッチ格子の点は合わせて置換ポリトープを表す。したがって、このポリトープを、格子及びその埋め込まれた置換によって量子化されたリーマン球の役割を果たす超球の中に埋め込む。
その粒度(つまり量子化)の結果として、確率密度分布の値は、(低次元置換の場合)超球または球に埋め込まれたポリトープの頂点の可算集合に対して一意に定義可能であるようにのみ定義される。置換演算子は、球の回転の下で確率密度値の変換を定義できる置換演算子表現を記述子、または、逆に、確率密度を表すベクトル空間の演算は、本開示にさらに説明されるように置換が任意のデータ構造及びモデルを符号化できることを表す置換結果を生じさせる。置換演算子表現、及び自然数としての置換符号化による任意のデータの表現を使用して、建設的な量子類似確率バーチャルマシンが定義される。
標準的な量子理論と同様に、Quanton置換演算子は標準的な量子論の波動関数の複雑な位相関数の確率性を符号化するように作用することができる。例えば、S2で、四元数置換はPalmerに注記されるように波動関数の空間エンタングルメント関係性を符号化できる。より高い次元で、ロータの一般的な幾何学的代数がこの形式論を拡張する。Quantonは頂点の上で確率密度の値の有限サンプルを提供し、頂点集合は、Palmerのモデルが使用される(ref[])場合、量子論的確率及び相関と一貫性のある確率測度を定義するためにも使用できる。
その頂点をベースにした確率密度の観点からのQuantonの量子化は、ベル不等式の達成を必要とせず、したがって真の量子−バーチャルマシンと対照的に、Quantonを「量子触発」近似確率バーチャルマシンにするQuantonバーチャルマシンを説明する。しかしながら、標準的な量子現象はQuantonによってエミュレートされる。この点で、Quantonの2つの重要な特性は、量子類似状態準備が確率密度(または混合モデル)の選択に対応する点、及び置換演算子が測定角度及び相関を、(機械学習EDAを介してまたは直接的な準備によって符号化されたように)頻度主義またはベイズ主義によって引き出すことができる観測状態空間(つまり、モデル状態空間)の粒度を定義するのに役立つ点である。
時間ドメイン及び空間ドメインは、データセットがパラメータとして時間を必要とするときに動態を符号化する、量子触発手法として使用される時間領域密度汎関数法(TDDFT)を使用することによって結合できる。TDDFTは、古典的なコンピュータで、及びQunatonモデルを用いて量子アルゴリズムを近似的にシミュレーションするために使用することができ、これは経時的にクラスタ化または推測のためにも使用できる。複雑性クラスQMA(Quantum Merlin Arthur)プロトコルにあり、現実の量子コンピュータの上でも指数関数的にスケーリングするリソースを必要とすることがある近似汎関数等の近似汎関数を使用してシミュレーションするのが非常に困難であるシステムがある[http://arxiv.org/abs/0712.0483]。
複雑な量子計算タスクを実施する汎関数を見つけることはきわめて困難であり、本開示は、問題の指定された範囲内で計算的に有用である汎関数を生じさせるように、分布推定アルゴリズム(EDA)に基づいて非常に固有の方法でいくつかの個別要素を結合することによって量子類似計算の近似値を求める古典近似を提供する。問題の範囲により、その規模またはサイズまたは複雑性を意味し、アプリケーションのドメインの中に制約される(つまり汎用計算の代わりに、専用計算を意味する)。
指定されたスケールは、置換のサイズ、またはQuantonによって表される構造の深さによって決定される。したがって、スケール内では、Quantonは高速で計算するが、置換スケールが小さすぎる場合、計算は指数関数的サイズまたは階乗サイズに縮退して戻る。したがって、必要とされるQuantonのサイズを推定することは、Quanton自体の量子化限度を、置換ポリトープの頂点の球面分布のための基礎として機能を果たす球状のフィボナッチ格子の隣接格子点間の距離の関数として推定することになる。
効果的なデータ構造符号化は、多くの他の根本的に困難な最適化問題だけではなく、例えば、分布アルゴリズム及び粒子群アルゴリズムの古典的推定と量子的推定の両方でアルゴリズム加速を可能にする際の主要な理由である。不十分なデータ構造は、実施すべきハック及び次善策を解が必要とすることを暗示している。
Quantonは一連の埋め込みを利用する。言い換えると、Quantonは、データのための表現としての機能を果たす確率粒子にプレコンパイルされる、階乗的に大きいデータ空間とn次元多様体との間で(通常行われるように)空間を速度と交換することなく、部分的に組合せの複雑性を評価し、したがって組合せの複雑性をコンパイルアウトする。
Quantonデータ符号化は、重ね合わせの状態に対して完全な同時確率密度を表すためにエンタングルメント及び重ね合わせの概念を利用し、すべての推論軌跡を同時に近似する(例えば、マルコフチェインモンテカルロ(MCMC))−いずれの現在の純粋に古典的なデータ符号化モデルでも可能ではない妙技。単一の粒子としての単一のQuantonデータ符号化は、大量の情報を符号化することができ、多数の係るQuanton符号化がより複雑な表現データ代用物のための量子粒子アンサンブルを形成する。
より複雑なデータ表現代用物の例として、例えば事例ベース推論(CBR)では、動的ケースメモリは、機械学習が、事例一致及び事例適応プロセスの両方の固有の部分である推論プロセスに必須である。現実世界の応用例では、たとえ状況が、困難な音声対音声機械翻訳の問題等の、知識が乏しい浅い事例集合から構成されていても、ビッグデータは高次元事例ベクトルの構造化されていない集合として到着し、メモリベースのまたはインスタンスベースの推論及び学習を必要とする。Quantonデータ符号化を使用する我々の手法では、事例インデックス付け問題には、事例を表す置換に対する確率密度の分布を通して内蔵の量子触発並行性を使用することによって一致が効率的に実行できるモデル化レベルで対処する。
Quantonは、それが「バックドア」と呼ばれてきたものを提供するので、最善の古典的な手法に対する二次加速、指数関数的加速、及び階乗加速を用いて非常に高速で実行できる推測手順の量子代用物を実装することを可能にする。Quantonバックドアは、連続多様体での埋め込みと、多様体と同じ多様体に対する接空間確率との間のその埋め込まれた確率密度との間に形成される接続である。これらは総問題空間を基準にしたスパースな数の点である。バックドアは高い組合せの複雑性を抜けるショートカットのように作用するため、バックドアは非常に高次元のデータ空間に劇的に影響を与え、データ空間を管理可能なレベルまで下げることができるスパースな数のパラメータである。したがって、Quantonは連続確率密度汎関数と構造との間にバックドアを設けることによってPによりNPの近似値を求める包括的な方法を可能にするため、Quantonデータ構造の使用の対象となる典型的な目標は、NP困難な問題を攻撃することにある。
一例は、置換に対する推測、計算行列パーマネント、及び連続配列問題だけではなく、(ベイズ)グラフィックモデルでのNP困難な最大事前確率(MAP)推測である。データ構造を使用して提示されるアルゴリズムは、古典的な加速を超える二次加速を有する近似MAP構成を迅速に見つけ出すことができ、置換に対する推測への近似推測を見つけ出すことができ、近似の近いパーマネントを計算し、これらのNP困難な問題のそれぞれに対して、古典的な方法が正確な解を選択できるように、近似候補の中からノイズが多い連続配列問題に対する解の近似値を迅速に求めることができる。
方向データのための複素正規分布、ケント、ガウシアン、ビンガム、ワトソン、ディリクレプロセス混合モデルまたはフォンミーゼスフィッシャー分布またはその多変量バージョンのいずれか1つまたは混合物は扱いやすい形式を示し、Quantonにとって必要とされるすべてのモデル化機能を有する。
本発明は、期待値最大化(EM)設定でパラメータの数値近似を提供する超球上の分布の混合物の生殖モデルを使用する。また、本実施形態は、分布視点から正しい埋め込み次元を選ぶことだけではなく、スペクトルクラスタ化のために正しい埋め込み次元を選ぶことに対する説明も提示できるようにする。しかしながら、テキスト解析論では、及びクラスタ化のために関係する文書間でセマンティックス(コンテンツ構造)を表すために、トピックは概念に対する置換として表現できる。置換に対する分布を学習するために、汎用マローズモデル(GMM)は、基準置換に近い置換に確率質量を集中させ、したがってこの分布からの置換は類似する可能性があり、このようにして類似する文書をクラスタ化する。GMMモデルで、パラメータ数は概念数とともに線形に伸び、このようにして通常置換の大きい離散空間と関連付けられた扱いやすさの問題を回避する。
特定の実施形態が説明されてきたが、これらの実施形態はほんの一例として示されており、本発明の範囲を限定することを目的としていない。実際に、本明細書に説明される新規な方法及びシステムは、多種多様の他の形で実施されてよい。さらに、本明細書に説明される方法及びシステムの形の多様な省略、置換、及び変更は、発明の精神から逸脱することなく行われてもよい。添付の特許請求の範囲及びその均等物は、本発明の範囲及び精神の範囲内となるだろう係る形式または修正形態をカバーすることを目的とする。

Claims (1)

  1. 量子類似マシンをエミュレートする方法であって、前記方法は回路によって実行され、
    ランダウ数に基づいた問題サイズに適合する最大置換群のサイズを決定することと、
    高次元空間において閉じた幾何学的面を生成することであって、前記閉じた幾何学的面が前記最大置換群の前記サイズに対応する、前記閉じた幾何学的面を生成することと、
    前記閉じた幾何学的面に頂点の格子を埋め込むことと、
    それぞれの置換を前記格子の対応する頂点に割り当てることと、
    線形接空間を前記格子の前記それぞれの頂点に関連付けることと、
    前記格子の前記頂点のそれぞれの置換の間の遷移演算子を量子ゲート演算と対応するように関連付けることと、
    置換を計算の代用物として関連付けることと、
    前記閉じた幾何学面全体に亘って非線形方向性確率分布関数を分布させることであって、前記非線形方向性確率分布関数が対応する前記遷移演算子のそれぞれの尤度を表す、前記非線形方向性確率分布関数を分布させることと、
    前記遷移演算子の前記尤度を修正するように前記非線形方向性確率分布関数を更新し、それによって量子ゲートのエミュレーションを生成することと、
    を含む、前記方法。
JP2017557330A 2015-05-05 2016-05-05 古典的なプロセッサで量子類似計算をエミュレートするためのquanton表現 Expired - Fee Related JP6989387B2 (ja)

Applications Claiming Priority (3)

Application Number Priority Date Filing Date Title
US201562156955P 2015-05-05 2015-05-05
US62/156,955 2015-05-05
PCT/US2016/031034 WO2016179419A1 (en) 2015-05-05 2016-05-05 Quanton representation for emulating quantum-like computation on classical processors

Publications (2)

Publication Number Publication Date
JP2018521382A true JP2018521382A (ja) 2018-08-02
JP6989387B2 JP6989387B2 (ja) 2022-01-05

Family

ID=57218374

Family Applications (1)

Application Number Title Priority Date Filing Date
JP2017557330A Expired - Fee Related JP6989387B2 (ja) 2015-05-05 2016-05-05 古典的なプロセッサで量子類似計算をエミュレートするためのquanton表現

Country Status (8)

Country Link
US (2) US10452989B2 (ja)
EP (1) EP3292466A4 (ja)
JP (1) JP6989387B2 (ja)
KR (1) KR102141274B1 (ja)
CN (1) CN107683460B (ja)
AU (2) AU2016258029A1 (ja)
CA (1) CA2983880A1 (ja)
WO (1) WO2016179419A1 (ja)

Cited By (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2020202265A1 (ja) * 2019-03-29 2020-10-08 株式会社ニコン 決定方法、決定装置、露光装置およびプログラム
JP2022519004A (ja) * 2018-11-19 2022-03-18 キューエムウェア アーゲー ハイブリッド型量子コンピュータを含むシステム及び方法、量子情報技術の態様並びに/又は他の特徴
JP2022537311A (ja) * 2019-06-21 2022-08-25 ベイト インク. 量子コンピュータをエミュレートするためのシステム及び該システムに使用するための方法
WO2022269712A1 (ja) 2021-06-21 2022-12-29 富士通株式会社 複数量子ビットオブザーバブルのパーティショニング方法、複数量子ビットオブザーバブルのパーティショニングプログラム、および情報処理装置
JP2023507745A (ja) * 2019-12-18 2023-02-27 ウニヴェルシダッド ポリテクニカ デ バレンシア 量子フィールドプログラマブルフォトニックゲートアレイ、集積フォトニック及び量子デバイス、並びにプログラマブル回路

Families Citing this family (204)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US9881256B2 (en) * 2014-08-22 2018-01-30 D-Wave Systems Inc. Systems and methods for problem solving, useful for example in quantum computing
US10387784B2 (en) * 2014-12-10 2019-08-20 Kyndi, Inc. Technical and semantic signal processing in large, unstructured data fields
US11797641B2 (en) 2015-02-03 2023-10-24 1Qb Information Technologies Inc. Method and system for solving the lagrangian dual of a constrained binary quadratic programming problem using a quantum annealer
CA2881033C (en) 2015-02-03 2016-03-15 1Qb Information Technologies Inc. Method and system for solving lagrangian dual of a constrained binary quadratic programming problem
GB2554554B (en) * 2015-03-09 2021-08-25 Mosca Michele Quantum circuit synthesis using deterministic walks
CN107683460B (zh) * 2015-05-05 2022-01-28 凯恩迪股份有限公司 在传统处理器上模拟量子样计算的quanton表示
US10860759B2 (en) * 2015-06-08 2020-12-08 Microsoft Technology Licensing, Llc System for reversible circuit compilation with space constraint, method and program
US10664249B2 (en) 2015-11-20 2020-05-26 Microsoft Technology Licensing, Llc Verified compilation of reversible circuits
US10481866B2 (en) * 2015-12-31 2019-11-19 Cbn Nano Technologies Inc. Mechanical computing systems
US10817796B2 (en) * 2016-03-07 2020-10-27 D-Wave Systems Inc. Systems and methods for machine learning
EP3427196B1 (en) 2016-03-11 2021-12-22 1QB Information Technologies Inc. Methods and systems for quantum computing
US10044638B2 (en) * 2016-05-26 2018-08-07 1Qb Information Technologies Inc. Methods and systems for quantum computing
US9870273B2 (en) 2016-06-13 2018-01-16 1Qb Information Technologies Inc. Methods and systems for quantum ready and quantum enabled computations
CN109716360B (zh) 2016-06-08 2023-08-15 D-波系统公司 用于量子计算的系统和方法
US10082539B2 (en) * 2016-06-28 2018-09-25 International Business Machines Corporation Using direct sums and invariance groups to test partially symmetric quantum-logic circuits
US20180046933A1 (en) * 2016-08-11 2018-02-15 Board Of Regents, The University Of Texas System System and method for controlling a quantum computing emulation device
US11205103B2 (en) 2016-12-09 2021-12-21 The Research Foundation for the State University Semisupervised autoencoder for sentiment analysis
US11263547B2 (en) 2017-01-30 2022-03-01 D-Wave Systems Inc. Quantum annealing debugging systems and methods
US10902346B2 (en) * 2017-03-28 2021-01-26 International Business Machines Corporation Efficient semi-supervised concept organization accelerated via an inequality process
US11026634B2 (en) 2017-04-05 2021-06-08 doc.ai incorporated Image-based system and method for predicting physiological parameters
US10831787B2 (en) * 2017-06-30 2020-11-10 Sap Se Security of a computer system
AU2018300240B2 (en) 2017-07-13 2023-06-08 California Institute Of Technology Neutral atom quantum information processor
JP6889865B2 (ja) * 2017-09-22 2021-06-18 オムロン株式会社 テンプレート作成装置、物体認識処理装置、テンプレート作成方法及びプログラム
US11250190B2 (en) * 2017-09-22 2022-02-15 International Business Machines Corporation Simulating quantum circuits
US10614371B2 (en) 2017-09-29 2020-04-07 International Business Machines Corporation Debugging quantum circuits by circuit rewriting
US10885678B2 (en) * 2017-09-29 2021-01-05 International Business Machines Corporation Facilitating quantum tomography
US20190138924A1 (en) * 2017-10-10 2019-05-09 Olaf Cames Quantum mechanical propabilistic apparatus to measure, forecast, visualize humanoid mental statuses
US10783298B2 (en) * 2017-10-13 2020-09-22 Bank Of America Corporation Computer architecture for emulating a binary correlithm object logic gate
US10783297B2 (en) * 2017-10-13 2020-09-22 Bank Of America Corporation Computer architecture for emulating a unary correlithm object logic gate
US11170137B1 (en) * 2017-11-15 2021-11-09 Amazon Technologies, Inc. Cloud-based simulation of quantum computing resources
US10853106B2 (en) * 2017-11-28 2020-12-01 Bank Of America Corporation Computer architecture for emulating digital delay nodes in a correlithm object processing system
JP7288905B2 (ja) 2017-12-01 2023-06-08 1キュービー インフォメーション テクノロジーズ インコーポレイテッド ロバスト推定問題の確率的最適化のためのシステムおよび方法
US11586915B2 (en) 2017-12-14 2023-02-21 D-Wave Systems Inc. Systems and methods for collaborative filtering with variational autoencoders
JP6968342B2 (ja) * 2017-12-25 2021-11-17 オムロン株式会社 物体認識処理装置、物体認識処理方法及びプログラム
CN108320027B (zh) * 2017-12-29 2022-05-13 国网河南省电力公司信息通信公司 一种基于量子计算的大数据处理方法
US10157226B1 (en) * 2018-01-16 2018-12-18 Accenture Global Solutions Limited Predicting links in knowledge graphs using ontological knowledge
US10877979B2 (en) 2018-01-16 2020-12-29 Accenture Global Solutions Limited Determining explanations for predicted links in knowledge graphs
US10878482B2 (en) 2018-01-19 2020-12-29 Hypernet Labs, Inc. Decentralized recommendations using distributed average consensus
US11244243B2 (en) 2018-01-19 2022-02-08 Hypernet Labs, Inc. Coordinated learning using distributed average consensus
US10909150B2 (en) 2018-01-19 2021-02-02 Hypernet Labs, Inc. Decentralized latent semantic index using distributed average consensus
US10942783B2 (en) 2018-01-19 2021-03-09 Hypernet Labs, Inc. Distributed computing using distributed average consensus
WO2019144046A1 (en) * 2018-01-19 2019-07-25 Hyperdyne, Inc. Distributed high performance computing using distributed average consensus
US11100418B2 (en) 2018-02-28 2021-08-24 D-Wave Systems Inc. Error reduction and, or, correction in analog computing including quantum processor-based computing
US11334693B1 (en) * 2018-03-07 2022-05-17 Keysight Technologies Canada Inc. Systems and methods for optimizing quantum computers
CN108595532A (zh) * 2018-04-02 2018-09-28 三峡大学 一种法律文本的量子聚类系统及方法
US11100417B2 (en) 2018-05-08 2021-08-24 International Business Machines Corporation Simulating quantum circuits on a computer using hierarchical storage
CN108683497B (zh) * 2018-05-11 2021-01-26 南京师范大学 多维空间码的构成装置
KR102100368B1 (ko) * 2018-05-17 2020-04-14 한국과학기술원 양자 데이터베이스를 위한 효과적 양자 메모리 구조
US10664761B2 (en) * 2018-05-25 2020-05-26 Microsoft Technology Licensing, Llc Generating quantum computing circuits by distributing approximation errors in a quantum algorithm
US11295223B2 (en) 2018-06-12 2022-04-05 International Business Machines Corporation Quantum feature kernel estimation using an alternating two layer quantum circuit
CN108984849B (zh) * 2018-06-21 2023-12-22 深圳万知达科技有限公司 一种基于量子叠加态的量子比较器设计方法
US11593707B2 (en) 2018-07-02 2023-02-28 Zapata Computing, Inc. Compressed unsupervised quantum state preparation with quantum autoencoders
CN109164702B (zh) * 2018-07-26 2021-09-14 西北工业大学 一种自适应多变量广义超螺旋方法
WO2020037300A1 (en) * 2018-08-17 2020-02-20 Zapata Computing, Inc. Quantum computer with exact compression of quantum states
WO2020047444A1 (en) 2018-08-31 2020-03-05 President And Fellows Of Harvard College Quantum computing for combinatorial optimization problems using programmable atom arrays
CN112119466B (zh) * 2018-09-03 2024-03-22 松下知识产权经营株式会社 电子密度推定方法、电子密度推定装置及电子密度推定程序
US20200097879A1 (en) * 2018-09-25 2020-03-26 Oracle International Corporation Techniques for automatic opportunity evaluation and action recommendation engine
US11467803B2 (en) 2019-09-13 2022-10-11 Oracle International Corporation Identifying regulator and driver signals in data systems
DE102018124146A1 (de) * 2018-09-29 2020-04-02 Trumpf Werkzeugmaschinen Gmbh + Co. Kg Schachteln von werkstücken für schneidprozesse einer flachbettwerkzeugmaschine
US11526793B2 (en) * 2018-10-04 2022-12-13 Intel Corporation Quantum state imaging for memory optimization
WO2020072981A1 (en) * 2018-10-05 2020-04-09 President And Fellows Of Harvard College Quantum convolutional neural networks
WO2020077288A1 (en) * 2018-10-12 2020-04-16 Zapata Computing, Inc. Quantum computer with improved continuous quantum generator
US11354460B2 (en) 2018-10-16 2022-06-07 Red Hat, Inc. Validator and optimizer for quantum computing simulator
WO2020086867A1 (en) 2018-10-24 2020-04-30 Zapata Computing, Inc. Hybrid quantum-classical computer system for implementing and optimizing quantum boltzmann machines
WO2020086362A2 (en) * 2018-10-25 2020-04-30 James Tagg Relativistic quantum computer / quantum gravity computer
US20200134503A1 (en) * 2018-10-31 2020-04-30 Black Brane Systems Inc. Quantum computing system and method
CA3117223A1 (en) 2018-11-21 2020-05-28 Zapata Computing, Inc. Hybrid quantum-classical computer for packing bits into qubits for quantum optimization algorithms
US11194642B2 (en) 2018-11-29 2021-12-07 International Business Machines Corporation Noise and calibration adaptive compilation of quantum programs
CN109583111A (zh) * 2018-12-05 2019-04-05 中国航空工业集团公司西安飞行自动控制研究所 一种基于任意型混沌多项式的加速度计不确定性分析方法
WO2020113339A1 (en) 2018-12-06 2020-06-11 1Qb Information Technologies Inc. Artificial intelligence-driven quantum computing
US11764940B2 (en) 2019-01-10 2023-09-19 Duality Technologies, Inc. Secure search of secret data in a semi-trusted environment using homomorphic encryption
JP7535049B2 (ja) * 2019-01-17 2024-08-15 ディー-ウェイブ システムズ インコーポレイテッド クラスタ収縮を使用するハイブリッドアルゴリズムのためのシステム及び方法
JP7425755B2 (ja) * 2019-02-07 2024-01-31 株式会社Preferred Networks 変換方法、訓練装置及び推論装置
CN113454657B (zh) * 2019-02-08 2025-08-22 国际商业机器公司 量子电路布置
US11900264B2 (en) * 2019-02-08 2024-02-13 D-Wave Systems Inc. Systems and methods for hybrid quantum-classical computing
US11625612B2 (en) 2019-02-12 2023-04-11 D-Wave Systems Inc. Systems and methods for domain adaptation
US11918336B2 (en) * 2019-02-19 2024-03-05 King Abdullah University Of Science And Technology Reduced feature generation for signal classification based on position weight matrix
WO2020172588A1 (en) 2019-02-22 2020-08-27 President And Fellows Of Harvard College Large-scale uniform optical focus array generation with a phase spatial light modulator
CN120223905A (zh) * 2019-02-28 2025-06-27 松下电器(美国)知识产权公司 编码方法、解码方法、编码装置及解码装置
CN109858628B (zh) * 2019-02-28 2021-04-27 北京百度网讯科技有限公司 编译量子电路的方法、装置、设备和计算机可读存储介质
US11853891B2 (en) 2019-03-11 2023-12-26 Sharecare AI, Inc. System and method with federated learning model for medical research applications
EP3938898A4 (en) * 2019-03-13 2023-03-29 Cognizant Technology Solutions U.S. Corporation SYSTEM AND METHOD FOR IMPLEMENTING MODULAR UNIVERSAL REPARAMETIZATION FOR MULTI-TASK DEEP LEARNING ACROSS DIVERSE DOMAINS
US11645620B2 (en) * 2019-03-15 2023-05-09 Tecnotree Technologies, Inc. Framework for explainability with recourse of black-box trained classifiers and assessment of fairness and robustness of black-box trained classifiers
EP3948692A4 (en) 2019-03-27 2023-03-29 Cognizant Technology Solutions U.S. Corporation METHOD AND SYSTEM USING AN OPTIMIZATION MACHINE WITH EVOLUTIONARY SURROGATE ASSESSED TARGETS
WO2020205624A1 (en) * 2019-03-29 2020-10-08 Google Llc Oblivious carry runway registers for performing piecewise additions
CN110135584B (zh) * 2019-03-30 2022-11-18 华南理工大学 基于自适应并行遗传算法的大规模符号回归方法及系统
US11372895B2 (en) 2019-04-01 2022-06-28 International Business Machines Corporation Sketching using a hybrid quantum-classical system
US11574560B2 (en) 2019-04-16 2023-02-07 International Business Machines Corporation Quantum state visualization device
US10637480B1 (en) 2019-04-25 2020-04-28 International Business Machines Corporation Multi-control quantum state inversion gate
EP3966750A1 (en) * 2019-05-06 2022-03-16 Verint Americas Inc. Systems and methods for combining model interpreters
EP3970083B1 (en) 2019-05-17 2024-04-24 President and Fellows of Harvard College System and method for multiplexed optical addressing of atomic memories
WO2020236255A1 (en) * 2019-05-23 2020-11-26 The Trustees Of Princeton University System and method for incremental learning using a grow-and-prune paradigm with neural networks
CN110233732B (zh) * 2019-05-24 2021-07-02 西北大学 一种基于簇态的动态量子代理盲签名方法
US11615329B2 (en) 2019-06-14 2023-03-28 Zapata Computing, Inc. Hybrid quantum-classical computer for Bayesian inference with engineered likelihood functions for robust amplitude estimation
CA3126553A1 (en) 2019-06-19 2020-12-24 1Qb Information Technologies Inc. Method and system for mapping a dataset from a hilbert space of a given dimension to a hilbert space of a different dimension
CN110298124B (zh) * 2019-07-03 2020-10-27 江南大学 一种基于滤波的工业控制系统执行器参数估计方法
WO2021007560A1 (en) 2019-07-11 2021-01-14 President And Fellows Of Harvard College System and method for parallel implementation of multi-qubit quantum gates
CN110414150B (zh) * 2019-07-30 2021-06-22 四川省公路规划勘察设计研究院有限公司 一种桥梁时变系统的张量子空间连续系统识别方法
EP4007980A4 (en) * 2019-08-01 2023-06-28 Zapata Computing, Inc. Quantum system and method for solving bayesian phase estimation problems
US11915802B2 (en) 2019-08-05 2024-02-27 Sharecare AI, Inc. Accelerated processing of genomic data and streamlined visualization of genomic insights
US12475393B2 (en) 2019-08-12 2025-11-18 International Business Machines Corporation Qubit sensory representation
GB2593413A (en) * 2019-08-12 2021-09-29 River Lane Res Ltd Simultaneous measurement of commuting operators
US20210073648A1 (en) * 2019-09-10 2021-03-11 AI Therapeutics, Inc. Techniques for semi-supervised training and associated applications
US11440194B2 (en) * 2019-09-13 2022-09-13 Honda Motor Co., Ltd. Physical human-robot interaction (pHRI)
US20210089862A1 (en) * 2019-09-23 2021-03-25 Samsung Electronics Co., Ltd. Method and apparatus with neural network data processing and/or training
CA3151055C (en) 2019-09-27 2022-08-30 Pierre-luc DALLAIRE-DEMERS Computer systems and methods for computing the ground state of a fermi-hubbard hamiltonian
US11526790B2 (en) 2019-09-27 2022-12-13 Oracle International Corporation Univariate anomaly detection in a sensor network
US11060885B2 (en) * 2019-09-30 2021-07-13 Oracle International Corporation Univariate anomaly detection in a sensor network
CN110825375B (zh) * 2019-10-12 2022-12-06 合肥本源量子计算科技有限责任公司 一种量子程序的转化方法、装置、存储介质和电子装置
US11605033B2 (en) 2019-11-27 2023-03-14 Amazon Technologies, Inc. Quantum computing task translation supporting multiple quantum computing technologies
WO2021108510A1 (en) * 2019-11-27 2021-06-03 Amazon Technologies, Inc. Quantum computing service supporting multiple quantum computing technologies
US11704715B2 (en) 2019-11-27 2023-07-18 Amazon Technologies, Inc. Quantum computing service supporting multiple quantum computing technologies
US11605016B2 (en) 2019-11-27 2023-03-14 Amazon Technologies, Inc. Quantum computing service supporting local execution of hybrid algorithms
US12051005B2 (en) 2019-12-03 2024-07-30 1Qb Information Technologies Inc. System and method for enabling an access to a physics-inspired computer and to a physics-inspired computer simulator
US20210173855A1 (en) * 2019-12-10 2021-06-10 Here Global B.V. Method, apparatus, and computer program product for dynamic population estimation
CN113128015B (zh) * 2019-12-31 2023-04-07 合肥本源量子计算科技有限责任公司 预估单振幅模拟量子计算所需资源的方法和系统
JP7259774B2 (ja) * 2020-01-15 2023-04-18 Jfeスチール株式会社 配送計画作成方法、及び配送計画作成装置
CN113222156B (zh) * 2020-01-21 2023-08-08 本源量子计算科技(合肥)股份有限公司 一种待执行操作的量子模拟方法、装置
CN113222153B (zh) * 2020-01-21 2023-08-08 本源量子计算科技(合肥)股份有限公司 一种量子态的模拟方法、装置、存储介质和电子装置
CA3167402A1 (en) 2020-02-13 2021-08-19 Yudong CAO Hybrid quantum-classical adversarial generator
US11216247B2 (en) 2020-03-02 2022-01-04 Oracle International Corporation Automatic asset anomaly detection in a multi-sensor network
US11188317B2 (en) 2020-03-10 2021-11-30 International Business Machines Corporation Classical artificial intelligence (AI) and probability based code infusion
US11747902B2 (en) 2020-03-11 2023-09-05 Apple Inc. Machine learning configurations modeled using contextual categorical labels for biosignals
CN111401562B (zh) * 2020-03-11 2023-12-15 本源量子计算科技(合肥)股份有限公司 一种终端界面中量子线路的运行方法及装置
US20210287773A1 (en) * 2020-03-13 2021-09-16 HypaHub, Inc. Hybrid computational system of classical and quantum computing for drug discovery and methods
US12072979B2 (en) 2020-03-19 2024-08-27 Peter Andrew Blemel Apparatus and application device for protection of data and information
CA3174231A1 (en) 2020-03-30 2021-10-07 Psiquantum, Corp. Encoded fusion measurements with local adaptivity
EP4128083A4 (en) * 2020-04-03 2024-04-03 The University of British Columbia METHOD FOR SIMULATING A QUANTUM COMPUTING, SYSTEM FOR SIMULATING A QUANTUM COMPUTING, METHOD FOR ISSUE OF A CALCULATION KEY, SYSTEM FOR ISSUE OF A CALCULATION KEY
US12099934B2 (en) * 2020-04-07 2024-09-24 Cognizant Technology Solutions U.S. Corporation Framework for interactive exploration, evaluation, and improvement of AI-generated solutions
US11177960B2 (en) 2020-04-21 2021-11-16 Sharecare AI, Inc. Systems and methods to verify identity of an authenticated user using a digital health passport
US12481907B2 (en) 2020-04-24 2025-11-25 Alibaba Group Holding Limited Methods and systems for tensor network contraction based on hypergraph decomposition and parameter optimization
US11681914B2 (en) * 2020-05-08 2023-06-20 International Business Machines Corporation Determining multivariate time series data dependencies
WO2021237350A1 (en) 2020-05-27 2021-12-02 1Qb Information Technologies Inc. Methods and systems for solving an optimization problem using a flexible modular approach
EP4158554A4 (en) 2020-06-02 2024-06-26 Zapata Computing, Inc. PERFORMING ROTATIONS CONTROLLED BY A BASIC INPUT STATE FUNCTION OF A QUANTUM COMPUTER
US11775841B2 (en) 2020-06-15 2023-10-03 Cognizant Technology Solutions U.S. Corporation Process and system including explainable prescriptions through surrogate-assisted evolution
CN111709252B (zh) * 2020-06-17 2023-03-28 北京百度网讯科技有限公司 基于预训练的语义模型的模型改进方法及装置
CN111813934B (zh) * 2020-06-22 2024-04-30 贵州大学 一种基于dma模型和特征划分多源文本主题模型聚类方法
US12424335B2 (en) 2020-07-08 2025-09-23 Cognizant Technology Solutions U.S. Corporation AI based optimized decision making for epidemiological modeling
EP4182857A2 (en) * 2020-07-15 2023-05-24 Google LLC Generative modeling of quantum hardware
CN114064812B (zh) * 2020-07-31 2025-09-05 中移(苏州)软件技术有限公司 一种数据处理方法、装置、设备及计算机可读存储介质
CN112527190B (zh) * 2020-09-11 2022-05-10 苏州浪潮智能科技有限公司 一种量子数据擦除的方法、系统、设备及可读存储介质
US12045743B2 (en) * 2020-09-24 2024-07-23 Microsoft Technology Licensing, Llc Mixing techniques for probabilistic quantum circuits with fallback
CN112215272A (zh) * 2020-09-29 2021-01-12 重庆大学 一种基于贝塞尔曲线的图像分类神经网络攻击方法
EP3975073B1 (en) * 2020-09-29 2024-02-28 Terra Quantum AG Hybrid quantum computation architecture for solving quadratic unconstrained binary optimization problems
KR102854188B1 (ko) * 2020-10-14 2025-09-04 텐센트 테크놀로지(센젠) 컴퍼니 리미티드 양자 회로 결정 방법 및 장치, 디바이스, 및 저장 매체
US12067458B2 (en) 2020-10-20 2024-08-20 Zapata Computing, Inc. Parameter initialization on quantum computers through domain decomposition
US12039012B2 (en) 2020-10-23 2024-07-16 Sharecare AI, Inc. Systems and methods for heterogeneous federated transfer learning
CN112446305B (zh) * 2020-11-10 2025-05-27 云南联合视觉科技有限公司 一种基于分类权重等距分布损失模型的行人重识别方法
CN112329380B (zh) * 2020-11-12 2024-01-19 南通大学 一种用于可逆电路优化的可逆门等价变换方法
EP4006753A1 (en) 2020-11-27 2022-06-01 Prisma Analytics GmbH Creating bias-free and self-predictive parameters
EP4006752A1 (en) 2020-11-27 2022-06-01 Prisma Analytics GmbH Method and system arrangement for processing big data
US11409940B2 (en) 2020-12-16 2022-08-09 International Business Machines Corporation Virtual to real waveform emulator
CN112651183A (zh) * 2021-01-19 2021-04-13 广西大学 一种量子分布式对抗统一深度哈希网络的可靠性评估方法
US11762956B2 (en) 2021-02-05 2023-09-19 Oracle International Corporation Adaptive pattern recognition for a sensor network
US11550580B2 (en) * 2021-02-24 2023-01-10 Northrop Grumman Systems Corporation Systems and methods for emulating a processor
CN114764619B (zh) * 2021-04-29 2023-08-08 本源量子计算科技(合肥)股份有限公司 一种基于量子线路的卷积操作方法及装置
CN112947908B (zh) * 2021-02-26 2024-09-13 上海商汤智能科技有限公司 代码生成方法、装置、设备及存储介质
US20230036827A1 (en) * 2021-03-02 2023-02-02 Cambridge Quantum Computing Limited Quantum computing system and method
GB202103338D0 (en) * 2021-03-10 2021-04-21 Cambridge Quantum Computing Ltd Control system and method utilizing variational inference
US12086567B1 (en) * 2021-03-14 2024-09-10 Jesse Forrest Fabian Computation system using a spherical arrangement of gates
CN113033703B (zh) * 2021-04-21 2021-10-26 北京百度网讯科技有限公司 量子神经网络训练方法及装置、电子设备和介质
CN113238224A (zh) * 2021-04-26 2021-08-10 中国人民解放军国防科技大学 一种基于量子机器学习的雷达稀疏成像方法
WO2023287487A2 (en) * 2021-05-21 2023-01-19 Arizona Board Of Regents On Behalf Of The University Of Arizona Processing signals using entanglement-assisted communication
CN115438790B (zh) * 2021-06-04 2024-05-07 本源量子计算科技(合肥)股份有限公司 量子态信息处理系统、量子测控系统、量子计算机
US12437216B2 (en) 2021-07-06 2025-10-07 International Business Machines Corporation Combined classical/quantum predictor evaluation
US12412106B2 (en) 2021-07-06 2025-09-09 International Business Machines Corporation Identifying related messages in a natural language interaction in multiple iterations
US12468977B2 (en) 2021-07-16 2025-11-11 International Business Machines Corporation Uncertainty aware parameter provision for a variational quantum algorithm
US11941484B2 (en) 2021-08-04 2024-03-26 Zapata Computing, Inc. Generating non-classical measurements on devices with parameterized time evolution
KR102789248B1 (ko) * 2021-08-06 2025-03-28 고려대학교 산학협력단 최솟값을 탐색하기 위한 방법
US11972290B2 (en) 2021-08-12 2024-04-30 International Business Machines Corporation Time management for enhanced quantum circuit operation employing a hybrid classical/quantum system
US12061952B2 (en) 2021-08-24 2024-08-13 International Business Machines Corporation Combined classical/quantum predictor evaluation with model accuracy adjustment
US12001920B2 (en) 2021-08-30 2024-06-04 Red Hat, Inc. Generating a global snapshot of a quantum computing device
CN114061583B (zh) * 2021-10-21 2023-07-07 郑州轻工业大学 基于自适应晶格卡尔曼滤波的移动机器人状态估计及自主导航方法
US12216996B2 (en) * 2021-11-02 2025-02-04 International Business Machines Corporation Reasonable language model learning for text generation from a knowledge graph
US11907092B2 (en) 2021-11-12 2024-02-20 Amazon Technologies, Inc. Quantum computing monitoring system
US12217090B2 (en) 2021-11-12 2025-02-04 Amazon Technologies, Inc. On-demand co-processing resources for quantum computing
WO2023094005A1 (en) 2021-11-27 2023-06-01 Zoe Life Technologies Ag Hardware based evaluation of unformatted data
CN114239464B (zh) * 2021-12-17 2023-08-11 深圳国微福芯技术有限公司 基于贝叶斯筛选器与重采样的电路的良率预测方法及系统
CN116415685B (zh) * 2021-12-30 2025-07-15 本源量子计算科技(合肥)股份有限公司 含噪声机器学习模型创建方法、机器学习框架及相关设备
US12524496B2 (en) 2022-01-24 2026-01-13 Bank Of America Corporation Dynamic access control using machine learning
CN114492813B (zh) * 2022-01-26 2022-12-27 北京百度网讯科技有限公司 量子电路处理方法、电路、计算设备、装置及存储介质
US20230306433A1 (en) * 2022-03-24 2023-09-28 Bank Of America Corporation Cognitive Identification of Credit Reporting Disputes and Dispute Resolution Using Quantum Computing
CN114648611B (zh) * 2022-04-12 2023-07-18 清华大学 局域轨道函数的三维重构方法及装置
CN114997060B (zh) * 2022-06-10 2025-07-01 湖南大学 一种声子晶体时变可靠性测试方法、计算设备及存储介质
US20230401470A1 (en) * 2022-06-14 2023-12-14 Microsoft Technology Licensing, Llc Combined table lookup at quantum computing device
CN115186566B (zh) * 2022-06-30 2025-12-05 哈尔滨工业大学 一种不同入射粒子能量效应智能预测方法及系统
CN115238788A (zh) * 2022-07-21 2022-10-25 大连理工大学 一种工业大数据的分类方法、系统、服务器及存储介质
US11687799B1 (en) * 2022-07-28 2023-06-27 Intuit, Inc. Integrated machine learning and rules platform for improved accuracy and root cause analysis
CN116821214B (zh) * 2022-09-01 2025-08-26 中移(苏州)软件技术有限公司 一种数据处理方法和装置,及存储介质
US12328578B2 (en) 2022-11-08 2025-06-10 Wistron Corporation Quantum service authorization management for securitizing 5G network slicing
US20240265195A1 (en) * 2023-02-07 2024-08-08 Multiverse Computing S.L. Method and System for Modifying Document Without Changing Hash Value
CN116175566B (zh) * 2023-02-10 2025-12-12 上海电气集团股份有限公司 机器人运动学参数误差的补偿方法、系统、设备和介质
CN116306875B (zh) * 2023-05-18 2023-08-01 成都理工大学 基于空间预学习与拟合的排水管网样本增量学习方法
US20240419998A1 (en) * 2023-06-16 2024-12-19 J4 Capital LLC Stochastic learning of computing inputs
CN116832423A (zh) * 2023-07-25 2023-10-03 本源量子计算科技(合肥)股份有限公司 一种量子卡牌游戏系统
CN116894271B (zh) * 2023-08-04 2024-04-26 中国医学科学院医学信息研究所 一种基于匿名化算法的数据共享隐私保护方法
CN117391208B (zh) * 2023-10-13 2024-12-20 北京百度网讯科技有限公司 用于量子线路的测量模拟方法、装置、设备以及存储介质
CN117556915B (zh) * 2024-01-10 2024-05-07 量子科技长三角产业创新中心 一种量子费舍信息的测量方法、装置、设备及存储介质
CN117556916B (zh) * 2024-01-12 2024-03-22 深圳量旋科技有限公司 Sn2反应路径模拟方法和装置、存储介质、量子计算设备
CN117689966B (zh) * 2024-02-04 2024-05-24 中国科学院深圳先进技术研究院 一种基于量子贝叶斯神经网络的磁共振图像分类方法
CN119171923B (zh) * 2024-09-04 2025-04-04 武汉瑞斯通信科技有限公司 超表面阵列的干扰抑制方法、电子设备及通信系统
CN119379534B (zh) * 2024-11-11 2025-11-18 中国科学技术大学 图像形状变形方法、装置、设备、介质和程序产品
CN119813162B (zh) * 2024-12-10 2025-10-31 电子科技大学 一种基于量子遗传算法优化分布式电源位置和容量的配电系统功率损耗最小化方法
CN119537624B (zh) * 2025-01-22 2025-04-11 潍坊学院 基于球面哈希的图文跨模态检索方法、设备和存储介质

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2005535025A (ja) * 2002-07-31 2005-11-17 ヤマハ発動機株式会社 量子ソフト演算に基づくインテリジェントメカトロニクス制御サスペンションシステム
JP2006268840A (ja) * 2005-03-21 2006-10-05 Microsoft Corp 組み込まれた1次元多様体経路に沿ったアイテムの自動レイアウト
US20120303574A1 (en) * 2008-06-18 2012-11-29 Reneses Ajenjo Ignacio Method for solving optimization problems in structured combinatorial objects

Family Cites Families (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR100350233B1 (ko) * 2000-03-27 2002-08-27 한국과학기술원 양자 연산 개념을 도입한 진화연산방법
US7849121B2 (en) * 2006-04-20 2010-12-07 Hewlett-Packard Development Company, L.P. Optical-based, self-authenticating quantum random number generators
JP5296189B2 (ja) * 2008-03-24 2013-09-25 ディー−ウェイブ システムズ,インコーポレイテッド アナログ処理用のシステム、装置、および方法
CN107683460B (zh) * 2015-05-05 2022-01-28 凯恩迪股份有限公司 在传统处理器上模拟量子样计算的quanton表示

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2005535025A (ja) * 2002-07-31 2005-11-17 ヤマハ発動機株式会社 量子ソフト演算に基づくインテリジェントメカトロニクス制御サスペンションシステム
JP2006268840A (ja) * 2005-03-21 2006-10-05 Microsoft Corp 組み込まれた1次元多様体経路に沿ったアイテムの自動レイアウト
US20120303574A1 (en) * 2008-06-18 2012-11-29 Reneses Ajenjo Ignacio Method for solving optimization problems in structured combinatorial objects

Cited By (13)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP7387191B2 (ja) 2018-11-19 2023-11-28 キューエムウェア アーゲー ハイブリッド型量子コンピュータを含むシステム
JP2022519004A (ja) * 2018-11-19 2022-03-18 キューエムウェア アーゲー ハイブリッド型量子コンピュータを含むシステム及び方法、量子情報技術の態様並びに/又は他の特徴
US12154004B2 (en) 2018-11-19 2024-11-26 QMware AG Systems and methods involving hybrid quantum machines, aspects of quantum information technology and/or other features
US11699092B2 (en) 2018-11-19 2023-07-11 QMware AG Systems and methods involving hybrid quantum machines, aspects of quantum information technology and/or other features
JPWO2020202265A1 (ja) * 2019-03-29 2020-10-08
JP7184166B2 (ja) 2019-03-29 2022-12-06 株式会社ニコン 決定方法、決定装置、露光装置およびプログラム
US11972325B2 (en) 2019-03-29 2024-04-30 Nikon Corporation Determination method, determination device, exposure device, and program
WO2020202265A1 (ja) * 2019-03-29 2020-10-08 株式会社ニコン 決定方法、決定装置、露光装置およびプログラム
JP7452885B2 (ja) 2019-06-21 2024-03-19 ベイト インク. 量子コンピュータをエミュレートするためのシステム及び該システムに使用するための方法
JP2022537311A (ja) * 2019-06-21 2022-08-25 ベイト インク. 量子コンピュータをエミュレートするためのシステム及び該システムに使用するための方法
JP2023507745A (ja) * 2019-12-18 2023-02-27 ウニヴェルシダッド ポリテクニカ デ バレンシア 量子フィールドプログラマブルフォトニックゲートアレイ、集積フォトニック及び量子デバイス、並びにプログラマブル回路
JP7777529B2 (ja) 2019-12-18 2025-11-28 ウニヴェルシダッド ポリテクニカ デ バレンシア 量子フィールドプログラマブルフォトニックゲートアレイ、集積フォトニック及び量子デバイス、並びにプログラマブル回路
WO2022269712A1 (ja) 2021-06-21 2022-12-29 富士通株式会社 複数量子ビットオブザーバブルのパーティショニング方法、複数量子ビットオブザーバブルのパーティショニングプログラム、および情報処理装置

Also Published As

Publication number Publication date
AU2019257544C1 (en) 2022-03-03
CN107683460A (zh) 2018-02-09
EP3292466A1 (en) 2018-03-14
US10452989B2 (en) 2019-10-22
WO2016179419A1 (en) 2016-11-10
AU2016258029A1 (en) 2017-11-16
KR20180004226A (ko) 2018-01-10
US20200250566A1 (en) 2020-08-06
JP6989387B2 (ja) 2022-01-05
AU2019257544B2 (en) 2021-11-04
US11205135B2 (en) 2021-12-21
CA2983880A1 (en) 2016-11-10
EP3292466A4 (en) 2019-01-02
CN107683460B (zh) 2022-01-28
KR102141274B1 (ko) 2020-08-04
US20160328253A1 (en) 2016-11-10
AU2019257544A1 (en) 2019-11-28

Similar Documents

Publication Publication Date Title
JP6989387B2 (ja) 古典的なプロセッサで量子類似計算をエミュレートするためのquanton表現
Zhang et al. A survey on graph diffusion models: Generative ai in science for molecule, protein and material
You et al. Graphrnn: Generating realistic graphs with deep auto-regressive models
Huynh et al. Quantum-inspired machine learning: a survey
CN107533553B (zh) 认知存储器图形索引、存储和检索
Bhatia et al. blockcluster: An R package for model-based co-clustering
Wall et al. Generative machine learning with tensor networks: Benchmarks on near-term quantum computers
Sarkar et al. An algorithm for DNA read alignment on quantum accelerators
Au-Yeung et al. Quantum algorithms for scientific computing
Joshi et al. InvNet: encoding geometric and statistical invariances in deep generative models
Maksymov et al. Optimal calibration of gates in trapped-ion quantum computers
Schrodi et al. Construction of hierarchical neural architecture search spaces based on context-free grammars
Aly et al. Hybrid butterfly-grey Wolf optimization (HB-GWO): A novel metaheuristic approach for feature selection in high-dimensional data
Hu et al. Labeling of human motion based on CBGA and probabilistic model
Bjerregaard et al. Riemannian generative decoder
Li et al. Efficient training of large vision models via advanced automated progressive learning
Plant et al. Data compression as a comprehensive framework for graph drawing and representation learning
Zhu et al. Structural landmarking and interaction modelling: a “slim” network for graph classification
Gkirtzou et al. The pyramid quantized Weisfeiler–Lehman graph representation
XU Quantum Machine Learning: Diverse Perspectives on Application Scenarios
Joseph et al. Advancing Quantum Machine Learning: From Theoretical Concepts to Experimental Implementations
Singh et al. Image Classification Method using Dynamic Quantum Inspired Genetic Algorithm
Łazarz Semantic analysis of multidimensional graph descriptors with applications for structural data mining
WO2023226310A1 (zh) 一种分子优化方法以及装置
Ye Automating Model Design with Meta-optimization

Legal Events

Date Code Title Description
A529 Written submission of copy of amendment under article 34 pct

Free format text: JAPANESE INTERMEDIATE CODE: A529

Effective date: 20171213

A621 Written request for application examination

Free format text: JAPANESE INTERMEDIATE CODE: A621

Effective date: 20190426

A977 Report on retrieval

Free format text: JAPANESE INTERMEDIATE CODE: A971007

Effective date: 20200423

A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20200512

A601 Written request for extension of time

Free format text: JAPANESE INTERMEDIATE CODE: A601

Effective date: 20200812

A521 Request for written amendment filed

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20201007

A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20210330

A601 Written request for extension of time

Free format text: JAPANESE INTERMEDIATE CODE: A601

Effective date: 20210610

A521 Request for written amendment filed

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20210927

TRDD Decision of grant or rejection written
A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

Effective date: 20211105

A61 First payment of annual fees (during grant procedure)

Free format text: JAPANESE INTERMEDIATE CODE: A61

Effective date: 20211202

R150 Certificate of patent or registration of utility model

Ref document number: 6989387

Country of ref document: JP

Free format text: JAPANESE INTERMEDIATE CODE: R150

S111 Request for change of ownership or part of ownership

Free format text: JAPANESE INTERMEDIATE CODE: R313113

R350 Written notification of registration of transfer

Free format text: JAPANESE INTERMEDIATE CODE: R350

LAPS Cancellation because of no payment of annual fees