論文の概要: A Note on Quantum Divide and Conquer for Minimal String Rotation
- arxiv url: http://arxiv.org/abs/2210.09149v1
- Date: Mon, 17 Oct 2022 14:51:49 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-22 07:09:51.227714
- Title: A Note on Quantum Divide and Conquer for Minimal String Rotation
- Title（参考訳）: 最小弦回転に対する量子分割と克服に関する一考察
- Authors: Qisheng Wang
- Abstract要約: 語彙的に最小限の弦の回転は、弦処理の基本的な問題である。
準最適量子アルゴリズムは、その開発中に提案され、量子分割や征服といった新しいアイデアが導入された。
- 参考スコア（独自算出の注目度）: 1.8275108630751844
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Lexicographically minimal string rotation is a fundamental problem on string
processing that has recently attracted a lot of attention in quantum computing.
Near-optimal quantum algorithms have been proposed during its development, with
new ideas such as quantum divide and conquer introduced. In this note, we
further study its quantum query complexity. Slightly improved quantum
algorithms by divide and conquer are proposed:
1. For the function problem, its query complexity is shown to be $\sqrt{n}
\cdot 2^{O\left(\sqrt{\log n}\right)}$, improving the recent result of
$\sqrt{n} \cdot 2^{\left(\log n\right)^{1/2+\varepsilon}}$ by Akmal and Jin
(2022).
2. For the decision problem, its query complexity is shown to be
$O\left(\sqrt{n \log^3 n \log \log n}\right)$, improving the recent result of
$O\left(\sqrt{n \log^5 n}\right)$ by Childs et al. (2022).
The purpose of this note is to point out some useful algorithmic tricks,
e.g., preprocessing and level-wise optimization, that can be used to improve
quantum algorithms, especially for those with a divide-and-conquer structure.
- Abstract（参考訳）: 語彙的に最小の弦の回転は、最近量子コンピューティングにおいて多くの注目を集めている文字列処理の基本的な問題である。
準最適量子アルゴリズムはその開発中に提案され、量子分割や征服のような新しいアイデアが導入された。
本稿では,量子クエリの複雑さをさらに研究する。
1. 関数問題に対して、そのクエリ複雑性は$\sqrt{n} \cdot 2^{O\left(\sqrt{\log n}\right)}$と示され、最近の結果である$\sqrt{n} \cdot 2^{\left(\log n\right)^{1/2+\varepsilon}}$をAkmal and Jin (2022)により改善する。
2. 決定問題の場合、クエリの複雑さは$O\left(\sqrt{n \log^3 n \log \log n}\right)$であり、Childsらによる$O\left(\sqrt{n \log^5 n}\right)$の最近の結果を改善する(2022)。
このノートの目的は、量子アルゴリズム、特に分割・結合構造を持つ人のために使用できる、プリプロセッシングやレベルワイズ最適化のような有用なアルゴリズムトリックを指摘することである。
関連論文リスト
- 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) - Towards Optimal Circuit Size for Sparse Quantum State Preparation [10.386753939552872]
我々は、$s$非ゼロ振幅を持つ$n$量子ビットスパース量子状態の準備を検討し、2つのアルゴリズムを提案する。
最初のアルゴリズムは$O(ns/log n + n)$ gatesを使用し、以前のメソッドを$O(log n)$で改善する。
2番目のアルゴリズムは、短いハミルトニアンパスを示す二進弦向けに調整されている。
論文 参考訳（メタデータ） (2024-04-08T02:13:40Z) - Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv
Factorization [2.684542790908823]
我々は、$tildeO(sqrtnk+k2)$-timeアルゴリズムを提案し、$tildeO(sqrtnz)$クエリを使用します。
2つ目の貢献は、$tildeO(sqrtnz)$の最適時間複雑性を達成する量子アルゴリズムである。
論文 参考訳（メタデータ） (2023-11-03T09:09:23Z) - 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) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - 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) - The First Optimal Acceleration of High-Order Methods in Smooth Convex
Optimization [88.91190483500932]
本研究では,滑らかな凸最小化問題の解法として最適高次アルゴリズムを求めるための基本的オープンな問題について検討する。
この理由は、これらのアルゴリズムが複雑なバイナリプロシージャを実行する必要があるため、最適でも実用でもないからである。
我々は、最初のアルゴリズムに$mathcalOleft(epsilon-2/(p+1)right)$pthのオーダーオーラクル複雑性を与えることで、この根本的な問題を解決する。
論文 参考訳（メタデータ） (2022-05-19T16:04:40Z) - Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。
本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
論文 参考訳（メタデータ） (2021-05-18T06:51:11Z) - Quantum algorithms for escaping from saddle points [7.191453718557392]
本研究では,サドル点からの脱出を保証できる保証付き量子アルゴリズムについて検討する。
我々の主な貢献は、勾配降下法における古典的摂動を置き換えるという考え方である。
また、Jordanによる量子勾配計算アルゴリズムの使い方を示す。
論文 参考訳（メタデータ） (2020-07-20T16:42:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。