論文の概要: 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つの異なるケースに対応している。
関連論文リスト
- On the Complexity of First-Order Methods in Stochastic Bilevel
Optimization [9.649991673557167]
両レベル最適化における定常点を求める問題は、下層問題に制約がなく、強い凸がある場合に考慮する。
既存のアプローチは、それらの分析を低レベルの解を知っているジェニーアルゴリズムに結びつける。
我々は、$O(epsilon-6), O(epsilon-4)$ 1次$y*$-aware oraclesを使って、$epsilon$固定点に収束する単純な一階法を提案する。
論文 参考訳(メタデータ) (2024-02-11T04:26:35Z) - Solving Dense Linear Systems Faster than via Preconditioning [15.781447266000159]
我々のアルゴリズムは$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) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳(メタデータ) (2020-06-06T13:34:41Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。