论文标题
用量子近似优化算法击败二进制油漆店问题的经典启发式方法
Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm
论文作者
论文摘要
二进制涂料店问题（BPSP）是汽车行业的APX优化问题。在这项工作中，我们展示了如何使用量子近似优化算法（QAOA）找到BPSP的解决方案，并证明具有恒定深度的QAOA能够平均在无限尺寸限制$ n \ rightarrow \ rightarrow \ infty $中平均击败经典的启发式方法。对于BPSP，众所周知，没有经典算法可以存在近似于多项式运行时的问题。我们引入了一个BPSP实例，该实例很难用QAOA解决，并在数值上研究了其性能并讨论了QAOA生成近似解决方案的能力。我们通过通过AWS架上在被困的离子量子计算机上运行小型实例的第一个实验来完成研究。
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\rightarrow\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.
