論文の概要: 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})$である。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
ランク1テンソルを$otimes_i=1N mathbbRd$で完了する際のサンプルと計算複雑性を再考する。
本稿では,一対のランダム線形系上で,ガウス・ヨルダンに相当するアルゴリズムを許容する問題のキャラクタリゼーションを提案する。
論文 参考訳（メタデータ） (2024-08-10T04:26:19Z) - Accelerated Variance-Reduced Forward-Reflected Methods for Root-Finding Problems [8.0153031008486]
そこで本研究では,Nesterovの高速前方反射法と分散還元法を新たに提案し,根絶問題の解法を提案する。
我々のアルゴリズムは単ループであり、ルートフィリング問題に特化して設計された非バイアス分散還元推定器の新たなファミリーを利用する。
論文 参考訳（メタデータ） (2024-06-04T15:23:29Z) - Partially Unitary Learning [0.0]
ヒルベルト空間の最適写像 $IN$ of $left|psirightrangle$ と $OUT$ of $left|phirightrangle$ が提示される。
この最適化問題の大域的な最大値を求める反復アルゴリズムを開発した。
論文 参考訳（メタデータ） (2024-05-16T17:13:55Z) - 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) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。