論文の概要: Efficient MILP Decomposition in Quantum Computing for ReLU Network Robustness

• arxiv url: http://arxiv.org/abs/2305.00472v2
• Date: Wed, 11 Oct 2023 07:47:07 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-13 13:13:59.928574
• Title: Efficient MILP Decomposition in Quantum Computing for ReLU Network Robustness
• Title（参考訳）: ReLUネットワークロバストネスのための量子コンピューティングにおけるMILPの効率的な分解
• Authors: Nicola Franco, Tom Wollschl\"ager, Benedikt Poggel, Stephan G\"unnemann, Jeanette Miriam Lorenz
• Abstract要約: 本研究では,MILP(Mixed-Integer Linear Programming)の2つの分解法について検討した。 我々は、元の問題をより小さなサブプロブレムに分割することに集中し、量子古典的ハードウェアのアプローチを組み合わせて反復的に解決する。 実験の結果,従来の量子アニール法やゲートベース量子コンピュータと比較して最大90%の量子ビットを削減できることがわかった。
• 参考スコア（独自算出の注目度）: 2.854196251981274
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Emerging quantum computing technologies, such as Noisy Intermediate-Scale Quantum (NISQ) devices, offer potential advancements in solving mathematical optimization problems. However, limitations in qubit availability, noise, and errors pose challenges for practical implementation. In this study, we examine two decomposition methods for Mixed-Integer Linear Programming (MILP) designed to reduce the original problem size and utilize available NISQ devices more efficiently. We concentrate on breaking down the original problem into smaller subproblems, which are then solved iteratively using a combined quantum-classical hardware approach. We conduct a detailed analysis for the decomposition of MILP with Benders and Dantzig-Wolfe methods. In our analysis, we show that the number of qubits required to solve Benders is exponentially large in the worst-case, while remains constant for Dantzig-Wolfe. Additionally, we leverage Dantzig-Wolfe decomposition on the use-case of certifying the robustness of ReLU networks. Our experimental results demonstrate that this approach can save up to 90\% of qubits compared to existing methods on quantum annealing and gate-based quantum computers.
• Abstract（参考訳）: Noisy Intermediate-Scale Quantum (NISQ) デバイスのような新しい量子コンピューティング技術は、数学的最適化問題の解決において潜在的な進歩をもたらす。 しかし、qubitの可用性、ノイズ、エラーの制限は、実用的な実装に困難をもたらす。 本研究では,本研究の課題を縮小するために設計された混合整数線形計画法(milp)の2つの分解法について検討し,利用可能なnisqデバイスをより効率的に利用する。 我々は、元の問題をより小さな部分問題に分割することに集中し、量子古典的ハードウェアアプローチを組み合わせることで反復的に解決する。 我々はBenders法とDantzig-Wolfe法でMILPの分解を詳細に解析する。 解析では、ベンダーズを解くのに必要な量子ビットの数は、最悪の場合指数関数的に大きいが、ダンツィヒ=ウォルフは一定である。 さらに,reluネットワークのロバスト性を検証するために,dantzig-wolfe分解を利用する。 実験の結果,従来の量子アニール法やゲートベース量子コンピュータと比較して最大90%の量子ビットを削減できることがわかった。

関連論文リスト

• Scaling Up the Quantum Divide and Conquer Algorithm for Combinatorial Optimization [0.8121127831316319]
  本稿では,デバイス間通信コストを大幅に削減する量子回路の構築手法を提案する。 そこで本研究では,従来のQDCA手法の約3倍の大きさのトラクタブル回路を構築できることを示す。
  論文  参考訳（メタデータ） (2024-05-01T20:49:50Z)
• Variational quantum eigensolver with linear depth problem-inspired ansatz for solving portfolio optimization in finance [7.501820750179541]
  本稿では,金融におけるポートフォリオ最適化問題を解決するために,変分量子固有解法(VQE)を提案する。 超伝導量子コンピュータWu Kongにおける最大55量子ビットのHDC実験を実装した。 HDCスキームは、NISQ時代に量子アドバンテージを達成する大きな可能性を示している。
  論文  参考訳（メタデータ） (2024-03-07T07:45:47Z)
• Quantum Semidefinite Programming with Thermal Pure Quantum States [0.5639904484784125]
  行列乗法重み付けアルゴリズムの量子化'''は、古典的アルゴリズムよりも2次的に高速なSDPの近似解が得られることを示す。 この量子アルゴリズムを改良し、ギブス状態サンプリング器を熱純量子(TPQ)状態に置き換えることで、同様のスピードアップが得られることを示す。
  論文  参考訳（メタデータ） (2023-10-11T18:00:53Z)
• Towards Neural Variational Monte Carlo That Scales Linearly with System Size [67.09349921751341]
  量子多体問題(Quantum many-body problem)は、例えば高温超伝導体のようなエキゾチックな量子現象をデミストする中心である。 量子状態を表すニューラルネットワーク(NN)と変分モンテカルロ(VMC)アルゴリズムの組み合わせは、そのような問題を解決する上で有望な方法であることが示されている。 ベクトル量子化技術を用いて,VMCアルゴリズムの局所エネルギー計算における冗長性を利用するNNアーキテクチャVector-Quantized Neural Quantum States (VQ-NQS)を提案する。
  論文  参考訳（メタデータ） (2022-12-21T19:00:04Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Quantum-inspired optimization for wavelength assignment [51.55491037321065]
  波長割当問題を解くための量子インスピレーションアルゴリズムを提案し,開発する。 本研究は,電気通信における現実的な問題に対する量子インスパイアされたアルゴリズムの活用の道筋をたどるものである。
  論文  参考訳（メタデータ） (2022-11-01T07:52:47Z)
• Squeezing and quantum approximate optimization [0.6562256987706128]
  変分量子アルゴリズムは、デジタル量子コンピュータを用いた最適化問題の解法として興味深い可能性を提供する。 しかし、そのようなアルゴリズムにおける達成可能な性能と量子相関の役割は未だ不明である。 我々は、IBM量子チップと同様に、システマティックな手順で高度に圧縮された状態が生成されるかを数値的に示す。
  論文  参考訳（メタデータ） (2022-05-20T18:00:06Z)
• Quantum Robustness Verification: A Hybrid Quantum-Classical Neural Network Certification Algorithm [1.439946676159516]
  本研究では、堅牢性多変数混合整数プログラム(MIP)の解法を含むReLUネットワークの検証について検討する。 この問題を軽減するために、ニューラルネットワーク検証にQCを用い、証明可能な証明書を計算するためのハイブリッド量子プロシージャを導入することを提案する。 シミュレーション環境では,我々の証明は健全であり,問題の近似に必要な最小量子ビット数に制限を与える。
  論文  参考訳（メタデータ） (2022-05-02T13:23:56Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。 これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。 本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
  論文  参考訳（メタデータ） (2022-02-17T18:59:20Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  マルチバスグラフ複雑性と非線形活性化関数の2つの革新の恩恵を受ける新しい変分量子アルゴリズムを導入する。 その結果,最適化性能が向上し,有効景観が2つ向上し,測定の進歩が減少した。
  論文  参考訳（メタデータ） (2021-06-24T20:16:02Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)

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

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