Algorithms · Optimization · Ising encoding
Workflow scheduling by QUBO modeling
Schedule a workflow of tasks — an instance of the workflow scheduling problem, a known NP-hard class of scheduling problems — for an industrial use case, in a way that can be represented and solved by quantum, classical, and hybrid quantum-classical algorithms.
Attested & literatureUpdated
- Record typeLiterature reference
- Reference implementationtask_scheduling_problem
- Reported costNot stated by the sources read
- Papers1
This record, used inside a worked example
This page says they develop a novel QUBO formulation
— here is a concrete, runnable instance of it.
QAOA, p=1, MaxCut on a 4-cycle
4 qubits on a 4-cycle (edges 0-1, 1-2, 2-3, 3-0), one QAOA layer with gamma=pi/8, beta=3*pi/8.
Where it ends up
- 010127%
- 101027%
- 00118%
- 01108%
- 12 more outcomes31%
0101 and 1010 are the two optimal cuts of a 4-cycle (alternating around the ring); at these angles measuring the register returns one of them clearly more often than any other cut.
Open that example in StudioSchedule a workflow of tasks — an instance of the workflow scheduling problem, a known NP-hard class of scheduling problems — for an industrial use case, in a way that can be represented and solved by quantum, classical, and hybrid quantum-classical algorithms. Pakhomchik, Yudin, Perelshtein, Alekseyenko and Yarkoni investigate the workflow scheduling problem, which they describe as a known NP-hard class of scheduling problems, using problem instances they derive from an industrial use case. They compare several quantum, classical, and hybrid quantum-classical algorithms against those instances. To make the problem solvable by quantum and hybrid methods, they develop a novel QUBO formulation to represent the scheduling problem, and they show how the resulting QUBO's complexity depends on the input problem. To manage that complexity for their specific application, they derive and present a decomposition method, which they say mitigates the complexity, and they report that they demonstrate the effectiveness of the approach. The abstract does not say which of the compared algorithms performs best, or by how much.
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
Pakhomchik, Yudin, Perelshtein, Alekseyenko and Yarkoni investigate the workflow scheduling problem, which they describe as a known NP-hard class of scheduling problems, using problem instances they derive from an industrial use case. They compare several quantum, classical, and hybrid quantum-classical algorithms against those instances. To make the problem solvable by quantum and hybrid methods, they develop a novel QUBO formulation to represent the scheduling problem, and they show how the resulting QUBO's complexity depends on the input problem. To manage that complexity for their specific application, they derive and present a decomposition method, which they say mitigates the complexity, and they report that they demonstrate the effectiveness of the approach. The abstract does not say which of the compared algorithms performs best, or by how much. The sources read state no complexity bound for this record (The abstract of arXiv:2205.04844, the only source read for this record, states no complexity expression, no big-O bound and no resource count for the algorithm it presents. It names the general problem class as "a known NP-hard class of scheduling problems", presented as an established fact about workflow scheduling in general, not a bound this paper proves. It also states that "the QUBO complexity depends on the input problem", naming a dependency without stating what it is: no formula, no scaling law, and no measure of QUBO size (variable count, term count) is quoted. Its comparison claim is: "We derive problem instances from an industrial use case and compare against several quantum, classical, and hybrid quantum-classical algorithms" — naming that a comparison was run but stating no outcome, no winner, and no number for any of the algorithms compared. Its closing claim is that the authors "demonstrate the effectiveness of the approach", stated without a metric, a number, or a comparison figure. The demonstration this record covers states no complexity bound of its own. The field is left empty on purpose rather than filled with a bound written from memory.).
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
- Record type
- Literature reference
- Reference implementation
- task_scheduling_problem
- Reported cost
- Not stated by the sources read
- Complexity basis
- The abstract of arXiv:2205.04844, the only source read for this record, states no complexity expression, no big-O bound and no resource count for the algorithm it presents. It names the general problem class as "a known NP-hard class of scheduling problems", presented as an established fact about workflow scheduling in general, not a bound this paper proves. It also states that "the QUBO complexity depends on the input problem", naming a dependency without stating what it is: no formula, no scaling law, and no measure of QUBO size (variable count, term count) is quoted. Its comparison claim is: "We derive problem instances from an industrial use case and compare against several quantum, classical, and hybrid quantum-classical algorithms" — naming that a comparison was run but stating no outcome, no winner, and no number for any of the algorithms compared. Its closing claim is that the authors "demonstrate the effectiveness of the approach", stated without a metric, a number, or a comparison figure. The demonstration this record covers states no complexity bound of its own. The field is left empty on purpose rather than filled with a bound written from memory.
- Circuit
- Not supplied
This record is not a concrete circuit.
Quantum vs classical
Classical baseline
Compare Optimization · Ising encoding with the strongest classical method for the same instance, input budget, and output metric.
Quantum claim
This reference exposes a quantum circuit pattern; it does not imply an application-level speedup without a matched benchmark.
How to compare
Report input loading, circuit depth, repetitions, classical preprocessing, post-processing, and wall-clock time together.
Nobody has reviewed this record for gaps yet.
ALGORITHM: Workflow scheduling by QUBO modeling
PROBLEM: Schedule a workflow of tasks — an instance of the workflow scheduling problem, a known NP-hard class of scheduling problems — for an industrial use case, in a way that can be represented and solved by quantum, classical, and hybrid quantum-classical algorithms.
IDEA: Pakhomchik, Yudin, Perelshtein, Alekseyenko and Yarkoni investigate the workflow scheduling problem, which they describe as a known NP-hard class of scheduling problems, using problem instances they derive from an industrial use case. They compare several quantum, classical, and hybrid quantum-classical algorithms against those instances. To make the problem solvable by quantum and hybrid methods, they develop a novel QUBO formulation to represent the scheduling problem, and they show how the resulting QUBO's complexity depends on the input problem. To manage that complexity for their specific application, they derive and present a decomposition method, which they say mitigates the complexity, and they report that they demonstrate the effectiveness of the approach. The abstract does not say which of the compared algorithms performs best, or by how much.
REPORTED COST: Not stated by the sources read
BASIS: The abstract of arXiv:2205.04844, the only source read for this record, states no complexity expression, no big-O bound and no resource count for the algorithm it presents. It names the general problem class as "a known NP-hard class of scheduling problems", presented as an established fact about workflow scheduling in general, not a bound this paper proves. It also states that "the QUBO complexity depends on the input problem", naming a dependency without stating what it is: no formula, no scaling law, and no measure of QUBO size (variable count, term count) is quoted. Its comparison claim is: "We derive problem instances from an industrial use case and compare against several quantum, classical, and hybrid quantum-classical algorithms" — naming that a comparison was run but stating no outcome, no winner, and no number for any of the algorithms compared. Its closing claim is that the authors "demonstrate the effectiveness of the approach", stated without a metric, a number, or a comparison figure. The demonstration this record covers states no complexity bound of its own. The field is left empty on purpose rather than filled with a bound written from memory.
PRIMARY SOURCE: A. I. Pakhomchik, S. Yudin, M. R. Perelshtein, A. Alekseyenko, S. Yarkoni (2022), Solving workflow scheduling problems with QUBO modeling — https://arxiv.org/abs/2205.04844
This is a literature reference record, not an executable circuit.A reference record, not runnable source. Leona cannot execute it, so it cannot be saved to your Library as a circuit.
Related entries
- QUBO operator mapping
Operators
- Ising formulations of NP-complete and NP-hard problems
Algorithms
- Ising cost Hamiltonian
Operators
- Quantum simulated annealing
Algorithms
References
- Solving workflow scheduling problems with QUBO modeling
A. I. Pakhomchik, S. Yudin, M. R. Perelshtein, A. Alekseyenko, S. Yarkoni · 2022
Primary source: it investigates the workflow scheduling problem as a known NP-hard class, derives problem instances from an industrial use case, compares several quantum, classical, and hybrid quantum-classical algorithms against them, develops a novel QUBO representation whose complexity it shows depends on the input problem, and presents a decomposition method to mitigate that complexity. Consult it for the QUBO formulation itself, the decomposition method, the industrial instances, and the comparison's outcome, none of which the abstract states.