تقرير
An Efficient Quantum Algorithm for Linear System Problem in Tensor Format
| العنوان: | An Efficient Quantum Algorithm for Linear System Problem in Tensor Format |
|---|---|
| المؤلفون: | Wu, Zeguan, Misra, Sidhant, Terlaky, Tamás, Yang, Xiu, Vuffray, Marc |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science Mathematics Quantum Physics |
| مصطلحات موضوعية: | Quantum Physics, Mathematics - Numerical Analysis, 65F05, 68Q12, 81P68 |
| الوصف: | Solving linear systems is at the foundation of many algorithms. Recently, quantum linear system algorithms (QLSAs) have attracted great attention since they converge to a solution exponentially faster than classical algorithms in terms of the problem dimension. However, low-complexity circuit implementations of the oracles assumed in these QLSAs constitute the major bottleneck for practical quantum speed-up in solving linear systems. In this work, we focus on the application of QLSAs for linear systems that are expressed as a low rank tensor sums, which arise in solving discretized PDEs. Previous works uses modified Krylov subspace methods to solve such linear systems with a per-iteration complexity being polylogarithmic of the dimension but with no guarantees on the total convergence cost. We propose a quantum algorithm based on the recent advances on adiabatic-inspired QLSA and perform a detailed analysis of the circuit depth of its implementation. We rigorously show that the total complexity of our implementation is polylogarithmic in the dimension, which is comparable to the per-iteration complexity of the classical heuristic methods. |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2403.19829 |
| رقم الأكسشن: | edsarx.2403.19829 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |