論文の概要: Beyond QUBO and HOBO formulations, solving the Travelling Salesman Problem on a quantum boson sampler
- arxiv url: http://arxiv.org/abs/2406.14252v1
- Date: Thu, 20 Jun 2024 12:25:00 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-21 13:52:01.141466
- Title: Beyond QUBO and HOBO formulations, solving the Travelling Salesman Problem on a quantum boson sampler
- Title（参考訳）: QUBOおよびHOBOの定式化を超えて、量子ボソンサンプリング器におけるトラベリングセールスマン問題の解法
- Authors: Daniel Goldsmith, Joe Day-Evans,
- Abstract要約: 量子デバイスからの全ての出力が有効な経路にマッピングされるため、設計上、ペナルティ項は存在しない。
ボソンサンプルを用いて研究を行ったが、この新しい定式化は他の量子デバイスと関係があると信じている。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: The Travelling Salesman Problem (TSP) is an important combinatorial optimisation problem, and is usually solved on a quantum computer using a Quadratic Unconstrained Binary Optimisation (QUBO) formulation or a Higher Order Binary Optimisation(HOBO) formulation. In these formulations, penalty terms are added to the objective function for outputs that don't map to valid routes. We present a novel formulation which needs fewer binary variables, and where, by design, there are no penalty terms because all outputs from the quantum device are mapped to valid routes. Simulations of a quantum boson sampler were carried out which demonstrate that larger networks can be solved with this penalty-free formulation than with formulations with penalties. Simulations were successfully translated to hardware by running a non-QUBO formulation with penalties on an early experimental prototype ORCA PT-1 boson sampler. Although we worked with a boson sampler, we believe that this novel formulation is relevant to other quantum devices. This work shows that a good embedding for combinatorial optimisation problems can solve larger problems with the same quantum computing resource. The flexibility of boson sampling quantum devices is a powerful asset in solving combinatorial optimisation problem, because it enables formulations where the output string is always mapped to a valid solution, avoiding the need for penalties.
- Abstract（参考訳）: トラベリングセールスマン問題(TSP)は重要な組合せ最適化問題であり、通常、二次的非制約二項最適化(QUBO)の定式化や高次二項最適化(HOBO)の定式化を用いて量子コンピュータ上で解かれる。
これらの定式化では、有効経路にマップされない出力に対する目的関数にペナルティ項が付加される。
量子デバイスからの全ての出力が有効な経路にマッピングされるため、設計上、ペナルティ項は存在しない。
量子ボソンサンプリング器のシミュレーションを行い、このペナルティのない定式化により、ペナルティを持つ定式化よりも大きなネットワークを解けることを示した。
シミュレーションは、初期の実験用プロトタイプ ORCA PT-1 ボソンサンプリング装置上で、罰則を付した非QUBOの定式化を実行することで、ハードウェアに変換された。
ボソンサンプルを用いて研究を行ったが、この新しい定式化は他の量子デバイスと関係があると信じている。
この研究は、組合せ最適化問題に対する優れた埋め込みが、同じ量子コンピューティングリソースでより大きな問題を解決することを示している。
ボソンサンプリング量子デバイスの柔軟性は、出力文字列が常に有効な解にマッピングされるような定式化を可能にするため、組合せ最適化問題を解決するための強力な資産である。
関連論文リスト
- Increasing the Hardness of Posiform Planting Using Random QUBOs for Programmable Quantum Annealer Benchmarking [1.6385815610837167]
我々は,多数の小さな離散係数スピングラスイジングモデルを融合させることにより,ポジフォーム植込みQUBOを計算的に困難にすることを検討する。
3つのD-Wave超伝導量子アニーリングプロセッサの性能をベンチマークする。
D-Wave QPUの地中サンプリング成功率は、我々が採用するランダムQUBOのサイズに対して変化しないことがわかった。
論文 参考訳（メタデータ） (2024-11-06T02:46:33Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - QAL-BP: An Augmented Lagrangian Quantum Approach for Bin Packing [4.589533935256401]
ビンパッキングは人工知能の分野でよく知られたNP-Hard問題である。
量子技術の最近の進歩は、かなりの計算スピードアップを達成するための有望な可能性を示している。
QAL-BPは, ビンパッキングに特化して設計された, 擬似非拘束バイナリ最適化(QUBO)の定式化である。
論文 参考訳（メタデータ） (2023-09-22T07:37:20Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。
これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。
本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
論文 参考訳（メタデータ） (2022-11-16T18:59:54Z) - Quantum-inspired optimization for wavelength assignment [51.55491037321065]
波長割当問題を解くための量子インスピレーションアルゴリズムを提案し,開発する。
本研究は,電気通信における現実的な問題に対する量子インスパイアされたアルゴリズムの活用の道筋をたどるものである。
論文 参考訳（メタデータ） (2022-11-01T07:52:47Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳（メタデータ） (2021-07-08T17:59:55Z) - Unconstrained Binary Models of the Travelling Salesman Problem Variants
for Quantum Optimization [0.0]
本稿では,Travelling Salesman Problem with Time Windows (TSPTW) の量子コンピュータ上での解法を詳細に分析する。
本稿では、制約のない二項最適化と高階二項最適化の定式化を導入する。
TSPTW問題のエッジベースおよびノードベースの定式化の利点を示す。
論文 参考訳（メタデータ） (2021-06-16T18:01:31Z) - Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。
本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。
Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
論文 参考訳（メタデータ） (2021-05-06T17:59:38Z) - Multimodal Container Planning: a QUBO Formulation and Implementation on
a Quantum Annealer [0.0]
マルチモーダル・コンテナ・プランニングの応用について述べる。
本稿では,この問題をQUBO問題定式化にマップする方法と,D-Wave Systems が生成する量子アニール上での実用化方法について述べる。
論文 参考訳（メタデータ） (2020-07-03T14:51:41Z) - Quantum Approximate Optimization for Hard Problems in Linear Algebra [0.0]
本稿では,線形代数における他の難解問題の構成要素として,二元線形最小平方体 (BLLS) に対するQAOAについて検討する。
この研究の範囲では、ノイズのない量子シミュレータ、デバイスリアリスティックノイズモデルを含むシミュレータ、2つのIBM Q 5-qubitマシンで実験を行った。
我々の数値は、基底状態のサンプリングの確率が$pleq3$のQAOA深さでBLLSのQAOAよりも優れていることを示している。
論文 参考訳（メタデータ） (2020-06-27T20:13:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。