Toeplitz matrix reconstruction algorithms (TMRAs) are one of the central subroutines in array processing for wireless communication applications. The classical TMRAs have shown excellent accuracy in the spectral estimation for both uncorrelated and coherence sources in the recent era. However, TMRAs incorporate the classical eigenvalue decomposition technique for estimating the eigenvalues of the Toeplitz-structured covariance matrices that demand very high computational complexity for large arrays. We demonstrate a low-complexity quantum simulation framework exploiting the structured Hamiltonian of Toeplitz and circulant variants. In this framework, we consider two approaches for the estimation of the eigenvalue spectrum of a given Toeplitz-structured matrix: first, an analytical framework with Jordan form-based sparse-decomposition of a dense-Toeplitz matrix, and second, an approximation method for the conversion of a Toeplitz matrix into a circulant matrix embedding quantum subroutines. We have also compared the efficacy of the proposed algorithms with standard Hamiltonian simulation and quantum phase estimation techniques for different quantum time resolutions and gate complexities. We show quantum gate-complexity analysis for our proposed algorithms. Considering the large dimensions of the Toeplitz matrix, we have employed random matrix theory in deriving the error bounds for the estimated eigenvalues. The numerical results are obtained partly in a classical computer and in an IBM quantum simulator.
Vandermonde matrix finds a wide range of applications in the digital signal processing domain including antenna array processing. Eigenspectrum estimation remains a challenge in such a system when the matrix dimension increases. This precise problem can be well addressed in a quantum simulation framework based on quantum Hamiltonian simulation (QHS). However, the structural exploitation of the matrix is never considered, which can give benefits in terms of quantum gate complexity. In this work, we exploit the special structural property of a dense Vandermonde matrix by decomposing it into several sparse matrices and then use them for a complexity-efficient eigenvalue spectrum estimation in a quantum framework. In this context, we propose an iterative quantum simulation framework for a Vandermonde-structured Hamiltonian called quantum Vandermonde simulation (QVS). The proposed approach requires fewer quantum gate operations compared to the standard QHS of a dense Vandermonde matrix. In this work, we have considered a large antenna array system, that exploits a delay Vandermonde matrix (DVM) to create a multi-beam beamformer using the proposed low complex quantum architecture. Extensive theoretical and numerical analysis in terms of complexity and other quality parameters have been conducted to show the benefit of the proposed method.
The structured matrix completion problem (SMCP) is ubiquitous in several signal processing applications. In this work, we consider a fixed pattern, namely Hankel-structure for the SMCP under quantum formalism. By exploiting its structure, a lower-gate-complexity quantum circuit realisation of a Hankel system is demonstrated. Further, we propose a quantum simulation algorithm for the Hankel-structured Hamiltonian with an advantage in quantum gate-operation complexity in comparison with the standard quantum Hamiltonian simulation technique. We show its application in eigenvalue spectrum estimation for signal processing applications. An error bound associated with this proposed quantum evolution is proposed with the consideration of spectrum estimation, and measurement uncertainty. Numerical results are reported adopting random matrix theory in its fold to evaluate the efficacy of the proposed architecture and algorithm for large dimensional systems including an example application in delay estimation for ranging operation in a wireless communication system.
This dissertation presents a study of quantum algorithms for problems that can be posed as matrix function tasks. In Chapter 1 we demonstrate a simple unifying framework for implementing of smooth functions of matrices on a quantum computer. This framework captures a variety of problems that can be solved by evaluating properties of some function of a matrix, and we identify speedups over classical algorithms for some problem classes. The analysis combines ideas from the classical theory of function approximation with the quantum algorithmic primitive of implementing linear combinations of unitary operators. In Chapter 2 we continue this study by looking at the role of sparsity of input matrices in constructing efficient quantum algorithms. We show that classically pre-processing an input matrix by spectral sparsification can be profitable for quantum Hamiltonian simulation algorithms, without compromising the simulation error or complexity. Such preprocessing incurs a one time cost linear in the size of the matrix, but can be exploited to exponentially speed up subsequent subroutines such as inversion. In Chapter 3, we give an application of this theory of matrix functions to the problem of estimating the Renyi entropy of an unknown quantum state. We combine matrix function techniques with mixed state quantum computation in the one-clean qubit model, and are able to bound of the expected runtime of our algorithm in terms of the unknown target quantity. In addition to the theme of analysing the complexity of our algorithms, we also identify instances that are of practical relevance, leading us to some problems of machine learning. In Chapter 4 we investigate kernel based learning methods using random features. We work with the QRAM input model suitable for big data, and show how matrix functions and the quantum Fourier transform can be used to devise a quantum algorithm for sampling random features that are optimised for given input data and choice of kernel. We obtain a potential exponential speedup over the best known classical algorithm even without explicit assumptions of sparsity or low rank. Finally in Chapter 5 we consider the technique of beamsearch decoding used in natural language processing. We work in the query model, and show how quantum search with advice can be used to construct a quantum search decoder that can find the optimal parse (which may for instance be a best translation, or text-to-speech transcript) at least quadratically faster than the best known classical algorithms, and obtain super-quadratic speedups in the expected runtime.
We study the potential utility of classical techniques of spectral sparsification of graphs as a preprocessing step for digital quantum algorithms, in particular, for Hamiltonian simulation. Our results indicate that spectral sparsification of a graph with
n nodes through a sampling method, e.g.\ as in \cite{Spielman2011resistances} using effective resistances, gives, with high probability, a locally computable matrix
H~ with row sparsity at most
O(polylogn). For a symmetric matrix
H of size
n with
m non-zero entries, a one-time classical runtime overhead of
O(m∣∣H∣∣tlogn/ε) expended in spectral sparsification is then found to be useful as a way to obtain a sparse matrix
H~ that can be used to approximate time evolution
eitH under the Hamiltonian
H to precision
ε. Once such a sparsifier is obtained, it could be used with a variety of quantum algorithms in the query model that make crucial use of row sparsity. We focus on the case of efficient quantum algorithms for sparse Hamiltonian simulation, since Hamiltonian simulation underlies, as a key subroutine, several quantum algorithms, including quantum phase estimation and recent ones for linear algebra. Finally, we also give two simple quantum algorithms to estimate the row sparsity of an input matrix, which achieve a query complexity of
O(n3/2) as opposed to
O(n2) that would be required by any classical algorithm for the task.
Estimating the eigenvalues of non-normal matrices is a foundational problem with far-reaching implications, from modeling non-Hermitian quantum systems to analyzing complex fluid dynamics. Yet, this task remains beyond the reach of standard quantum algorithms, which are predominantly tailored for Hermitian matrices. Here we introduce a new class of quantum algorithms that directly address this challenge. The central idea is to construct eigenvalue signals through customized quantum simulation protocols and extract them using advanced classical signal-processing techniques, thereby enabling accurate and efficient eigenvalue estimation for general non-normal matrices. Crucially, when supplied with purified quantum state inputs, our algorithms attain Heisenberg-limited precision--achieving optimal performance. These results extend the powerful guided local Hamiltonian framework into the non-Hermitian regime, significantly broadening the frontier of quantum computational advantage. Our work lays the foundation for a rigorous and scalable quantum computing approach to one of the most demanding problems in linear algebra.
Quantum phase estimation is a cornerstone in quantum algorithm design, allowing for the inference of eigenvalues of exponentially-large sparse matrices.The maximum rate at which these eigenvalues may be learned, –known as the Heisenberg limit–, is constrained by bounds on the circuit complexity required to simulate an arbitrary Hamiltonian. Single-control qubit variants of quantum phase estimation that do not require coherence between experiments have garnered interest in recent years due to lower circuit depth and minimal qubit overhead. In this work we show that these methods can achieve the Heisenberg limit, a l s o when one is unable to prepare eigenstates of the system. Given a quantum subroutine which provides samples of a `phase function' g ( k ) = ∑ j A j e i ϕ j k with unknown eigenphases ϕ j and overlaps A j at quantum cost O ( k ) , we show how to estimate the phases { ϕ j } with (root-mean-square) error δ for total quantum cost T = O ( δ − 1 ) . Our scheme combines the idea of Heisenberg-limited multi-order quantum phase estimation for a single eigenvalue phase [Higgins et al (2009) and Kimmel et al (2015)] with subroutines with so-called dense quantum phase estimation which uses classical processing via time-series analysis for the QEEP problem [Somma (2019)] or the matrix pencil method. For our algorithm which adaptively fixes the choice for k in g ( k ) we prove Heisenberg-limited scaling when we use the time-series/QEEP subroutine. We present numerical evidence that using the matrix pencil technique the algorithm can achieve Heisenberg-limited scaling as well.