論文の概要: Quantum-inspired classical algorithm for graph problems by Gaussian boson sampling

• arxiv url: http://arxiv.org/abs/2302.00536v1
• Date: Wed, 1 Feb 2023 16:02:31 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-02 17:16:55.434394
• Title: Quantum-inspired classical algorithm for graph problems by Gaussian boson sampling
• Title（参考訳）: ガウスボソンサンプリングによるグラフ問題に対する量子インスピレーション付き古典的アルゴリズム
• Authors: Changhun Oh, Liang Jiang, Nicol\'as Quesada
• Abstract要約: グラフ理論問題に応用可能な量子インスピレーション付き古典アルゴリズムを提案する。 ガウスボソンサンプリング器で符号化されるグラフの隣接行列は非負であり、量子干渉を必要としない。
• 参考スコア（独自算出の注目度）: 2.8655318786364408
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a quantum-inspired classical algorithm that can be used for graph-theoretical problems, such as finding the densest $k$-subgraph and finding the maximum weight clique, which are proposed as applications of a Gaussian boson sampler. The main observation from Gaussian boson samplers is that a given graph's adjacency matrix to be encoded in a Gaussian boson sampler is nonnegative, which does not necessitate quantum interference. We first provide how to program a given graph problem into our efficient classical algorithm. We then numerically compare the performance of ideal and lossy Gaussian boson samplers, our quantum-inspired classical sampler, and the uniform sampler for finding the densest $k$-subgraph and finding the maximum weight clique and show that the advantage from Gaussian boson samplers is not significant in general. We finally discuss the potential advantage of a Gaussian boson sampler over the proposed sampler.
• Abstract（参考訳）: 本稿では,最も高密度な$k$-部分グラフの探索や最大重みの傾きの探索など,グラフ理論上の問題に応用可能な量子インスピレーション付き古典的アルゴリズムを提案する。 ガウスボソンサンプリング器の主な観測は、ガウスボソンサンプリング器に符号化されるグラフの隣接行列が非負であり、量子干渉を必要としないことである。 まず,与えられたグラフ問題を効率的な古典アルゴリズムにプログラムする方法を提案する。 次に, 理想と損失の大きいガウスボソンサンプリング器, 量子インスパイアされた古典的なサンプリング器, および最も高密度な$k$-サブグラフを発見し, 最大重量傾きを求める均一なサンプリング器の性能を比較し, ガウスボソンサンプリング器の利点が一般に有意でないことを示す。 提案したサンプリング器に対するガウスボソンサンプリング器の可能性について論じる。

関連論文リスト

• Gaussian Boson Sampling to Accelerate NP-Complete Vertex-Minor Graph Classification [0.9935277311162707]
  2つのグラフが互いに小さいかどうかを決定するNP完全問題に対するハイブリッド量子古典アルゴリズムを提案する。 ワンショット分類精度と入力スクイーズ量とのトレーディングが可能なグラフ埋め込みを見つける。 本稿では,グラフスペクトルに基づく新しい古典的アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-02-05T21:24:11Z)
• Some Constructions of Private, Efficient, and Optimal $K$-Norm and Elliptic Gaussian Noise [54.34628844260993]
  微分プライベートな計算は、しばしば$d$次元統計学の感度に束縛されて始まる。 純粋な微分プライバシーのために、$K$-normメカニズムは統計学の感度空間に合わせた規範を用いてこのアプローチを改善することができる。 本稿では,総和,数,投票の単純な統計量について両問題を解く。
  論文  参考訳（メタデータ） (2023-09-27T17:09:36Z)
• Classical algorithm for simulating experimental Gaussian boson sampling [2.1684911254068906]
  ガウスボソンサンプリングは実験的量子優位性を示す有望な候補である。 高い光子損失率とノイズの存在にもかかわらず、それらは現在、最もよく知られた古典的アルゴリズムで古典的にシミュレートすることが難しいと主張されている。 本稿ではガウスボソンサンプリングをシミュレートする古典的テンソルネットワークアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-06T14:19:48Z)
• Solving Graph Problems Using Gaussian Boson Sampling [22.516585968074146]
  ノイズの多い中間スケールの量子コンピュータを用いてグラフ問題を解く。 我々は,大きな光子クリック数を持つGBS増幅の存在と,特定の雑音下での強化を実験的に観察した。 我々の研究は、既存の中間スケール量子コンピュータを用いて現実の問題をテストするためのステップである。
  論文  参考訳（メタデータ） (2023-02-02T08:25:47Z)
• Langevin Monte Carlo for Contextual Bandits [72.00524614312002]
  Langevin Monte Carlo Thompson Sampling (LMC-TS) が提案されている。 提案アルゴリズムは,文脈的帯域幅の特別な場合において,最高のトンプソンサンプリングアルゴリズムと同じサブ線形残差を達成できることを示す。
  論文  参考訳（メタデータ） (2022-06-22T17:58:23Z)
• Experimentally finding dense subgraphs using a time-bin encoded Gaussian boson sampling device [0.0]
  我々は、時間ビン符号化干渉計を用いて、GBSを実験的に実装し、サンプルを抽出し、グラフ内の高密度部分グラフの探索を強化する。 その結果,10個のノードを含むグラフにおいて,3と4のサブグラフの古典的手法よりも改善が見られた。 我々は、光回路における不完全性の役割と、アルゴリズムの性能について数値的に検討する。
  論文  参考訳（メタデータ） (2022-04-11T16:56:30Z)
• Certification of Gaussian Boson Sampling via graph theory [4.063872661554895]
  実ガウスボソンサンプリング装置の光子計数とグラフ中の完全マッチング数との接続を利用する。 本フレームワークでは,グラフ特徴ベクトルとグラフカーネルの分布を利用した2つのアプローチを提案する。
  論文  参考訳（メタデータ） (2022-02-15T20:22:28Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。 次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
  論文  参考訳（メタデータ） (2021-05-03T16:36:27Z)
• 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)
• Nearly Linear Row Sampling Algorithm for Quantile Regression [54.75919082407094]
  データの次元にほぼ線形なサンプル複雑性を持つ量子化損失関数の行サンプリングアルゴリズムを提案する。 行サンプリングアルゴリズムに基づいて、量子レグレッションの最も高速なアルゴリズムと、バランスの取れた有向グラフのグラフスペーシフィケーションアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-15T13:40:07Z)
• Bandit Samplers for Training Graph Neural Networks [63.17765191700203]
  グラフ畳み込みネットワーク(GCN)の訓練を高速化するために, ばらつきを低減したサンプリングアルゴリズムが提案されている。 これらのサンプリングアルゴリズムは、グラフ注意ネットワーク(GAT)のような固定重みよりも学習重量を含む、より一般的なグラフニューラルネットワーク(GNN)には適用できない。
  論文  参考訳（メタデータ） (2020-06-10T12:48:37Z)

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

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