論文の概要: Quantum speedups for treewidth
- arxiv url: http://arxiv.org/abs/2202.08186v1
- Date: Wed, 16 Feb 2022 16:47:47 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-25 16:28:09.177358
- Title: Quantum speedups for treewidth
- Title(参考訳): treewidthの量子速度向上
- Authors: Vladislavs K\c{l}evickis, Kri\v{s}j\=anis Pr\=usis, Jevg\=enijs
Vihrovs
- Abstract要約: グラフのツリー幅の正確な値を計算するための3つの量子アルゴリズムを示す。
木幅に対する最も高速な古典的アルゴリズムは時間と空間でO (1.755n) である。
O*(2n)$時間と$O*(sqrt2n)$空間でツリー幅を計算するための古典的な時間空間のトレードオフも与えている。
- 参考スコア(独自算出の注目度): 0.06445605125467573
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study quantum algorithms for computing the exact value of
the treewidth of a graph. Our algorithms are based on the classical algorithm
by Fomin and Villanger (Combinatorica 32, 2012) that uses $O(2.616^n)$ time and
polynomial space. We show three quantum algorithms with the following
complexity, using QRAM in both exponential space algorithms: $\bullet$
$O(1.618^n)$ time and polynomial space; $\bullet$ $O(1.554^n)$ time and
$O(1.452^n)$ space; $\bullet$ $O(1.538^n)$ time and space. In contrast, the
fastest known classical algorithm for treewidth uses $O(1.755^n)$ time and
space. The first two speed-ups are obtained in a fairly straightforward way.
The first version uses additionally only Grover's search and provides a
quadratic speedup. The second speedup is more time-efficient and uses both
Grover's search and the quantum exponential dynamic programming by Ambainis et
al. (SODA '19). The third version uses the specific properties of the classical
algorithm and treewidth, with a modified version of the quantum dynamic
programming on the hypercube. Lastly, as a small side result, we also give a
new classical time-space tradeoff for computing treewidth in $O^*(2^n)$ time
and $O^*(\sqrt{2^n})$ space.
- Abstract(参考訳): 本稿では,グラフのツリー幅の正確な値を計算するための量子アルゴリズムについて検討する。
我々のアルゴリズムは、O(2.616^n)$時間と多項式空間を使用するFomin and Villanger (Combinatorica 32, 2012) の古典的アルゴリズムに基づいている。
指数空間アルゴリズムの両方で QRAM を用いる3つの量子アルゴリズムを示す: $\bullet$$O(1.618^n)$ time and polynomial space; $\bullet$$O(1.554^n)$ time and $O(1.452^n)$ space; $\bullet$$O(1.538^n)$ time and space。
対照的に、最も早く知られている木幅の古典的アルゴリズムは、o(1.755^n)$ time and spaceである。
最初の2つのスピードアップは比較的簡単な方法で得られる。
最初のバージョンはgroverの検索のみを使用し、二次的なスピードアップを提供する。
第2のスピードアップはより時間効率が高く、AmbainisらによるGroverの探索と量子指数動的プログラミングの両方を用いる(SODA '19)。
第3版は、ハイパーキューブ上の量子動的プログラミングの修正版と共に、古典的なアルゴリズムとtreewidthの特定の特性を使用する。
最後に、小さな副作用として、木幅を$O^*(2^n)$ time と $O^*(\sqrt{2^n})$ space で計算するための新しい古典的時間空間トレードオフを与える。
関連論文リスト
- 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) - Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages [104.90415092306219]
4つの形式は、ツリー随伴文法(TAG)、線形指数文法(LIG)、プッシュダウン随伴オートマトン(PAA)、組込みプッシュダウンオートマトン(EPDA)に相当する。
我々は,文字列の導出量(文字列のすべてのオートマトン重み)と全導出量(全ての導出量重み)を計算するための新しいアルゴリズムを設計する。
EPDA の場合、我々のアルゴリズムは、$mathcalO(|Gamma|2)$ および $ の因子による Alonso et al. (2001) のアルゴリズムよりも空間効率と時間効率が良い。
論文 参考訳(メタデータ) (2023-10-23T18:26:00Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳(メタデータ) (2023-08-18T17:52:12Z) - Quantum Speedups for Bayesian Network Structure Learning [0.0]
ノードが$n$のネットワークの場合、最も高速な既知のアルゴリズムは、最悪の場合は$O(cn)$で実行され、20年で改善はない。
近年の量子コンピューティングの発展に触発されて、BNSLが量子スピードアップを認めているかどうかを問う。
我々は、$c leq 1.817$と$c leq 1.982$の2つのアルゴリズムを与える。
論文 参考訳(メタデータ) (2023-05-31T09:15:28Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳(メタデータ) (2022-12-03T02:45:23Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳(メタデータ) (2022-06-07T18:00:01Z) - Memory Compression with Quantum Random-Access Gates [0.0]
量子ランダムアクセスゲートを備えた量子アルゴリズムに対して、類似した結果を示す。
空間非効率であるがスパースな量子データ構造を構築することはしばしば可能である。
論文 参考訳(メタデータ) (2022-03-10T19:27:53Z) - Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。
本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
論文 参考訳(メタデータ) (2021-05-18T06:51:11Z) - Classical and Quantum Algorithms for Constructing Text from Dictionary
Problem [0.0]
辞書(小文字列列)からテキストを構築する際の問題の解法について検討する。
この問題はバイオインフォマティクスに応用され、小さな断片から長いDNA配列を再構築するSequenceアセンブリー法と関係がある。
論文 参考訳(メタデータ) (2020-05-28T22:44:01Z) - Faster classical Boson Sampling [0.15229257192293197]
平均ケースタイムの複雑さがより速く、$m$が$n$に比例するBoson Samplingのアルゴリズムを提案する。
この結果により、ボソンサンプリングによる量子計算の超越性を確立するために必要な問題サイズが増大する。
論文 参考訳(メタデータ) (2020-05-07T20:01:02Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳(メタデータ) (2020-04-14T11:05:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。