論文の概要: Alleviating the quantum Big-$M$ problem

• arxiv url: http://arxiv.org/abs/2307.10379v1
• Date: Wed, 19 Jul 2023 18:00:05 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-21 16:00:50.229559
• Title: Alleviating the quantum Big-$M$ problem
• Title（参考訳）: 量子Big-M$問題を軽減する
• Authors: Edoardo Alessandroni, Sergi Ramos, Ingo Roth, Emiliano Traversi, Leandro Aolita
• Abstract要約: 我々は量子ビッグ-M$問題の理論を発展させる。 SDP緩和に基づく実用的なQUBO変換アルゴリズムを提供する。 我々の発見は、現在および短期量子だけでなく、量子に着想を得た解法にも関係している。
• 参考スコア（独自算出の注目度）: 0.5911087507716211
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A major obstacle towards practical quantum optimizations is the reformulation of constrained problems as a quadratic unconstrained binary optimization (QUBO). Existing QUBO translators significantly over-estimate the weight $M$ of the penalization terms. This issue, known as the "Big-$M$" problem in classical optimization, becomes even more daunting for quantum solvers, since it affects the physical energy scale. We develop a theory of the quantum big-$M$ problem. We observe that finding the optimal $M$ is NP-hard and establish relevant upper bounds on the Hamiltonian spectral gap $\Delta$, formalizing the intuition that $\Delta=\mathcal{O}(M^{-1})$. Most importantly, we deliver a practical QUBO-reformulation algorithm based on the SDP relaxation. Numerical benchmarks show an impressive out-performance over previous methods. In particular, for portfolio optimization (PO) instances of up to 24 qubits, our algorithm gives values of $M$ ($\Delta$) orders of magnitude smaller (greater). Additionally, we experimentally solve 6-qubit PO instances with an approximately adiabatic algorithm on an IonQ device. There, we observe a remarkable advantage both in the probability of right solution and in the average solution quality. Our findings are relevant not only to current and near-term quantum but also quantum-inspired solvers.
• Abstract（参考訳）: 実用的な量子最適化への大きな障害は、二分最適化(qubo)としての制約付き問題の再構成である。 既存のqubo翻訳者はペナルイゼーション用語の重量をかなり過大評価している。 この問題は古典的最適化において「大きな$m$」問題と呼ばれ、物理的エネルギースケールに影響を与えるため、量子ソルバにとってさらに厄介な問題となる。 我々は量子ビッグ-M$問題の理論を発展させる。 最適な$M$を見つけることはNPハードであり、ハミルトニアンスペクトルギャップ$\Delta$で関連する上限を確立し、$\Delta=\mathcal{O}(M^{-1})$という直観を定式化する。 最も重要なことは、SDP緩和に基づく実践的なQUBO変換アルゴリズムを提供することである。 数値ベンチマークでは、従来の手法よりも優れた性能を示している。 特に、最大24キュービットのポートフォリオ最適化(PO)インスタンスの場合、我々のアルゴリズムは、M$$$\Delta$)のオーダーを桁違いに小さくする(より大きい)。 さらに,IonQ デバイス上での近似断熱アルゴリズムを用いて 6-qubit PO インスタンスを実験的に解く。 そこで我々は,正しい解の確率と平均解の質の両方において顕著な利点を見出した。 我々の発見は、現在および短期量子だけでなく、量子に着想を得た解法にも関係している。

関連論文リスト

• 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)
• A quantum annealing approach to the minimum distance problem of quantum codes [0.0]
  本稿では,量子安定化器符号の最小距離を準拘束的二項最適化問題として再定式化することで計算する手法を提案する。 D-Wave Advantage 4.1quantum annealerと比較することにより,本手法の実用性を示す。
  論文  参考訳（メタデータ） (2024-04-26T21:29:42Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• Single-Layer Digitized-Counterdiabatic Quantum Optimization for $p$-spin Models [8.463477025989542]
  我々は、デジタルカウンタダイバティック量子最適化(DCQO)アルゴリズムを利用して、4つの局所相互作用までの$p$-spinモデルの最適解を求める。 変分法を用いてパラメータを最適化することにより,それぞれ100ドル,93%,83%のインスタンスに対して,単位精度2-スピン,3-スピン,4-スピンの問題を解く。
  論文  参考訳（メタデータ） (2023-11-11T22:49:16Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer [13.528362112761805]
  本稿では,量子ハードウェアの制約を保存する量子最適化アルゴリズムの,これまでで最大の実行方法を示す。 我々は、最大20キュービットと2キュービットゲート深さ最大159の量子進化を制限するXY-QAOA回路を実行する。 本稿では,アルゴリズムのトレードオフと,短期量子ハードウェア上での実行に対する影響について論じる。
  論文  参考訳（メタデータ） (2022-06-13T16:21:04Z)
• Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm [0.7046417074932257]
  量子近似最適化アルゴリズム(QAOA)の性能を最先端の古典解法と比較する。 古典的解法は線形時間複雑性において高品質な近似解を生成することができる。 異なるグラフ、重み付けされたMaxCut、最大独立集合、および3-SATといった他の問題は、短期量子デバイスにおける量子優位性を達成するのに適しているかもしれない。
  論文  参考訳（メタデータ） (2022-06-07T20:59:19Z)
• 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)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。 3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
  論文  参考訳（メタデータ） (2021-08-03T17:49:09Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。 我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。 我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
  論文  参考訳（メタデータ） (2020-04-14T11:05:26Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。