論文の概要: Asymptotically Faster Quantum Distributed Algorithms for Approximate
Steiner Trees and Directed Minimum Spanning Trees
- arxiv url: http://arxiv.org/abs/2304.02825v1
- Date: Thu, 6 Apr 2023 02:18:52 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-07 15:32:16.882030
- Title: Asymptotically Faster Quantum Distributed Algorithms for Approximate
Steiner Trees and Directed Minimum Spanning Trees
- Title（参考訳）: 近似スタイナー木と最小スパンニング木に対する漸近的に高速な量子分散アルゴリズム
- Authors: Phillip A. Kerger, David E. Bernal Neira, Zoe Gonzalez Izquierdo,
Eleanor G. Rieffel
- Abstract要約: 確率の高い分散計算の量子ConGEST-CLIQUEモデルに2つのアルゴリズムを提案する。
従来のCONGEST-CLIQUEモデルでは、既知のアルゴリズムよりもラウンドとメッセージの複雑さが低い。
Groverの検索アルゴリズムの分散バージョンを使用して三角形探索を高速化する既存のフレームワークは、スピードアップのコアにある。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The CONGEST and CONGEST-CLIQUE models have been carefully studied to
represent situations where the communication bandwidth between processors in a
network is severely limited. Messages of only $O(log(n))$ bits of information
each may be sent between processors in each round. The quantum versions of
these models allow the processors instead to communicate and compute with
quantum bits under the same bandwidth limitations. This leads to the following
natural research question: What problems can be solved more efficiently in
these quantum models than in the classical ones? Building on existing work, we
contribute to this question in two ways. Firstly, we present two algorithms in
the Quantum CONGEST-CLIQUE model of distributed computation that succeed with
high probability; one for producing an approximately optimal Steiner Tree, and
one for producing an exact directed minimum spanning tree, each of which uses
$\tilde{O}(n^{1/4})$ rounds of communication and $\tilde{O}(n^{9/4})$ messages,
where $n$ is the number of nodes in the network. The algorithms thus achieve a
lower asymptotic round and message complexity than any known algorithms in the
classical CONGEST-CLIQUE model. At a high level, we achieve these results by
combining classical algorithmic frameworks with quantum subroutines. An
existing framework for using distributed version of Grover's search algorithm
to accelerate triangle finding lies at the core of the asymptotic speedup.
Secondly, we carefully characterize the constants and logarithmic factors
involved in our algorithms as well as related algorithms, otherwise commonly
obscured by $\tilde{O}$ notation. The analysis shows that some improvements are
needed to render both our and existing related quantum and classical algorithms
practical, as their asymptotic speedups only help for very large values of $n$.
- Abstract（参考訳）: CONGESTとCONGEST-CLIQUEモデルは、ネットワーク内のプロセッサ間の通信帯域幅が著しく制限されている状況を表現するために慎重に研究されている。
O(log(n))$ビットの情報のみのメッセージは、各ラウンドのプロセッサ間で送信することができる。
これらのモデルの量子バージョンにより、プロセッサは同じ帯域制限下で量子ビットと通信し、計算することができる。
古典量子モデルよりもこれらの量子モデルでより効率的に解くことができる問題は何か?
既存の作業に基づいて、私たちはこの質問に2つの方法で貢献します。
まず, 分散計算の量子連続格子モデルにおいて, ほぼ最適なスタイナーツリーを生成するためのアルゴリズムと, ネットワーク内のノード数を$n$とする$\tilde{o}(n^{1/4})$ rounds と$\tilde{o}(n^{9/4})$メッセージを使用する完全有向最小スパンニングツリーを生成するアルゴリズムの2つのアルゴリズムを提案する。
したがって、このアルゴリズムは古典集合-ユークリッドモデルにおける既知のアルゴリズムよりも低い漸近的ラウンドとメッセージ複雑性を達成する。
高レベルでは、古典的アルゴリズムフレームワークと量子サブルーチンを組み合わせることで、これらの結果を達成する。
Groverの検索アルゴリズムの分散バージョンを使用して三角形探索を高速化する既存のフレームワークは、漸近的スピードアップの中核にある。
第二に、我々のアルゴリズムと関連するアルゴリズムにかかわる定数と対数要素を慎重に特徴づけるが、そうでなければ$\tilde{O}$表記法でよく分からない。
この分析は、我々の量子アルゴリズムと既存の量子アルゴリズムと古典アルゴリズムの両方を実用的にするためにいくつかの改善が必要であることを示している。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Quantum Complexity for Discrete Logarithms and Related Problems [7.077306859247421]
我々は、群理論問題に対する量子計算の一般モデルを構築し、これを量子ジェネリックグループモデルと呼ぶ。
このモデルでは、量子複雑性の低い境界と、DLのほぼ一致するアルゴリズムと関連する問題を示す。
Shorのアルゴリズムのバリエーションは、量子群演算の数を減らすために古典的な計算を利用することができる。
論文 参考訳（メタデータ） (2023-07-06T15:32:50Z) - Quantum Simulation of the First-Quantized Pauli-Fierz Hamiltonian [0.5097809301149342]
我々は、我々の分割と形式主義の征服を通じて、大きな$Lambda$の量子化よりも優れたスケーリングと量子化を得られることを示す。
また,マルチコントロールされたXゲート群を実装する新しい方法を含む,ゲート最適化のための新しいアルゴリズムおよび回路レベル技術も提供する。
論文 参考訳（メタデータ） (2023-06-19T23:20:30Z) - Efficient quantum linear solver algorithm with detailed running costs [0.0]
量子信号処理に基づくフィルタリング手法を用いて,アイデアダイアバティックな量子コンピューティングを組み合わせた量子線形解法アルゴリズムを提案する。
我々のプロトコルは、初期実装において、最先端技術に対する量子線形解決器のコストを桁違いに削減する。
論文 参考訳（メタデータ） (2023-05-19T00:07:32Z) - Quantum Algorithms for Sampling Log-Concave Distributions and Estimating
Normalizing Constants [8.453228628258778]
我々は,対数凹分布をサンプリングし,正規化定数を推定するための量子アルゴリズムを開発した。
我々はモンテカルロ法と量子ウォークの量子アナログを利用する。
また、正規化定数を推定するための1/epsilon1-o(1)$量子下界も証明する。
論文 参考訳（メタデータ） (2022-10-12T19:10:43Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。
ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
論文 参考訳（メタデータ） (2022-07-07T08:04:15Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。
本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
論文 参考訳（メタデータ） (2021-05-18T06:51:11Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳（メタデータ） (2020-05-09T02:48:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。