論文の概要: Reducing QUBO Density by Factoring Out Semi-Symmetries
- arxiv url: http://arxiv.org/abs/2412.17841v2
- Date: Fri, 27 Dec 2024 16:49:23 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-30 17:21:54.636384
- Title: Reducing QUBO Density by Factoring Out Semi-Symmetries
- Title（参考訳）: 半対称性の分解によるQUBO密度の低減
- Authors: Jonas Nüßlein, Leo Sünkel, Jonas Stein, Tobias Rohe, Daniëlle Schuman, Sebastian Feld, Corey O'Meara, Giorgio Cortiana, Claudia Linnhoff-Popien,
- Abstract要約: 本稿では,QUBO行列におけるテクステミシンメトリの概念を紹介する。
提案アルゴリズムは結合数と回路深さを最大45%削減することを示した。
- 参考スコア（独自算出の注目度）: 4.581191399651181
- License:
- Abstract: Quantum Approximate Optimization Algorithm (QAOA) and Quantum Annealing are prominent approaches for solving combinatorial optimization problems, such as those formulated as Quadratic Unconstrained Binary Optimization (QUBO). These algorithms aim to minimize the objective function $x^T Q x$, where $Q$ is a QUBO matrix. However, the number of two-qubit CNOT gates in QAOA circuits and the complexity of problem embeddings in Quantum Annealing scale linearly with the number of non-zero couplings in $Q$, contributing to significant computational and error-related challenges. To address this, we introduce the concept of \textit{semi-symmetries} in QUBO matrices and propose an algorithm for identifying and factoring these symmetries into ancilla qubits. \textit{Semi-symmetries} frequently arise in optimization problems such as \textit{Maximum Clique}, \textit{Hamilton Cycles}, \textit{Graph Coloring}, and \textit{Graph Isomorphism}. We theoretically demonstrate that the modified QUBO matrix $Q_{\text{mod}}$ retains the same energy spectrum as the original $Q$. Experimental evaluations on the aforementioned problems show that our algorithm reduces the number of couplings and QAOA circuit depth by up to $45\%$. For Quantum Annealing, these reductions also lead to sparser problem embeddings, shorter qubit chains and better performance. This work highlights the utility of exploiting QUBO matrix structure to optimize quantum algorithms, advancing their scalability and practical applicability to real-world combinatorial problems.
- Abstract（参考訳）: 量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)と量子アニーリング(Quantum Annealing)は、擬似非制約二項最適化(Quantum Unconstrained Binary Optimization, QUBO)として定式化されたような組合せ最適化問題に対する顕著なアプローチである。
これらのアルゴリズムは目的関数 $x^T Q x$ を最小化することを目的としており、$Q$ は QUBO 行列である。
しかし、QAOA回路における2量子CNOTゲートの数と量子アニーリングにおける問題埋め込みの複雑さは、Q$の非ゼロカップリングの数と線形にスケールし、計算およびエラー関連の大きな課題に寄与する。
そこで本研究では,QUBO 行列における \textit{semi-symmetries} の概念を導入し,これらの対称性をアンシラ量子ビットに同定・分解するアルゴリズムを提案する。
\textit{Semi-symmetries} はしばしば \textit{Maximum Clique}, \textit{Hamilton Cycles}, \textit{Graph Coloring}, \textit{Graph Isomorphism} などの最適化問題に現れる。
理論的には、修正 QUBO 行列 $Q_{\text{mod}}$ が元の $Q$ と同じエネルギースペクトルを保持することを証明している。
上記の問題に対する実験結果から,本アルゴリズムは結合数とQAOA回路の深さを最大45 %まで削減することを示した。
量子アニーリング(Quantum Annealing)では、これらの削減はスペーサー問題埋め込み、短いキュービットチェーン、より良いパフォーマンスをもたらす。
この研究はQUBO行列構造を利用して量子アルゴリズムを最適化し、そのスケーラビリティと現実の組合せ問題への適用性を向上する。
関連論文リスト
- Reducing QAOA Circuit Depth by Factoring out Semi-Symmetries [4.958204128486634]
修正 QUBO 行列 $Q_Hamilton$ が元の $Q$ と同じエネルギースペクトルを記述することを示す。
提案アルゴリズムは結合数を最大49%$、回路深さを最大41%$に削減した。
論文 参考訳（メタデータ） (2024-11-13T18:04:01Z) - Encodings of the weighted MAX k-CUT on qubit systems [0.0]
本稿では,重み付きMAX k-CUT問題の量子ビットシステム上での符号化法について検討する。
各種符号化方式について検討し,これらの手法の有効性について検討する。
重み付きおよび非重み付きグラフインスタンスの数値シミュレーションは、これらの符号化方式の有効性を実証する。
論文 参考訳（メタデータ） (2024-11-13T13:21:35Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Symmetries and Dimension Reduction in Quantum Approximate Optimization
Algorithm [1.3469999282609788]
我々は、$n-要素$d$-ary文字列の集合上で定義される最適化問題の一般化された定式化に焦点を当てる。
我々の主な貢献は、当初提案されたQAOAの次元を含む。
アルゴリズムをより小さな次元の空間に制限することは、回路の量子シミュレーションと古典シミュレーションの両方を著しく加速させる可能性がある。
論文 参考訳（メタデータ） (2023-09-25T00:35:40Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - An entanglement perspective on the quantum approximate optimization
algorithm [0.0]
ランダム化および最適化されたQAOA回路による絡み合いの増大と広がりについて検討する。
また、ランダム行列理論に関連する絡み合いスペクトルについても検討する。
論文 参考訳（メタデータ） (2022-06-14T17:37:44Z) - QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum
machines [81.4597482536073]
量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。
量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。
提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
論文 参考訳（メタデータ） (2022-05-24T03:49:10Z) - Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。
レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
論文 参考訳（メタデータ） (2022-03-01T19:47:16Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳（メタデータ） (2021-07-08T17:59:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。