論文の概要: Gaussian-boson-sampling-enhanced dense subgraph finding shows limited advantage over efficient classical algorithms

• arxiv url: http://arxiv.org/abs/2301.13217v1
• Date: Mon, 30 Jan 2023 19:00:03 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-01 18:54:51.652240
• Title: Gaussian-boson-sampling-enhanced dense subgraph finding shows limited advantage over efficient classical algorithms
• Title（参考訳）: gaussian-boson-sampling-enhanced dense subgraph findingは効率的な古典アルゴリズムよりも限定的な利点を示している
• Authors: Naomi R. Solomons, Oliver F. Thomas, Dara P. S. McCutcheon
• Abstract要約: 本研究では,高密度サブグラフ探索アルゴリズムに適用したGBSに対する損失やスペクトル不純物を含む誤差源の影響について検討する。 これらのアルゴリズムの有効性は誤りに対して極めて堅牢であり、基礎となるGBSをシミュレートできる効率的な古典的アルゴリズムが存在することが判明した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent claims of achieving exponential quantum advantage have attracted attention to Gaussian boson sampling (GBS), a potential application of which is dense subgraph finding. We investigate the effects of sources of error including loss and spectral impurity on GBS applied to dense subgraph finding algorithms. We find that the effectiveness of these algorithms is remarkably robust to errors, to such an extent that there exist efficient classical algorithms that can simulate the underlying GBS. These results imply that the speedup of GBS-based algorithms for the dense subgraph problem over classical approaches is at most polynomial, though this could be achieved on a quantum device with dramatically less stringent requirements on loss and photon purity than general GBS.
• Abstract（参考訳）: 指数的量子優位性を達成するという最近の主張は、密度の低い部分グラフ発見の潜在的応用であるガウスボソンサンプリング(GBS)に注目されている。 高密度サブグラフ探索アルゴリズムに適用したgbsに対する損失やスペクトル不純物を含む誤差の発生源の影響について検討した。 これらのアルゴリズムの有効性は誤りに対して極めて堅牢であり、基礎となるGBSをシミュレートできる効率的な古典的アルゴリズムが存在することが判明した。 これらの結果は、古典的アプローチによる高密度サブグラフ問題に対するGBSベースのアルゴリズムの高速化は、ほとんどの多項式であるが、一般のGBSよりも損失と光子純度が劇的に低い量子デバイスで実現可能であることを示唆している。

関連論文リスト

• Classical modelling of a lossy Gaussian bosonic sampler [0.0]
  損失GBSインスタンスの近似古典シミュレーションのためのアルゴリズムを提案する。 アルゴリズムの複雑さは、項数が固定されたときのモードの数を絞っている。 量子的優位性を証明したと主張する最近の実験では、これらの条件が満たされている。
  論文  参考訳（メタデータ） (2024-04-01T09:19:27Z)
• Gaussian Boson Sampling to Accelerate NP-Complete Vertex-Minor Graph Classification [0.9935277311162707]
  2つのグラフが互いに小さいかどうかを決定するNP完全問題に対するハイブリッド量子古典アルゴリズムを提案する。 ワンショット分類精度と入力スクイーズ量とのトレーディングが可能なグラフ埋め込みを見つける。 本稿では,グラフスペクトルに基づく新しい古典的アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-02-05T21:24:11Z)
• Quantum Bayesian Optimization [64.58749619145908]
  本稿では,量子ガウスプロセスアップパー信頼度境界(Q-GP-UCB)アルゴリズムを提案する。 O(polylog T) は古典的設定における Omega(sqrt(T)) の左下限よりもかなり小さい。 線形核を持つQ-GP-UCBは、新しい信頼楕円体解析により、量子線形 UCB アルゴリズムよりも小さな後悔を実現する。
  論文  参考訳（メタデータ） (2023-10-09T03:10:42Z)
• Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
  不均一な問題に対する近似メッセージパッシングアルゴリズム(AMP)を導出する。 特に,情報理論の閾値よりも大きい信号と雑音の比を必要とする既知のアルゴリズムが,ランダムよりも優れた処理を行うための統計的・計算的ギャップの存在を同定する。
  論文  参考訳（メタデータ） (2023-02-13T19:57:17Z)
• Solving Graph Problems Using Gaussian Boson Sampling [22.516585968074146]
  ノイズの多い中間スケールの量子コンピュータを用いてグラフ問題を解く。 我々は,大きな光子クリック数を持つGBS増幅の存在と,特定の雑音下での強化を実験的に観察した。 我々の研究は、既存の中間スケール量子コンピュータを用いて現実の問題をテストするためのステップである。
  論文  参考訳（メタデータ） (2023-02-02T08:25:47Z)
• Experimentally finding dense subgraphs using a time-bin encoded Gaussian boson sampling device [0.0]
  我々は、時間ビン符号化干渉計を用いて、GBSを実験的に実装し、サンプルを抽出し、グラフ内の高密度部分グラフの探索を強化する。 その結果,10個のノードを含むグラフにおいて,3と4のサブグラフの古典的手法よりも改善が見られた。 我々は、光回路における不完全性の役割と、アルゴリズムの性能について数値的に検討する。
  論文  参考訳（メタデータ） (2022-04-11T16:56:30Z)
• Misspecified Gaussian Process Bandit Optimization [59.30399661155574]
  カーネル化されたバンディットアルゴリズムは、この問題に対して強い経験的および理論的性能を示した。 本稿では、未知関数を$epsilon$-一様近似で近似できるエンフェミス特定カーネル化帯域設定を、ある再生カーネルヒルベルト空間(RKHS)において有界ノルムを持つ関数で導入する。 提案アルゴリズムは,不特定性に関する事前知識を伴わず,$epsilon$への最適依存を実現する。
  論文  参考訳（メタデータ） (2021-11-09T09:00:02Z)
• Gaussian boson sampling with partial distinguishability [0.0]
  本稿では,仮想モードと識別不可能性に基づくアプローチを用いて,部分的な識別可能性を持つGBSについて検討する。 GBSにおける量子超越性の境界は, 偏微分可能性によってさらに推し進めることができることを示す。
  論文  参考訳（メタデータ） (2021-05-20T08:17:51Z)
• Learned Block Iterative Shrinkage Thresholding Algorithm for Photothermal Super Resolution Imaging [52.42007686600479]
  深層ニューラルネットワークに展開する反復アルゴリズムを用いて,学習したブロックスパース最適化手法を提案する。 本稿では、正規化パラメータの選択を学ぶことができる学習ブロック反復収縮しきい値アルゴリズムを使用することの利点を示す。
  論文  参考訳（メタデータ） (2020-12-07T09:27:16Z)
• 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)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。