論文の概要: Improved Algorithm and Lower Bound for Variable Time Quantum Search
- arxiv url: http://arxiv.org/abs/2302.06749v1
- Date: Mon, 13 Feb 2023 23:24:49 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-15 16:47:05.309709
- 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}$という係数で改善されるが、アルゴリズムは従来知られていた量子アルゴリズムよりも大幅に単純である。
関連論文リスト
- Replicable Learning of Large-Margin Halfspaces [50.330457600322084]
我々は,大マージンハーフスペースを学習する問題に対して,効率的なアルゴリズムを提供する。
Impagliazzo, Lei, Pitassi, Sorrellによるアルゴリズム [STOC 2022] の改良を行った。
論文 参考訳(メタデータ) (2024-02-21T15:06:51Z) - 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) - 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) - 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) - 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) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳(メタデータ) (2020-07-07T17:10:00Z) - Resonant Quantum Search with Monitor Qubits [0.0]
連続的ハミルトニアンと共振を利用した一般化探索問題($N$項目中$k$マークされた項目を探索する)のアルゴリズムを提案する。
この共振アルゴリズムはGroverアルゴリズムと同じ時間複雑性$O(sqrtN/k)$を持つ。
論文 参考訳(メタデータ) (2020-02-21T19:31:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。