論文の概要: QUBO Resolution of the Job Reassignment Problem
- arxiv url: http://arxiv.org/abs/2309.16473v1
- Date: Thu, 28 Sep 2023 14:37:23 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-29 14:07:54.350549
- Title: QUBO Resolution of the Job Reassignment Problem
- Title(参考訳): 雇用再割り当て問題のQUBO解決
- Authors: I\~nigo Perez Delgado, Beatriz Garc\'ia Markaida, Alejandro Mata Ali,
Aitor Moreno Fdez. de Leceta
- Abstract要約: 雇用再割り当て問題(雇用再割り当て問題)のサブ・プロブレメーション・スキームを提案する。
このスキームのコスト関数はQUBOハミルトニアンによって記述され、ゲートベースとアニーリング量子コンピュータの両方で実装できる。
- 参考スコア(独自算出の注目度): 44.99833362998488
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We present a subproblemation scheme for heuristical solving of the JSP (Job
Reassignment Problem). The cost function of the JSP is described via a QUBO
hamiltonian to allow implementation in both gate-based and annealing quantum
computers. For a job pool of $K$ jobs, $\mathcal{O}(K^2)$ binary variables --
qubits -- are needed to solve the full problem, for a runtime of
$\mathcal{O}(2^{K^2})$. With the presented heuristics, the average variable
number of each of the $D$ subproblems to solve is $\mathcal{O}(K^2/2D)$, and
the expected total runtime $\mathcal{O}(D2^{K^2/2D})$, achieving an exponential
speedup.
- Abstract(参考訳): 本稿では、JSP(Job Reassignment Problem)のヒューリスティックな解決のためのサブプロブレメーション方式を提案する。
JSPのコスト関数はQUBOハミルトニアンによって記述され、ゲートベースとアニーリング量子コンピュータの両方で実装できる。
k$ジョブのジョブプールでは、$\mathcal{o}(k^2)$バイナリ変数 -qubits -- が、$\mathcal{o}(2^{k^2})$のランタイムの完全な問題を解決するために必要となる。
提示されたヒューリスティックスでは、解決すべき$D$サブプロブレムの平均変数数は$\mathcal{O}(K^2/2D)$、期待される総ランタイム$\mathcal{O}(D2^{K^2/2D})$である。
関連論文リスト
- Noisy Computing of the $\mathsf{OR}$ and $\mathsf{MAX}$ Functions [22.847963422230155]
ノイズの多いクエリを使って$n$変数の関数を計算することの問題を考察する。
我々は, [ (1 pm o(1)) fracnlog frac1deltaD_mathsfKL(p | 1-p) ] のクエリ数が十分であり,両関数の計算に必要であることを示す。
論文 参考訳(メタデータ) (2023-09-07T19:37:52Z) - A polynomial quantum computing algorithm for solving the dualization
problem [75.38606213726906]
2つの単調素関数 $f:0,1n to 0,1$ と $g:0,1n to 0,1$ が与えられたとき、双対化問題は$g$が$f$の双対かどうかを決定することである。
本稿では,双対化問題の決定版を時間内に解く量子コンピューティングアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-08-28T18:12:54Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳(メタデータ) (2023-06-02T18:55:27Z) - 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) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳(メタデータ) (2022-12-01T15:57:58Z) - The First Optimal Acceleration of High-Order Methods in Smooth Convex
Optimization [88.91190483500932]
本研究では,滑らかな凸最小化問題の解法として最適高次アルゴリズムを求めるための基本的オープンな問題について検討する。
この理由は、これらのアルゴリズムが複雑なバイナリプロシージャを実行する必要があるため、最適でも実用でもないからである。
我々は、最初のアルゴリズムに$mathcalOleft(epsilon-2/(p+1)right)$pthのオーダーオーラクル複雑性を与えることで、この根本的な問題を解決する。
論文 参考訳(メタデータ) (2022-05-19T16:04:40Z) - Optimal (controlled) quantum state preparation and improved unitary
synthesis by quantum circuits with any number of ancillary qubits [20.270300647783003]
制御量子状態準備(CQSP)は、与えられた$n$-qubit状態に対するすべての$iin 0,1k$に対して、$|irangle |0nrangleから |irangle |psi_irangle $への変換を提供することを目的としている。
我々は、深さ$Oleft(n+k+frac2n+kn+k+mright)$とサイズ$Oleft(2n+kright)$のCQSPを実装するための量子回路を構築する。
論文 参考訳(メタデータ) (2022-02-23T04:19:57Z) - Computational Complexity of Normalizing Constants for the Product of
Determinantal Point Processes [12.640283469603357]
正規化定数の計算における計算複雑性について検討する。
例えば、$sum_Sdet(bf A_S,S)p$は、すべての(固定された)正の偶数に対して、$p$ が UP-hard で Mod$_3$P-hard であることを示す。
論文 参考訳(メタデータ) (2021-11-28T14:08:25Z) - Projection-Free Algorithm for Stochastic Bi-level Optimization [17.759493152879013]
本研究は、目的関数が他の最適化問題に依存する二段階最適化問題を解く最初のプロジェクションフリーアルゴリズムを示す。
提案されている$textbfStochastic $textbfF$rank-$textbfW$olfe ($textbfSCFW$)は、凸目的に対して$mathcalO(epsilon-2)$のサンプル複雑性を実現するために示されている。
論文 参考訳(メタデータ) (2021-10-22T11:49:15Z) - The planted matching problem: Sharp threshold and infinite-order phase
transition [25.41713098167692]
ランダムに重み付けされた$ntimes n$ bipartite graphに隠された完全マッチング$M*$を再構築する問題について検討する。
任意の小さな定数 $epsilon>0$ に対して $sqrtd B(mathcalP,mathcalQ) ge 1+epsilon$ が成り立つ場合、任意の推定値の再構築誤差は $0$ から有界であることが示される。
論文 参考訳(メタデータ) (2021-03-17T00:59:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。