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

• arxiv url: http://arxiv.org/abs/2307.10379v3
• Date: Thu, 8 Feb 2024 10:17:30 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-09 19:23:00.041044
• Title: Alleviating the quantum Big-$M$ problem
• Title（参考訳）: 量子Big-M$問題を軽減する
• Authors: Edoardo Alessandroni, Sergi Ramos-Calderer, Ingo Roth, Emiliano Traversi, Leandro Aolita
• Abstract要約: 古典的には "Big-$M$" 問題として知られており、物理的エネルギースケールに影響を与える。 我々は、量子ビッグ-M$問題を体系的に包含し、最適の$M$を見つけるのにNPハードネスを明らかにする。 本稿では,SDP緩和に基づく実用的な翻訳アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 0.237499051649312
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A major obstacle for quantum optimizers is the reformulation of constraints as a quadratic unconstrained binary optimization (QUBO). Current QUBO translators exaggerate the weight $M$ of the penalty terms. Classically known as the "Big-$M$" problem, the issue becomes even more daunting for quantum solvers, since it affects the physical energy scale. We take a systematic, encompassing look at the quantum big-$M$ problem, revealing NP-hardness in finding the optimal $M$ and establishing bounds on the Hamiltonian spectral gap $\Delta$, inversely related to the expected run-time of quantum solvers. We propose a practical translation algorithm, based on SDP relaxation, that outperforms previous methods in numerical benchmarks. Our algorithm gives values of $\Delta$ orders of magnitude greater, e.g. for portfolio optimization instances. Solving such instances with an adiabatic algorithm on 6-qubits of an IonQ device, we observe significant advantages in time to solution and average solution quality. Our findings are relevant to quantum and quantum-inspired solvers alike.
• Abstract（参考訳）: 量子オプティマイザの大きな障害は、2次非制約バイナリ最適化(QUBO)としての制約の修正である。 現在のQUBO翻訳者は、罰則の重量をM$で誇張している。 古典的に "big-$m$" 問題として知られているこの問題は、物理的エネルギースケールに影響を与えるため、量子ソルバにとってさらに厄介な問題となる。 量子big-m$問題に関する体系的かつ包括的な考察を行い、最適な$m$ を見つけるためのnp-ハードネスを明らかにし、ハミルトニアンスペクトルギャップ上の境界を、量子ソルバの期待実行時間と逆関係に設定する。 本研究では,sdp緩和に基づく実用的な翻訳アルゴリズムを提案する。 このアルゴリズムは、例えばポートフォリオ最適化インスタンスに対して、$\delta$order of magnitudeの値を与える。 そこで,IonQ装置の6量子ビットにおける断熱的アルゴリズムを用いて,解法時間と平均解法品質に有意な利点を観測した。 我々の発見は、量子および量子に着想を得た解法にも関係している。

関連論文リスト

• 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)

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

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