Presentation
Solving the Binary Paintshop Problem with the Quantum Approximate Optimisation Algorithm
Speaker
Event Type
Focus Session
Graph Algorithms
Post Moore’s Law Computing
Quantum Computing
TimeWednesday, June 19th11:45am - 12:10pm
LocationPanorama 1
DescriptionWe investigate the application of a novel heuristic algorithm for combinatorial optimization with noisy intermediate scale quantum (NISQ) processors, the Quantum Approximate Optimization Algorithm,(QAOA) to solve an industry relevant problem, the binary paint shop problem.
In the binary painthop problem we strive to minimize the number of color changes that are necessary to color a given sequence of cars, because color changes in the paintshop require expensive cleaning procedures. Every car has to be painted twice with two different colors, however there is no predefined sequence the colors have to be applied. This problem is known to be NP-hard, i.e. it is intractable to find the optimal solution, and additionally APX-hard, i.e. it is even difficult to find a good approximation to the problem.
We present classically simulated results of the application of QAOA on the binary paintshop problem. QAOA is a hybrid quantum algorithm for NISQ devices that in its original version consists of a parametrized circuit that is optimized with an outer learning loop. We show how to come up with good parameters for the circuits with little to no prior execution of the parametrized circuit on the quantum processor.
In the binary painthop problem we strive to minimize the number of color changes that are necessary to color a given sequence of cars, because color changes in the paintshop require expensive cleaning procedures. Every car has to be painted twice with two different colors, however there is no predefined sequence the colors have to be applied. This problem is known to be NP-hard, i.e. it is intractable to find the optimal solution, and additionally APX-hard, i.e. it is even difficult to find a good approximation to the problem.
We present classically simulated results of the application of QAOA on the binary paintshop problem. QAOA is a hybrid quantum algorithm for NISQ devices that in its original version consists of a parametrized circuit that is optimized with an outer learning loop. We show how to come up with good parameters for the circuits with little to no prior execution of the parametrized circuit on the quantum processor.
Speaker
