The article analyses methods for determining the direction of arrival (DOA) of radio signals, particularly the MUSIC and ESPRIT algorithms. It is shown that the complexity of traditional approaches grows cubically with the number of antennas, which complicates their application in large-scale systems. The use of quantum algorithms for solving systems of linear equations and computing eigenvalues is proposed, allowing for a significant reduction in computational costs. The study examines the processing of complex matrices and presents a comparison table between classical and quantum versions of the algorithm in terms of computational complexity and structure.
The article analyses methods for determining the direction of arrival (DOA) of radio signals, particularly the MUSIC and ESPRIT algorithms. It is shown that the complexity of traditional approaches grows cubically with the number of antennas, which complicates their application in large-scale systems. The use of quantum algorithms for solving systems of linear equations and computing eigenvalues is proposed, allowing for a significant reduction in computational costs. The study examines the processing of complex matrices and presents a comparison table between classical and quantum versions of the algorithm in terms of computational complexity and structure.
The direction of arrival (DOA) estimation in array signal processing is an important research area. The effectiveness of the direction of arrival greatly determines the performance of multi-input multi-output (MIMO) antenna systems. The multiple signal classification (MUSIC) algorithm, which is the most canonical and widely used subspace-based method, has a moderate estimation performance of DOA. However, in hybrid massive MIMO systems, the received signals at the antennas are not sent to the receiver directly, and spatial covariance matrix, which is essential in MUSIC algorithm, is thus unavailable. Therefore, the spatial covariance matrix reconstruction is required for the application of MUSIC in hybrid massive MIMO systems. In this article, we present a quantum algorithm for MUSIC-based DOA estimation in hybrid massive MIMO systems. Compared with the best-known classical algorithm, our quantum algorithm can achieve an exponential speedup on some parameters and a polynomial speedup on others under some mild conditions. In our scheme, we first present the quantum subroutine for the beam sweeping based spatial covariance matrix reconstruction, where we implement a quantum singular vector transition process to avoid extending the steering vectors matrix into the Hermitian form. Second, a variational quantum density matrix eigensolver (VQDME) is proposed for obtaining signal and noise subspaces, where we design a novel objective function in the form of the trace of density matrices product. Finally, a quantum labeling operation is proposed for the direction of arrival estimation of the signal.
The direction of arrival (DOA) estimation in array signal processing is an important research area. The effectiveness of the direction of arrival greatly determines the performance of multi-input multi-output (MIMO) antennas. The multiple signal classification (MUSIC) algorithm, which is the most canonical and widely used subspace-based method for direction angle estimation, has a moderate estimation performance of DOA. In this article, we present a quantum algorithm for performing MUSIC. Compared with the best-known classical algorithm, quantum MUSIC can show a polynomial speedup. In our scheme, we first efficiently implement a non-Hermitian chain product subroutine for the matrix ${\stackrel{\ifmmode \hat{}\else \^{}\fi{}}{R}}_{ss}\ensuremath{\in}{R}^{N\ifmmode\times\else\texttimes\fi{}N}$ with L snapshots, where the method is different from that of Cong and Duan [I. Cong and L. Duan, New J. Phys. 18, 073011 (2016)]. In this subroutine, we perform amplitude transduction [Y. R. Sanders, G. H. Low, A. Scherer, and D. W. Berry, Phys. Rev. Lett. 122, 020502 (2019)] by testing an inequality to neglect the calculation of the approximate arcsine function. Second, a quantum labeling operation based on the principal eigenvalues is proposed for preparing the coherent state of the principal eigenvectors. Finally, we generalize our results to some quantum algorithms with quantum principal component analysis subroutines and some existing quantum algorithms where the covariance matrices occur in the non-Hermitian chain product form.
We demonstrate that the problem of amplitude estimation, a core subroutine used in many quantum algorithms, can be mapped directly to a problem in signal processing called direction of arrival (DOA) estimation. The DOA task is to determine the direction of arrival of an incoming wave with the fewest possible measurements. The connection between amplitude estimation and DOA allows us to make use of the vast amount of signal processing algorithms to post-process the measurements of the Grover iterator at predefined depths. Using an off-the-shelf DOA algorithm called ESPRIT together with a compressed-sensing based sampling approach, we create a phase-estimation free, parallel quantum amplitude estimation (QAE) algorithm with a worst-case sequential query complexity of ∼4.3/ε and a parallel query complexity of ∼0.26/ε at 95% confidence. This performance is statistically equivalent and a 16× improvement over Rall and Fuller [Quantum 7, 937 (2023)], for sequential and parallel query complexity respectively, which to our knowledge is the best published result for amplitude estimation. The approach presented here provides a simple, robust, parallel method to performing QAE, with many possible avenues for improvement borrowing ideas from the wealth of literature in classical signal processing.
Abstract The multiple signal classification (MUSIC) algorithm is a well-established method to evaluate the direction of arrival (DOA) of signals. However, the construction and eigen-decomposition of the sample covariance matrix (SCM) are computationally costly for MUSIC in hybrid multiple input multiple output (MIMO) systems, which limits the application and advancement of the algorithm. In this paper, we present a novel quantum method for MUSIC in hybrid MIMO systems. Our scheme makes the following three contributions. First, the quantum subroutine for constructing the approximate SCM is designed, along with the quantum circuit for the steering vector and a proposal for quantum singular vector transformation. Second, the variational density matrix eigensolver is proposed to determine the signal and noise subspaces utilizing the destructive swap test. As a proof of principle, we conduct two numerical experiments using a quantum simulator. Finally, the quantum labelling procedure is explored to determine the DOA. The proposed quantum method can potentially achieve exponential speedup on certain parameters and polynomial speedup on others under specific moderate circumstances, compared with their classical counterparts.
Eigenproblem arises in a large number of disciplines of sciences and engineering. Combining quantum algorithms to solve linear differential equations, quantum singular value estimation and quantum phase estimation, we propose quantum algorithms to compute the eigenvalues of diagonalizable matrices of two types: matrices that only have real eigenvalues and normal matrices. The quantum algorithms return a quantum state such that the first register stores eigenvalues and the second register stores the corresponding eigenvectors. For normal matrices, the complexity to obtain this quantum state is dominated by the complexity to perform quantum singular value estimation. For the other case, the complexity is determined by the solving of a linear system of differential equations. Under certain conditions (e.g. sparse), the complexities are polylog on the size n of the given matrix. If we perform measurements, then we can obtain all the eigenvalues classically. If M is s sparse, then the complexity is O(sn∥M∥maxκ2/ϵ2), where κ is the condition number of the matrix of eigenvectors.
Solving linear systems and computing eigenvalues are two fundamental problems in linear algebra. For solving linear systems, many efficient quantum algorithms have been discovered. For computing eigenvalues, currently, we have efficient quantum algorithms for Hermitian and unitary matrices. However, the general case is far from fully understood. Combining quantum phase estimation, quantum algorithm to solve linear differential equations and quantum singular value estimation, we propose two quantum algorithms to compute the eigenvalues of diagonalizable matrices that only have real eigenvalues and normal matrices. The output of the quantum algorithms is a superposition of the eigenvalues and the corresponding eigenvectors. The complexities are dominated by solving a linear system of ODEs and performing quantum singular value estimation, which usually can be solved efficiently in a quantum computer. In the special case when the matrix M is s-sparse, the complexity is O(sρ2κ2/ε2) for diagonalizable matrices that only have real eigenvalues, and O(sρ∥M∥max/ε2) for normal matrices. Here ρ is an upper bound of the eigenvalues, κ is the conditioning of the eigenvalue problem, and ε is the precision to approximate the eigenvalues. We also extend the quantum algorithm to diagonalizable matrices with complex eigenvalues under an extra assumption.