論文の概要: Approximate sampling from decoded quantum interferometry via Markov chain Monte Carlo methods

• arxiv url: http://arxiv.org/abs/2607.28120v1
• Date: Thu, 30 Jul 2026 12:29:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-31 21:37:00.552162
• Title: Approximate sampling from decoded quantum interferometry via Markov chain Monte Carlo methods
• Title（参考訳）: マルコフ連鎖モンテカルロ法によるデコード量子干渉計からの近似サンプリング
• Authors: Elies Gil-Fuster, Matan Ninio, Lennart Bittel, Yishai Shimoni, Jens Eisert, Stefan Woerner, Almudena Carrera Vázquez,
• Abstract要約: 近似最適化に取り組むために、復号量子干渉法(DQI)が提案されている。 古典的なサンプリング手法がDQIの最適化能力をエミュレートできるかどうかを検討する。
• 参考スコア（独自算出の注目度）: 1.23852866176407
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Optimization problems are among the leading candidates for industrially relevant quantum advantage. Decoded quantum interferometry (DQI) has been proposed to tackle approximate optimization, establishing a connection to classical decoding problems. While previous work has primarily focused on the theoretical complexity of DQI, comparatively little is known about its empirical performance relative to classical algorithms. In this work, we shed further light on the complexity of DQI and investigate numerically whether classical sampling methods can emulate the optimization capabilities of DQI. We first present a simplified analytical characterization of DQI that connects its expected performance to binomial statistics, and we identify concrete obstacles in further studying the complexity of DQI. Exploiting the fact that DQI output probabilities are efficiently computable, we apply Markov chain Monte Carlo (MCMC) techniques, particularly block-Gibbs sampling, to sample from the induced distribution. We study the runtime scaling of these methods for two optimization problems called max-XORSAT, where we reach beyond $1000$ effective qubits; and OPI, where we reach beyond $150$ effective qubits. Our results show that MCMC algorithms can reliably attain the approximation ratios expected from DQI across a broad range of problem sizes. In OPI, in the regime where a super-polynomial advantage is claimed for DQI, we observe an empirical runtime for MCMC that scales approximately as $1.1^{n}$, indicating exponential growth with a comparatively small base. Our findings do not refute existing quantum advantage claims but provide new empirical evidence that classical sampling algorithms can closely match DQI's optimization performance, offering a more nuanced perspective on the practical advantage of DQI.
• Abstract（参考訳）: 最適化問題は、産業的に関連する量子優位性の主要な候補の一つである。 デコード量子インターフェロメトリ(DQI)は、近似最適化に取り組むために提案され、古典的なデコード問題への接続を確立する。 これまでの研究は主にDQIの理論的複雑さに焦点を当ててきたが、古典的なアルゴリズムと比較して経験的な性能についてはあまり知られていない。 そこで本研究では,DQIの複雑性をさらに強調し,古典的なサンプリング手法がDQIの最適化能力をエミュレートできるかどうかを数値的に検討する。 まず、期待性能と二項統計を結合するDQIの簡易解析的特徴付けを行い、さらにDQIの複雑さを研究する上での具体的な障害を特定する。 DQI出力確率が効率よく計算可能であることを証明し、マルコフ連鎖モンテカルロ法(特にブロックギブスサンプリング)を誘導分布からのサンプルに適用する。 Max-XORSATという,1,000ドル以上の有効量子ビット,150ドル以上の有効量子ビットを持つOPIという2つの最適化問題に対して,これらの手法のランタイムスケーリングについて検討する。 この結果から,MCMCアルゴリズムはDQIから期待される近似比を幅広い問題サイズで確実に達成できることがわかった。 OPI では、DQI に対して超多項式的優位性が主張される体制において、MCMC に対する経験的ランタイムを観察し、およそ1.1^{n}$ でスケールし、比較的小さなベースで指数的成長を示す。 我々の発見は、既存の量子優位性主張を否定するものではないが、古典的なサンプリングアルゴリズムがDQIの最適化性能と密接に一致し、DQIの実用的優位性についてより曖昧な視点を提供するという新しい実証的な証拠を提供する。

関連論文リスト

• Quartic quantum speedups for community detection [84.14713515477784]
  我々は,準量子スピードアップを実現するハイパーグラフコミュニティ検出のための量子アルゴリズムを開発した。 提案アルゴリズムは,従来検討されていた PCA や $p$XORSAT といった問題を超えて拡張した Kikuchi 法に基づいている。
  論文  参考訳（メタデータ） (2025-10-09T17:35:17Z)
• 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)
• Performance Benchmarking of Quantum Algorithms for Hard Combinatorial Optimization Problems: A Comparative Study of non-FTQC Approaches [0.0]
  本研究は、4つの異なる最適化問題にまたがっていくつかの非フォールト耐性量子コンピューティングアルゴリズムを体系的にベンチマークする。 我々のベンチマークには、変分量子固有解法など、ノイズの多い中間スケール量子(NISQ)アルゴリズムが含まれている。 以上の結果から,FTQC以外のアルゴリズムは全ての問題に対して最適に動作しないことが明らかとなり,アルゴリズム戦略の調整の必要性が浮き彫りになった。
  論文  参考訳（メタデータ） (2024-10-30T08:41:29Z)
• Optimization by Decoded Quantum Interferometry [38.063836468778895]
  Decoded Quantum Interferometry (DQI) は、量子フーリエ変換を用いて、復号化問題に対する最適化問題を削減する量子アルゴリズムである。 有限体上の最適適合を近似するために、DQIは既知の古典的アルゴリズムよりも超多項式的なスピードアップを達成する。
  論文  参考訳（メタデータ） (2024-08-15T17:47:42Z)
• Efficient molecular conformation generation with quantum-inspired algorithm [4.625636280559916]
  本稿では,分子展開(MU)問題の解法として量子インスパイアされたアルゴリズムを提案する。 我々のアプローチによって決定されたコンフォメーションと密度汎関数理論(DFT)の根平均二乗偏差は無視できる。 その結果,量子ハードウェアが成熟する以前にも,現実的な問題を解決するために量子インスパイアされたアルゴリズムを適用できることが示唆された。
  論文  参考訳（メタデータ） (2024-04-22T11:40:08Z)
• Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum Computing [93.83016310295804]
  AQCは研究関心の問題を実装でき、コンピュータビジョンタスクのための量子表現の開発に拍車をかけた。 本研究では,この情報を確率的バランスの取れたk平均クラスタリングに活用する可能性について検討する。 最適でない解を捨てる代わりに, 計算コストを少なくして, 校正後部確率を計算することを提案する。 これにより、合成タスクと実際の視覚データについて、D-Wave AQCで示すような曖昧な解とデータポイントを識別することができる。
  論文  参考訳（メタデータ） (2023-10-18T17:59:45Z)
• Quantum algorithm for stochastic optimal stopping problems with applications in finance [60.54699116238087]
  有名な最小二乗モンテカルロ (LSM) アルゴリズムは、線形最小二乗回帰とモンテカルロシミュレーションを組み合わせることで、最適停止理論の問題を解決する。 プロセスへの量子アクセス、最適な停止時間を計算するための量子回路、モンテカルロの量子技術に基づく量子LSMを提案する。
  論文  参考訳（メタデータ） (2021-11-30T12:21:41Z)

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

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