論文の概要: Gaussian Boson Sampling to Accelerate NP-Complete Vertex-Minor Graph
Classification
- arxiv url: http://arxiv.org/abs/2402.03524v1
- Date: Mon, 5 Feb 2024 21:24:11 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-07 17:48:58.085848
- Title: Gaussian Boson Sampling to Accelerate NP-Complete Vertex-Minor Graph
Classification
- Title（参考訳）: NP完全頂点グラフ分類を高速化するガウスボソンサンプリング
- Authors: Mushkan Sureka, Saikat Guha
- Abstract要約: 2つのグラフが互いに小さいかどうかを決定するNP完全問題に対するハイブリッド量子古典アルゴリズムを提案する。
ワンショット分類精度と入力スクイーズ量とのトレーディングが可能なグラフ埋め込みを見つける。
本稿では,グラフスペクトルに基づく新しい古典的アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 0.9935277311162707
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Gaussian Boson Sampling (GBS) generate random samples of photon-click
patterns from a class of probability distributions that are hard for a
classical computer to sample from. Despite heroic demonstrations for quantum
supremacy using GBS, Boson Sampling, and instantaneous quantum polynomial (IQP)
algorithms, systematic evaluations of the power of these quantum-enhanced
random samples when applied to provably hard problems, and performance
comparisons with best-known classical algorithms have been lacking. We propose
a hybrid quantum-classical algorithm using the GBS for the NP-complete problem
of determining if two graphs are vertex minor of one another. The graphs are
encoded in GBS and the generated random samples serve as feature vectors in the
support vector machine (SVM) classifier. We find a graph embedding that allows
trading between the one-shot classification accuracy and the amount of input
squeezing, a hard-to-produce quantum resource, followed by repeated trials and
majority vote to reach an overall desired accuracy. We introduce a new
classical algorithm based on graph spectra, which we show outperforms various
well-known graph-similarity algorithms. We compare the performance of our
algorithm with this classical algorithm and analyze their time vs problem-size
scaling, to yield a desired classification accuracy. Our simulation suggests
that with a near-term realizable GBS device- $5$ dB pulsed squeezer, $12$-mode
unitary, and reasonable assumptions on coupling efficiency, on-chip losses and
detection efficiency of photon number resolving detectors-we can solve a
$12$-node vertex minor instances with about $10^3$ fold lower time compared to
a powerful desktop computer.
- Abstract（参考訳）: gaussian boson sampling (gbs) は、古典的なコンピュータではサンプリングが難しい確率分布のクラスから、フォトンクリックパターンのランダムなサンプルを生成する。
GBS, Boson Sampling, instantaneous quantum polynomial (IQP) アルゴリズムを用いた量子超越性に関するヒロイックな実証にもかかわらず、証明可能な難解な問題に適用した場合のこれらの量子強調ランダムサンプルのパワーの体系的評価や、よく知られた古典的アルゴリズムのパフォーマンス比較は不足している。
2つのグラフが互いに頂点マイナーかどうかを決定するNP完全問題に対して,GBSを用いたハイブリッド量子古典アルゴリズムを提案する。
グラフはGBSでエンコードされ、生成されたランダムサンプルはサポートベクトルマシン(SVM)分類器の機能ベクトルとして機能する。
私たちは、ワンショットの分類精度と、生産が難しい量子リソースである入力スクイーズ量とのトレーディングを可能にするグラフ埋め込みを見出した。
本稿では,グラフスペクトルに基づく新しい古典的アルゴリズムを提案する。
本アルゴリズムの性能をこの古典的アルゴリズムと比較し,その時間と問題規模のスケーリングを解析し,望ましい分類精度を得る。
シミュレーションによれば、短期的に実現可能なgbsデバイス – 5ドルのdbパルススクイーサー、12ドルのユニタリ、結合効率、光子数分解検出器のオンチップ損失、検出効率に関する合理的な仮定 — によって、私たちは、パワフルなデスクトップコンピュータに比べて約10^3$の時間で12ドルのノードバーテックスマイナーインスタンスを解決できる。
関連論文リスト
- Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security [50.16790546184646]
まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。
次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
論文 参考訳（メタデータ） (2023-11-07T04:59:02Z) - Solving Graph Problems Using Gaussian Boson Sampling [22.516585968074146]
ノイズの多い中間スケールの量子コンピュータを用いてグラフ問題を解く。
我々は,大きな光子クリック数を持つGBS増幅の存在と,特定の雑音下での強化を実験的に観察した。
我々の研究は、既存の中間スケール量子コンピュータを用いて現実の問題をテストするためのステップである。
論文 参考訳（メタデータ） (2023-02-02T08:25:47Z) - Sample efficient graph classification using binary Gaussian boson
sampling [0.0]
本稿では,グラフ構造化データを用いた機械学習タスクにおける量子アルゴリズムの変形について述べる。
我々の装置は、光子数分解検出器とは対照的に、バイナリ(光/光)検出器のみを必要とする。
論文 参考訳（メタデータ） (2023-01-03T17:23:43Z) - Validation tests of GBS quantum computers give evidence for quantum
advantage with a decoherent target [62.997667081978825]
複数モードデータの検証に指紋としてグループカウント確率の正P位相空間シミュレーションを用いる。
偽データを解き放つ方法を示し、これを古典的なカウントアルゴリズムに適用する。
論文 参考訳（メタデータ） (2022-11-07T12:00:45Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。
ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
論文 参考訳（メタデータ） (2022-07-07T08:04:15Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Certification of Gaussian Boson Sampling via graph theory [4.063872661554895]
実ガウスボソンサンプリング装置の光子計数とグラフ中の完全マッチング数との接続を利用する。
本フレームワークでは,グラフ特徴ベクトルとグラフカーネルの分布を利用した2つのアプローチを提案する。
論文 参考訳（メタデータ） (2022-02-15T20:22:28Z) - Unsupervised Event Classification with Graphs on Classical and Photonic
Quantum Computers [0.0]
フォトニック量子コンピュータは、量子コンピューティングの離散量子ビットベースのパラダイムよりもいくつかの利点を提供している。
新物理の探索に使用する異常検出モデルを構築した。
ガウスボソンサンプリングとQ平均と呼ばれるK平均への量子拡張を組み合わせた新しい異常検出法を提案する。
論文 参考訳（メタデータ） (2021-03-05T19:02:31Z) - Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。
任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
論文 参考訳（メタデータ） (2020-11-26T18:22:21Z) - Plug-And-Play Learned Gaussian-mixture Approximate Message Passing [71.74028918819046]
そこで本研究では,従来のi.i.d.ソースに適した圧縮圧縮センシング(CS)リカバリアルゴリズムを提案する。
我々のアルゴリズムは、Borgerdingの学習AMP(LAMP)に基づいて構築されるが、アルゴリズムに普遍的な復調関数を採用することにより、それを大幅に改善する。
数値評価により,L-GM-AMPアルゴリズムは事前の知識を必要とせず,最先端の性能を実現する。
論文 参考訳（メタデータ） (2020-11-18T16:40:45Z) - Quantum Sampling Algorithms for Near-Term Devices [0.0]
ギブス分布全体を符号化することで、偏りのないサンプルを提供する量子アルゴリズムのファミリを導入する。
このアプローチが従来のマルコフ連鎖アルゴリズムの高速化につながることを示す。
短期量子デバイス上で、潜在的に有用なサンプリングアルゴリズムを探索する扉を開く。
論文 参考訳（メタデータ） (2020-05-28T14:46:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。