論文の概要: Classical and Quantum Algorithms for Variants of Subset-Sum via Dynamic
Programming
- arxiv url: http://arxiv.org/abs/2111.07059v2
- Date: Fri, 22 Jul 2022 09:45:42 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-08 05:56:49.539290
- Title: Classical and Quantum Algorithms for Variants of Subset-Sum via Dynamic
Programming
- Title（参考訳）: 動的プログラミングによるサブセットサム変数の古典的および量子的アルゴリズム
- Authors: Jonathan Allcock and Yassine Hamoudi and Antoine Joux and Felix
Klingelh\"ofer and Miklos Santha
- Abstract要約: Subset-Sumは、$n$整数の多重集合がターゲット値$mに等しい部分集合を含むかどうかを判断しなければならない問題である。
本稿では,新しい動的プログラミングに基づくデータ構造を導入し,Subset-Sum や多くの変種に応用する。
- 参考スコア（独自算出の注目度）: 0.5949779668853554
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Subset-Sum is an NP-complete problem where one must decide if a multiset of
$n$ integers contains a subset whose elements sum to a target value $m$. The
best-known classical and quantum algorithms run in time $\tilde{O}(2^{n/2})$
and $\tilde{O}(2^{n/3})$, respectively, based on the well-known
meet-in-the-middle technique. Here we introduce a novel classical
dynamic-programming-based data structure with applications to Subset-Sum and a
number of variants, including Equal-Sums (where one seeks two disjoint subsets
with the same sum), 2-Subset-Sum (a relaxed version of Subset-Sum where each
item in the input set can be used twice in the summation), and Shifted-Sums, a
generalization of both of these variants, where one seeks two disjoint subsets
whose sums differ by some specified value.
Given any modulus $p$, our data structure can be constructed in time
$O(n^2p)$, after which queries can be made in time $O(n^2)$ to the lists of
subsets summing to any value modulo $p$. We use this data structure in
combination with variable-time amplitude amplification and a new quantum pair
finding algorithm, extending the quantum claw finding algorithm to the multiple
solutions case, to give an $O(2^{0.504n})$ quantum algorithm for Shifted-Sums,
an improvement on the best-known $O(2^{0.773n})$ classical running time.
Incidentally, we obtain new $\tilde{O}(2^{n/2})$ and $\tilde{O}(2^{n/3})$
classical and quantum algorithms for Subset-Sum, not based on the seminal
meet-in-the-middle method. We also study Pigeonhole Equal-Sums and Pigeonhole
Modular Equal-Sums, where the existence of a solution is guaranteed by the
pigeonhole principle. For the former problem, we give faster classical and
quantum algorithms with running time $\tilde{O}(2^{n/2})$ and
$\tilde{O}(2^{2n/5})$, respectively. For the more general modular problem, we
give a classical algorithm that also runs in time $\tilde{O}(2^{n/2})$.
- Abstract（参考訳）: Subset-SumはNP完全問題であり、$n$整数の多重集合がターゲット値$m$に等しい部分集合を含むかどうかを判断しなければならない。
最もよく知られた古典的および量子的アルゴリズムは、よく知られたミート・イン・ザ・ミドル法に基づいて、それぞれ $\tilde{O}(2^{n/2})$ と $\tilde{O}(2^{n/3})$ の時間で実行される。
ここでは、新しい古典的動的プログラミングベースのデータ構造をSubset-Sumに適用し、Equal-Sums (同じ和で2つの非結合部分集合を求める)、2-Subset-Sum (入力集合の各項目を和で2回使用できるSubset-Sumの緩和版)、Shifted-Sums(これらの変種を一般化したシフトト-Sums)など、いくつかの変種を求める。
任意の modulus $p$ が与えられたら、我々のデータ構造は、時間$O(n^2p)$ で構築でき、その後、任意の値 modulo $p$ にまとめるサブセットのリストに対して、時間$O(n^2)$ でクエリを作成できる。
このデータ構造を可変時間振幅増幅アルゴリズムと新しい量子ペア探索アルゴリズムと組み合わせて、量子クロー探索アルゴリズムを多重解の場合まで拡張し、シフトサムに対する$o(2^{0.504n})$量子アルゴリズムを与え、最もよく知られた$o(2^{0.773n})$クラシック実行時間を改善した。
ちなみに、ここでは、半素のミート・イン・ザ・ミドル法ではなく、新しい$\tilde{O}(2^{n/2})$と$\tilde{O}(2^{n/3})$の古典的および量子的アルゴリズムを得る。
また, ピジョンホール等式とピジョンホール等式式式等式についても検討し, ピジョンホールの原理により解の存在が保証されることを示した。
従来の問題に対して、動作時間 $\tilde{O}(2^{n/2})$ と $\tilde{O}(2^{2n/5})$ の高速な古典的および量子的アルゴリズムを与える。
より一般的なモジュラー問題に対しては、時間$\tilde{o}(2^{n/2})$で走る古典的なアルゴリズムを与える。
関連論文リスト
- 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) - Quantum spectral method for gradient and Hessian estimation [4.193480001271463]
勾配降下は連続最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、クエリの複雑さを$widetildeO (1/varepsilon)$とすることで、その勾配の$varepsilon$-approximationを返す量子アルゴリズムを提案する。
また、ニュートン法の量子アナログを改善することを目的としたヘッセン推定のための2つの量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-07-04T11:03:48Z) - Towards Optimal Circuit Size for Sparse Quantum State Preparation [10.386753939552872]
我々は、$s$非ゼロ振幅を持つ$n$量子ビットスパース量子状態の準備を検討し、2つのアルゴリズムを提案する。
最初のアルゴリズムは$O(ns/log n + n)$ gatesを使用し、以前のメソッドを$O(log n)$で改善する。
2番目のアルゴリズムは、短いハミルトニアンパスを示す二進弦向けに調整されている。
論文 参考訳（メタデータ） (2024-04-08T02:13:40Z) - Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security [50.16790546184646]
まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。
次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
論文 参考訳（メタデータ） (2023-11-07T04:59:02Z) - Fast and Practical Quantum-Inspired Classical Algorithms for Solving
Linear Systems [11.929584800629673]
線形系を解くための高速で実用的な量子インスパイアされた古典的アルゴリズムを提案する。
我々の主な貢献は、線形系を解くために量子に着想を得た古典的アルゴリズムへの重球運動量法の適用である。
論文 参考訳（メタデータ） (2023-07-13T08:46:19Z) - Dynamic Algorithms for Matroid Submodular Maximization [11.354502646593607]
マトロイドおよび濃度制約の下でのサブモジュラー複雑性は、機械学習、オークション理論、最適化における幅広い応用の問題である。
本稿では、これらの問題を動的に考慮し、モノトン部分モジュラ関数 $f: 2V rightarrow mathbbR+$ にアクセスでき、基底となる基底集合 $V$ の元の挿入と削除のシーケンス $calmathS$ が与えられる。
マトロイド制約下でのサブモジュラー問題に対する最初の完全動的アルゴリズムを開発する。
論文 参考訳（メタデータ） (2023-06-01T17:54:15Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文 参考訳（メタデータ） (2022-04-22T12:37:56Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z) - Improved Classical and Quantum Algorithms for Subset-Sum [1.376408511310322]
ランダムなサブセットサムを解くための古典的および量子的アルゴリズムを提案する。
本稿では,前回のベストタイムの複雑性よりも優れた量子ウォークを,サブセットサムに対して提案する。
論文 参考訳（メタデータ） (2020-02-12T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。