論文の概要: 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)。
このノートの目的は、量子アルゴリズム、特に分割・結合構造を持つ人のために使用できる、プリプロセッシングやレベルワイズ最適化のような有用なアルゴリズムトリックを指摘することである。
関連論文リスト
- Space-Efficient Quantum Error Reduction without log Factors [50.10645865330582]
本稿では,多数決のランダムウォーク解釈に類似したライン上の重み付けウォークとして理解可能な,新たに単純化された浄化器の構成を提案する。
我々の浄化器は、前者よりも指数関数的に空間の複雑さが良く、精製されるアルゴリズムの音質-完全性ギャップに四分法的に依存している。
論文 参考訳（メタデータ） (2025-02-13T12:04:39Z) - 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 Algorithm for Minimizing the Maximal Loss [16.91814406135565]
我々は量子アルゴリズムと下界の体系的な研究を行い、最大で$N$凸、リプシッツ関数を最小化する。
我々は、量子アルゴリズムが$tildeOmega(sqrtNepsilon-2/3)$クエリを1次量子オラクルに取らなければならないことを証明している。
論文 参考訳（メタデータ） (2024-02-20T06:23:36Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Taming Quantum Time Complexity [45.867051459785976]
時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。
我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
論文 参考訳（メタデータ） (2023-11-27T14:45:19Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Pauli String Partitioning Algorithm with the Ising Model for
Simultaneous Measurement [0.0]
本研究では,パウリ弦を1つの量子回路で同時に測定可能な部分群に分割する効率的なアルゴリズムを提案する。
我々の分割アルゴリズムは、量子化学のための変分量子固有解法における測定総数を劇的に削減する。
論文 参考訳（メタデータ） (2022-05-09T01:49:21Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - Quantum Algorithm for Lexicographically Minimal String Rotation [5.905222176603487]
語彙的最小弦回転(lexicographically minimal string rotation, LMSR)は、語彙的順序で弦のすべての回転の中で最小の回転を求める問題である。
LMSRのための$O(n3/4)$量子クエリアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-12-17T03:13:45Z) - Quantum algorithms for escaping from saddle points [7.191453718557392]
本研究では,サドル点からの脱出を保証できる保証付き量子アルゴリズムについて検討する。
我々の主な貢献は、勾配降下法における古典的摂動を置き換えるという考え方である。
また、Jordanによる量子勾配計算アルゴリズムの使い方を示す。
論文 参考訳（メタデータ） (2020-07-20T16:42:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。