IEEE Transactions on Quantum Engineering

A Proposed Quantum Framework for Low-Complexity Quantum Simulation and Spectrum Estimation of Hankel-Patterned Systems

Mostafizur Rahaman Laskar, Amit Kumar Dutta

Published Jan 1, 2023• 2 citations

Abstract

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.

DOI: 10.1109/tqe.2023.3329213

Related papers

A Low-Complexity Quantum Simulation Framework for Toeplitz-Structured Matrix and Its Application in Signal Processing

Mostafizur Rahaman Laskar, Subhadeep Mondal, Amit Kumar Dutta

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.

IEEE Transactions on Quantum EngineeringJan 1, 20235 citations

A Complexity-Efficient Quantum Architecture and Simulation for Eigen Spectrum Estimation of Vandermonde System in a Large Antenna Array

Mostafizur Rahaman Laskar, Amit Kumar Dutta

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.

IEEE Transactions on Circuits and Systems I Regular PapersFeb 28, 20235 citations

Computational Complexity Analysis of Quantum Algorithms using Random Matrix Theory

Jincheng Zhang

This paper investigates the application of Random Matrix Theory (RMT) to the analytical complexity assessment of quantum algorithms. Traditional methods for estimating the computational complexity of quantum algorithms often rely on heuristics and approximations, frequently leading to overly pessimistic or overly optimistic results. We propose a novel approach utilizing RMT to model the statistical behavior of quantum circuits. Specifically, we leverage the eigenvalues and eigenvectors of random matrices to characterize the evolution of quantum states under arbitrary quantum circuits. This allows for a more precise estimation of the number of quantum gates (operations) required to achieve a desired level of accuracy in solving a given problem. We demonstrate, through illustrative examples, how RMT can provide tighter and more accurate bounds on the computational complexity compared to conventional techniques. The core claim of this work is that RMT offers a fundamentally new perspective on complexity analysis, promising to reveal deeper insights into the performance characteristics of quantum algorithms and potentially guide the design of more efficient quantum solutions.

Sep 1, 20260 citations

Eigen-Spectrum Estimation and Source Detection in a Massive Sensor Array Based on Quantum Assisted Hamiltonian Simulation Framework

Mostafizur Rahaman Laskar, Subhadeep Mondal, Amit Kumar Dutta

In this work, we propose quantum assisted eigenvalue estimation and target detection algorithms for a large sensor array via Hamiltonian simulation. Quantum algorithms provide complexity advantage of a certain class of problems on a quantum computer with fewer physical resources as compared to their classical counterparts. The proposed algorithms make use of the quantum phase estimation (QPE) as its core computing component. We have introduced an analytical quantum framework to map from classical to quantum in the context of target detection. Target detection involves an appropriate choice of threshold based on the probability of detection or false alarm. We exploited the massive sensor array structure and invoked the random matrix theory to propose an optimal threshold. It also takes into account the quantum measurement noise in the framework. Numerical simulations are performed to ascertain the efficacy of the proposed framework. The results suggest near term applications of the quantum algorithm for large-scale linear systems.

IEEE Transactions on CommunicationsApr 13, 20228 citations

Hamiltonian Simulation and Linear Combination of Unitary Decomposition of Structured Matrices

Robin Ollive, Stéphane Louise

To process a problem with a Quantum Processing Unit (QPU), it must be transformed into a sequence of quantum operators, or gates. These operators are either packed into a query (i.e. quantum algorithm primitive) that encodes the problem, or used to construct the cost function for Variationnal Quantum Algorithm (VQA). Typical queries are the problem Hamiltonian Simulation (HS) and the problem Block-Encoding (BEing). To construct the circuits associated with the quantum description, the problem must be mapped as a Linear Combination of Hamiltonian (LCH) or a Linear Combination of nitaries (LCU) matrices. All the summed Hamiltonian matrices or unitary matrices must have a known decomposition in basic gates. The complexity of this query should be incorporated into the quantum algorithm's query complexity, thereby limiting the processing possibilities of QPU for many problems. In this work, we propose Hamiltonian matrices used to map the problem of interest, and that behave like a single qubit when expressed in the appropriate basis. It leads to a framework, the Special Tripotent Hamiltonian (STH) Framework, able to implement most of the typical problems considered for quantum computing. These methods address many problems implemented on QPUs, ranging from second-quantization chemistry operators to graphs associated with Partial Differential Equations (PDE), sparse matrices, and higher-order optimization problems. This work underlines interesting properties associated with the STH basic gate decomposition. These include the ability to switch between LCH and LCU, map non-Hermitian problems, and construct the quantum circuit queries required for quantum computing. We also provide a list of STH that are used for the matrix decomposition of many structured matrices. These structured matrices are associated with graph adjacency matrices that can be combined to implement structured matrices.

quant-pharXiv:2603.17816Mar 19, 20260 citations

Automated Verification of Hamiltonian Simulation by Quantum Signal Processing

Min Lai, Yu-Fang Chen, Shih-Han Hung

We present, to the best of our knowledge, the first fully automated verification framework for QSP-based Hamiltonian simulation. Our framework exploits the structure of the simulation algorithm: Hamiltonians are given as weighted sums of Pauli strings, embedded into larger unitaries through block encodings, and transformed into time-evolution operators by quantum signal processing (QSP). Using a symbolic Pauli-sum semantics for ancilla-indexed circuit blocks, our verifier proves that the distinguished all-zero ancilla block is proportional to the target Hamiltonian and infers the subnormalization factor automatically. It then verifies the QSP layer by extracting the implemented polynomial transformation and certifying its approximation error. This structure-aware abstraction is essential for scalability. Composing our verified block encoding and QSP wrapper yields an estimated macro-expanded size of about 1.52 million gates. The verifier certifies the block encoding once and checks the QSP layer through its abstract interface, without expanding the oracle calls. Our implementation verifies block encodings of structured Pauli-sum Hamiltonians with up to 256 system qubits and verifies QSP Hamiltonian-simulation instances by extracting their implemented polynomials and checking the resulting approximation bounds. These results show that fully automated verification can handle common Hamiltonian-simulation circuits at substantial scale when it exploits their algorithmic structure.

cs.PLCross-listedarXiv:2610.39491Oct 30, 20260 citations