Search

Many standard linear algebra problems can be solved on a quantum computer by using recently developed quantum linear algebra algorithms that make use of block encodings and quantum eigenvalue/singular value transformations. A block encoding embeds a properly scaled matrix of interest A in a larger unitary transformation U that can be decomposed into a product of simpler unitaries and implemented efficiently on a quantum computer. Although quantum algorithms can potentially achieve exponential speedup in solving linear algebra problems compared to the best classical algorithm, such a gain in efficiency ultimately hinges on our ability to construct an efficient quantum circuit for the block encoding of A, which is difficult in general, and not trivial even for well structured sparse matrices. In this paper, we give a few examples on how efficient quantum circuits can be explicitly constructed for some well structured sparse matrices and discuss a few strategies used in these constructions. We also provide implementations of these quantum circuits in MATLAB.

We provide a modular circuit-level implementation and resource estimates for several methods of block-encoding a dense $N\times N$ matrix of classical data to precision $\epsilon$; the minimal-depth method achieves a $T$-depth of $\mathcal {O}(\log (N/\epsilon)),$ while the minimal-count method achieves a $T$-count of $\mathcal{O} (N \log(\log(N)/\epsilon))$. We examine resource tradeoffs between the different approaches, and we explore implementations of two separate models of quantum random access memory. As a part of this analysis, we provide a novel state preparation routine with $T$-depth $\mathcal {O}(\log (N/\epsilon))$, improving on previous constructions with scaling $\mathcal {O}(\log ^{2} (N/\epsilon))$. Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.

Abstract: TDOA based passive location is an important application in sensor networks. The signal data must be transferred from one sensor to another, which is used to estimate TDOA. Therefore, a data compression method has to be used for the sake of reducing the volume of data. In order to improve coding efficiency, a block-encoding method based on windowed Discrete Fourier Transform (DFT) is proposed. We design a polyphase structure to achieve windowed DFT, which can achieve real time processing of the high sampling rate. Compared with transform coding to the whole data, the block-encoding method is easy to implement in engineering with lower computation complexity, and therefore saves computational resources. Simulation results show that TDOA estimation accuracy based on data block-encoding data is close to that based on the whole encoding method for high SNR. [Copyright &y& Elsevier]