論文の概要: Time and Query Optimal Quantum Algorithms Based on Decision Trees
- arxiv url: http://arxiv.org/abs/2105.08309v2
- Date: Sun, 16 Oct 2022 10:15:46 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-30 20:07:01.084991
- Title: Time and Query Optimal Quantum Algorithms Based on Decision Trees
- Title（参考訳）: 決定木に基づく時間とクエリの最適量子アルゴリズム
- Authors: Salman Beigi, Leila Taghavi, Artin Tajdini
- Abstract要約: 量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。
本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
- 参考スコア（独自算出の注目度）: 2.492300648514128
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: It has recently been shown that starting with a classical query algorithm
(decision tree) and a guessing algorithm that tries to predict the query
answers, we can design a quantum algorithm with query complexity $O(\sqrt{GT})$
where $T$ is the query complexity of the classical algorithm (depth of the
decision tree) and $G$ is the maximum number of wrong answers by the guessing
algorithm [arXiv:1410.0932, arXiv:1905.13095]. In this paper we show that,
given some constraints on the classical algorithms, this quantum algorithm can
be implemented in time $\tilde O(\sqrt{GT})$. Our algorithm is based on
non-binary span programs and their efficient implementation. We conclude that
various graph theoretic problems including bipartiteness, cycle detection and
topological sort can be solved in time $O(n^{3/2}\log n)$ and with $O(n^{3/2})$
quantum queries. Moreover, finding a maximal matching can be solved with
$O(n^{3/2})$ quantum queries in time $O(n^{3/2}\log n)$, and maximum bipartite
matching can be solved in time $O(n^2\log n)$.
- Abstract（参考訳）: 最近、古典的なクエリアルゴリズム(決定木)と、クエリの答えを予測しようとする推測アルゴリズムから始め、クエリの複雑さを持つ量子アルゴリズムを設計できることが示されている($O(\sqrt{GT})$ ここで、$T$は古典的なアルゴリズム(決定木の深さ)のクエリの複雑さであり、$G$は推測アルゴリズム[arXiv:1410.0932, arXiv: 1905.13095]による間違った答えの最大数である。
本稿では,古典的アルゴリズムに制約を加えると,この量子アルゴリズムは時間$\tilde O(\sqrt{GT})$で実装可能であることを示す。
アルゴリズムは非バイナリスパンプログラムとその効率的な実装に基づいている。
二成分性、サイクル検出、位相ソートを含む様々なグラフ理論の問題は、時間$o(n^{3/2}\log n)$と$o(n^{3/2})$量子クエリで解くことができる。
さらに、最大マッチングを見つけるには、時間で$O(n^{3/2}\log n)$$$$O(n^{3/2}\log n)$で解け、最大二部マッチングは時間で$O(n^2\log n)$で解ける。
関連論文リスト
- 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 algorithms for Hopcroft's problem [45.45456673484445]
計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。
この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。
我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
論文 参考訳（メタデータ） (2024-05-02T10:29:06Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Algoritmo de Contagem Qu\^antico Aplicado ao Grafo Bipartido Completo [0.0]
Groverのアルゴリズムは、$O(sqrtN/k)$ stepsを使って$N$要素を持つ、順序のないデータベースで$k$要素を見つけることができる。
この研究は、他のグラフのマーク要素の値$k$を推定するために量子カウントアルゴリズムを使用する問題に取り組む。
論文 参考訳（メタデータ） (2023-12-05T21:15:09Z) - On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$ [4.956977275061968]
我々は、$textMOD_mn$を計算するための正確な量子アルゴリズムを示す。
我々は、0,1n$ を有限集合 $X$ が$n$ 未満であるような対称関数の広いクラスの正確な量子クエリ複雑性を示す。
論文 参考訳（メタデータ） (2023-03-20T08:17:32Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - 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) - Fast Classical and Quantum Algorithms for Online $k$-server Problem on
Trees [0.19573380763700712]
木上の$k$サーバ問題に対するオンラインアルゴリズムを検討する。
Chrobak と Larmore は最適な競合比を持つこの問題に対して$k$-competitive アルゴリズムを提案した。
本稿では,前処理に要するO(nlog n)$時間複雑性を持つ新しい時間効率アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-08-01T14:21:45Z) - Quantum algorithms for graph problems with cut queries [17.149741568581096]
量子アルゴリズムは、$O(d log(n)2) の後に最大$d$のグラフを学習できることを示す。
また、量子アルゴリズムは、$O(sqrtm log(n)3/2)$多くのカットクエリで一般的なグラフを学習できることを示す。
論文 参考訳（メタデータ） (2020-07-16T12:21:01Z) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳（メタデータ） (2020-02-20T17:52:18Z) - Quantum Algorithms for the Most Frequently String Search, Intersection
of Two String Sequences and Sorting of Strings Problems [0.0]
弦の3つの問題を解くアルゴリズムについて研究する。
1つ目は、最も頻度の高い文字列検索問題である。
2つ目は、2つの弦列の交叉である。
第三の問題は長さ$k$の$n$文字列をソートすることだ。
論文 参考訳（メタデータ） (2020-01-07T07:22:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。