論文の概要: The true cost of factoring: Linking magic and number-theoretic complexity in Shor's algorithm

• arxiv url: http://arxiv.org/abs/2605.05347v1
• Date: Wed, 06 May 2026 18:16:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-08 22:27:11.36952
• Title: The true cost of factoring: Linking magic and number-theoretic complexity in Shor's algorithm
• Title（参考訳）: ファクタリングの真のコスト:ショアのアルゴリズムにおけるマジックと数論的な複雑さのリンク
• Authors: Alessio Paviglianiti, Matteo Seclì, Emanuele Tirrito, Vincenzo Savona,
• Abstract要約: パラメタカルショアのファクタリングアルゴリズムにおける非安定化性(またはマジック)の生成について検討する。 明示的な解析理論を開発することにより,アルゴリズムの実行を成功させる上でのマジックの基本的役割を実証する。 本研究は,タスクの古典的アルゴリズム的難易度と,量子ハードウェア上での非安定化器価格との間に,簡潔な概念的リンクを生じさせるものである。
• 参考スコア（独自算出の注目度）: 0.18665975431697432
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The execution cost of quantum algorithms is typically quantified through asymptotic gate counts and qubit register sizes, yet these metrics do not directly capture which genuinely quantum resources, and in what amount, must be created and maintained for the computation to succeed. The systematic quantification of such information-theoretic requirements in quantum computing protocols remains an extremely challenging open problem, despite their direct role in establishing quantum advantage. To address this gap, we investigate the generation of non-stabilizerness (or magic), one of the key resources, in the paradigmatic Shor's factoring algorithm, revealing a deep connection between intrinsic quantum complexity and the computational hardness of the underlying number-theoretic problem. By developing an explicit analytic theory, we demonstrate the fundamental role of magic in the successful execution of the algorithm, and show that Shor's routine maximally exploits the quantum resource in practically relevant regimes. Our findings create a concise conceptual link between the classical algorithmic difficulty of a task and the non-stabilizer price to solve it on quantum hardware, complementing standard circuit-cost analyses with a resource-based metric that is naturally aligned with the real bottlenecks of fault-tolerant quantum computing.
• Abstract（参考訳）: 量子アルゴリズムの実行コストは、典型的には漸近ゲート数と量子ビットレジスタサイズによって定量化されるが、これらのメトリクスは、真に量子的なリソースを直接キャプチャするわけではなく、その計算が成功するためには、どの量が生成され、維持されなければならない。 量子コンピューティングプロトコルにおけるそのような情報理論的な要求の体系的な定量化は、量子優位性を確立する上で直接の役割があるにもかかわらず、非常に困難なオープンな問題である。 このギャップに対処するために、Shorの因果分解アルゴリズムにおいて、鍵となる資源の一つである非安定化器性(または魔法)の生成について検討し、本質的な量子複雑性と基礎となる数理論問題の計算硬度との深い関係を明らかにする。 明示的な解析理論を開発することにより、アルゴリズムの実行を成功させる上でのマジックの基本的役割を実証し、Shorのルーチンが実際に関連する状況下で量子資源を最大限に活用していることを示す。 本研究は,古典的アルゴリズムの難易度と,量子ハードウェア上での非安定化器価格との間には,従来の回路コスト分析を,フォールトトレラント量子コンピューティングの真のボトルネックと自然に整合したリソースベースの計量で補完する,簡潔な概念的リンクを構築した。

関連論文リスト

• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [62.46800898243033]
  量子学習理論の最近の進歩は、様々な古典的な入力によって生成された測定データから、大きな量子ビット回路の線形特性を効率的に学習できるのか? 我々は、小さな予測誤差を達成するためには、$d$で線形にスケーリングするサンプルの複雑さが必要であることを証明し、それに対応する計算複雑性は、dで指数関数的にスケールする可能性がある。 そこで本研究では,古典的影と三角展開を利用したカーネルベースの手法を提案し,予測精度と計算オーバーヘッドとのトレードオフを制御可能とした。
  論文  参考訳（メタデータ） (2024-08-22T08:21:28Z)
• Unitary Complexity and the Uhlmann Transformation Problem [39.6823854861458]
  本稿では, 単項合成問題の枠組みを導入し, 還元と単項複雑性クラスについて考察する。 このフレームワークは、ある絡み合った状態が局所的な操作によって別の状態に変換される複雑さを研究するのに使用します。 そこで我々は,多くの自然量子情報処理タスクの計算複雑性を研究するための新しい手法を提案する。
  論文  参考訳（メタデータ） (2023-06-22T17:46:39Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。 提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
  論文  参考訳（メタデータ） (2023-04-18T11:57:15Z)
• Learning the Complexity of Weakly Noisy Quantum States [0.5662299435213419]
  ターゲット量子状態の古典的シャドウ表現を利用して、弱雑音量子状態の回路複雑性を予測する。 本研究は,学習アルゴリズムと量子状態複雑性の橋渡しを行い,量子状態の固有特性を特徴付ける学習アルゴリズムのパワーを強調した。
  論文  参考訳（メタデータ） (2023-03-31T06:02:44Z)
• Circuit Symmetry Verification Mitigates Quantum-Domain Impairments [69.33243249411113]
  本稿では,量子状態の知識を必要とせず,量子回路の可換性を検証する回路指向対称性検証を提案する。 特に、従来の量子領域形式を回路指向安定化器に一般化するフーリエ時間安定化器(STS)手法を提案する。
  論文  参考訳（メタデータ） (2021-12-27T21:15:35Z)
• Quantum amplitude damping for solving homogeneous linear differential equations: A noninterferometric algorithm [0.0]
  本研究は,同種LDEを解くための効率的な量子アルゴリズムを構築するために,量子振幅減衰演算を資源として利用する新しい手法を提案する。 このようなオープンな量子系にインスパイアされた回路は、非干渉法で解の実際の指数項を構成することができることを示す。
  論文  参考訳（メタデータ） (2021-11-10T11:25:32Z)
• Synthesis of Quantum Circuits with an Island Genetic Algorithm [44.99833362998488]
  特定の演算を行うユニタリ行列が与えられた場合、等価な量子回路を得るのは非自明な作業である。 量子ウォーカーのコイン、トフォリゲート、フレドキンゲートの3つの問題が研究されている。 提案したアルゴリズムは量子回路の分解に効率的であることが証明され、汎用的なアプローチとして、利用可能な計算力によってのみ制限される。
  論文  参考訳（メタデータ） (2021-06-06T13:15:25Z)
• Resource-efficient encoding algorithm for variational bosonic quantum simulations [0.0]
  量子コンピューティングのノイズ中間スケール量子(NISQ)時代には、量子資源は限られている。 ボゾン基底と励起状態計算のための資源効率のよい量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-02-23T19:00:05Z)

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

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