論文の概要: Truncated Modular Exponentiation Operators: A Strategy for Quantum Factoring

• arxiv url: http://arxiv.org/abs/2405.17021v2
• Date: Thu, 6 Jun 2024 11:36:36 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-07 20:13:39.056525
• Title: Truncated Modular Exponentiation Operators: A Strategy for Quantum Factoring
• Title（参考訳）: Trncated Modular Exponentiation Operators: A Strategy for Quantum Factoring
• Authors: Robert L. Singleton Jr,
• Abstract要約: 本稿では、ワークレジスタが$vert 1 rangle$で始まるという単純な観察に依存するME演算子を構築する方法を提案する。 しかし、ME演算子は極めて寛容であり、レベルが省略された近似形式は、正確な演算子と同様に、要因を抽出できることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Modular exponentiation (ME) operators are one of the fundamental components of Shor's algorithm, and the place where most of the quantum resources are deployed. I propose a method for constructing the ME operators that relies upon the simple observation that the work register starts in state $\vert 1 \rangle$. Therefore, we do not have to create an ME operator $U$ that accepts a general input, but rather, one that takes an input from the periodic sequence of states $\vert f(x) \rangle$ for $x \in \{0, 1, \cdots, r-1\}$, where $f(x)$ is the ME function with period $r$. The operator $U$ can be partitioned into $r$ levels, where the gates in level $x \in \{0, 1, \cdots, r-1\}$ increment the state $\vert f(x) \rangle$ to the state $\vert f(x+1) \rangle$. The gates below $x$ do not affect the state $\vert f(x+1) \rangle$. The obvious problem with this method is that it is self-defeating: If we knew the operator $U$, then we would know the period $r$ of the ME function, and there would be no need for Shor's algorithm. I show, however, that the ME operators are very forgiving, and truncated approximate forms in which levels have been omitted are able to extract factors just as well as the exact operators. I demonstrate this by factoring the numbers $N = 21, 33, 35, 143, 247$ by using less than half the requisite number of levels in the ME operators. This procedure works because the method of continued fractions only requires an approximate phase value. This is the basis for a factorization strategy in which we fill the circuits for the ME operators with more and more gates, and the correlations between the various composite operators $U^p$ (where $p$ is a power of two) compensate for the missing levels.
• Abstract（参考訳）: Modular Exponentiation (ME) 演算子はShorアルゴリズムの基本的な構成要素の1つであり、ほとんどの量子リソースがデプロイされる場所である。 本稿では、作業レジスタが状態$\vert 1 \rangle$から始まるという単純な観察に依存するME演算子を構築する方法を提案する。 したがって、一般的な入力を受け入れるME演算子$U$を作成する必要はないが、代わりに、状態の周期列$\vert f(x) \rangle$ for $x \in \{0, 1, \cdots, r-1\}$に対して$f(x)$は周期$r$を持つME関数である。 演算子$U$は$r$レベルに分割することができ、レベル$x \in \{0, 1, \cdots, r-1\}$のゲートは状態$\vert f(x) \rangle$を状態$\vert f(x+1) \rangle$にインクリメントする。 x$ 以下のゲートは状態 $\vert f(x+1) \rangle$ に影響しない。 もし演算子$U$を知っていたら、ME関数の期間$r$を知っていて、Shorのアルゴリズムは必要ないでしょう。 しかし、ME演算子は極めて寛容であり、レベルが省略された近似形式は、正確な演算子と同様に、要因を抽出できることを示す。 私はこれを、ME演算子の要求レベルの半分以下を使用することで、$N = 21, 33, 35, 143, 247$の数値を分解して示します。 この手順は連続分数法が近似位相値のみを必要とするため機能する。 これは、ME演算子の回路をより多くのゲートで埋める分解戦略の基礎であり、様々な合成演算子$U^p$($p$は2のパワーである)間の相関は、不足レベルを補う。

関連論文リスト

• Limit formulas for norms of tensor power operators [49.1574468325115]
  作用素 $phi:Xrightarrow Y$ がバナッハ空間の間に与えられると、そのテンソルパワーを考える。 k$ 根を取ると、$phiotimes k$ の作用素ノルムが 2$ 支配ノルムに収束することを示す。
  論文  参考訳（メタデータ） (2024-10-30T14:39:21Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Hardness of Low Rank Approximation of Entrywise Transformed Matrix Products [9.661328973620531]
  自然言語処理における高速アルゴリズムにインスパイアされ、エントリ変換された設定における低階近似について研究する。 我々は、平坦なスパースベクトルのレバレッジスコアの低境界に依存するStrong Exponential Time hypothesis (SETH) から、新しい還元を与える。 我々の低階アルゴリズムは行列ベクトルに依存しているため、我々の下限は、小さな行列に対してさえも$f(UV)W$は$Omega(n2-o(1))$時間を必要とすることを示すために拡張される。
  論文  参考訳（メタデータ） (2023-11-03T14:56:24Z)
• Spectral theory of $p$-adic unitary operator [0.0]
  U$のスペクトル分解は$psi$が$p$進波動関数であるときに完了する。 $mathbbQ_p$ のアーベル拡大理論は、$p$-進ユニタリ作用素の位相的性質と結びついている。
  論文  参考訳（メタデータ） (2023-10-18T19:04:06Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• Basic quantum subroutines: finding multiple marked elements and summing numbers [1.1265248232450553]
  量子クエリーの最適数$O(sqrtN k)$を用いて、サイズ$N$のリスト内のすべての$k$マーク要素を見つける方法を示す。
  論文  参考訳（メタデータ） (2023-02-20T19:11:44Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。 我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
  論文  参考訳（メタデータ） (2022-02-10T16:10:41Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Fast digital methods for adiabatic state preparation [0.0]
  ゲート型量子コンピュータにおいて,逆誤差の複雑多元対数を伴う断熱状態生成のための量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-04-08T18:00:01Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。