論文の概要: Quantum Algorithms for Graph Coloring and other Partitioning, Covering,
and Packing Problems
- arxiv url: http://arxiv.org/abs/2311.08042v1
- Date: Tue, 14 Nov 2023 10:07:14 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-15 14:37:31.447512
- Title: Quantum Algorithms for Graph Coloring and other Partitioning, Covering,
and Packing Problems
- Title（参考訳）: グラフカラー化とその他の分割, 被覆, 包装問題に対する量子アルゴリズム
- Authors: Serge Gaspers, Jerry Zirui Li
- Abstract要約: 我々は、U を F から k 集合に分割し、U を F から k 集合で被覆し、K を F から U へ非交差集合にパックする問題を考察する。
我々の有界エラー量子アルゴリズムは、O*((2+c)(n/2))でSet Partition, Set Cover, Set Packingに対して動作する。
- 参考スコア（独自算出の注目度）: 4.930083514545936
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Let U be a universe on n elements, let k be a positive integer, and let F be
a family of (implicitly defined) subsets of U. We consider the problems of
partitioning U into k sets from F, covering U with k sets from F, and packing k
non-intersecting sets from F into U. Classically, these problems can be solved
via inclusion-exclusion in O*(2^n) time [BjorklundHK09]. Quantumly, there are
faster algorithms for graph coloring with running time O(1.9140^n) [ShimizuM22]
and for Set Cover with a small number of sets with running time O(1.7274^n
|F|^O(1)) [AmbainisBIKPV19]. In this paper, we give a quantum speedup for Set
Partition, Set Cover, and Set Packing whenever there is a classical enumeration
algorithm that lends itself to a quadratic quantum speedup, which, for any
subinstance on a subset X of U, enumerates at least one member of a
k-partition, k-cover, or k-packing (if one exists) restricted to (or projected
onto, in the case of k-cover) the set X in O*(c^{|X|}) time with c<2.
Our bounded-error quantum algorithm runs in O*((2+c)^(n/2)) for Set
Partition, Set Cover, and Set Packing. When c<=1.147899, our algorithm is
slightly faster than O*((2+c)^(n/2)); when c approaches 1, it matches the
running time of [AmbainisBIKPV19] for Set Cover when |F| is subexponential in
n.
For Graph Coloring, we further improve the running time to O(1.7956^n) by
leveraging faster algorithms for coloring with a small number of colors to
better balance our divide-and-conquer steps. For Domatic Number, we obtain a
O((2-\epsilon)^n) running time for some \epsilon>0.
- Abstract（参考訳）: U を n 個の元上の宇宙とし、k を正の整数とし、F を U の(単純に定義された)部分集合の族とする。 U を F から k 個の集合に分割し、U を F から k 個の集合で包含し、F から k 個の集合を U へ包含する問題を考える。
量子的には、実行時間 O(1.9140^n)[清水M22] と、実行時間 O(1.7274^n |F|^O(1)) [アンバイニスBIKPV19] の少数の集合を持つ集合被覆に対する高速なグラフカラー化アルゴリズムが存在する。
本稿では、u の部分集合 x 上の任意の部分集合に対して、c<2 で o*(c^{|x|}) の時間 o*(c^{|x|}) における集合 x に制限された k-partition、k-cover、k-packing の少なくとも 1 つのメンバを列挙する古典的列挙アルゴリズムが存在する場合、集合分割、集合被覆、集合充填の量子スピードアップを与える。
我々の有界エラー量子アルゴリズムは、O*((2+c)^(n/2))でSet Partition, Set Cover, Set Packingに対して動作する。
c<=1.147899 の場合、我々のアルゴリズムは O*((2+c)^(n/2)) よりもわずかに高速である。
グラフカラー化では,より高速な色付けアルゴリズムを活用してO(1.7956^n)へのランニング時間を向上し,配当とコンカッドのバランスを改善する。
ドマティック数の場合、ある \epsilon>0 に対して O((2-\epsilon)^n) ランニング時間を得る。
関連論文リスト
- Anytime Acceleration of Gradient Descent [92.02082223856479]
我々は,任意の停止時間に対して,勾配降下が$O(T-1.03)$の収束保証を達成するための段階的スケジュールを提案する。
我々はこの理論を拡張して、滑らかで強い凸最適化のために$exp(-Omega(T/kappa0.97)$の収束を保証する。
論文 参考訳（メタデータ） (2024-11-26T18:29:44Z) - On the (Classical and Quantum) Fine-Grained Complexity of Log-Approximate CVP and Max-Cut [2.2776283699063664]
最大カット問題(Max-Cut)の1-varepsilon$と1-varepsilon1/2$から、任意の有限$ell_p$-normの下での$gamma$-Approximate Closest Vector Problemへの線形サイズの縮小を示す。
有限 $ell_p$-norm における $o(sqrtlog nfrac1p)$- Approximate Closest Vector Problem に対する部分指数時間(古典的あるいは量子的)アルゴリズムは、状態よりも高速であることを示す。
論文 参考訳（メタデータ） (2024-11-06T18:58:17Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - From Bit-Parallelism to Quantum String Matching for Labelled Graphs [0.0]
二次時間で解ける多くの問題は、ビットパラレルのスピードアップが$w$で、$w$はコンピュータワードサイズである。
このような制限されたグラフの族上の単純なビット並列アルゴリズムは、現実的な量子アルゴリズムに変換可能であることを示す。
論文 参考訳（メタデータ） (2023-02-06T15:14:34Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - Solving the semidefinite relaxation of QUBOs in matrix multiplication
time, and faster with a quantum computer [0.20999222360659603]
いくつかの量子SDOソルバは、低精度な状態において高速化を提供する。
この事実を利用してアルゴリズムの精度への依存を指数関数的に改善する。
我々のアルゴリズムの量子実装は、$mathcalO left(ns + n1.5 cdot textpolylog left(n, | C |_F, frac1epsilon right)$の最悪の実行時間を示す。
論文 参考訳（メタデータ） (2023-01-10T23:12:05Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - 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 Speedups of Optimizing Approximately Convex Functions with
Applications to Logarithmic Regret Stochastic Convex Bandits [8.682187438614296]
量子アルゴリズムは、$F(x*)-min_xincal K F(x)leqepsilon$が$tildeO(n3)$が$F$となるような$x*incal K$を求める。
応用として、ゼロ階凸包帯に対して $tildeO(n5log2 T)$ regret の量子関数アルゴリズムを与える。
論文 参考訳（メタデータ） (2022-09-26T03:19:40Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z) - Improved Classical and Quantum Algorithms for Subset-Sum [1.376408511310322]
ランダムなサブセットサムを解くための古典的および量子的アルゴリズムを提案する。
本稿では,前回のベストタイムの複雑性よりも優れた量子ウォークを,サブセットサムに対して提案する。
論文 参考訳（メタデータ） (2020-02-12T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。