論文の概要: Decoded Quantum Interferometry Requires Structure

• arxiv url: http://arxiv.org/abs/2509.14509v1
• Date: Thu, 18 Sep 2025 00:51:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-19 17:26:53.014851
• Title: Decoded Quantum Interferometry Requires Structure
• Title（参考訳）: デコード量子干渉計は構造を必要とする
• Authors: Eric R. Anschuetz, David Gamarnik, Jonathan Z. Lu,
• Abstract要約: MAX-$k$-XOR-SATの典型例における復号量子干渉法(DQI)の性能について検討した。 DQI は、多くの標準的な符号のアンサンブルに対して、量子ワッサーシュタイン計量の下ではおよそリプシッツであることが証明されている。
• 参考スコア（独自算出の注目度）: 1.121518046252855
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the performance of Decoded Quantum Interferometry (DQI) on typical instances of MAX-$k$-XOR-SAT when the transpose of the constraint matrix is drawn from a standard ensemble of LDPC parity check matrices. We prove that if the decoding step of DQI corrects up to the folklore efficient decoding threshold for LDPC codes, then DQI is obstructed by a topological feature of the near-optimal space of solutions known as the overlap gap property (OGP). As the OGP is widely conjectured to exactly characterize the performance of state-of-the-art classical algorithms, this result suggests that DQI has no quantum advantage in optimizing unstructured MAX-$k$-XOR-SAT instances. We also give numerical evidence supporting this conjecture by showing that approximate message passing (AMP)--a classical algorithm conjectured to saturate the OGP threshold--outperforms DQI on a related ensemble of MAX-$k$-XOR-SAT instances. Finally, we prove that depth-$1$ QAOA outperforms DQI at sufficiently large $k$ under the same decoding threshold assumption. Our result follows by showing that DQI is approximately Lipschitz under the quantum Wasserstein metric over many standard ensembles of codes. We then prove that MAX-$k$-XOR-SAT exhibits both an OGP and a related topological obstruction known as the chaos property; this is the first known OGP threshold for MAX-$k$-XOR-SAT at fixed $k$, which may be of independent interest. Finally, we prove that both of these topological properties inhibit approximately Lipschitz algorithms such as DQI from optimizing MAX-$k$-XOR-SAT to large approximation ratio.
• Abstract（参考訳）: LDPCパリティチェック行列の標準アンサンブルから制約行列の変換を行う際に, MAX-$k$-XOR-SATの典型例に対する復号量子干渉法(DQI)の性能について検討する。 DQIの復号ステップがLDPC符号の民話効率の良い復号しきい値まで正しければ、DQIはオーバーラップギャップ特性(OGP)として知られる解の最適に近い空間の位相的特徴によって妨害される。 OGPは最先端の古典的アルゴリズムの性能を正確に特徴付けると広く推測されているため、この結果はDQIが非構造化MAX-$k$-XOR-SATインスタンスを最適化する量子的優位性を持たないことを示唆している。 また、OGPしきい値の飽和を予想する古典的アルゴリズムである近似メッセージパッシング(AMP)が、MAX-$k$-XOR-SATインスタンスの関連するアンサンブル上でDQIを出力することを示すことにより、この予想を支持する数値的な証拠を与える。 最後に、深さ1$QAOAが、同じ復号しきい値仮定の下で十分大きな$k$でDQIを上回っていることを証明する。 我々の結果は、DQI が、多くの標準符号のアンサンブル上の量子ワッサーシュタイン計量の下で、ほぼリプシッツであることを示すことで従う。 次に、MAX-$k$-XOR-SAT がカオス特性として知られる OGP と関連する位相的障害物の両方を示すことを証明し、これは固定された $k$ における MAX-$k$-XOR-SAT に対する最初の OGPしきい値である。 最後に、これらのトポロジカルな性質は、DQIのようなおよそリプシッツアルゴリズムがMAX-$k$-XOR-SATを大きな近似比に最適化することを妨げていることを証明した。

関連論文リスト

• The Geometry of LLM Quantization: GPTQ as Babai's Nearest Plane Algorithm [52.89358421626026]
  GPTQは、LLMスケールでのワンショットポストトレーニング量子化の標準手法の1つとして登場した。 GPTQは古典的最近ベクトル問題に対するババイの最も近い平面アルゴリズムと数学的に同一であることを示す。
  論文  参考訳（メタデータ） (2025-07-24T16:22:18Z)
• IGMaxHS -- An Incremental MaxSAT Solver with Support for XOR Clauses [0.0]
  IGMaxHS は iMaxHS と GaussMaxHS をベースとしているが, XOR の制約は GaussMaxHS よりも少ない。 IGMaxHSは、不正な不満足な判断も、不正なモデルも、一貫性のないコストモデルの組み合わせも報告していない唯一の解決法である。 IGMaxHSは,ミュンヘン量子ツールキットを用いたシミュレーションにより,量子カラーコードを復号化可能であることを示す。
  論文  参考訳（メタデータ） (2024-10-21T11:21:21Z)
• Optimization by Decoded Quantum Interferometry [42.169154389732036]
  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)
• The Overlap Gap Property limits limit swapping in the QAOA [5.578103948136372]
  量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は、組合せ最適化問題(COP)のために設計された量子アルゴリズムである。 また, スピングラス型COPの局所アルゴリズムが, 基礎となるErd"os-R'enyiハイパーグラフの対数深さでの性能に制限されている場合, ランダム正規ハイパーグラフも同様に制限されることを示す。
  論文  参考訳（メタデータ） (2024-04-09T07:45:06Z)
• 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)
• Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
  量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。 任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
  論文  参考訳（メタデータ） (2020-11-26T18:22:21Z)

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

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