論文の概要: Discovering New Problems for Decoded Quantum Interferometry
- arxiv url: http://arxiv.org/abs/2610.06753v1
- Date: Mon, 05 Oct 2026 17:30:10 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-08 23:06:17.447124
- Title: Discovering New Problems for Decoded Quantum Interferometry
- Title（参考訳）: Decoded Quantum Interferometryの新しい問題発見
- Abstract要約: Decoded Quant Interferometry (DQI) は古典的な誤り訂正を用いて最適化問題を解く。
コードパラメータや復号保証,古典的ベースラインなどによって,候補問題を検出する健全性ルールを開発する。
どちらの場合も、復号保証と Prange の再起動との有限長比較を証明し、テストしたより大きなケースでは、DQI の期待品質は、古典的解法が固定予算内で到達する品質を超えている。
- 参考スコア（独自算出の注目度）: 0.12891210250935145
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Decoded quantum interferometry (DQI) uses classical error correction to solve optimization problems, but it is hard to tell which problems could give it a quantum advantage. We develop soundness rules that screen candidate problems by their code parameters, decoding guarantees and classical baselines. For the standard objective of counting satisfied constraints, we prove that under worst-case Hamming decoding DQI's guarantee can exceed Prange completion by at most $(\sqrt{2}-1)/2$. Optimal polynomial intersection (OPI) attains this margin cap asymptotically, so no candidate in this setting can exceed OPI's margin. We also derive a performance law for real-valued objectives: the objective fixes both the solution quality and which errors the decoder must correct. An AI-agent search guided by these rules found two candidate applications. Alternant max-agreement on McEliece-type public keys tests what a secret decoder is worth to DQI against classical solvers that see only the public instance. Multiplicative polynomial intersection, a knapsack-type problem built from discrete logarithms, pairs a cosine objective with a public decoder for signed errors. For both we prove decoding guarantees and finite-length comparisons with Prange restarts, and on the larger instances we tested, DQI's expected quality exceeds what our classical solvers reach within fixed budgets.
- Abstract（参考訳）: 復号化量子干渉法 (DQI) は古典的誤り補正を用いて最適化問題を解くが、どの問題が量子的優位性をもたらすかを判断することは困難である。
コードパラメータや復号保証,古典的ベースラインなどによって,候補問題を検出する健全性ルールを開発する。
満たされた制約を数える標準的な目的として、最悪の場合のハミング復号法では、DQIの保証は、少なくとも$(\sqrt{2}-1)/2$ の Prange 完備化を超えることが証明される。
最適多項式交叉(OPI)はこのマージンキャップを漸近的に達成するので、このセッティングの候補がOPIのマージンを超えることはない。
目的は、ソリューションの品質とデコーダが正さなければならないエラーの両方を修正します。
これらのルールでガイドされたAIエージェント検索は、2つの候補アプリケーションを発見した。
McEliece型公開鍵の他の最大値取得は、公開インスタンスのみを見る古典的な解決者に対して、DQIに秘密のデコーダがどんな価値があるかをテストする。
離散対数から構築されたknapsack型問題である乗法多項式交叉は、符号付きエラーに対する公開デコーダとコサイン目的をペアリングする。
どちらの場合も、復号保証と Prange の再起動との有限長比較を証明し、テストしたより大きなケースでは、DQI の期待品質は、古典的解法が固定予算内で到達する品質を超えている。
関連論文リスト
- A provable quantum advantage for approximate optimization via decoded quantum interferometry [0.815557531820863]
Decoded quantum Interferometry (DQI) は、量子コンピュータ上で近似最適化問題に取り組むための新しいパラダイムである。
DQIは、全ての高次古典的アルゴリズムよりも確実に優れていることを示す。
論文 参考訳（メタデータ） (2026-10-01T17:48:56Z) - Cycle Codes and Decoded Quantum Interferometry [1.2336438977950792]
固定されたインスタンスに対して不完全復号化が存在する場合の満足度保証を導出し、ランダムなインスタンスに対する事前結果を一般化する。
最小重復号法は、二進サイクル符号の既知の結果とは対照的に、$q>2$のすべてのフィールドに対してNPハードであることが示される。
論文 参考訳（メタデータ） (2026-09-30T16:07:40Z) - Worst-Case Quantum Algorithm for Optimal Polynomial Intersection Beyond Decoded Quantum Interferometry [6.7936678022428225]
最適多項式補間問題(OPI)は、できるだけ多くの与えられた入力に対して所定の部分集合に値を持つ有限体上の低次を求める。
副生成物として、特定のパラメータ状態における太陽とウーターの存在境界も改善する。
我々の結果は、任意の距離分離可能符号(MDS)に関してMax-LINSAT問題に拡張される。
論文 参考訳（メタデータ） (2026-07-16T07:18:57Z) - Verifiable Quantum Advantage via Optimized DQI Circuits [2.149968465453488]
Decoded Quantum Interferometry (DQI) はスーパーポリノミカル量子スピードアップのためのフレームワークを提供する。
DQIをリードソロモン(Reed-Solomon, RS)コードである最適多項式区間(OPI)問題に適用する。
我々は、OPIのDQIが、最適スピードアップによる検証可能な量子優位性の最初の候補であることを示す。
論文 参考訳（メタデータ） (2025-10-13T03:19:28Z) - How Many Code and Test Cases Are Enough? Evaluating Test Cases Generation from a Binary-Matrix Perspective [51.30005925128432]
LLM(Large Language Models)が自動生成するテストケースの評価は、非常に難しい作業です。
既存のベンチマークは高い計算コスト、インフレーションのスコア、稀でクリティカルな欠陥に対する自明なバグに対するバイアスに悩まされている。
本稿では,ベンチマーク構築をバイナリコードテスト行列の最適な診断基準として定式化するフレームワークを提案する。
論文 参考訳（メタデータ） (2025-10-09T18:29:24Z) - Sample Smart, Not Hard: Correctness-First Decoding for Better Reasoning in LLMs [72.82403830490084]
我々は、復号規則は正確さによって校正されるべきであり、自信だけではならないと論じている。
Greedy-Threshold はこの目標を達成するための単純な戦略を提案します。
この結果から,不確実性の下での復号化が問題視され,数学や一般推論のベンチマークで有意な差がみられた。
論文 参考訳（メタデータ） (2025-10-07T14:46:12Z) - Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security [50.16790546184646]
まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。
次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
論文 参考訳（メタデータ） (2023-11-07T04:59:02Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。