論文の概要: The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth

• arxiv url: http://arxiv.org/abs/2412.12558v1
• Date: Tue, 17 Dec 2024 05:34:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-18 13:57:20.091852
• Title: The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth
• Title（参考訳）: ヤコビファクタリング回路:ニアリニアゲートとサブリニア空間と深さを持つ量子ファクタリング
• Authors: Gregory D. Kahanamoku-Meyer, Seyoon Ragavan, Vinod Vaikuntanathan, Katherine Van Kirk,
• Abstract要約: 本稿では、古典的硬さがRSAと同値であると期待されているものを含む、整数の大規模なクラスを分解する小型量子回路を提案する。 我々の知る限り、古典的にハードなファクタリング問題に対して、サブ線形量子ビットカウントを達成した初めてのMod-time回路である。 We build on the quantum algorithm found by Li, Peng, Du and Suter (Nature Scientific Reports 2012) which instead on computing the Jacobi symbol in quantum superposition。
• 参考スコア（独自算出の注目度）: 8.938538037322381
• License:
• Abstract: We present a compact quantum circuit for factoring a large class of integers, including some whose classical hardness is expected to be equivalent to RSA (but not including RSA integers themselves). To our knowledge, it is the first polynomial-time circuit to achieve sublinear qubit count for a classically-hard factoring problem; the circuit also achieves sublinear depth and nearly linear gate count. We build on the quantum algorithm for squarefree decomposition discovered by Li, Peng, Du and Suter (Nature Scientific Reports 2012), which relies on computing the Jacobi symbol in quantum superposition. Our circuit completely factors any number $N$, whose prime decomposition has distinct exponents, and finds at least one non-trivial factor if not all exponents are the same. In particular, to factor an $n$-bit integer $N=P^2 Q$ (with $P$ and $Q$ prime, and $Q<2^m$ for some $m$), our circuit uses $\tilde{O}(m)$ qubits and has depth at most $\tilde{O}(m + n/m)$, with $\tilde{O}(n)$ quantum gates. When $m=\Theta(n^a)$ with $2/3 < a < 1$, the space and depth are sublinear in $n$, yet no known classical algorithms exploit the relatively small size of $Q$ to run faster than general-purpose factoring algorithms. We thus believe that factoring such numbers has potential to be the most concretely efficient classically-verifiable proof of quantumness currently known. The technical core of our contribution is a new space-efficient and parallelizable quantum algorithm to compute the Jacobi symbol of $A$ mod $B$, in the regime where $B$ is classical and much larger than $A$. In the context of the larger Jacobi algorithm for factoring $N = P^2Q$, this reduces the overall qubit count to be roughly proportional to the length of $Q$, rather than the length of $N$. Finally, we note that our circuit for computing the Jacobi symbol generalizes to related problems, such as computing the GCD.
• Abstract（参考訳）: 古典的硬さがRSAと同値であると予想されるもの(RSA整数自身は含まない)を含む、整数の大規模なクラスを分解するためのコンパクト量子回路を提案する。 我々の知る限り、古典的にハードなファクタリング問題に対してサブ線形量子ビット数を達成するのは初めての多項式時間回路であり、回路はまた、サブ線形深さとほぼ線形ゲート数も達成している。 我々は、Li, Peng, Du and Suter (Nature Scientific Reports 2012)によって発見された2乗分解のための量子アルゴリズムを構築し、量子重ね合わせにおけるヤコビ記号の計算に依存する。 我々の回路は、素分解が異なる指数を持つ任意の数$N$を完全に決定し、すべての指数が同じでない場合、少なくとも1つの非自明な因子を見つける。 特に$n$-bit整数$N=P^2 Q$($P$と$Q$素数、$Q<2^m$ for some $m$)を分解するために、我々の回路は$\tilde{O}を使用する。 (m)$ qubits で、最大$\tilde{O}(m + n/m)$、$\tilde{O} の深さを持つ。 (n)$量子ゲート。 m=\Theta(n^a)$が2/3 < a < 1$のとき、空間と深さは$n$のサブ線形となるが、既知の古典的アルゴリズムでは、一般的な因数分解アルゴリズムよりも高速に走るために、比較的小さな$Q$を利用する。 したがって、そのような数を分解することは、現在知られている量子性の最も具体的な古典的に検証可能な証明である可能性があると信じている。 我々の貢献の技術的コアは、A$mod$B$のヤコビ記号を計算するための空間効率で並列化可能な新しい量子アルゴリズムである。 これは、$N = P^2Q$ を分解するより大きなヤコビアルゴリズムの文脈において、全体の qubit 数は、$N$ の長さではなく、$Q$ の長さに大まかに比例する。 最後に、ヤコビ記号の計算回路は、GCDの計算などの関連する問題に一般化されていることに留意する。

関連論文リスト

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Fast quantum integer multiplication with zero ancillas [0.5755004576310334]
  我々は,ゼロアンシラ量子ビットを用いた準四進時間量子乗法の新しいパラダイムを導入する。 関連するキュービットは入力と出力レジスタ自身のみである。 我々のアルゴリズムは、実際的な問題の大きさよりも優れている可能性がある。
  論文  参考訳（メタデータ） (2024-03-26T18:00:03Z)
• Do you know what q-means? [50.045011844765185]
  クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。 クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。 また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
  論文  参考訳（メタデータ） (2023-08-18T17:52:12Z)
• An Efficient Quantum Factoring Algorithm [0.27195102129094995]
  我々は、$tildeO(n3/2)$の量子回路を独立に実行することで、$n$bit整数を分解できることを示した。 アルゴリズムの正しさは、指数的古典的因数分解アルゴリズムで使われるものに似た数論的な仮定に依存する。
  論文  参考訳（メタデータ） (2023-08-12T13:57:38Z)
• An Efficient Quantum Decoder for Prime-Power Fields [1.0878040851638]
  ブロックサイズ$n$に対して$p$が小さい$q = pm$の場合、時間内の問題を解く量子アルゴリズムが存在することを示す。 一方、古典的アルゴリズムはこの問題をはるかに小さな逆因子に対してのみ効率的に解くことができる。
  論文  参考訳（メタデータ） (2022-10-20T19:35:50Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。 異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。 我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
  論文  参考訳（メタデータ） (2022-06-07T18:00:01Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  量子順序付き二項決定図($OBDD$)モデルについて検討する。 入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。 read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
  論文  参考訳（メタデータ） (2022-04-22T12:37:56Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• Low-depth Quantum State Preparation [3.540171881768714]
  量子コンピューティングにおける重要なサブルーチンは、$N$複素数の古典的なデータを重ね合わせの$n=lceil logNrceil$-qubit状態の振幅にロードすることである。 ここでは、古典的データを用いた量子状態準備におけるこの時空トレードオフについて検討する。 我々は、$mathcal O(n2)$の回路深さを持つ量子アルゴリズムを提案し、任意の$N$複素数を符号化する。
  論文  参考訳（メタデータ） (2021-02-15T13:11:43Z)
• Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
  量子アルゴリズムの設計と回路下界の一般接続を確立する。 我々の証明は、学習理論、擬似ランダム性、計算複雑性に関するいくつかの研究に基づいている。
  論文  参考訳（メタデータ） (2020-12-03T14:03:20Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。 我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。 我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
  論文  参考訳（メタデータ） (2020-04-14T11:05:26Z)

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

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