論文の概要: A nearly linear-time Decoded Quantum Interferometry algorithm for the Optimal Polynomial Intersection problem

• arxiv url: http://arxiv.org/abs/2601.15171v1
• Date: Wed, 21 Jan 2026 16:48:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-22 21:27:50.465191
• Title: A nearly linear-time Decoded Quantum Interferometry algorithm for the Optimal Polynomial Intersection problem
• Title（参考訳）: 最適多項式補間問題に対するニア線形復号量子干渉法アルゴリズム
• Authors: Ansis Rosmanis,
• Abstract要約: 最近、JordanらはDecoded Quantum Interferometry (DQI)と呼ばれる新しい量子アルゴリズム技術を導入した。 彼らは、OPI (Optimal Polynomial Intersection) と呼ばれる制約条件問題を提示し、時間内で動作するDQIアルゴリズムが、既知のどの古典的アルゴリズムよりも大きな制約を満足できることを示した。 これらの改善によって,OPI問題に対するほぼ線形時間DQIアルゴリズムがもたらされることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recently, Jordan et al. (Nature, 2025) introduced a novel quantum-algorithmic technique called Decoded Quantum Interferometry (DQI) for solving specific combinatorial optimization problems associated with classical codes. They presented a constraint-satisfaction problem called Optimal Polynomial Intersection (OPI) and showed that, for this problem, a DQI algorithm running in polynomial time can satisfy a larger fraction of constraints than any known polynomial-time classical algorithm. In this work, we propose several improvements to the DQI algorithm, including sidestepping the quadratic-time Dicke state preparation. Given random access to the input, we show how these improvements result in a nearly linear-time DQI algorithm for the OPI problem. Concurrently and independently with this work, Khattar et al. (arXiv:2510:10967) also construct a nearly linear-time DQI algorithm for OPI using slightly different techniques.
• Abstract（参考訳）: 最近、Jordan et al (Nature, 2025) は、古典符号に関連する特定の組合せ最適化問題を解決するために、Decoded Quantum Interferometry (DQI) と呼ばれる新しい量子アルゴリズムを導入した。 彼らは Optimal Polynomial Intersection (OPI) と呼ばれる制約満足度問題を提示し、この問題に対して、多項式時間で動作するDQIアルゴリズムは、既知の多項式時間古典アルゴリズムよりも大きな制約を満足できることを示した。 本研究では,2次時間Dicke状態の準備をサイドステッピングするなど,DQIアルゴリズムのいくつかの改良を提案する。 入力にランダムにアクセスすると、これらの改善がOPI問題に対するほぼ線形時間DQIアルゴリズムにどのように影響するかを示す。 この研究と並行して、Khattar et al (arXiv:2510:10967) もわずかに異なる手法を用いて、OPIのほぼ線形時間DQIアルゴリズムを構築した。

関連論文リスト

• A Non-Variational Quantum Approach to the Job Shop Scheduling Problem [0.3078691410268859]
  短期的ハードウェア制限を軽減するために設計されたQAOAの変種であるIterative-QAOAを紹介する。 我々は,Just-in-Time Job Shop Scheduling Problem (JIT-JSSP) のインスタンスをIonQ Forte Generation QPU上でベンチマークする。 反復-QAOAは、評価された全ての問題インスタンスに対して、最適解と高品質でほぼ最適解を見つけるために、しっかりと収束していることがわかった。
  論文  参考訳（メタデータ） (2025-10-30T16:14:13Z)
• Optimization of Quadratic Constraints by Decoded Quantum Interferometry [0.0]
  Decoded Quantum Interferometry (DQI) を2次制約を含む最適化問題に拡張する。 我々は、最大QDSATに対してDQI状態を作成するための効率的なアルゴリズムを提供する。 2次OPIがmax-QUADSATのインスタンスであることを示し、アルゴリズムを用いて最適化する。
  論文  参考訳（メタデータ） (2025-10-09T10:49:17Z)
• Optimization by Decoded Quantum Interferometry [38.063836468778895]
  Decoded Quantum Interferometry (DQI) は、量子フーリエ変換を用いて、復号化問題に対する最適化問題を削減する量子アルゴリズムである。 有限体上の最適適合を近似するために、DQIは既知の古典的アルゴリズムよりも超多項式的なスピードアップを達成する。
  論文  参考訳（メタデータ） (2024-08-15T17:47:42Z)
• 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 Review on Quantum Approximate Optimization Algorithm and its Variants [47.89542334125886]
  量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm、QAOA)は、難解な最適化問題を解くことを目的とした、非常に有望な変分量子アルゴリズムである。 この総合的なレビューは、様々なシナリオにおけるパフォーマンス分析を含む、QAOAの現状の概要を提供する。 我々は,提案アルゴリズムの今後の展望と方向性を探りながら,選択したQAOA拡張と変種の比較研究を行う。
  論文  参考訳（メタデータ） (2023-06-15T15:28:12Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。 本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。 提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
  論文  参考訳（メタデータ） (2021-07-08T17:59:55Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。 本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。 Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
  論文  参考訳（メタデータ） (2021-05-06T17:59:38Z)

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

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