論文の概要: Quantum exact search with adjustable parameters and its applications
- arxiv url: http://arxiv.org/abs/2210.12644v1
- Date: Sun, 23 Oct 2022 07:53:57 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-18 09:56:38.943851
- Title: Quantum exact search with adjustable parameters and its applications
- Title（参考訳）: 調整可能なパラメータを用いた量子完全探索とその応用
- Authors: Guanzhong Li and Lvzhou Li
- Abstract要約: Groverのアルゴリズムは、非構造化データベース内のマークされた要素を探すために、古典的なアルゴリズムよりも2次的なスピードアップを提供する。
本稿では,ブロッホ球面上の固定軸の周りで幾何学的に回転すると考えられるパラメータを調整可能な探索フレームワークを提案する。
- 参考スコア（独自算出の注目度）: 0.2741266294612775
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Grover's algorithm provides a quadratic speedup over classical algorithms to
search for marked elements in an unstructured database. When it is known
beforehand there are $M$ marked elements in $N$ elements, there exist several
schemes to achieve the exact version that returns a marked element with
certainty, by using the generalized Grover's iteration
$G(\alpha,\beta):=S_r(\beta)\, S_o(\alpha)$, where the phase oracle
$S_o(\alpha)$ multiplies a marked state by $e^{i\alpha}$, and the phase
rotation $S_r(\beta)$ multiplies the initial state $\ket{\psi_0}$ (an
equal-superposition of all states) by $e^{-i\beta}$. However, in all the
existing schemes the value range of $\alpha$ and $\beta$ is limited; for
instance, in the three early schemes $\alpha$ and $\beta$ are determined by
$M/N$.
Thus, a natural question arises: {\it Given the phase oracle $S_o(\alpha)$
with an arbitrary angle $\alpha$, or the phase rotation $S_r(\beta)$ with an
arbitrary angle $\beta$, can we always construct an exact search algorithm
without sacrificing the quadratic speedup advantage?} The significance of this
problem lies not only in the expansion of mathematical form, but also in its
application value. We answer the question affirmatively, by presenting a search
framework with adjustable parameters. Technically, we propose the {\it
fixed-axis-rotation (FXR) method} where each iteration of the search algorithm
can be geometrically seen as rotating about a fixed axis on the Bloch sphere.
Furthermore, two applications of the proposed search framework are developed:
the first is to learn exactly the secret string hidden by the Hamming distance
oracle, and the other to solve the element distinctness promise problem
deterministically. The two applications correspond to the two different cases
where $\alpha$ or $\beta$ is fixed respectively.
- Abstract（参考訳）: グローバーのアルゴリズムは、非構造化データベースのマークされた要素を検索するために、古典的なアルゴリズムの二次的な高速化を提供する。
前述した通り、$M$のマーク要素が$N$要素の中に存在するとき、一般化したGroverの反復である$G(\alpha,\beta):=S_r(\beta)\, S_o(\alpha)$, ここで、相 oracle $S_o(\alpha)$ がマークされた状態を $e^{i\alpha}$ で乗算し、相回転 $S_r(\beta)$ が初期状態$\ket{\psi_0}$(全ての状態の等しい仮定)を$e^{i\beta}$ で乗算することにより、確実性でマークされた要素を返す正確なバージョンを達成するためのスキームが存在する。
しかし、既存のスキームでは$\alpha$と$\beta$の値範囲は限られており、初期の3つのスキームでは$\alpha$と$\beta$は$m/n$で決定される。
したがって、自然な疑問が生じる: 任意の角度の位相オラクル $S_o(\alpha)$ または任意の角度の位相回転 $S_r(\beta)$ が与えられると、二次スピードアップの利点を犠牲にすることなく、常に正確な探索アルゴリズムを構築することができるか?
} この問題の重要さは、数学的形式の拡大だけでなく、その応用価値にも関係している。
我々は,パラメータを調整可能な検索フレームワークを提示することにより,質問に肯定的に答える。
技術的には,探索アルゴリズムの各反復を,ブロッホ球面上の固定軸に回転するものとして幾何学的に見ることのできる固定軸回転法(FXR)を提案する。
さらに,提案手法の2つの応用として,ハミング距離オラクルに隠された秘密文字列を正確に学習すること,および,その要素の明瞭度を決定論的に解くことの2つを開発した。
2つのアプリケーションは、それぞれ$\alpha$と$\beta$を固定する2つの異なるケースに対応している。
関連論文リスト
- Quantum linear system algorithm with optimal queries to initial state preparation [0.0]
線形システムの量子アルゴリズムは、2つのオラクルを問合せして解状態$A-1|brangle$を生成する。
本稿では,$mathbfThetaleft (1/sqrtpright)$クエリを$O_b$に変換する量子線形系アルゴリズムを提案する。
微分方程式の解法のような様々な応用において、ブロックプレコンディショニングスキームを用いて$p$への依存をさらに改善することができる。
論文 参考訳（メタデータ） (2024-10-23T18:00:01Z) - LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
任意の$K$に対して、$n$とは独立に「普遍集合」$Uサブセット[n]$が存在し、任意の$Q$と任意の行$i$に対して、大きな注目スコアが$A_i,j$ in row $i$ of $A$は全て$jin U$を持つことを示す。
我々は、視覚変換器のスキームの利点を実証的に示し、トレーニング中に我々の普遍的なセットを使用する新しいモデルのトレーニング方法を示した。
論文 参考訳（メタデータ） (2024-10-07T19:47:13Z) - Solving Dense Linear Systems Faster Than via Preconditioning [1.8854491183340518]
我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$であることを示す。
特に、我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$である。
主アルゴリズムはランダム化ブロック座標降下法とみなすことができる。
論文 参考訳（メタデータ） (2023-12-14T12:53:34Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - 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) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。
実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文 参考訳（メタデータ） (2021-05-17T16:40:48Z) - Leveraging Unknown Structure in Quantum Query Algorithms [0.0]
本研究では,事前の約束がなくても,これらのスピードアップが持続することを示すために,修正されたスパンプログラムアルゴリズムを示す。
我々のアルゴリズムは、$tildeO(sqrtkn)$クエリを使って、少なくとも$k$のエッジを持つパスがある場合、この問題を解決する。
論文 参考訳（メタデータ） (2020-12-02T15:32:52Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Problem-Complexity Adaptive Model Selection for Stochastic Linear
Bandits [20.207989166682832]
2つの一般的な線形バンディット設定におけるモデル選択の問題について考察する。
まず、[K]$におけるarm $iの平均的な報酬は、$mu_i+ langle alpha_i,t,theta*|$である。
我々は、ALBが$O(|theta*|sqrtT)$の後悔のスケーリングを達成することを示す。
論文 参考訳（メタデータ） (2020-06-04T02:19:00Z) - Fast digital methods for adiabatic state preparation [0.0]
ゲート型量子コンピュータにおいて,逆誤差の複雑多元対数を伴う断熱状態生成のための量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-04-08T18:00:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。