論文の概要: Verifiable Quantum Advantage via Optimized DQI Circuits

• arxiv url: http://arxiv.org/abs/2510.10967v1
• Date: Mon, 13 Oct 2025 03:19:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-14 18:06:30.178006
• Title: Verifiable Quantum Advantage via Optimized DQI Circuits
• Title（参考訳）: 最適化DQI回路による量子アドバンテージの検証
• Authors: Tanuj Khattar, Noah Shutty, Craig Gidney, Adam Zalcman, Noureldin Yosri, Dmitri Maslov, Ryan Babbush, Stephen P. Jordan,
• Abstract要約: Decoded Quantum Interferometry (DQI) はスーパーポリノミカル量子スピードアップのためのフレームワークを提供する。 DQIをリードソロモン(Reed-Solomon, RS)コードである最適多項式区間(OPI)問題に適用する。 我々は、OPIのDQIが、最適スピードアップによる検証可能な量子優位性の最初の候補であることを示す。
• 参考スコア（独自算出の注目度）: 2.149968465453488
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Decoded Quantum Interferometry (DQI) provides a framework for superpolynomial quantum speedups by reducing certain optimization problems to reversible decoding tasks. We apply DQI to the Optimal Polynomial Intersection (OPI) problem, whose dual code is Reed-Solomon (RS). We establish that DQI for OPI is the first known candidate for verifiable quantum advantage with optimal asymptotic speedup: solving instances with classical hardness $O(2^N)$ requires only $\widetilde{O}(N)$ quantum gates, matching the theoretical lower bound. Realizing this speedup requires highly efficient reversible RS decoders. We introduce novel quantum circuits for the Extended Euclidean Algorithm, the decoder's bottleneck. Our techniques, including a new representation for implicit B\'ezout coefficient access, and optimized in-place architectures, reduce the leading-order space complexity to the theoretical minimum of $2nb$ qubits while significantly lowering gate counts. These improvements are broadly applicable, including to Shor's algorithm for the discrete logarithm. We analyze OPI over binary extension fields $GF(2^b)$, assess hardness against new classical attacks, and identify resilient instances. Our resource estimates show that classically intractable OPI instances (requiring $>10^{23}$ classical trials) can be solved with approximately 5.72 million Toffoli gates. This is substantially less than the count required for breaking RSA-2048, positioning DQI as a compelling candidate for practical, verifiable quantum advantage.
• Abstract（参考訳）: Decoded Quantum Interferometry (DQI) は、ある種の最適化問題を可逆復号化タスクに還元することにより、超ポリノミカル量子スピードアップのためのフレームワークを提供する。 二重符号がリードソロモン (Reed-Solomon) である最適多項式区間 (OPI) 問題に DQI を適用した。 古典的硬度$O(2^N)$の問題を解くには、理論的な下界に一致するように、$\widetilde{O}(N)$の量子ゲートしか必要としない。 このスピードアップを実現するには、高効率で可逆的なRSデコーダが必要である。 本稿では,デコーダのボトルネックである拡張ユークリッドアルゴリズムのための新しい量子回路を提案する。 暗黙的B'ezout係数アクセスのための新しい表現や、最適化されたインプレースアーキテクチャを含む我々の手法は、先行階空間の複雑さを理論最小2nb$ qubitsに削減し、ゲート数を大幅に削減する。 これらの改善は、離散対数に対するショアのアルゴリズムなど、広く適用できる。 バイナリ拡張フィールド上のOPIを$GF(2^b)$で解析し、新しい古典的攻撃に対するハードネスを評価し、レジリエントなインスタンスを特定する。 我々の資源推定は、古典的に難解なOPIインスタンス($>10^{23}$古典的トライアル)を約5.72百万のトフォリゲートで解けることを示している。 これはRSA-2048を破るのに必要な数よりも大幅に小さく、実用的で検証可能な量子優位性の候補としてDQIを位置づけている。

関連論文リスト

• Optimization by Decoded Quantum Interferometry [42.169154389732036]
  Decoded Quantum Interferometry (DQI) という量子アルゴリズムを導入する。 有限体上のデータに近似するために、DQIは我々の知るどの時間よりも良い近似比を達成する。
  論文  参考訳（メタデータ） (2024-08-15T17:47:42Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。 補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。 各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
  論文  参考訳（メタデータ） (2022-06-30T03:15:23Z)
• Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications [10.436969366019015]
  我々は、$Theta(n)$-depth回路は、$O(ndlog d)$ acillary qubitsを持つ$Theta(log(nd))で作成可能であることを示す。 我々は、ハミルトンシミュレーション、方程式の線形系解法、量子ランダムアクセスメモリの実現など、異なる量子コンピューティングタスクにおける結果の適用について論じる。
  論文  参考訳（メタデータ） (2022-01-27T13:16:30Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  マルチバスグラフ複雑性と非線形活性化関数の2つの革新の恩恵を受ける新しい変分量子アルゴリズムを導入する。 その結果,最適化性能が向上し,有効景観が2つ向上し,測定の進歩が減少した。
  論文  参考訳（メタデータ） (2021-06-24T20:16:02Z)

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

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