論文の概要: Quantum Search on Computation Trees
- arxiv url: http://arxiv.org/abs/2505.22405v1
- Date: Wed, 28 May 2025 14:35:18 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-29 20:07:45.813274
- Title: Quantum Search on Computation Trees
- Title（参考訳）: 計算木における量子探索
- Authors: Jevgēnijs Vihrovs,
- Abstract要約: モンタナロ(ToC)によるバックトラック木探索のための量子ウォークアルゴリズムの一般化を示す。
このフレームワークは、変数時間探索、量子分割と圧縮、爆弾クエリアルゴリズムなど、他の多くの量子フレームワークを再定義するための、簡単で便利な方法を提供する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We show a simple generalization of the quantum walk algorithm for search in backtracking trees by Montanaro (ToC 2018) to the case where vertices can have different times of computation. If a vertex $v$ in the tree of depth $D$ is computed in $t_v$ steps from its parent, then we show that detection of a marked vertex requires $\text{O}(\sqrt{TD})$ queries to the steps of the computing procedures, where $T = \sum_v t_v^2$. This framework provides an easy and convenient way to re-obtain a number of other quantum frameworks like variable time search, quantum divide & conquer and bomb query algorithms. The underlying algorithm is simple, explicitly constructed, and has low poly-logarithmic factors in the complexity. As a corollary, this gives a quantum algorithm for variable time search with unknown times with optimal query complexity $\text{O}(\sqrt{T \log \min(n,t_{\max})})$, where $T = \sum_i t_i^2$ and $t_{\max} = \max_i t_i$ if $t_i$ is the number of steps required to compute the $i$-th variable. This resolves the open question of the query complexity of variable time search, as the matching lower bound was recently shown by Ambainis, Kokainis and Vihrovs (TQC'23). As another result, we obtain an $\widetilde{\text{O}}(n)$ time algorithm for the geometric task of determining if any three lines among $n$ given intersect at the same point, improving the $\text{O}(n^{1+\text{o}(1)})$ algorithm of Ambainis and Larka (TQC'20).
- Abstract（参考訳）: モンタナロ (ToC 2018) によるバックトラック木探索のための量子ウォークアルゴリズムの簡単な一般化と, 頂点が計算時間が異なる場合について述べる。
深さ木内のvertex $v$が親から$t_v$のステップで計算されると、マークされたvertexの検出には$\text{O}(\sqrt{TD})$のクエリが必要で、$T = \sum_v t_v^2$である。
このフレームワークは、変数時間探索、量子分割と圧縮、爆弾クエリアルゴリズムなど、他の多くの量子フレームワークを再定義するための、簡単で便利な方法を提供する。
基礎となるアルゴリズムは単純で明示的な構成であり、複雑度が低くなる。
ここで、$T = \sum_i t_i^2$ and $t_{\max} = \max_i t_i$ if $t_i$は$i$-th変数を計算するのに必要なステップ数である。
これは変数時間探索のクエリ複雑性に関するオープンな疑問を解き、最近アンバイニス、コカイニス、ビフロフス(TQC'23)によって一致する下界が示されている。
別の結果として、$\widetilde{\text{O}}(n)$ time algorithm for the geometry task for any three lines among given $n$ intersect at the same point, improve the $\text{O}(n^{1+\text{o}(1)})$ algorithm of Ambainis and Larka (TQC'20)。
関連論文リスト
- Measuring quantum relative entropy with finite-size effect [53.64687146666141]
相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。
我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
論文 参考訳（メタデータ） (2024-06-25T06:07:20Z) - 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) - 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) - Time and Query Complexity Tradeoffs for the Dihedral Coset Problem [0.19731444261635428]
Z_N$のディヘドラルコセット問題(DCP)は量子コンピューティングやポスト量子暗号において広く研究されている。
Ettinger-Hoyerアルゴリズムは$O(log(N))$クエリでDCPを解くことが知られている。
本稿では,Ettinger-Hoyerアルゴリズムよりも線形クエリ方式を改良した最初のアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-06-29T05:30:54Z) - Logarithmic Regret from Sublinear Hints [76.87432703516942]
自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。
また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
論文 参考訳（メタデータ） (2021-11-09T16:50:18Z) - Online Sub-Sampling for Reinforcement Learning with General Function
Approximation [111.01990889581243]
本稿では,RLアルゴリズムによって収集されたデータポイントの情報取得量を測定する,効率的なオンラインサブサンプリングフレームワークを確立する。
複雑性バウンド関数クラスを持つ値ベースのメソッドの場合、$proptooperatornamepolylog(K)$ timesに対してのみポリシーを更新する必要がある。
少なくとも$Omega(K)$倍のポリシーを更新する既存のアプローチとは対照的に、当社のアプローチはポリシーの解決における最適化コールの数を劇的に削減します。
論文 参考訳（メタデータ） (2021-06-14T07:36:25Z) - Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。
本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
論文 参考訳（メタデータ） (2021-05-18T06:51:11Z) - Quantum speedups for dynamic programming on $n$-dimensional lattice
graphs [0.11470070927586015]
複雑性を$widetilde O(T_Dn)$で表すと、$T_D D+1$となる。
最もよく知られている古典的アルゴリズムは $textpoly(m,n)log n T_Dn$ であるが、量子アルゴリズムの時間複雑性は $textpoly(m,n)log n T_Dn$ である。
論文 参考訳（メタデータ） (2021-04-29T14:50:03Z) - Leveraging Unknown Structure in Quantum Query Algorithms [0.0]
本研究では,事前の約束がなくても,これらのスピードアップが持続することを示すために,修正されたスパンプログラムアルゴリズムを示す。
我々のアルゴリズムは、$tildeO(sqrtkn)$クエリを使って、少なくとも$k$のエッジを持つパスがある場合、この問題を解決する。
論文 参考訳（メタデータ） (2020-12-02T15:32:52Z) - 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) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。