Hermitian Matrix Definiteness from Quantum Phase Estimation
- URL: http://arxiv.org/abs/2009.04117v2
- Date: Thu, 24 Nov 2022 19:00:13 GMT
- Title: Hermitian Matrix Definiteness from Quantum Phase Estimation
- Authors: Andr\'es G\'omez and Javier Mas
- Abstract summary: An algorithm to classify a general Hermitian matrix according to its signature is presented.
It builds on the Quantum Phase Estimation algorithm, which stores the sign of the eigenvalues of a Hermitian matrix in one ancillary qubit.
The algorithm is probabilistic, but it shows good performance, achieving 97% of correct classifications with few qubits.
- Score: 3.04585143845864
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: An algorithm to classify a general Hermitian matrix according to its
signature (positive semi-definite, negative or indefinite) is presented. It
builds on the Quantum Phase Estimation algorithm, which stores the sign of the
eigenvalues of a Hermitian matrix in one ancillary qubit. The signature of the
matrix is extracted from the mean value of a spin operator in this single
ancillary qubit. The algorithm is probabilistic, but it shows good performance,
achieving 97% of correct classifications with few qubits. The computational
cost scales comparably to the classical one in the case of a generic matrix,
but improves significantly for restricted classes of matrices like $k$-local or
sparse hamiltonians.
Related papers
- Tensor networks based quantum optimization algorithm [0.0]
In optimization, one of the well-known classical algorithms is power iterations.
We propose a quantum realiziation to circumvent this pitfall.
Our methodology becomes instance agnostic and thus allows one to address black-box optimization within the framework of quantum computing.
arXiv Detail & Related papers (2024-04-23T13:49:11Z) - Polynomial-depth quantum algorithm for computing matrix determinant [46.13392585104221]
We propose an algorithm for calculating the determinant of a square matrix, and construct a quantum circuit realizing it.
Each row of the matrix is encoded as a pure state of some quantum system.
The admitted matrix is therefore arbitrary up to the normalization of quantum states of those systems.
arXiv Detail & Related papers (2024-01-29T23:23:27Z) - Quantum Eigensolver for General Matrices [5.811990276393904]
We present a novel family of quantum algorithms tailored for solving the eigenvalue problem for general matrices.
Our algorithms find applications in diverse domains, including estimating the relaxation time of Markov chains.
These applications underscore the significance of our quantum eigensolvers for problems across various disciplines.
arXiv Detail & Related papers (2024-01-22T16:29:08Z) - A square-root speedup for finding the smallest eigenvalue [0.6597195879147555]
We describe a quantum algorithm for finding the smallest eigenvalue of a Hermitian matrix.
This algorithm combines Quantum Phase Estimation and Quantum Amplitude Estimation to achieve a quadratic speedup.
We also provide a similar algorithm with the same runtime that allows us to prepare a quantum state lying mostly in the matrix's low-energy subspace.
arXiv Detail & Related papers (2023-11-07T22:52:56Z) - Vectorization of the density matrix and quantum simulation of the von
Neumann equation of time-dependent Hamiltonians [65.268245109828]
We develop a general framework to linearize the von-Neumann equation rendering it in a suitable form for quantum simulations.
We show that one of these linearizations of the von-Neumann equation corresponds to the standard case in which the state vector becomes the column stacked elements of the density matrix.
A quantum algorithm to simulate the dynamics of the density matrix is proposed.
arXiv Detail & Related papers (2023-06-14T23:08:51Z) - A quantum algorithm for solving eigenproblem of the Laplacian matrix of
a fully connected weighted graph [4.045204834863644]
We propose an efficient quantum algorithm to solve the eigenproblem of the Laplacian matrix of a fully connected weighted graph.
Specifically, we adopt the optimal Hamiltonian simulation technique based on the block-encoding framework.
We also show that our algorithm can be extended to solve the eigenproblem of symmetric (non-symmetric) normalized Laplacian matrix.
arXiv Detail & Related papers (2022-03-28T02:24:08Z) - Quantum algorithms for matrix operations and linear systems of equations [65.62256987706128]
We propose quantum algorithms for matrix operations using the "Sender-Receiver" model.
These quantum protocols can be used as subroutines in other quantum schemes.
arXiv Detail & Related papers (2022-02-10T08:12:20Z) - Robust 1-bit Compressive Sensing with Partial Gaussian Circulant
Matrices and Generative Priors [54.936314353063494]
We provide recovery guarantees for a correlation-based optimization algorithm for robust 1-bit compressive sensing.
We make use of a practical iterative algorithm, and perform numerical experiments on image datasets to corroborate our results.
arXiv Detail & Related papers (2021-08-08T05:28:06Z) - Quantum algorithms for spectral sums [50.045011844765185]
We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices.
We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
arXiv Detail & Related papers (2020-11-12T16:29:45Z) - Optimal Iterative Sketching with the Subsampled Randomized Hadamard
Transform [64.90148466525754]
We study the performance of iterative sketching for least-squares problems.
We show that the convergence rate for Haar and randomized Hadamard matrices are identical, andally improve upon random projections.
These techniques may be applied to other algorithms that employ randomized dimension reduction.
arXiv Detail & Related papers (2020-02-03T16:17:50Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.