Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm

Abstract

The binary paint shop problem (BPSP) is an APX-hard optimization problem of the automotive industry. In this work, we show how to use the Quantum Approximate Optimization Algorithm (QAOA) to find solutions of the BPSP and demonstrate that QAOA with constant depth is able to beat classical heuristics on average in the infinite size limit $n\to \infty$. For the BPSP, it is known that no classical algorithm can exist which approximates the problem in polynomial runtime. We introduce a BPSP instance which is hard to solve with QAOA, and numerically investigate its performance and discuss QAOA's ability to generate approximate solutions. We complete our studies by running first experiments of small-sized instances on a trapped-ion quantum computer through AWS Braket.

References in corpus (31)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• A variational eigenvalue solver on a quantum processor
• Ising formulations of many NP problems
• A Quantum Approximate Optimization Algorithm
• Quantum Circuit Learning
• Demonstration of Two-Qubit Algorithms with a Superconducting Quantum Processor
• Demonstration of a small programmable quantum computer with atomic qubits
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Benchmarking an 11-qubit quantum computer
• Simulating quantum computation by contracting tensor networks
• Digitized adiabatic quantum computing with a superconducting circuit
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Continuous-variable quantum neural networks
• Demonstration of Universal Parametric Entangling Gates on a Multi-Qubit Lattice
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
• Unsupervised Machine Learning on a Hybrid Quantum Computer
• Quantum Supremacy through the Quantum Approximate Optimization Algorithm
• Near-optimal quantum circuit for Grover's unstructured search using a transverse field
• Efficient variational simulation of non-trivial quantum states
• A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
• Benchmarking the Quantum Approximate Optimization Algorithm
• Basic circuit compilation techniques for an ion-trap quantum machine
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
• Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem
• Classical algorithms for quantum mean values
• For Fixed Control Parameters the Quantum Approximate Optimization Algorithm's Objective Function Value Concentrates for Typical Instances
• Classical and Quantum Bounded Depth Approximation Algorithms
• Quantum Annealing: a journey through Digitalization, Control, and hybrid Quantum Variational schemes
• Comparison of QAOA with Quantum and Simulated Annealing
• Forbidden subspaces for level-1 QAOA and IQP circuits

Cited by in corpus (15)

• Noisy intermediate-scale quantum (NISQ) algorithms
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Quantum Computing: Towards Industry Reference Problems
• Hybrid quantum ResNet for car classification and its hyperparameter optimization
• Large-scale quantum approximate optimization on non-planar graphs with machine learning noise mitigation
• Quantum algorithms with local particle number conservation: noise effects and error correction
• Quantum Computing Techniques for Multi-Knapsack Problems
• Recursive greedy initialization of the quantum approximate optimization algorithm with guaranteed improvement
• Fermionic Quantum Approximate Optimization Algorithm
• An Optimization Case Study for solving a Transport Robot Scheduling Problem on Quantum-Hybrid and Quantum-Inspired Hardware
• Experimental Demonstration of Fermionic QAOA with One-Dimensional Cyclic Driver Hamiltonian
• Multi-disk clutch optimization using quantum annealing
• Quantum Approximation Optimization Algorithm for the Trellis based Viterbi Decoding of Classical Error Correcting Codes
• Classical optimization with imaginary time block encoding on quantum computers: The MaxCut problem
• Optimisation-Free Recursive QAOA for the Binary Paint Shop Problem