Quantum algorithm for the gradient of a logarithm-determinant
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909798045319168 |
|---|---|
| author | Baker, Thomas E. Greasley, Jaimie A. |
| author_facet | Baker, Thomas E. Greasley, Jaimie A. |
| contents | The logarithm-determinant is an widely-present operation in many areas of physics and computer science. Derivatives of the logarithm-determinant compute physically relevant quantities in statistical physics models, quantum field theories, as well as the inverses of matrices. A multi-variable version of the quantum gradient algorithm is developed here to evaluate the derivative of the logarithm-determinant. From this, the inverse of a sparse-rank input operator may be determined efficiently. Measuring an expectation value of the quantum state--instead of all $N^2$ elements of the input operator--can be accomplished in $O(k/\varepsilon^2)$ time in the idealized case for $k$ relevant eigenvectors of the input matrix with precision $\varepsilon$. A practical implementation of the required operator will likely need $\log_2N$ overhead, giving an overall complexity of $O((k\log_2 N)/\varepsilon^2)$. The method applies widely and converges super-linearly in $k$ when the condition number is high. The best classical method we are aware of scales as $N$.
Given the same resource assumptions as other algorithms, such that an equal superposition of eigenvectors is available efficiently, the algorithm is evaluated in the practical case as $O(\log_2 N/\varepsilon^2)$. The output is given in $O(1)$ queries of oracle, which is given explicitly here and only relies on time-evolution operators that can be implemented with arbitrarily small error. The algorithm is envisioned for fully error-corrected quantum computers but may be implementable on near-term machines. We discuss how this algorithm can be used for kernel-based quantum machine-learning. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_09413 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Quantum algorithm for the gradient of a logarithm-determinant Baker, Thomas E. Greasley, Jaimie A. Quantum Physics Mathematical Physics The logarithm-determinant is an widely-present operation in many areas of physics and computer science. Derivatives of the logarithm-determinant compute physically relevant quantities in statistical physics models, quantum field theories, as well as the inverses of matrices. A multi-variable version of the quantum gradient algorithm is developed here to evaluate the derivative of the logarithm-determinant. From this, the inverse of a sparse-rank input operator may be determined efficiently. Measuring an expectation value of the quantum state--instead of all $N^2$ elements of the input operator--can be accomplished in $O(k/\varepsilon^2)$ time in the idealized case for $k$ relevant eigenvectors of the input matrix with precision $\varepsilon$. A practical implementation of the required operator will likely need $\log_2N$ overhead, giving an overall complexity of $O((k\log_2 N)/\varepsilon^2)$. The method applies widely and converges super-linearly in $k$ when the condition number is high. The best classical method we are aware of scales as $N$. Given the same resource assumptions as other algorithms, such that an equal superposition of eigenvectors is available efficiently, the algorithm is evaluated in the practical case as $O(\log_2 N/\varepsilon^2)$. The output is given in $O(1)$ queries of oracle, which is given explicitly here and only relies on time-evolution operators that can be implemented with arbitrarily small error. The algorithm is envisioned for fully error-corrected quantum computers but may be implementable on near-term machines. We discuss how this algorithm can be used for kernel-based quantum machine-learning. |
| title | Quantum algorithm for the gradient of a logarithm-determinant |
| topic | Quantum Physics Mathematical Physics |
| url | https://arxiv.org/abs/2501.09413 |