論文の概要: Succinct QUBO formulations for permutation problems by sorting networks

• arxiv url: http://arxiv.org/abs/2603.07579v2
• Date: Fri, 13 Mar 2026 16:59:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-16 13:35:07.445461
• Title: Succinct QUBO formulations for permutation problems by sorting networks
• Title（参考訳）: ネットワークソートによる置換問題に対する逐次QUBO定式化
• Authors: Katalin Friedl, Levente Gegő, László Kabódi, Viktória Nemkin,
• Abstract要約: 比較交換ネットワークを用いた置換に対するQUBOの定式化を導入し,バイナリ変数は$O(n log2 n)$である。 提案手法の中心的な特徴は、各置換が一意な変数の割り当てに対応し、偏りのないサンプリングを可能にすることである。 制約付き置換の非バイアスサンプリングが重要である地域では,本手法が実用上有用であることが期待されている。
• 参考スコア（独自算出の注目度）: 0.1590850178837849
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quadratic Unconstrained Binary Optimization (QUBO) is a standard NP-hard optimization problem. Recently, it has gained renewed interest through quantum computing, as QUBOs directly reduce to the Ising model, on which quantum annealing devices are based. We introduce a QUBO formulation for permutations using compare-exchange networks, with only $O(n \log^2 n)$ binary variables. This is a substantial improvement over the standard permutation matrix encoding, which requires $n^2$ variables and has a much denser interaction graph. A central feature of our approach is uniformity: each permutation corresponds to a unique variable assignment, enabling unbiased sampling. Our construction also allows additional constraints, including fixed points and parity. Moreover, it provides a representation of permutations that supports the operations multiplication and inversion, and also makes it possible to check the order of a permutation. This can be used to uniformly generate permutations of a given order or, for example, permutations that commute with a specified permutation. To our knowledge, this is the first result linking oblivious compare-exchange networks with QUBO encodings. While similar functionality can be achieved using permutation matrices, our method yields QUBOs that are both smaller and sparser. We expect this method to be practically useful in areas where unbiased sampling of constrained permutations is important, including cryptography and combinatorial design.
• Abstract（参考訳）: Quadratic Unconstrained Binary Optimization (QUBO) は標準のNPハード最適化問題である。 近年、QUBOは量子アニールデバイスをベースとしたIsingモデルに直接還元されるため、量子コンピューティングを通じて新たな関心を集めている。 比較交換ネットワークを用いた置換に対するQUBOの定式化を導入し,バイナリ変数は$O(n \log^2 n)$である。 これは標準置換行列符号化よりも大幅に改善され、$n^2$変数が必要であり、より密な相互作用グラフを持つ。 それぞれの置換は一意な変数の割り当てに対応し、偏りのないサンプリングを可能にする。 私たちの構造は、固定点やパリティを含む追加の制約も許容します。 さらに、操作の乗算と反転をサポートする置換の表現を提供し、置換の順序をチェックすることもできる。 これは与えられた順序の置換を均一に生成したり、例えば特定の置換と通勤する置換をすることができる。 我々の知る限りでは、これは、見知らぬ比較交換ネットワークとQUBOエンコーディングをリンクする最初の結果である。 同様の機能は置換行列を用いて実現できるが,本手法ではより小さくてスペーサーなQUBOが得られる。 本手法は,暗号や組合せ設計など,制約付き置換のアンバイアスサンプリングが重要である分野において,実用的に有用であることが期待されている。

関連論文リスト

• Learnable Permutation for Structured Sparsity on Transformer Models [17.777454274409912]
  構造的空間性は、一般的なモデルプルーニング技術として現れている。 重みの置換は、打ち切り後のパフォーマンスをさらに改善するための有望な方向である。 本稿では、新しいエンドツーエンドの学習可能な置換フレームワークを提案する。
  論文  参考訳（メタデータ） (2026-01-30T13:44:00Z)
• Variational quantum algorithms for permutation-based combinatorial problems: Optimal ansatz generation with applications to quadratic assignment problems and beyond [1.17431678544333]
  本稿では,1ビットと2ビットの置換ゲートで分割可能な全ての置換を生成する新しい回路に基づく量子変分アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-05-09T12:12:26Z)
• Quantum Fisher-Yates shuffle: Unifying methods for generating uniform superpositions of permutations [0.0]
  置換に対する均一な重ね合わせは、量子エラー補正、暗号、最適化において中心的な役割を果たす。 我々は、古典的なフィッシャー・イェーツシャッフルの単純かつ強力な量子化を導入し、効率的な量子アルゴリズムの組を生み出した。 Qiskitにおける我々の実装はオープンソースコードとして利用可能であり、量子置換に基づくアルゴリズムのサポートと将来的な探索が可能である。
  論文  参考訳（メタデータ） (2025-04-24T22:24:39Z)
• Random sampling of permutations through quantum circuits [0.0]
  我々は,Steinhaus-Johnson-Trotterアルゴリズムからインスピレーションを得た,置換のランダムサンプリングのための古典的アルゴリズムを提案する。 我々は、置換のランダムサンプリングに量子回路モデルを用いた古典的アルゴリズムの量子アナログを開発する。
  論文  参考訳（メタデータ） (2024-09-04T18:19:30Z)
• Sampled Transformer for Point Sets [80.66097006145999]
  スパース変換器は、連続列列列関数の普遍近似器でありながら、自己アテンション層の計算複雑性を$O(n)$に下げることができる。 我々は、追加の帰納バイアスを伴わずに点集合要素を直接処理できる$O(n)$複雑性サンプリング変換器を提案する。
  論文  参考訳（メタデータ） (2023-02-28T06:38:05Z)
• Automatic and effective discovery of quantum kernels [41.61572387137452]
  量子コンピューティングは、カーネルマシンが量子カーネルを利用してデータ間の類似度を表現できるようにすることで、機械学習モデルを強化することができる。 本稿では,ニューラルアーキテクチャ検索やAutoMLと同じような最適化手法を用いて,この問題に対するアプローチを提案する。 その結果、高エネルギー物理問題に対する我々のアプローチを検証した結果、最良のシナリオでは、手動設計のアプローチに関して、テストの精度を一致または改善できることが示された。
  論文  参考訳（メタデータ） (2022-09-22T16:42:14Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。 レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
  論文  参考訳（メタデータ） (2022-03-01T19:47:16Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。 そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-30T19:17:35Z)
• Quantum Error Mitigation Relying on Permutation Filtering [84.66087478797475]
  本稿では,既存の置換に基づく手法を特殊なケースとして含む,置換フィルタ(permutation filters)と呼ばれる一般的なフレームワークを提案する。 提案するフィルタ設計アルゴリズムは, 常に大域的最適度に収束し, フィルタが既存の置換法よりも大幅に改善できることを示す。
  論文  参考訳（メタデータ） (2021-07-03T16:07:30Z)
• Batch Bayesian Optimization on Permutations using Acquisition Weighted Kernels [86.11176756341114]
  決定点プロセスに基づく新しい効率的なバッチ取得方法であるLAWを紹介します。 本研究では,理論特性の知見を得るための後悔分析法を提案する。 二次代入などの置換を含むいくつかの標準問題に対する手法を評価する。
  論文  参考訳（メタデータ） (2021-02-26T10:15:57Z)

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

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