論文の概要: Dual-Matrix Domain-Wall: A Novel Technique for Generating Permutations
by QUBO and Ising Models with Quadratic Sizes
- arxiv url: http://arxiv.org/abs/2308.01024v1
- Date: Wed, 2 Aug 2023 09:15:30 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-03 13:29:14.639394
- Title: Dual-Matrix Domain-Wall: A Novel Technique for Generating Permutations
by QUBO and Ising Models with Quadratic Sizes
- Title（参考訳）: デュアルマトリックスドメインウォール:QUBOとIsingモデルによる2次元サイズによる置換生成の新手法
- Authors: Koji Nakano and Shunsuke Tsukiyama and Yasuaki Ito and Takashi Yazane
and Junko Yano and Takumi Kato and Shiro Ozaki and Rie Mori and Ryota Katsuki
- Abstract要約: 本稿では、二重行列ドメインウォールと呼ばれる新しい置換符号化手法を提案する。
これは、カーネル内の二次項の数と最大絶対係数値を著しく減少させる。
また、部分置換と準非制約バイナリ最適化(QUBO)モデルへの符号化手法の適用性を実証する。
- 参考スコア（独自算出の注目度）: 0.303547603131988
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Ising model is defined by an objective function using a quadratic formula
of qubit variables. The problem of an Ising model aims to determine the qubit
values of the variables that minimize the objective function, and many
optimization problems can be reduced to this problem. In this paper, we focus
on optimization problems related to permutations, where the goal is to find the
optimal permutation out of the $n!$ possible permutations of $n$ elements. To
represent these problems as Ising models, a commonly employed approach is to
use a kernel that utilizes one-hot encoding to find any one of the $n!$
permutations as the optimal solution. However, this kernel contains a large
number of quadratic terms and high absolute coefficient values. The main
contribution of this paper is the introduction of a novel permutation encoding
technique called dual-matrix domain-wall, which significantly reduces the
number of quadratic terms and the maximum absolute coefficient values in the
kernel. Surprisingly, our dual-matrix domain-wall encoding reduces the
quadratic term count and maximum absolute coefficient values from $n^3-n^2$ and
$2n-4$ to $6n^2-12n+4$ and $2$, respectively. We also demonstrate the
applicability of our encoding technique to partial permutations and Quadratic
Unconstrained Binary Optimization (QUBO) models. Furthermore, we discuss a
family of permutation problems that can be efficiently implemented using
Ising/QUBO models with our dual-matrix domain-wall encoding.
- Abstract（参考訳）: イジングモデルは、量子ビット変数の二次公式を用いて目的関数によって定義される。
イジングモデルの問題は、目的関数を最小化する変数のキュービット値を決定することを目的としており、多くの最適化問題をこの問題に還元することができる。
本稿では,$nから最適な置換を見つけることを目的として,置換に関連する最適化問題に着目する。
可能な$n$要素の置換。
これらの問題をIsingモデルとして表現するために、一般的なアプローチは、シングルホットエンコーディングを使用したカーネルを使用して、$n!のどれかを見つけることである。
最適な解決策として$ permutations。
しかし、このカーネルには多くの二次項と高い絶対係数値が含まれている。
この論文の主な貢献は、双対行列型ドメイン壁と呼ばれる新しい置換符号化技術の導入であり、二次項の数と核内の最大絶対係数値を著しく削減している。
驚くべきことに、デュアルマトリックスのドメインウォールエンコーディングは、二次項数と最大絶対係数をそれぞれ$n^3-n^2$と$n-4$から$6n^2-12n+4$と$2$に削減する。
また、部分置換と準非制約バイナリ最適化(QUBO)モデルへの符号化手法の適用性を実証する。
さらに、Ising/QUBOモデルを用いて効率よく実装できる置換問題のファミリーと、ドメインウォールの二重行列符号化について論じる。
関連論文リスト
- Kissing to Find a Match: Efficient Low-Rank Permutation Representation [33.880247068298374]
そこで本稿では,低ランク行列係数化を用いて近似し,次いで非線形性を用いて,大きな置換行列の次元性の呪いに取り組むことを提案する。
提案手法の適用性とメリットを,様々な問題に対する一連の実験を通じて実証する。
論文 参考訳（メタデータ） (2023-08-25T08:59:03Z) - Quasi-binary encoding based quantum alternating operator ansatz [7.681120805934572]
本稿では, 離散変数を持つ2次最適化モデルを解くための準バイナリ符号化に基づくアルゴリズムを提案する。
QAOAフレームワークの他の部分では、CVaR-QAOAやパラメータスケジューリング手法といったアイデアもQAOAアルゴリズムに取り入れています。
論文 参考訳（メタデータ） (2023-04-14T03:49:26Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。
これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。
本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
論文 参考訳（メタデータ） (2022-11-16T18:59:54Z) - Kernelized multi-graph matching [0.0]
本稿では,グラフの属性とエッジの両方を扱う,新しいカーネル化されたマルチグラフマッチング手法を提案する。
結果の安定性の向上につながるプロジェクタをいくつか提案する。
論文 参考訳（メタデータ） (2022-10-11T07:22:47Z) - Optimal Diagonal Preconditioning: Theory and Practice [23.79536881427839]
本稿では,列数や列数の最大化を同時に達成するために,最適対角前処理の問題を提案する。
実装が容易なベースライン分岐アルゴリズムを提案する。
次に, 片側最適対角前条件問題に特化し, 標準双対SDP問題として定式化できることを実証する。
論文 参考訳（メタデータ） (2022-09-02T04:21:28Z) - Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。
レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
論文 参考訳（メタデータ） (2022-03-01T19:47:16Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-02-23T02:39:04Z) - Fast Differentiable Matrix Square Root and Inverse Square Root [65.67315418971688]
微分可能な行列平方根と逆平方根を計算するためのより効率的な2つの変種を提案する。
前方伝搬には, Matrix Taylor Polynomial (MTP) を用いる方法と, Matrix Pad'e Approximants (MPA) を使用する方法がある。
一連の数値実験により、両方の手法がSVDやNSの繰り返しと比較してかなりスピードアップすることが示された。
論文 参考訳（メタデータ） (2022-01-29T10:00:35Z) - Fast Differentiable Matrix Square Root [65.67315418971688]
微分可能な行列平方根を計算するために、より効率的な2つの変種を提案する。
前方伝播には, Matrix Taylor Polynomial (MTP) を用いる方法がある。
もう1つの方法は Matrix Pad'e Approximants (MPA) を使うことである。
論文 参考訳（メタデータ） (2022-01-21T12:18:06Z) - Sparse Quadratic Optimisation over the Stiefel Manifold with Application
to Permutation Synchronisation [71.27989298860481]
二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。
そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-30T19:17:35Z) - Combinatorial optimization through variational quantum power method [0.0]
本稿では,電力繰り返しに対する変分量子回路法を提案する。
ユニタリ行列の固有ペアや関連するハミルトン多様体を見つけるのに使うことができる。
回路は、短期量子コンピュータ上で簡単にシミュレートできる。
論文 参考訳（メタデータ） (2020-07-02T10:34:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。