# 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

Quantum Computing Scientist