Quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916768023314432 |
|---|---|
| author | Zenchuk, Alexander I. Bochkin, Georgii A. Qi, Wentao Kumar, Asutosh Wu, Junde |
| author_facet | Zenchuk, Alexander I. Bochkin, Georgii A. Qi, Wentao Kumar, Asutosh Wu, Junde |
| contents | We propose quantum algorithms, purely quantum in nature, for calculating the determinant and inverse of an $(N-1)\times (N-1)$ matrix (depth is $O(N^2\log N)$) which is a simple modification of the algorithm for calculating the determinant of an $N\times N$ matrix (depth is $O(N\log^2 N)$. The basic idea is to encode each row of the matrix into a pure state of some quantum system. In addition, we use the representation of the elements of the inverse matrix in terms of algebraic complements. This algorithm together with that for matrix multiplication { proposed earlier} yields the algorithm for solving systems of linear algebraic equations (depth is $O(N\log^2 N)$. Measurement of the ancilla state with output 1 (probability is $\sim 2^{-O(N\log N)}$) removes the garbage acquired during calculation. Appropriate circuits for all three algorithms are presented and have the same estimation $O(N\log N)$ for the space (number of qubits in the circuit). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_16619 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems Zenchuk, Alexander I. Bochkin, Georgii A. Qi, Wentao Kumar, Asutosh Wu, Junde Quantum Physics We propose quantum algorithms, purely quantum in nature, for calculating the determinant and inverse of an $(N-1)\times (N-1)$ matrix (depth is $O(N^2\log N)$) which is a simple modification of the algorithm for calculating the determinant of an $N\times N$ matrix (depth is $O(N\log^2 N)$. The basic idea is to encode each row of the matrix into a pure state of some quantum system. In addition, we use the representation of the elements of the inverse matrix in terms of algebraic complements. This algorithm together with that for matrix multiplication { proposed earlier} yields the algorithm for solving systems of linear algebraic equations (depth is $O(N\log^2 N)$. Measurement of the ancilla state with output 1 (probability is $\sim 2^{-O(N\log N)}$) removes the garbage acquired during calculation. Appropriate circuits for all three algorithms are presented and have the same estimation $O(N\log N)$ for the space (number of qubits in the circuit). |
| title | Quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2401.16619 |