論文の概要: Custom Penalty QAOA via Walsh-Hadamard Transform
- arxiv url: http://arxiv.org/abs/2610.04908v1
- Date: Sun, 04 Oct 2026 03:40:51 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-11 08:05:35.905164
- Title: Custom Penalty QAOA via Walsh-Hadamard Transform
- Title（参考訳）: Walsh-Hadamard変換によるカスタムペナルティQAOA
- Abstract要約: ウォルシュ・アダマール変換(WHT)が任意のペナルティ関数に対してこの障害を取り除くことを示す。
我々はWalshカスタムペナルティQAOA(WCP-QAOA)としてこの枠組みを提案する。
- 参考スコア（独自算出の注目度）: 3.249853429482705
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Inequality constraints in combinatorial optimization are conventionally handled by introducing slack variables and quadratic penalties, which increase the qubit count and distort the optimization landscape. Slack-free formulations instead apply a nonlinear custom penalty function directly to the constraint, which are difficult to be implemented in quantum approximate optimization algorithm (QAOA). We show that the Walsh--Hadamard transform (WHT) removes this obstruction for any penalty function: a penalty applied to a linear constraint is exactly a weighted sum of Pauli-$Z$ strings. We propose this framework as the Walsh custom penalty QAOA (WCP-QAOA). Truncating the expansion at Walsh degree $k$ costs $\mathcal{O}(n^k)$ Pauli terms and leaves the qubit count untouched. The truncation is the optimal degree-$k$ approximation of the penalty in $L^2$, and we give a condition on the discarded Walsh coefficients under which the truncated Hamiltonian still ranks every feasible solution below every infeasible one. Since evaluating a Walsh coefficient from its definition requires all $2^n$ penalty values, we give an algorithm that returns any coefficient in sub-exponential time, so that the degree-$k$ Hamiltonian is obtained in time polynomial in $n$ for fixed $k$. We show that for the exponential penalty, there exists a closed product form of WHT, and hence a closed form expression to calculate the Walsh coefficients. We identify structural shortcuts that shorten the exact spectrum. We also tested WCP-QAOA in solving a 6-qubit knapsack problem.
- Abstract（参考訳）: 組合せ最適化における不等式制約は、従来の方法ではスラック変数と二次ペナルティを導入し、量子ビット数を増やし、最適化景観を歪ませることによって処理される。
Slackフリーな定式化は、量子近似最適化アルゴリズム(QAOA)において実装が難しい制約に直接非線形なカスタムペナルティ関数を適用する。
我々は、ウォルシュ・アダマール変換(WHT)が任意のペナルティ関数に対するこの障害を取り除くことを示す: 線形制約に適用されるペナルティは、正確にはパウリ-$Z$弦の重み付き和である。
本稿では,WalshカスタムペナルティQAOA(WCP-QAOA)として提案する。
ウォルシュ次数$k$での展開の縮約には、$\mathcal{O}(n^k)$ Pauli という用語が用いられる。
トランケーションは最適次数-k$$$L^2$のペナルティの近似であり、切り捨てられたウォルシュ係数に条件を与える。
ウォルシュ係数をその定義から評価するためには、全ての2^n$のペナルティ値を必要とするので、任意の係数を指数以下の時間で返却するアルゴリズムを与えるので、次数-k$ハミルトンは固定$k$に対して$n$の時間多項式で得られる。
指数ペナルティに対して、WHTの閉積形式が存在し、したがってウォルシュ係数を計算するための閉形式表現が存在することを示す。
正確なスペクトルを短くする構造的ショートカットを同定する。
また,6量子knapsack問題の解法としてWCP-QAOAを試験した。
関連論文リスト
- Clipped or Unclipped? Finite-Sample Trade-offs for Averaged SGD under Heavy-Tailed Noise [66.13091490213743]
グラディエントクリッピングはトレーニングを安定させるために広く用いられているが、平均的なSGDの統計的精度を改善する必要はない。
有限条件の$p$-th モーメント,$pge2$ の条件下で, クリッピングおよび非クリッピングのPolyak-Ruppert平均 SGD の比較を導出した。
我々の主な結果は、$p>2$の場合、ガウス項が未開偏差境界を独占する明確な精度と信頼条件を与える。
論文 参考訳（メタデータ） (2026-09-26T21:47:14Z) - Sharp Oracle-Regret Tradeoffs for Projection-Free Online Convex Optimization [55.29259818039367]
我々は, オンライン凸最適化において, 実現可能な集合へのアクセスが正確な線形最適化オラクルに制限された場合に達成可能な後悔を特徴づける。
コンベックス$G$-Lipschitzの損失に対して、直径は最大$D$、合計$Q$オークルコールは$Q$、厳格な制限はラウンド当たり$B$である。
論文 参考訳（メタデータ） (2026-09-23T22:25:52Z) - Penalized Nonreversible Langevin for Constrained Sampling [3.6350635582369417]
本稿では,$(x)propto ef(x)mathbf 1_mathcal C(x)から抽出するペナル化非可逆ランゲヴィンアルゴリズムを提案する。
論文 参考訳（メタデータ） (2026-09-21T20:24:08Z) - A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。
我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
論文 参考訳（メタデータ） (2026-09-09T10:13:43Z) - Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
一般的な実現可能性の下では、我々のLEDGERアルゴリズムは、期待される損失$O(sqrt T)と期待される予算違反$O(sqrtTlog(eT))を達成します。
スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。
論文 参考訳（メタデータ） (2026-09-07T01:38:41Z) - Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
基本的で長期にわたる課題は、その効率的な近似である。
一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。
本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
論文 参考訳（メタデータ） (2026-04-09T16:38:14Z) - Tight inapproximability of max-LINSAT and implications for decoded quantum interferometry [0.0]
我々は、非時間アルゴリズムが任意の定数でランダム割当比$r/q$を超えることを、Hstadの定理から直接還元することで証明する。
この閾値は、デコードされた量子干渉法を規定する半円法則の$ell/mから0$制限と一致する。
論文 参考訳（メタデータ） (2026-03-04T19:26:26Z) - CLASP: An online learning algorithm for Convex Losses And Squared Penalties [1.096028999747108]
本稿では,2乗制約違反を伴う累積損失を最小限に抑えるアルゴリズムであるCLASPを紹介する。
凸損失の場合、CLASPは後悔の$Oleft(Tmax,1-right)$と累積二乗ペナルティ$Oleft(T1-right)$ for any $in (0,1)$を達成する。
最も重要なことは、強い凸問題に対して、CLASPは後悔と累積二乗のペナルティの両方に関する最初の対数保証を提供する。
論文 参考訳（メタデータ） (2026-01-22T16:13:52Z) - Regret and Cumulative Constraint Violation Analysis for Online Convex
Optimization with Long Term Constraints [24.97580261894342]
本稿では,長期的制約を伴うオンライン凸最適化について考察する。
新たなアルゴリズムが最初に提案され、静的後悔のために$mathcalO(Tmaxc,1-c)$bound、累積制約違反のために$mathcalO(T(1-c)/2)$boundを達成する。
論文 参考訳（メタデータ） (2021-06-09T15:18:06Z) - Revisiting Modified Greedy Algorithm for Monotone Submodular
Maximization with a Knapsack Constraint [75.85952446237599]
修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。
最適なデータ依存上界を導出する。
また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
論文 参考訳（メタデータ） (2020-08-12T15:40:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。