論文の概要: Quantum algorithms through graph composition

• arxiv url: http://arxiv.org/abs/2504.02115v1
• Date: Wed, 02 Apr 2025 20:20:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-04 12:55:08.922348
• Title: Quantum algorithms through graph composition
• Title（参考訳）: グラフ合成による量子アルゴリズム
• Authors: Arjan Cornelissen,
• Abstract要約: 本稿では、量子アルゴリズムを生成するための st-connectivity framework の一般化であるグラフ合成フレームワークを紹介する。 st接続性フレームワークが学習グラフフレームワーク,重み付き決定木フレームワーク,および後者のゼロエラーバージョンをどう仮定するかを示す。 また、空間効率の高い有向st接続問題、パターンマッチング問題、固定探索問題に対する既存の量子アルゴリズムを単純化する。
• 参考スコア（独自算出の注目度）: 0.40792653193642503
• License:
• Abstract: In this work, we introduce the graph composition framework, a generalization of the st-connectivity framework for generating quantum algorithms, where the availability of each of the graph's edges is computed by a span program. We provide an exact characterization of the resulting witness sizes in terms of effective resistances of related graphs. We also provide less-powerful, but easier-to-use upper bounds on these witness sizes. We give generic time-efficient implementations of algorithms generated through the graph composition framework, in the quantum read-only memory model, which is a weaker assumption than the more common quantum random-access model. Along the way, we simplify the span program algorithm, and remove the dependence of its analysis on the effective spectral gap lemma. We unify the quantum algorithmic frameworks that are based on span programs or the quantum adversary bound. In particular, we show how the st-connectivity framework subsumes the learning graph framework, the weighted-decision-tree framework, and a zero-error version of the latter. We show that the graph composition framework subsumes part of the quantum divide and conquer framework, and that it is itself subsumed by the multidimensional quantum walk framework. Moreover, we show that the weighted-decision-tree complexity is quadratically related to deterministic query complexity, and to the GT-bound with polynomial exponent 3/2. For the latter, we also provide a matching separation. We apply our techniques to give improved algorithms for various string-search problems, namely the Dyck-language recognition problem of depth 3, the 3-increasing subsequence problem, and the OR $\circ$ pSEARCH problem. We also simplify existing quantum algorithms for the space-efficient directed st-connectivity problem, the pattern-matching problem and the infix-search problem.
• Abstract（参考訳）: 本稿では,各グラフのエッジの可用性をスパンプログラムで計算する,量子アルゴリズム生成のためのst接続フレームワークの一般化であるグラフ合成フレームワークを紹介する。 我々は、関連するグラフの有効抵抗の観点から、結果の目撃者サイズを正確に評価する。 また、これらの目撃者サイズの上限は、あまり強力ではなく、使いやすくも提供しています。 より一般的な量子ランダムアクセスモデルよりも弱い仮定である量子読み取り専用メモリモデルにおいて、グラフ合成フレームワークによって生成されるアルゴリズムの時間効率の一般的な実装を提供する。 その過程で、スパンプログラムアルゴリズムを単純化し、効率的なスペクトルギャップ補間に対する解析の依存性を除去する。 我々は、スパンプログラムや量子対向境界に基づく量子アルゴリズムフレームワークを統一する。 特に、st接続性フレームワークが学習グラフフレームワーク、重み付き決定木フレームワーク、および後者のゼロエラーバージョンをどう仮定するかを示す。 グラフ合成フレームワークは、量子分割と征服のフレームワークの一部を仮定し、多次元の量子ウォークフレームワークがそれ自身を仮定していることを示す。 さらに、重み付き決定木複雑性は、決定論的クエリ複雑性と多項式指数3/2のGTバウンドに二次的に関係していることを示す。 後者については、一致した分離も提供します。 そこで本手法を応用して,深度3のDyck言語認識問題,3増加サブシーケンス問題,OR$\circ$ pSEARCH問題などの文字列探索問題に対する改良アルゴリズムを提案する。 また、空間効率の高い有向st接続問題、パターンマッチング問題、固定探索問題に対する既存の量子アルゴリズムを単純化する。

関連論文リスト

• Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck [55.22418739014892]
  量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。 3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。 数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
  論文  参考訳（メタデータ） (2023-11-19T00:06:11Z)
• Quantum Algorithm for Maximum Biclique Problem [11.96554895748371]
  頂点の最大数で双斜線を同定することは、多くの応用分野に相当な意味を持つ。 本稿では,時間的複雑性O*(2(n/2))を持つ基底破れアルゴリズムqMBSを提案する。 最大二進問題と最大二進問題に適した2つの変種を詳述する。
  論文  参考訳（メタデータ） (2023-09-08T04:43:05Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• Benchmarking Small-Scale Quantum Devices on Computing Graph Edit Distance [52.77024349608834]
  グラフ編集距離(GED: Graph Edit Distance)は、2つのグラフ間の(異なる)相似性の度合いを測定する。 本稿では、GED計算における2つの量子アプローチの比較研究について述べる。
  論文  参考訳（メタデータ） (2021-11-19T12:35:26Z)
• Near-term Efficient Quantum Algorithms for Entanglement Analysis [5.453850739960517]
  絡み合いは量子物理学において重要な役割を担い、量子情報処理の鍵となる資源である。 本研究は、この困難に対処するために、ハイブリッド量子古典的手法を利用した3つの短期的効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-22T15:15:58Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。 本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。 提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
  論文  参考訳（メタデータ） (2021-07-08T17:59:55Z)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。 本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
  論文  参考訳（メタデータ） (2021-06-11T09:43:09Z)
• Quantum algorithm for Feynman loop integrals [0.0]
  量子アルゴリズムのFeynmanループ積分への新しいベンチマーク適用を提案する。 ファインマンプロパゲーターの2つのオンシェル状態は、キュービットの2つの状態と同一視される。 量子アルゴリズムは、マルチループファインマン図形の因果特異構成を展開するために用いられる。
  論文  参考訳（メタデータ） (2021-05-18T17:41:56Z)
• Entropic barriers as a reason for hardness in both classical and quantum algorithms [2.062593640149623]
  古典的および量子的アルゴリズムを用いて3つの規則ランダムグラフ上の3-XORSATという難解な最適化問題を解く。 大規模なエネルギー障壁を乗り越えることができない新しい準グレーディアルゴリズムを導入することにより、問題硬度は主にエントロピー障壁によるものであることを示す。
  論文  参考訳（メタデータ） (2021-01-30T07:58:24Z)
• Quantum algorithms for learning a hidden graph and beyond [0.05076419064097732]
  本稿では、量子アルゴリズムを用いて、託宣によって提供された未知のグラフを学習する問題について研究する。 ORおよびパリティクエリモデルにおいて、最も優れた古典的アルゴリズムの高速化を実現する量子アルゴリズムを提供する。 さらに、グループテスト問題の"ガッペ"バージョンに対して、Ambainisらのアルゴリズムに基づいて、この問題に対する時間効率の量子アルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-11-17T13:12:43Z)

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

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