The Quantum Approximate Algorithm for Solving Traveling Salesman Problem

The Quantum Approximate Optimization Algorithm(QAOA)is an algorithmic framework for finding approximate solutions to combinatorial optimization problems.It consists of interleaved unitary transformations induced by two operators labelled the mixing and problem Hamiltonians.To fit this framework,one needs to transform the original problem into a suitable form and embed it into these two Hamiltonians.In this paper,for the well-known NP-hard Traveling Salesman Problem(TSP),we encode its constraints into the mixing Hamiltonian rather than the conventional approach of adding penalty terms to the problem Hamiltonian.Moreover,we map edges(routes)connecting each pair of cities to qubits,which decreases the search space significantly in comparison to other approaches.As a result,our method can achieve a higher probability for the shortest round-trip route with only half the number of qubits consumed compared to IBM Q’s approach.We argue the formalization approach presented in this paper would lead to a generalized framework for finding,in the context of QAOA,high-quality approximate solutions to NP optimization problems.

Direction of arrival estimation method based on quantum electromagnetic field optimization in the impulse noise

In order to resolve direction finding problems in the impulse noise,a direction of arrival(DOA)estimation method is proposed.The proposed DOA estimation method can restrain the impulse noise by using infinite norm exponential kernel covariance matrix and obtain excellent performance via the maximumlikelihood(ML)algorithm.In order to obtain the global optimal solutions of this method,a quantum electromagnetic field optimization(QEFO)algorithm is designed.In view of the QEFO algorithm,the proposed method can resolve the difficulties of DOA estimation in the impulse noise.Comparing with some traditional DOA estimation methods,the proposed DOA estimation method shows high superiority and robustness for determining the DOA of independent and coherent sources,which has been verified via the Monte-Carlo experiments of different schemes,especially in the case of snapshot deficiency,low generalized signal to noise ratio(GSNR)and strong impulse noise.Beyond that,the Cramer-Rao bound(CRB)of angle estimation in the impulse noise and the proof of the convergence of the QEFO algorithm are provided in this paper.