論文の概要: Compressed Quadratization of Higher Order Binary Optimization Problems
- arxiv url: http://arxiv.org/abs/2001.00658v1
- Date: Thu, 2 Jan 2020 22:48:50 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-16 04:50:23.217859
- Title: Compressed Quadratization of Higher Order Binary Optimization Problems
- Title（参考訳）: 高次二項最適化問題の圧縮擬似化
- Authors: Avradip Mandal, Arnab Roy, Sarvagya Upadhyay and Hayato
Ushijima-Mwesigwa
- Abstract要約: 量子および量子に着想を得たアニールの最近のハードウェア進歩は、NPハード最適化問題を解くためにかなりのスピードアップを約束している。
本研究では,イジング空間において,1項の次数還元には2変数の導入が必要であることを証明した。
高次イジング問題に対して、これは結果のQUBO問題のよりコンパクトな表現をもたらす。
- 参考スコア（独自算出の注目度）: 5.833700634137687
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recent hardware advances in quantum and quantum-inspired annealers promise
substantial speedup for solving NP-hard combinatorial optimization problems
compared to general-purpose computers. These special-purpose hardware are built
for solving hard instances of Quadratic Unconstrained Binary Optimization
(QUBO) problems. In terms of number of variables and precision of these
hardware are usually resource-constrained and they work either in Ising space
{-1,1} or in Boolean space {0,1}. Many naturally occurring problem instances
are higher-order in nature. The known method to reduce the degree of a
higher-order optimization problem uses Rosenberg's polynomial. The method works
in Boolean space by reducing the degree of one term by introducing one extra
variable. In this work, we prove that in Ising space the degree reduction of
one term requires the introduction of two variables. Our proposed method of
degree reduction works directly in Ising space, as opposed to converting an
Ising polynomial to Boolean space and applying previously known Rosenberg's
polynomial. For sparse higher-order Ising problems, this results in a more
compact representation of the resultant QUBO problem, which is crucial for
utilizing resource-constrained QUBO solvers.
- Abstract（参考訳）: 量子および量子インスパイアされたアニーラーの最近のハードウェア進歩は、汎用コンピュータと比較してnp-hard combinatorial optimization問題を解くための大幅なスピードアップを約束している。
これらの専用ハードウェアは、擬似非拘束バイナリ最適化(QUBO)問題のハードインスタンスを解くために構築されている。
変数数やハードウェアの精度に関しては、通常はリソース制約があり、イジング空間 {-1,1} やブール空間 {0,1} で動作します。
自然に発生する問題の多くは自然に高次である。
高階最適化問題の次数を減少させる既知の方法はローゼンバーグ多項式を用いる。
この方法はブール空間において、1つの余剰変数を導入して1項の次数を減らして機能する。
本研究では,イジング空間において,1項の次数還元には2変数の導入が必要であることを示す。
提案手法はイジング多項式をブール空間に変換し、既知のローゼンバーグ多項式を適用するのとは対照的に、イジング空間において直接作用する。
厳密な高次Ising問題に対しては、リソース制約付きQUBO問題をよりコンパクトに表現し、資源制約付きQUBOソルバの活用に不可欠である。
関連論文リスト
- An encoding of argumentation problems using quadratic unconstrained binary optimization [1.104960878651584]
そこで本研究では,NP-Complete問題から準拘束的二項最適化問題への抽象化問題を符号化する手法を開発した。
QUBOの定式化により、QuantumやDigital Annealersといった新しいコンピューティングアーキテクチャを活用することができる。
論証や議論の実施における古典的問題の正しさと適用性を証明するために,実験を行った。
論文 参考訳（メタデータ） (2024-09-09T11:29:46Z) - Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。
これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。
本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
論文 参考訳（メタデータ） (2022-11-16T18:59:54Z) - Sparse Polynomial Optimization: Theory and Practice [5.27013884159732]
本書は、この課題に重要な科学的意味を持って取り組むためのいくつかの取り組みを提示している。
これは計算複雑性の観点からうまくスケールする代替の最適化スキームを提供する。
制約のない問題や制約のない問題に対して、緩和の疎開的階層を提示する。
論文 参考訳（メタデータ） (2022-08-23T18:56:05Z) - Penalty Weights in QUBO Formulations: Permutation Problems [0.0]
量子コンピュータで動くよう設計された最適化アルゴリズムは 近年 研究の関心を集めています
これらの解法の多くは、二項形式と二項形式の問題を最適化することしかできない。
多くの最適化問題があり、自然に置換として表される。
より有望な結果をもたらすペナルティ重みを計算するための新しい静的手法を提案する。
論文 参考訳（メタデータ） (2022-06-20T22:00:38Z) - Comparing the Digital Annealer with Classical Evolutionary Algorithm [0.0]
特殊なハードウェアを使用するソルバの例として、IBMのQuantum System OneとD-waveのQuantum Annealer (QA)、富士通のDigital Annealer (DA)がある。
論文 参考訳（メタデータ） (2022-05-26T19:04:20Z) - Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
ヒルベルト空間全体の部分空間への発展を制限する混合作用素を構築するための枠組みを提案する。
我々は,「ワンホット」状態の部分空間を保存するために設計された「XY」ミキサーを,多くの計算基底状態によって与えられる部分空間の一般の場合に一般化する。
我々の分析は、現在知られているよりもCXゲートが少ない"XY"ミキサーのトロタライズも有効である。
論文 参考訳（メタデータ） (2022-03-11T17:19:26Z) - An Accelerated Variance-Reduced Conditional Gradient Sliding Algorithm
for First-order and Zeroth-order Optimization [111.24899593052851]
条件勾配アルゴリズム(Frank-Wolfeアルゴリズムとも呼ばれる)は、最近、機械学習コミュニティで人気を取り戻している。
ARCSは、ゼロ階最適化において凸問題を解く最初のゼロ階条件勾配スライディング型アルゴリズムである。
1次最適化では、ARCSの収束結果は、勾配クエリのオラクルの数で、従来のアルゴリズムよりも大幅に優れていた。
論文 参考訳（メタデータ） (2021-09-18T07:08:11Z) - Computational Overhead of Locality Reduction in Binary Optimization
Problems [0.0]
本稿では,2つの局所的(二次的)コスト関数のみに対応可能な解法の大部分に必要な局所性低減の効果について論じる。
Microsoft Azure Quantumのモンテカルロ並列解法を用いて、2つの局所表現へのポスト還元により、問題の解決がかなり困難になることを示す。
論文 参考訳（メタデータ） (2020-12-17T15:49:55Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳（メタデータ） (2020-06-16T17:55:46Z) - Hardness of Random Optimization Problems for Boolean Circuits,
Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。
ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
論文 参考訳（メタデータ） (2020-04-25T05:45:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。