論文の概要: The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth
- arxiv url: http://arxiv.org/abs/2412.12558v3
- Date: Thu, 05 Jun 2025 21:35:58 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-09 17:28:42.754322
- 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要約: 本稿では,整数のクラスを分解する小型量子回路を提案する。
P2 Q$ の形の $n$-bit 整数を $log Q = Theta(na)$ for $a in (2/3, 1) とする。
我々の回路は、Li, Peng, Du, Suter (Nature Scientific Reports 2012) によって発見された平方自由分解のための量子アルゴリズムに基づいており、これは量子重ね合わせにおけるヤコビ記号の計算に依存している。
- 参考スコア（独自算出の注目度）: 8.938538037322381
- License: http://creativecommons.org/licenses/by/4.0/
- 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). Most notably, we factor $n$-bit integers of the form $P^2 Q$ with $\log Q = \Theta(n^a)$ for $a \in (2/3, 1)$ in space and depth sublinear in n (specifically, $\tilde{O}(\log Q)$) using $\tilde{O}(n)$ quantum gates; for these integers, no known classical algorithms exploit the relatively small size of $Q$ to run asymptotically faster than general-purpose factoring algorithms. To our knowledge, this is the first polynomial-time circuit to achieve sublinear qubit count for a classically-hard factoring problem. We thus believe that factoring such numbers has potential to be the most concretely efficient classically-verifiable proof of quantumness currently known. Our circuit builds 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. The technical core of our contribution is a new space-efficient quantum algorithm to compute the Jacobi symbol of $A$ mod $B$, in the regime where $B$ is classical and much larger than $A$. Our circuit for computing the Jacobi symbol generalizes to related problems such as computing the greatest common divisor and modular inverses, and thus could be of independent interest.
- Abstract（参考訳）: 古典的硬さがRSAと同値であると予想されるもの(RSA整数自身は含まない)を含む、整数の大規模なクラスを分解するためのコンパクト量子回路を提案する。
最も注目すべきは、$P^2 Q$ with $\log Q = \Theta(n^a)$ for $a \in (2/3, 1)$ in space and depth sublinear in n (特に$\tilde{O}(\log Q)$) using $\tilde{O}(n)$ quantum gates; これらの整数に対して、既知の古典的アルゴリズムは、一般的な因子化アルゴリズムよりも漸近的に高速に$Q$の小さいサイズを利用する。
我々の知る限り、これは古典的にハードなファクタリング問題に対して線形量子ビットカウントを達成した最初の多項式時間回路である。
したがって、そのような数を分解することは、現在知られている量子性の最も具体的な古典的に検証可能な証明である可能性があると信じている。
我々の回路は、Li, Peng, Du, Suter (Nature Scientific Reports 2012) によって発見された平方自由分解のための量子アルゴリズムに基づいており、これは量子重ね合わせにおけるヤコビ記号の計算に依存している。
我々の貢献の技術的コアは、A$mod$B$のヤコビ記号を計算するための空間効率のよい新しい量子アルゴリズムである。
ヤコビ記号を計算するための回路は、最大公約数やモジュラー逆数などの関連する問題を一般化するので、独立した関心を持つことができる。
関連論文リスト
- 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) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳（メタデータ） (2023-05-09T20:53:27Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。