論文の概要: A Nested Amplitude Amplification Protocol for the Binary Knapsack Problem

• arxiv url: http://arxiv.org/abs/2604.05776v1
• Date: Tue, 07 Apr 2026 12:14:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-08 17:42:09.809832
• Title: A Nested Amplitude Amplification Protocol for the Binary Knapsack Problem
• Title（参考訳）: 二つのKnapsack問題に対するNested Amplitude Amplification Protocol
• Authors: Laurin Demmler, Maximilian Hess,
• Abstract要約: Amplitude Amplification は、Grover Adaptive Search (GAS) によって最適化された、探索問題の証明可能な高速化を提供する。 本研究では,二分数knapsack問題に対するネスト振幅増幅プロトコルを提案し,決定木を深さで分割し,第1変数の部分増幅を行い,全探索空間上でグローバルGASを実行する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Amplitude Amplification offers a provable speedup for search problems, which is leveraged in combinatorial optimization by Grover Adaptive Search (GAS). The protocol demands deep circuits that are challenging with regards to NISQ capabilities. We propose a nested Amplitude Amplification protocol for the binary knapsack problem that splits the decision tree at a tunable depth, performing a partial amplification on the first variables before executing a global GAS on the full search space. The partial amplification is implemented by an Inner Iteration Finder that selects the rotation count maximizing marked-subspace amplitude. The resulting biased superposition serves as the initial state for the outer Amplitude Amplification. Using the Quantum Tree Generator for feasible-state preparation and an efficient classical amplitude-tracking scheme, we simulate the protocol on knapsack instances of sizes intractable by statevector simulation. Our results show that the nested approach reduces the cost of improving an incumbent solution compared to baseline GAS, particularly for a specific subset of knapsack instances. As combinatorial problems in domains such as semiconductor supply-chain planning grow in scale, methods that reduce circuit cost are an important step toward eventual quantum advantage for such applications.
• Abstract（参考訳）: Amplitude Amplificationは、Grover Adaptive Search (GAS)による組合せ最適化で活用される、探索問題の証明可能なスピードアップを提供する。 このプロトコルは、NISQ機能に関して挑戦するディープ回路を必要とする。 本研究では,二分数knapsack問題に対するネスト振幅増幅プロトコルを提案する。これは決定木を調整可能な深さで分割し,全探索空間上でグローバルGASを実行する前に第1変数を部分増幅する。 部分増幅は、マークサブスペース振幅を最大化する回転数を選択するインナーイテレーションファインダによって実装される。 結果として生じる偏重積は、外振幅増幅の初期状態として機能する。 本研究では, 量子木生成器を用いて, 状態ベクトルシミュレーションにより抽出可能なサイズのknapsackインスタンス上で, プロトコルをシミュレートする。 以上の結果から,ネストしたアプローチは,特にknapsackインスタンスの特定のサブセットにおいて,ベースラインGASと比較して既存のソリューションを改善するコストを低減させることが示された。 半導体サプライチェーン計画のような領域の組合せ問題は規模が大きくなるにつれて、回路コストを下げる手法は、そのようなアプリケーションにとって最終的な量子優位性に向けた重要なステップとなる。

関連論文リスト

• Downlink MIMO Channel Estimation from Bits: Recoverability and Algorithm [30.586086257221382]
  主な課題は、ユーザ機器(UE)からの限られたフィードバックから基地局(BS)のダウンリンクチャネル状態情報(CSI)を取得することである。 本稿では、UE側で圧縮とガウスディザリングに基づく量子化戦略を採用し、BS側で最大極大推定器(MLE)を定式化する単純なフィードバックフレームワークを提案する。 このアルゴリズムは、高次高調波探索(HR)ソルバをサブルーチンとして統合するために慎重に設計されており、この難しいMLE問題に効果的に取り組む鍵であることが判明した。
  論文  参考訳（メタデータ） (2024-11-25T02:15:01Z)
• Quantum tree generator improves QAOA state-of-the-art for the knapsack problem [0.0]
  本稿では,knapsack問題に適した量子近似最適化アルゴリズム(QAOA)を提案する。 我々は、最近提案された量子ツリー生成器を、クナップサック問題に対する全ての実現可能なソリューションのための効率的な状態準備回路として、Grover-mixer QAOAのフレームワークと組み合わせる。 最大20個のknapsack項目を持つハードベンチマークセットでは、現在のCopula-QAOAよりも改善された性能を示す。
  論文  参考訳（メタデータ） (2024-11-01T11:37:07Z)
• Grover Adaptive Search with Spin Variables [2.518901558555741]
  このスピンベースアルゴリズムのために設計された新しい量子辞書サブルーチンを導入する。 このアプローチの重要な利点は、量子回路を構成するのに必要なCNOTゲートの数を大幅に削減することである。
  論文  参考訳（メタデータ） (2024-10-15T14:24:27Z)
• Amplitude amplification-inspired QAOA: Improving the success probability for solving 3SAT [55.78588835407174]
  振幅増幅アルゴリズムは、可変代入を満たすために非構造化探索に適用することができる。 Quantum Approximate Optimization Algorithm (QAOA)は、ノイズのある中間量子デバイスのための3SATを解くための有望な候補である。 振幅増幅によるQAOAの変種を導入し、3SATの成功確率を改善する。
  論文  参考訳（メタデータ） (2023-03-02T11:52:39Z)
• Variational Amplitude Amplification for Solving QUBO Problems [0.0]
  本研究は、キュービット重畳状態に適したQUBO問題に焦点をあてる。 我々は、QUBOをコストオラクルの演算として符号化する回路設計を、標準Grover拡散演算子$U_textrms$と組み合わせると、最適および近似最適解に対応する状態の測定確率が高くなることを示す。
  論文  参考訳（メタデータ） (2023-01-31T14:33:40Z)
• Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors [59.33977545294148]
  O(k log L)$サンプルは振幅に基づく経験損失関数を最小化する任意のベクトルに信号が近いことを保証するのに十分であることを示す。 この結果はスパース位相検索に適応し、基底信号が$s$-sparseおよび$n$-dimensionalである場合、$O(s log n)$サンプルは同様の保証に十分であることを示す。
  論文  参考訳（メタデータ） (2021-06-29T12:49:54Z)
• Composably secure data processing for Gaussian-modulated continuous variable quantum key distribution [58.720142291102135]
  連続可変量子鍵分布(QKD)は、ボソニックモードの二次構造を用いて、2つのリモートパーティ間の秘密鍵を確立する。 構成可能な有限サイズセキュリティの一般的な設定におけるホモダイン検出プロトコルについて検討する。 特に、ハイレート(非バイナリ)の低密度パリティチェックコードを使用する必要のあるハイシグネチャ・ツー・ノイズ・システマを解析する。
  論文  参考訳（メタデータ） (2021-03-30T18:02:55Z)
• Plug-And-Play Learned Gaussian-mixture Approximate Message Passing [71.74028918819046]
  そこで本研究では,従来のi.i.d.ソースに適した圧縮圧縮センシング(CS)リカバリアルゴリズムを提案する。 我々のアルゴリズムは、Borgerdingの学習AMP(LAMP)に基づいて構築されるが、アルゴリズムに普遍的な復調関数を採用することにより、それを大幅に改善する。 数値評価により,L-GM-AMPアルゴリズムは事前の知識を必要とせず,最先端の性能を実現する。
  論文  参考訳（メタデータ） (2020-11-18T16:40:45Z)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。 我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
  論文  参考訳（メタデータ） (2020-04-23T05:00:21Z)

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

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