Fugu-MT 論文翻訳(概要): Improved Algorithm and Lower Bound for Variable Time Quantum Search

論文の概要: Improved Algorithm and Lower Bound for Variable Time Quantum Search

arxiv url: http://arxiv.org/abs/2302.06749v2
Date: Wed, 3 May 2023 07:12:32 GMT
ステータス: 処理完了
システム内更新日: 2023-05-04 17:53:43.081578
Title: Improved Algorithm and Lower Bound for Variable Time Quantum Search
Title（参考訳）: 可変時間量子探索のための改良アルゴリズムと低境界
Authors: Andris Ambainis, Martins Kokainis, Jevg\=enijs Vihrovs
Abstract要約: 変数時間探索は、異なる項目に対するクエリに異なる時間を要する量子探索の形式である。我々の最初の結果は、複雑さの$O(sqrtTlog n)$で可変時間探索を行う新しい量子アルゴリズムである。 2つ目の結果は、$Omega(sqrtTlog T)$の量子下界である。
参考スコア（独自算出の注目度）: 1.2246649738388389
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We study variable time search, a form of quantum search where queries to different items take different time. Our first result is a new quantum algorithm that performs variable time search with complexity $O(\sqrt{T}\log n)$ where $T=\sum_{i=1}^n t_i^2$ with $t_i$ denoting the time to check the $i$-th item. Our second result is a quantum lower bound of $\Omega(\sqrt{T\log T})$. Both the algorithm and the lower bound improve over previously known results by a factor of $\sqrt{\log T}$ but the algorithm is also substantially simpler than the previously known quantum algorithms.
Abstract（参考訳）: 変数時間探索は、異なる項目に対するクエリに異なる時間を要する量子探索の形式である。我々の最初の結果は、複雑さを持つ変数時間探索を行う新しい量子アルゴリズムである$O(\sqrt{T}\log n)$ where $T=\sum_{i=1}^n t_i^2$ with $t_i$。 2つ目の結果は、$\Omega(\sqrt{T\log T})$の量子下界である。アルゴリズムと下限は、従来知られていた結果に対して$\sqrt{\log t}$という係数で改善されるが、アルゴリズムは従来知られていた量子アルゴリズムよりも大幅に単純である。

関連論文リスト

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)
Replicable Learning of Large-Margin Halfspaces [46.91303295440005]
我々は,大マージンハーフスペースを学習する問題に対して,効率的なアルゴリズムを提供する。 Impagliazzo, Lei, Pitassi, Sorrellによるアルゴリズム [STOC 2022] の改良を行った。
論文参考訳（メタデータ） (2024-02-21T15:06:51Z)
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)
A Note on Quantum Divide and Conquer for Minimal String Rotation [1.8275108630751844]
語彙的に最小限の弦の回転は、弦処理の基本的な問題である。準最適量子アルゴリズムは、その開発中に提案され、量子分割や征服といった新しいアイデアが導入された。
論文参考訳（メタデータ） (2022-10-17T14:51:49Z)
Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文参考訳（メタデータ） (2022-06-07T18:00:01Z)
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)
Asymptotically Optimal Circuit Depth for Quantum State Preparation and General Unitary Synthesis [24.555887999356646]
この問題は量子アルゴリズム設計、ハミルトニアンシミュレーション、量子機械学習において基本的な重要性を持っているが、その回路深さと大きさの複雑さは、アシラリー量子ビットが利用可能である時点では未解決のままである。本稿では,$psi_vrangle$を奥行きで作成できる$m$Acillary qubitsを用いた量子回路の効率的な構築について検討する。我々の回路は決定論的であり、状態を準備し、正確にユニタリを実行し、アシラリー量子ビットを厳密に利用し、深さは幅広いパラメータ状態において最適である。
論文参考訳（メタデータ） (2021-08-13T09:47:11Z)
Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
論文参考訳（メタデータ） (2021-05-18T06:51:11Z)
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)
Resonant Quantum Search with Monitor Qubits [0.0]
連続的ハミルトニアンと共振を利用した一般化探索問題($N$項目中$k$マークされた項目を探索する)のアルゴリズムを提案する。この共振アルゴリズムはGroverアルゴリズムと同じ時間複雑性$O(sqrtN/k)$を持つ。
論文参考訳（メタデータ） (2020-02-21T19:31:34Z)

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