論文の概要: Computational Overhead of Locality Reduction in Binary Optimization
Problems
- arxiv url: http://arxiv.org/abs/2012.09681v2
- Date: Mon, 19 Jul 2021 18:02:18 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-20 08:25:19.077200
- Title: Computational Overhead of Locality Reduction in Binary Optimization
Problems
- Title（参考訳）: 二元最適化問題における局所性低減の計算オーバーヘッド
- Authors: Elisabetta Valiante, Maritza Hernandez, Amin Barzegar, Helmut G.
Katzgraber
- Abstract要約: 本稿では,2つの局所的(二次的)コスト関数のみに対応可能な解法の大部分に必要な局所性低減の効果について論じる。
Microsoft Azure Quantumのモンテカルロ並列解法を用いて、2つの局所表現へのポスト還元により、問題の解決がかなり困難になることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recently, there has been considerable interest in solving optimization
problems by mapping these onto a binary representation, sparked mostly by the
use of quantum annealing machines. Such binary representation is reminiscent of
a discrete physical two-state system, such as the Ising model. As such,
physics-inspired techniques -- commonly used in fundamental physics studies --
are ideally suited to solve optimization problems in a binary format. While
binary representations can be often found for paradigmatic optimization
problems, these typically result in k-local higher-order unconstrained binary
optimization cost functions. In this work, we discuss the effects of locality
reduction needed for the majority of the currently available quantum and
quantum-inspired solvers that can only accommodate 2-local (quadratic) cost
functions. General locality reduction approaches require the introduction of
ancillary variables which cause an overhead over the native problem. Using a
parallel tempering Monte Carlo solver on Microsoft Azure Quantum, as well as
k-local binary problems with planted solutions, we show that post reduction to
a corresponding 2-local representation the problems become considerably harder
to solve. We further quantify the increase in computational hardness introduced
by the reduction algorithm by measuring the variation of number of variables,
statistics of the coefficient values, and the population annealing entropic
family size. Our results demonstrate the importance of avoiding locality
reduction when solving optimization problems.
- Abstract（参考訳）: 近年、量子アニールマシンの使用によって引き起こされるバイナリ表現にマッピングすることで最適化問題の解決に大きな関心が寄せられている。
そのような二進表現は、イジングモデルのような離散的な物理的二状態系を想起させる。
そのため、物理学にインスパイアされた技術(基礎物理学研究でよく使われる)は、最適化問題を二項形式で解くのに理想的に適している。
バイナリ表現はパラダイム最適化の問題でよく見られるが、一般的にはk-局所高次非拘束型バイナリ最適化コスト関数となる。
本研究では,2-局所(量子)コスト関数のみに対応可能な,現在利用可能な量子および量子に触発された解法の大部分に必要な局所性低減の効果について考察する。
一般的な局所性低減アプローチでは、ネイティブ問題にオーバーヘッドをもたらす補助変数を導入する必要がある。
microsoft azure quantum上の並列テンパリングモンテカルロソルバと、植込みされたソリューションを用いたkローカルバイナリ問題を用いて、対応する2ローカル表現へのポストリダクションにより、問題は解決がかなり困難になることを示す。
さらに, 変数数の変化, 係数値の統計値, 集団別エントロピーファミリーサイズを測定することにより, 還元アルゴリズムが導入する計算硬さの増大を定量化する。
その結果,最適化問題を解決する際に局所性低下を回避することの重要性が示された。
関連論文リスト
- Analysis of the Non-variational Quantum Walk-based Optimisation Algorithm [0.0]
本稿では,多種多様な最適化問題を解くために設計された非変分量子アルゴリズムを詳細に紹介する。
このアルゴリズムは、増幅状態の繰り返しの準備と測定から最適解とほぼ最適解を返す。
論文 参考訳（メタデータ） (2024-07-29T13:54:28Z) - Quantum optimization using a 127-qubit gate-model IBM quantum computer can outperform quantum annealers for nontrivial binary optimization problems [0.0]
ゲートモデル量子コンピュータにおける二項最適化問題に対する包括的量子解法を提案する。
最大127キュービットの問題の正しい解を一貫して提供する。
我々は、古典的に非自明な2進最適化問題に対して、IBM量子コンピュータ上でこの解法をベンチマークする。
論文 参考訳（メタデータ） (2024-06-03T19:08:01Z) - An Optimization-based Deep Equilibrium Model for Hyperspectral Image
Deconvolution with Convergence Guarantees [71.57324258813675]
本稿では,ハイパースペクトル画像のデコンボリューション問題に対処する新しい手法を提案する。
新しい最適化問題を定式化し、学習可能な正規化器をニューラルネットワークの形で活用する。
導出した反復解法は、Deep Equilibriumフレームワーク内の不動点計算問題として表現される。
論文 参考訳（メタデータ） (2023-06-10T08:25:16Z) - Quantum approximate optimization algorithm for qudit systems [0.0]
量子近似最適化アルゴリズム(QAOA)について考察する。
本稿では、QAOAを用いて様々な整数最適化問題を定式化する方法を説明する。
最大$kのカラー化問題にマッピングした充電最適化問題の数値計算結果を示す。
論文 参考訳（メタデータ） (2022-04-01T10:37:57Z) - A Constrained Optimization Approach to Bilevel Optimization with
Multiple Inner Minima [49.320758794766185]
そこで本研究では,両レベル問題を等価な制約付き最適化に変換する手法を提案する。
このようなアプローチには、(a)多重内極小問題への対処、(b)ジャコビアン計算のない完全一階効率など、いくつかの利点がある。
論文 参考訳（メタデータ） (2022-03-01T18:20:01Z) - Quadratic Unconstrained Binary Optimisation via Quantum-Inspired
Annealing [58.720142291102135]
本稿では,2次非制約二項最適化の事例に対する近似解を求める古典的アルゴリズムを提案する。
我々は、チューニング可能な硬さと植え付けソリューションを備えた大規模問題インスタンスに対して、我々のアプローチをベンチマークする。
論文 参考訳（メタデータ） (2021-08-18T09:26:17Z) - Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
マルチバスグラフ複雑性と非線形活性化関数の2つの革新の恩恵を受ける新しい変分量子アルゴリズムを導入する。
その結果,最適化性能が向上し,有効景観が2つ向上し,測定の進歩が減少した。
論文 参考訳（メタデータ） (2021-06-24T20:16:02Z) - Machine Learning Framework for Quantum Sampling of Highly-Constrained,
Continuous Optimization Problems [101.18253437732933]
本研究では,連続空間の逆設計問題を,制約のないバイナリ最適化問題にマッピングする,汎用的な機械学習ベースのフレームワークを開発する。
本研究では, 熱発光トポロジを熱光応用に最適化し, (ii) 高効率ビームステアリングのための拡散メタグレーティングを行うことにより, 2つの逆設計問題に対するフレームワークの性能を示す。
論文 参考訳（メタデータ） (2021-05-06T02:22:23Z) - Solving Quadratic Unconstrained Binary Optimization with
divide-and-conquer and quantum algorithms [0.0]
分割・対数手法を用いて、元の問題を小さな問題の集合に還元する。
この手法は任意のQUBOインスタンスに適用でき、全古典的またはハイブリッドな量子古典的アプローチにつながる。
論文 参考訳（メタデータ） (2021-01-19T19:00:40Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z) - Modeling Linear Inequality Constraints in Quadratic Binary Optimization
for Variational Quantum Eigensolver [0.0]
本稿では, 変分量子固有解法における配向型変分形式の利用について紹介する。
通常、いくつかの最適化問題に現れる4つの制約がモデル化されている。
提案手法の主な利点は、変分形式のパラメータの数が一定であることである。
論文 参考訳（メタデータ） (2020-07-26T23:36:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。