論文の概要: Worst-Case Quantum Algorithm for Optimal Polynomial Intersection Beyond Decoded Quantum Interferometry

• arxiv url: http://arxiv.org/abs/2607.14650v1
• Date: Thu, 16 Jul 2026 07:18:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-17 17:01:33.02253
• Title: Worst-Case Quantum Algorithm for Optimal Polynomial Intersection Beyond Decoded Quantum Interferometry
• Title（参考訳）: Decoded Quantum Interferometry を超越した最適多項式断面積に対するWorst-Case Quantum Algorithm
• Abstract要約: 最適多項式補間問題(OPI)は、できるだけ多くの与えられた入力に対して所定の部分集合に値を持つ有限体上の低次を求める。 副生成物として、特定のパラメータ状態における太陽とウーターの存在境界も改善する。 我々の結果は、任意の距離分離可能符号(MDS)に関してMax-LINSAT問題に拡張される。
• 参考スコア（独自算出の注目度）: 6.7936678022428225
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Optimal Polynomial Intersection (OPI) problem asks us to find a low-degree polynomial over a finite field whose values lie in prescribed subsets on as many given inputs as possible. Decoded quantum interferometry (DQI) gives a quantum algorithm for OPI in parameter regimes beyond those achieved by the best known classical heuristics. Follow-up works improve the parameter regimes, but their analyses are limited to average-case settings. Recently, Sun and Wootters showed that, even in the worst case, OPI has a solution in a larger parameter regime than the one covered by DQI. However, they left open whether one can design a quantum algorithm that solves OPI in the worst-case beyond the DQI regime. We give such a quantum algorithm. As a byproduct, we also improve the existential bound of Sun and Wootters in certain parameter regimes. In particular, when each subset contains roughly half of the field elements, our algorithm finds a solution with satisfaction rate $s=1$ whenever the rate satisfies $R>0.75$. This matches the previous average-case bound, whereas DQI cannot achieve $s=1$ unless $R=1$. Our existential bound guarantees the existence of a solution when $R> 0.7158$, improving over the previous threshold $R>0.7495$. More generally, our existential results extend to the Max-LINSAT problem with respect to arbitrary maximum distance separable (MDS) codes. The corresponding algorithmic results apply only to MDS codes whose dual admits an efficient list decoder. Our results are obtained through a novel application of a Brascamp--Lieb-type inequality in the MDS setting, which may have further applications.
• Abstract（参考訳）: 最適多項式補間(OPI)問題は、できるだけ多くの与えられた入力に対して所定の部分集合に値を持つ有限体上の低次多項式を求める。 復号量子干渉法(Decoded quantum interferometry, DQI)は、最もよく知られた古典的ヒューリスティックスによって達成されたパラメータ規則のOPIの量子アルゴリズムを提供する。 フォローアップ作業はパラメータ構造を改善するが、その分析は平均ケース設定に限られる。 最近、Sun と Wootters は、最悪の場合においても、OPI は DQI でカバーされているものよりも大きなパラメータ構造で解を持つことを示した。 しかし、彼らは、DQI体制を超えた最悪のケースでOPIを解決する量子アルゴリズムを設計できるかどうかを公表した。 我々はそのような量子アルゴリズムを与える。 副生成物として、特定のパラメータ状態における太陽とウーターの存在境界も改善する。 特に、各部分集合がフィールド要素の約半分を含む場合、我々のアルゴリズムは満足度が$R>0.75$であるときに、満足度が$s=1$の解を求める。 これは以前の平均ケース境界と一致するが、DQIは$R=1$でない限り$s=1$を達成できない。 我々の存在境界は、$R> 0.7158$のときの解の存在を保証し、以前のしきい値$R> 0.7495$よりも改善する。 より一般的に、我々の存在結果は任意の最大距離分離可能符号(MDS)に関してMax-LINSAT問題にまで拡張される。 対応するアルゴリズムは、効率的なリストデコーダを持つMSS符号にのみ適用される。 MDS設定におけるBrascamp-Lieb型不等式を新たに適用することにより,さらなる応用が期待できる。

関連論文リスト

• Efficient Exact Quantum Sampling from the Sun-Wootters Distribution for Optimal Polynomial Intersection [0.0]
  ポリノミアル・インターセクション (OPI) は、半円法則によって支配される満足度を保証するデコード量子干渉法 (DQI) を実現するための構造化された最適化問題である。 P_u$ は素体上の平衡 OPI に対して効率的にサンプリング可能であることを示す。
  論文  参考訳（メタデータ） (2026-07-17T22:33:06Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• 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)
• 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)
• Decoded Quantum Interferometry Requires Structure [1.121518046252855]
  MAX-$k$-XOR-SATの典型例における復号量子干渉法(DQI)の性能について検討した。 DQI は、多くの標準的な符号のアンサンブルに対して、量子ワッサーシュタイン計量の下ではおよそリプシッツであることが証明されている。
  論文  参考訳（メタデータ） (2025-09-18T00:51:36Z)
• Limitations of Quantum Approximate Optimization in Solving Generic Higher-Order Constraint-Satisfaction Problems [0.0]
  量子近似最適化アルゴリズムの最適化問題に対する量子優位性を実現する能力はまだ不明である。 ランダムなMax-$k$XOR上でのQAOAの性能を$k$の関数と節対変数比として解析する。 満足度の高いレベルに達するには、非常に大きな$p$が必要であり、変動コンテキストと短期デバイスの両方において、かなり難しいとみなす必要がある。
  論文  参考訳（メタデータ） (2024-11-28T21:39:58Z)
• 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)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。 本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T14:37:21Z)
• Universal Quantum Speedup for Branch-and-Bound, Branch-and-Cut, and Tree-Search Algorithms [13.152347996965297]
  混合プログラム(MIP)は、コンピュータサイエンス、オペレーションリサーチ、ファイナンシャルエンジニアリングに関心を持つ多くの最適化問題をモデル化する。 Branch-and-Cutアルゴリズムは、ブランチ・アンド・バウンド論理とカットプレーンルーチンを組み合わせることで、現代のMIPソルバのコアとなる。 本稿では,古典的分岐と境界のアルゴリズムを用いた量子アルゴリズムIncremental-Quantum-Branch-and-Boundを提案する。
  論文  参考訳（メタデータ） (2022-10-06T21:08:46Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• 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)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。 量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。 提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
  論文  参考訳（メタデータ） (2022-05-24T03:49:10Z)

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

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