Fugu-MT 論文翻訳(概要): A Note on Quantum Divide and Conquer for Minimal String Rotation

論文の概要: A Note on Quantum Divide and Conquer for Minimal String Rotation

arxiv url: http://arxiv.org/abs/2210.09149v2
Date: Thu, 20 Feb 2025 02:04:15 GMT
ステータス: 翻訳完了
システム内更新日: 2025-02-21 17:43:16.712483
Title: A Note on Quantum Divide and Conquer for Minimal String Rotation
Title（参考訳）: 最小弦回転の量子除算とコンカーについての一考察
Authors: Qisheng Wang,
Abstract要約: 語彙的に最小限の弦の回転は、弦処理の基本的な問題である。この問題を解決するために、準最適量子アルゴリズムが提案されている。量子クエリの複雑性は$sqrtn cdot 2O(sqrtlog n)$であることを示す。
参考スコア（独自算出の注目度）: 3.1157817010763136
License:
Abstract: Lexicographically minimal string rotation is a fundamental problem in string processing that has recently garnered significant attention in quantum computing. Near-optimal quantum algorithms have been proposed for solving this problem, utilizing a divide-and-conquer structure. In this note, we show that its quantum query complexity is $\sqrt{n} \cdot 2^{O(\sqrt{\log n})}$, improving the prior result of $\sqrt{n} \cdot 2^{(\log n)^{1/2+\varepsilon}}$ due to Akmal and Jin (SODA 2022). Notably, this improvement is quasi-polylogarithmic, which is achieved by only logarithmic level-wise optimization using fault-tolerant quantum minimum finding.
Abstract（参考訳）: 語彙的に最小限の弦の回転は、最近量子コンピューティングにおいて大きな注目を集めている文字列処理の基本的な問題である。この問題の解法として、配位・対数構造を用いた準最適量子アルゴリズムが提案されている。ここでは、量子クエリの複雑性が$\sqrt{n} \cdot 2^{O(\sqrt{\log n})}$であることを示し、Akmal と Jin (SODA 2022) による $\sqrt{n} \cdot 2^{(\log n)^{1/2+\varepsilon}}$ の事前結果を改善する。特に、この改善は準多元性であり、フォールトトレラントな量子最小値探索を用いた対数レベルの最適化のみによって達成される。

関連論文リスト

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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。