QUBO Resolution of the Job Reassignment Problem
- URL: http://arxiv.org/abs/2309.16473v2
- Date: Fri, 29 Sep 2023 07:46:27 GMT
- Title: QUBO Resolution of the Job Reassignment Problem
- Authors: I\~nigo Perez Delgado, Beatriz Garc\'ia Markaida, Alejandro Mata Ali,
Aitor Moreno Fdez. de Leceta
- Abstract summary: We present a subproblemation scheme for the (Job Reassignment Problem)
The cost function of the scheme is described via a QUBO hamiltonian to allow implementation in both gate-based and annealing quantum computers.
- Score: 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.
Related papers
- Accelerated Variance-Reduced Forward-Reflected Methods for Root-Finding Problems [8.0153031008486]
We propose a novel class of Nesterov's accelerated forward-reflected-based methods with variance reduction to solve root-finding problems.
Our algorithm is single-loop and leverages a new family of unbiased variance-reduced estimators specifically designed for root-finding problems.
arXiv Detail & Related papers (2024-06-04T15:23:29Z) - On Partially Unitary Learning [0.0]
An optimal mapping between Hilbert spaces $IN$ of $left|psirightrangle$ and $OUT$ of $left|phirightrangle$ is presented.
An algorithm finding the global maximum of this optimization problem is developed and it's application to a number of problems is demonstrated.
arXiv Detail & Related papers (2024-05-16T17:13:55Z) - Noisy Computing of the $\mathsf{OR}$ and $\mathsf{MAX}$ Functions [22.847963422230155]
We consider the problem of computing a function of $n$ variables using noisy queries.
We show that an expected number of queries of [ (1 pm o(1)) fracnlog frac1deltaD_mathsfKL(p | 1-p) ] is both sufficient and necessary to compute both functions.
arXiv Detail & Related papers (2023-09-07T19:37:52Z) - A polynomial quantum computing algorithm for solving the dualization
problem [75.38606213726906]
Given two monotone prime functions $f:0,1n to 0,1$ and $g:0,1n to 0,1$ the dualization problem consists in determining if $g$ is the dual of $f$.
We present a quantum computing algorithm that solves the decision version of the dualization problem in time.
arXiv Detail & Related papers (2023-08-28T18:12:54Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
We introduce efficient $(1+varepsilon)$-approximation algorithms for the binary matrix factorization (BMF) problem.
The goal is to approximate $mathbfA$ as a product of low-rank factors.
Our techniques generalize to other common variants of the BMF problem.
arXiv Detail & Related papers (2023-06-02T18:55:27Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems.
We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$.
We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
arXiv Detail & Related papers (2022-12-03T02:45:23Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
This work considers the sample complexity of obtaining an $varepsilon$-optimal policy in an average reward Markov Decision Process (AMDP)
We prove an upper bound of $widetilde O(H varepsilon-3 ln frac1delta)$ samples per state-action pair, where $H := sp(h*)$ is the span of bias of any optimal policy, $varepsilon$ is the accuracy and $delta$ is the failure probability.
arXiv Detail & Related papers (2022-12-01T15:57:58Z) - The First Optimal Acceleration of High-Order Methods in Smooth Convex
Optimization [88.91190483500932]
We study the fundamental open question of finding the optimal high-order algorithm for solving smooth convex minimization problems.
The reason for this is that these algorithms require performing a complex binary procedure, which makes them neither optimal nor practical.
We fix this fundamental issue by providing the first algorithm with $mathcalOleft(epsilon-2/(p+1)right) $pth order oracle complexity.
arXiv Detail & Related papers (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]
Controlled quantum state preparation (CQSP) aims to provide the transformation of $|irangle |0nrangle to |irangle |psi_irangle $ for all $iin 0,1k$ for the given $n$-qubit states.
We construct a quantum circuit for implementing CQSP, with depth $Oleft(n+k+frac2n+kn+k+mright)$ and size $Oleft(2n+kright)$
arXiv Detail & Related papers (2022-02-23T04:19:57Z) - Computational Complexity of Normalizing Constants for the Product of
Determinantal Point Processes [12.640283469603357]
We study the computational complexity of computing the normalizing constant.
We show that $sum_Sdet(bf A_S,S)p$ exactly for every (fixed) positive even integer $p$ is UP-hard and Mod$_3$P-hard.
arXiv Detail & Related papers (2021-11-28T14:08:25Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.