Quantum-enhanced algorithms for classical target detection in complex environments

Quantum computational approaches to some classic target identification and localization algorithms, especially for radar images, are investigated, and are found to raise a number of quantum statistics and quantum measurement issues with much broader applicability. Such algorithms are computationally intensive, involving coherent processing of large sensor data sets in order to extract a small number of low profile targets from a cluttered background. Target enhancement is accomplished through accurate statistical characterization of the environment, followed by optimal identification of statistical outliers. The algorithm is inspired by recent approaches to quantum machine learning, but requires significant extensions, including previously overlooked “quantum analog-digital” conversion steps (which are found to substantially increase the required number of qubits), “quantum statistical” generalization of the classic phase estimation and Grover search algorithms, and careful consideration of projected measurement operations. The key result of the paper is that the environmental covariance matrix estimation and manipulation at the heart of the statistical analysis, together with the target identification step, actually enable a highly efficient quantum implementation. However, several potential bottlenecks, especially those associated with data loading and conversion, are exhibited as well. Although no fundamental barrier to quantum speed-up is identified, optimal algorithm implementation, accounting for additional numbers of qubits and possible new error correction protocols associated with the quantum analog representation, remains an interesting question for future research.

Figure 1

Radar data collection geometry: Scene reflections from $N_p$ transmitted pulses $S_0\left(t\right)$ are detected by $N_R$ receivers, generating $M_S=N_p{N}_R$ received signals $S_m\left(t\right)$. Each pulse consists of an outgoing spherical wave, visualized here as a set of rays, so that $S_m\left(t\right)$ is a superposition of returns from every point in the scene—see (2.3) and (2.6). The scene consists of a target containing region (red stars, in general moving) surrounded by $K$ ($=8$ here) target-free clutter regions used to characterize the background statistics. The pulse compression operation (2.8) converts the signal time traces into image functions $\mathrm{\Sigma }\left(x\right)$ and ${\left\{W_k\left(x\right)\right\}}_{k=1}^K$, with $x=(\mathbf{x},\mathbf{v})$ some combination of spatial and velocity degrees of freedom depending on the measurement geometry. The $W_k$ are used to estimate the environmental covariance matrix $\widehat{G}$ via (2.18), and its inverse is used to optimally filter the target region data—see (2.20). As described in Sec. 3a, the quantum implementation of this filtering operation is based on importing these data into appropriately formatted quantum states $|{\psi }_{\mathrm{\Sigma }}\rangle$ and $|{\psi }_W\rangle$.

Figure 2

QSTAP machine learning algorithm flow chart: The classical target and background compressed datasets $\mathrm{\Sigma }\left(x\right)$ and ${\left\{W_k\left(x\right)\right\}}_{k=1}^K$, respectively, are loaded into quantum memory in standard “quantum digital” register format—see (3.1) and (3.6). Each must then be converted to quantum analog form (qD/A operation described in Appendix pp1) in order to implement the unitary evolution (3.12) via the density-matrix exponentiation approach (Sec. 4). The latter underlies the quantum phase estimation (Sec. 5) and linear algebra (Sec. 6) algorithms composing the HHL algorithm, and implementing the clutter suppression operation (2.20). The “Structured $\otimes N$” label signifies that many copies of the background dataset are required [essentially one for each micro-time step in the evolution (Sec. 4a)], and that an additional binary hierarchical structure must be imposed on the space of these copies to maintain efficient density-matrix phase estimation (see Sec. 5b2). The analog form HHL output state $|{\mathrm{\Sigma }}_G^{\mathcal{A}}\rangle \rangle$ must first be converted back to digital form (qA/D operation described in Appendix pp1) in order to construct the detection statistic (2.21) in the form of a state $\left|\right|{\mathrm{\Sigma }}_G{|}^2-h_0{\mathrm{\Sigma }}_{0,G}\rangle$. An extension of the Grover algorithm is then used to estimate the number of targets $N_{\gamma }$ and the quantum state $|{\gamma }_1\rangle$ describing their locations (Secs. 7 and 8).

Figure 3

Generalized quantum phase estimation quantum data structure implementing (5.16)–(5.18), maintaining the quantum advantage based on the binary decomposition (top line) of the sequence of simulation times $t_J=\epsilon J$. For each $J$ the evolution operator $\widehat{U}\left(t_J\right)$ is decomposed into a product of binary time interval operators (second line; here $\widehat{U}\left(0\right)$ is the identity operator whenever $J_j=0$). As indicated by the arrows, each $\widehat{U}\left(\epsilon J_j{2}^j\right)$ entangles a particular input environmental data state $|{\mathrm{\Psi }}_W\left(j\right)\rangle$ (third line) with the evolving working subspace ${\mathcal{H}}_{\mathrm{\Sigma }}$. The latter is initialized with the imaging data state $|{\psi }_{\mathrm{\Sigma }}\rangle$ [defined by (3.2)]. As indicated by the magenta box, each $|{\mathrm{\Psi }}_W\left(j\right)\rangle$ is in turn a product of $N_j=2^j\epsilon /\mathrm{\Delta }t$ copies of the underlying environmental data states $|{\psi }_W\rangle$ [defined by (3.8)] required to implement the generalized Suzuki-Trotter evolution operation (4.19) with time step $\mathrm{\Delta }t$. As discussed in the text, this hierarchical data structure is required to ensure proper parallel construction of the entangled state (5.15)—a uniform superposition of every evolved state $\left|\mathrm{\Psi }\right(t_J)\rangle$ (bottom line)—with the same data state $|{\mathrm{\Psi }}_W\left(j\right)\rangle$ applied consistently for every $J$ for which $J_j=1$. The evolution operators may also include qubit recycling and dissipation (see Sec. 4c) without affecting this underlying structure.