論文の概要: Encoding trade-offs and design toolkits in quantum algorithms for
discrete optimization: coloring, routing, scheduling, and other problems
- arxiv url: http://arxiv.org/abs/2203.14432v2
- Date: Sat, 19 Aug 2023 00:25:03 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-23 03:16:01.856341
- Title: Encoding trade-offs and design toolkits in quantum algorithms for
discrete optimization: coloring, routing, scheduling, and other problems
- Title（参考訳）: 離散最適化のための量子アルゴリズムにおけるトレードオフと設計ツールキットのエンコード:色付け、ルーティング、スケジューリング、その他の問題
- Authors: Nicolas PD Sawaya, Albert T Schmitz, Stuart Hadfield
- Abstract要約: 離散最適化問題(整数型最適化問題)を直感的に合成・解析する手法を提案する。
この方法は、符号化に依存しない離散量子中間表現(DQIR)を用いて表現される。
第二に、複数のランタイムエンコーディングを比較した数値的研究を行う。
第3に、我々は16レベルの量子変数までの低深度グラフ由来部分ミキサー(GDPM)を設計する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Challenging combinatorial optimization problems are ubiquitous in science and
engineering. Several quantum methods for optimization have recently been
developed, in different settings including both exact and approximate solvers.
Addressing this field of research, this manuscript has three distinct purposes.
First, we present an intuitive method for synthesizing and analyzing discrete
(i.e., integer-based) optimization problems, wherein the problem and
corresponding algorithmic primitives are expressed using a discrete quantum
intermediate representation (DQIR) that is encoding-independent. This compact
representation often allows for more efficient problem compilation, automated
analyses of different encoding choices, easier interpretability, more complex
runtime procedures, and richer programmability, as compared to previous
approaches, which we demonstrate with a number of examples. Second, we perform
numerical studies comparing several qubit encodings; the results exhibit a
number of preliminary trends that help guide the choice of encoding for a
particular set of hardware and a particular problem and algorithm. Our study
includes problems related to graph coloring, the traveling salesperson problem,
factory/machine scheduling, financial portfolio rebalancing, and integer linear
programming. Third, we design low-depth graph-derived partial mixers (GDPMs) up
to 16-level quantum variables, demonstrating that compact (binary) encodings
are more amenable to QAOA than previously understood. We expect this toolkit of
programming abstractions and low-level building blocks to aid in designing
quantum algorithms for discrete combinatorial problems.
- Abstract（参考訳）: 組合せ最適化の問題は、科学と工学においてユビキタスである。
最適化のためのいくつかの量子手法は、厳密解と近似解法の両方を含む様々な設定で最近開発されている。
この研究分野に対して、この写本には3つの異なる目的がある。
まず,符号化非依存な離散量子中間表現(dqir)を用いて,問題と対応するアルゴリズムプリミティブを表現し,離散(整数ベース)最適化問題の合成と解析を行うための直感的手法を提案する。
このコンパクトな表現は、多くの例で示すように、より効率的な問題コンパイル、異なる符号化選択の自動解析、より簡単な解釈可能性、より複雑な実行手順、より豊かなプログラム可能性を可能にする。
第2に、いくつかの量子ビット符号化を比較した数値研究を行い、その結果、特定のハードウェア群と特定の問題やアルゴリズムに対する符号化の選択を導くためのいくつかの予備的傾向を示す。
本研究は,グラフ彩色,巡回セールスパーソン問題,ファクトリー/マシンスケジューリング,金融ポートフォリオのリバランス,整数線形計画に関する問題を含む。
第3に、我々は16レベル量子変数までの低深度グラフ由来部分ミキサー(GDPM)を設計し、コンパクト(バイナリ)エンコーディングが以前理解していたよりもQAOAに適していることを示した。
我々は、このプログラミング抽象化のツールキットと低レベルビルディングブロックが、離散組合せ問題に対する量子アルゴリズムの設計を支援することを期待している。
関連論文リスト
- Exploring the Potential of Qutrits for Quantum Optimization of Graph
Coloring [0.0]
Qutritsは、短期デバイス上のいくつかの問題を解決するのに役立つかもしれない。
我々はPennyLaneを用いてノイズレスシミュレーションを行い、量子ビットベースのQAOAに対する定式化を比較する。
この研究は、クォートリットが近距離デバイス上のいくつかの問題を解決するのに有用であることを示しているが、ノイズの多い環境におけるその可能性を評価するにはさらなる作業が必要であることを示唆している。
論文 参考訳（メタデータ） (2023-08-15T21:31:37Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - QuAnt: Quantum Annealing with Learnt Couplings [18.40480332882025]
我々はデータからQUBOフォームを導出するのではなく、勾配のバックプロパゲーションを通して学習する。
本稿では,グラフマッチングや2次元点雲のアライメント,3次元回転推定といった多種多様な問題に対する学習QUBOの利点を示す。
論文 参考訳（メタデータ） (2022-10-13T17:59:46Z) - Quantum Sparse Coding [5.130440339897477]
我々はスパース符号化のための量子インスピレーション付きアルゴリズムを開発した。
量子コンピュータとイジングマシンの出現は、より正確な推定につながる可能性がある。
我々はLightrの量子インスパイアされたデジタルプラットフォーム上でシミュレーションデータを用いて数値実験を行う。
論文 参考訳（メタデータ） (2022-09-08T13:00:30Z) - Optimization-based Block Coordinate Gradient Coding for Mitigating
Partial Stragglers in Distributed Learning [58.91954425047425]
本稿では,分散学習における部分トラグラーの緩和を目的とした,新たな勾配符号化方式を提案する。
L の符号パラメータを L に表わした勾配座標符号化方式を提案する。
論文 参考訳（メタデータ） (2022-06-06T09:25:40Z) - Quantum Feature Selection [2.5934039615414615]
機械学習では、より少ない機能がモデルの複雑さを減少させる。
本稿では,2次非制約二元最適化問題に基づく特徴選択アルゴリズムを提案する。
反復法や欲求法とは対照的に、我々の直接的なアプローチは高品質な解をもたらす。
論文 参考訳（メタデータ） (2022-03-24T16:22:25Z) - Resource Optimisation of Coherently Controlled Quantum Computations with
the PBS-calculus [55.2480439325792]
量子計算のコヒーレント制御は、いくつかの量子プロトコルやアルゴリズムを改善するために使用できる。
我々は、量子光学にインスパイアされたコヒーレント制御のためのグラフィカル言語PBS計算を洗練する。
論文 参考訳（メタデータ） (2022-02-10T18:59:52Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳（メタデータ） (2021-07-08T17:59:55Z) - Optimal qubit assignment and routing via integer programming [0.22940141855172028]
論理量子回路を2ビット接続に制限のあるハードウェアにマッピングする問題を考察する。
我々はこの問題を2変数のネットワークフロー定式化を用いて整数線形プログラムとしてモデル化する。
本稿では,回路の忠実度,全深度,クロストークの尺度などのコスト関数について考察する。
論文 参考訳（メタデータ） (2021-06-11T15:02:26Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z) - Discovering Representations for Black-box Optimization [73.59962178534361]
ブラックボックス最適化符号化は手作業で行うのではなく,自動的に学習可能であることを示す。
学習された表現は、標準的なMAP-Elitesよりも桁違いに少ない評価で高次元の問題を解くことができることを示す。
論文 参考訳（メタデータ） (2020-03-09T20:06:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。