論文の概要: A Quantum-Inspired Approach to MaxCut Based on Sparse Walsh/Pauli-Correlation Encoding
- arxiv url: http://arxiv.org/abs/2609.08907v1
- Date: Tue, 08 Sep 2026 15:41:24 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-11 15:22:36.607901
- Title: A Quantum-Inspired Approach to MaxCut Based on Sparse Walsh/Pauli-Correlation Encoding
- Title（参考訳）: Sparse Walsh/Pauli-Correlationエンコーディングに基づくMaxCutへの量子インスピレーションによるアプローチ
- Abstract要約: スパースパウリ相関符号化に基づく量子インスパイアされたMaxCut用Walsh/PCEソルバを提案する。
選択したGsetインスタンス,G1,G6,G12,G18について,ランダム検索と10種以上のタブ検索との比較を行った。
- 参考スコア（独自算出の注目度）: 37.094697562212154
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present a quantum-inspired Walsh/PCE solver for MaxCut based on sparse Pauli-correlation encodings. Instead of assigning one qubit or one variable to each graph vertex directly, the method represents relaxed binary variables through expectation values of diagonal Pauli/Walsh observables. These correlators are computed classically from sparse Walsh autocorrelations, producing a compact differentiable relaxation of the MaxCut objective. We evaluate the method on selected Gset instances, G1, G6, G12, and G18, and compare it with random search and tabu search over 10 independent seeds. The proposed model uses $801$ active parameters, corresponding to only $0.306\%$ of the full Walsh space over $18$ qubits. After a final bitflip local search, Walsh/PCE achieves approximation ratios of $0.99033 \pm 0.00226$ on G1, $0.95647 \pm 0.01604$ on G6, $0.96007 \pm 0.00951$ on G12, and $0.92964 \pm 0.02202$ on G18, outperforming both baselines on all tested instances. The method also yields the lowest average runtime in all cases. These results suggest that sparse Walsh/PCE representations provide an efficient quantum-inspired route for MaxCut and may be further extended to hardware-based estimation of Pauli/Walsh correlators.
- Abstract（参考訳）: スパースパウリ相関符号化に基づく量子インスパイアされたMaxCut用Walsh/PCEソルバを提案する。
1つのキュービットまたは1つの変数を各グラフ頂点に直接割り当てる代わりに、この方法は、対角パウリ/ウォルシュ観測値の期待値を通して緩和されたバイナリ変数を表現する。
これらの相関子はスパースウォルシュ自己相関から古典的に計算され、マックスコートの目的をコンパクトに微分可能緩和する。
選択したGsetインスタンス,G1,G6,G12,G18について,ランダム検索と10種以上のタブ検索との比較を行った。
提案したモデルでは、活性パラメータが801ドルであり、Walsh空間の総和が18ドル以上の0.306ドル%にしか満たない。
最終的なビットフリップローカルサーチの後、Walsh/PCEは、G1上の0.99033 \pm 0.00226$、G6上の0.95647 \pm 0.01604$、G12上の0.96007 \pm 0.00951$、G18上の0.92964 \pm 0.02202$の近似比を達成し、テストされたすべてのインスタンスで両方のベースラインを上回っている。
このメソッドは、すべてのケースにおいて最も低い平均ランタイムも生成します。
これらの結果は、疎ウォルシュ/PCE表現がMaxCutの効率的な量子インスパイアされた経路を提供し、さらにハードウェアによるPauli/Walsh相関器の推定にまで拡張される可能性があることを示唆している。
関連論文リスト
- Rand-SEMI-QAOA: Finite-Budget Depth-One MaxCut Ensembles on Compressed Quantum Registers [0.0]
Rand-SEMI-QAOA は MaxCut の有限予算 QRAO-QAOA アンサンブルである。
このメソッドは、製品$X$ファミリから置き換えることなく、ラベルを均一にサンプリングする。
正確なゲージの恒等式は、積族ラベルが QRAO ハミルトニアンの軌道を生成することを示している。
論文 参考訳（メタデータ） (2026-08-16T09:47:55Z) - Asymptotical Analysis of the $(1+(λ,λ))$ GA Escape Time from Local Optima on Jump Functions [0.5156484100374058]
本稿では,確率論からの極限定理に基づく進化的アルゴリズムのランタイム解析へのアプローチを開発する。
この研究の主な成果は、Antipov, Doerr and Karavaev (2022) の業績から得られる脱走時間に対する上限の締め付けである。
論文 参考訳（メタデータ） (2026-07-15T18:37:48Z) - An End-to-End Hybrid Quantum--Classical Sampling Workflow for Discrete Markov Random Fields: A Reproducible Case Study [0.0]
小型離散マルコフ確率場(MRFs)の振幅符号化i.d.サンプリングについて検討する。
これにより、量子指数的スピードアップは排除されるが、独立回路サンプルに基づく古典的MCMCとクリーンな比較が可能となる。
F_mathrmVQC, F_mathrmMPS) = (0.31, 0.96), (0.21, 0.96), (0.17, 0.88)$ at compressions 10.7times$, $34.1times$, and $111。
論文 参考訳（メタデータ） (2026-07-10T18:33:14Z) - Quantum Advantage in Tolerant Junta Testing [0.5442955439283729]
適応設定において、許容値$k$-juntaテスト問題に対する最初の超多項式量子優位性を確立する。
特定のパラメータ体系内では、高い精度で寛容な$k$-juntaテストが$mathrmpoly(k)$quantumquantumquantum(k)$で解けることを示す。
論文 参考訳（メタデータ） (2026-06-22T11:42:39Z) - Sublinear Time Quantum Sensitivity Sampling [57.356528942341534]
本稿では、量子感応サンプリングのための統一的なフレームワークを提案し、量子コンピューティングの利点を古典近似問題の幅広いクラスに拡張する。
我々のフレームワークは、コアセットを構築するための合理化されたアプローチを提供し、クラスタリング、回帰、低ランク近似などのアプリケーションにおいて、大幅なランタイム改善を提供します。
論文 参考訳（メタデータ） (2025-09-20T20:18:49Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Efficient Quantum State Preparation with Walsh Series [0.0]
Walsh Series Loader (WSL) と呼ばれる新しい近似量子状態準備法が導入された。
WSLは1つの実変数の実数値関数によって定義される量子状態に近似し、深さは数$n$の量子ビットとは独立である。
論文 参考訳（メタデータ） (2023-07-17T10:44:28Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - 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) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。