| Quantum approximate optimization algorithm is a heuristic algorithm proposed by Farhi et al.As an approximation algorithm,it does not give the best result,but a"good enough" result.The quantum approximate optimization algorithm is an algorithm framework that uses classical resources to find approximate solutions to combinatorial optimization problems,which is derived from the quantum adiabatic algorithm.When solving combinatorial optimization problems with constraints,it is necessary to find a way to encode the problem constraints into the scheme and solve each problem instance with the desired quality.In recent quantum computers,quantum approximate optimization algorithm is regarded as one of the promising algorithms to show quantum advantages.This paper presents a feasible method for solving constrained optimization problems in the framework of quantum approximate optimization algorithm.Namely,quantum approximate optimization algorithm assisted by classical greedy algorithm.QAOA-AC method combines two classes of methods for dealing with constraints in the quantum approximate optimization algorithm:quadratic unconstrained binary optimization method and quantum alternating operator ansatz method,By taking the approximate optimal solution obtained by the classical greedy algorithm as a new constraint condition and redesigning the coding evolution operator,this method further reduces the feasible solution space of algorithm evolution,and is suitable for optimization problems with linear inequality constraints.A penalty term is added to the target operator so that the expected value of the solution that does not satisfy the constraint condition is worse than that of the solution that does.In this paper,we propose and discuss several quantum approximate optimization algorithm frameworks to solve combinatorial optimization problems with equality or inequality constraints.We formalize the coding methods for different types of constraints,and prove the effectiveness and efficiency of the proposed scheme by examples and the results of some famous NP optimization problems.The QAOA-AC method is compared with the existing methods,and it is believed that the method proposed in this paper can solve the constrained optimization problem more efficiently. |
