論文の概要: Shor's algorithm requires Fanout

• arxiv url: http://arxiv.org/abs/2608.06703v1
• Date: Fri, 07 Aug 2026 02:00:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-10 16:21:25.326277
• Title: Shor's algorithm requires Fanout
• Title（参考訳）: ShorのアルゴリズムはFanoutを必要とする
• Authors: Lucas Gretta, Malvika Raj Joshi,
• Abstract要約: 我々は、任意の$n$-qubit modulusに対して、QFTを一定の深さで近似するには、必ずしも$n$-qubit Fanout演算が必要であることを示す。 我々は、$mathsfQFT_q$ gate を用いて、無視できないフェリニティの状態を構築することで、この逆を証明する。 Shor'sのような$q = 2n$の場合、単一の$mathsfQFT_2n$ gateを使って$mathsfFANOUT_n$を近似する。
• 参考スコア（独自算出の注目度）: 0.14323566945483496
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Shor's algorithm is a canonical quantum supremacy target whose core operation relies on the Quantum Fourier Transform (QFT). We resolve an open question of Fang, Fenner, Green, Homer and Zhang from 2006 by showing that approximating QFT in constant depth, for any $n$-qubit modulus, necessarily requires the $n$-qubit Fanout operation. Formally, let $\mathsf{QFT}_q$ be the gate acting on $n = \lceil \log q \rceil$ qubits that computes the QFT under modulus $q$. It is known that any $n$-qubit $\mathsf{QFT}_q$ can be implemented in constant depth using $\mathsf{FANOUT}_n$, i.e. $\mathsf{QFT}_q \in \mathsf{QAC}^0_f$. We prove the converse by using a $\mathsf{QFT}_q$ gate to construct a state of ``non-negligible felinity". Consequently, $\mathsf{QFT}_q \in \mathsf{QAC}^0 \iff \mathsf{FANOUT}_n \in \mathsf{QAC^0}$. In the case of $q = 2^n$, such as in Shor's, we approximate $\mathsf{FANOUT}_n$ using a single $\mathsf{QFT}_{2^n}$ gate and $O(1)$ two-qubit local gates, thus tying the feasibility of realizing Shor's algorithm with NISQ circuits to that of Fanout.
• Abstract（参考訳）: Shorのアルゴリズムは量子フーリエ変換(QFT)に依存する正準量子超越ターゲットである。 我々は2006年のFang, Fenner, Green, Homer, Zhang のオープンな質問を解決し、QFT を一定の深さで近似すると、任意の$n$-qubit modulus に対して、必然的に$n$-qubit Fanout 演算が必要になることを示す。 正式には、$\mathsf{QFT}_q$ を$n = \lceil \log q \rceil$ qubits に作用するゲートとし、q$ で QFT を計算する。 任意の$n$-qubit $\mathsf{QFT}_q$は、$\mathsf{FANOUT}_n$、すなわち$\mathsf{QFT}_q \in \mathsf{QAC}^0_f$を用いて一定の深さで実装できることが知られている。 逆は $\mathsf{QFT}_q$ gate を用いて ``非無視性フェリニティの状態を構築することによって証明する。 したがって、$\mathsf{QFT}_q \in \mathsf{QAC}^0 \iff \mathsf{FANOUT}_n \in \mathsf{QAC^0}$である。 Shor'sのような$q = 2^n$の場合、$\mathsf{FANOUT}_n$を1つの$\mathsf{QFT}_{2^n}$ gateと$O(1)$ 2-qubitローカルゲートで近似することにより、ShorのアルゴリズムをNISQ回路で実現することが可能となる。

関連論文リスト

• $\mathsf{QAC}^0$ Contains $\mathsf{TC}^0$ (with Many Copies of the Input) [0.9023122463034333]
  $mathsfQAC0$は、任意の単一量子ビットゲートと一般化されたトフォリゲートから構成される定数深さ量子回路のクラスである。 我々は、$mathsfQAC0$回路が従来の回路よりもはるかに強力であることを示す。
  論文  参考訳（メタデータ） (2026-01-06T18:40:44Z)
• A Faster Quantum Fourier Transform [0.0]
  本稿では,量子フーリエ変換(QFT)を高精度かつ近似的に実装するアルゴリズムについて述べる。 量子ビットの2つの分割に再帰するQFTの新たな定式化を活用することで、これらのコストを削減することができることを示す。
  論文  参考訳（メタデータ） (2025-01-19T06:18:52Z)
• Quantum Sabotage Complexity [0.7812210699650152]
  ここでは$mathsfQ(f_mathsfsab)$を示し、$f_mathsfsab$の量子クエリ複雑性を示す。 f$がインデックス関数であるとき、$mathsfQ(f_mathsfsab)=Theta(sqrtmathsfsab)$は、$mathsfQ(f_mathsfsab)=Theta(sqrtmathsf)の可能性を除外する。
  論文  参考訳（メタデータ） (2024-08-22T17:57:58Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• SQ Lower Bounds for Learning Bounded Covariance GMMs [46.289382906761304]
  P= sum_i=1k w_i MathcalN(boldsymbol mu_i,mathbf Sigma_i)$ という形で、分離されたガウスの混合を $mathbbRd$ で学習することに焦点を当てる。 この問題に対する統計的クエリ(SQ)アルゴリズムは、少なくともdOmega (1/epsilon)$の複雑さを必要とすることを証明している。
  論文  参考訳（メタデータ） (2023-06-22T17:23:36Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• StoqMA meets distribution testing [0.0]
  We provide a novel connection between $mathsfStoqMA$ and distribution testing via reversible circuits。 いずれの変種も$mathsfStoqMA$は、任意の無作為な乱数ビットと完全音性を持たず、$mathsfNP$に含まれることを示す。 我々の結果は、$mathsfMA subseteq mathsfStoqMA subseteq mathsfSBP$ [BBT06]という階層構造を崩壊させる一歩を踏み出した。
  論文  参考訳（メタデータ） (2020-11-11T12:30:42Z)

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

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