論文の概要: 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の明示
- 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次的なスピードアップが保証される。
関連論文リスト
- Hardness of High-Dimensional Linear Classification [58.29089693778071]
我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。
どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
論文 参考訳（メタデータ） (2026-03-19T15:53:41Z) - Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
周期的な対角構造を持つスパース行列を符号化するための明示的な量子回路を提供する。
本手法の様々な応用は, 微分問題を解く文脈で論じる。
論文 参考訳（メタデータ） (2026-02-11T07:24:33Z) - Classical and Quantum Algorithms for Topological Invariants of Torus Bundles [0.42970700836450476]
我々は非可換トーラス構造を利用して閉トーラスのスキイン代数をその対称部分代数にユニタリの根に埋め込む。
個々の展開係数の抽出は#P完全であることが証明されているが、これらの係数を非無視的な構成の分数に対して効率的に近似できる量子アルゴリズムが存在する。
論文 参考訳（メタデータ） (2025-12-22T04:58:14Z) - 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) - Halving the Cost of Quantum Algorithms with Randomization [0.138120109831448]
量子信号処理(QSP)は、線形演算子の変換を実装するための体系的なフレームワークを提供する。
近年の研究では、量子チャネルへのユニタリゲートを促進する技術であるランダム化コンパイルが開発されている。
提案アルゴリズムは, 平均進化が対象関数に収束するように戦略的に選択されたランダム化の確率的混合を実装し, 誤差は等価個体よりも2次的に小さい。
論文 参考訳（メタデータ） (2024-09-05T17:56:51Z) - 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) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。