論文の概要: From Hilbert's Tenth Problem to Quantum Speedup: Explicit Oracles for Bounded Diophantine Systems

• arxiv url: http://arxiv.org/abs/2605.13980v1
• Date: Wed, 13 May 2026 18:01:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-16 00:43:04.072719
• Title: From Hilbert's Tenth Problem to Quantum Speedup: Explicit Oracles for Bounded Diophantine Systems
• Title（参考訳）: ヒルベルトの10番目の問題から量子スピードアップ: 境界ディオファンチン系におけるOracleの明示
• Authors: Gabriel Escrig, M. A. Martin-Delgado,
• Abstract要約: 我々は、有界整数領域上のディオファント方程式を解くために、完全に可逆的なアルゴリズムフレームワークを導入する。 抽象ブラックボックスの仮定を超えて、この明示的なアーキテクチャ合成は、必要な量子演算が有界なオーバーヘッドとして働くことを保証している。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Solving non-linear Diophantine systems lies at the mathematical core of integer optimization and cryptography. While the general unbounded problem is undecidable, even over bounded integer domains it remains classically intractable in the worst case. In this work, we introduce a fully reversible quantum algorithmic framework tailored to solve arbitrary polynomial Diophantine equations over bounded integer domains. The core of our approach is the explicit, gate-level synthesis of an evaluation oracle for amplitude amplification. By coherently evaluating polynomial constraints via in-place two's complement arithmetic and routing operations into a single recycled accumulator, this garbage-free strategy achieves a compact and scalable synthesis of the underlying non-linear arithmetic. Through analytical derivations and empirical circuit simulations, we prove that the overall spatial complexity is bounded by $q = \mathcal{O}((n + d^2)\log_2 N)$ logical qubits for $n$ variables, maximum degree $d$, and interval length $N$. The non-Clifford Toffoli depth is upper-bounded by $\mathcal{O}(q^2)$. This structural scaling exponent remains invariant to the variable count, modulated linearly only by the coefficients' Hamming weights. By moving beyond abstract black-box assumptions, this explicit architectural synthesis guarantees that the necessary quantum arithmetic acts as a bounded polynomial overhead. This ensures a quadratic speedup over classical exhaustive search, whether retrieving a unique assignment or dynamically enumerating an unknown number of solutions.
• Abstract（参考訳）: 非線型ディオファントス系を解くことは、整数最適化と暗号の数学的中心にある。 一般の非有界問題は決定不能であるが、有界な整数領域でさえ、最悪の場合、古典的に難解である。 本研究では、有界整数領域上の任意の多項式ディオファントイン方程式を解くために、完全に可逆な量子アルゴリズムフレームワークを導入する。 我々のアプローチの核心は振幅増幅のための評価オラクルの明示的でゲートレベルの合成である。 In-place 2の補数演算とルーティング演算を1つのリサイクルアキュムレータにコヒーレントに評価することにより、このガベージフリー戦略は、基礎となる非線形算術のコンパクトでスケーラブルな合成を実現する。 解析的導出と経験的回路シミュレーションにより、空間的複雑性は$q = \mathcal{O}((n + d^2)\log_2 N)$$$n$変数、最大次数$d$、インターバル長$N$で有界であることが証明される。 非クリフォードトフォリ深さは$\mathcal{O}(q^2)$で上界される。 この構造的スケーリング指数は変数数に不変であり、係数のハミング重みによってのみ線形に変調される。 抽象ブラックボックスの仮定を超えて、この明示的なアーキテクチャ合成は、必要な量子演算が有界多項式のオーバーヘッドとして作用することを保証している。 これにより、一意の代入を取得するか、未知の数の解を動的に列挙するかにかかわらず、古典的な徹底的な探索よりも2次的なスピードアップが保証される。

関連論文リスト

• Constant-Factor Improvements in Quantum Algorithms for Linear Differential Equations [0.4199844472131922]
  我々は、ハミルトニアンシミュレーションアルゴリズムの線形結合である有望な新しい量子微分方程式解法に対する定数係数境界を証明した。 我々の新しい公式は、少なくとも2桁の精度で従来の状態よりも改善され、状態の準備にかなりのコストがかかる場合、スピードアップははるかに大きくなる可能性がある。
  論文  参考訳（メタデータ） (2025-06-25T18:50:44Z)
• Quantum Framework for Simulating Linear PDEs with Robin Boundary Conditions [0.6144680854063939]
  一般線形偏微分方程式(PDE)を数値シミュレーションするための明示的でオラクルのない量子フレームワークを提案する。 我々のアプローチは、一般的な有限差分法による離散化から始まり、結果の系をユニタリ量子進化を認めるものに変換するためにシュロディンガー化法を適用する。
  論文  参考訳（メタデータ） (2025-06-25T14:23:38Z)
• Quantum oracles for the finite element method [45.200826131319815]
  本研究では,N倍の剛性および質量行列のブロックエンコーディングに使用されるオラクルの実装に必要な量子ルーチンについて検討した。 本稿では, 要素幾何学, 平方根の計算, 条件演算の実装など, 必要なオラクルを構築する方法を示す。
  論文  参考訳（メタデータ） (2025-04-28T14:28:31Z)
• 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)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• A refinement of Reznick's Positivstellensatz with applications to quantum information theory [72.8349503901712]
  ヒルベルトの17番目の問題において、アルティンはいくつかの変数の任意の正定値が2つの平方和の商として書けることを示した。 レズニックはアルティンの結果の分母は常に変数の平方ノルムの$N$-次パワーとして選択できることを示した。
  論文  参考訳（メタデータ） (2019-09-04T11:46:26Z)

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

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