| Time: Nov 12, 11:00-12:00 (Taipei Time) |
| Speaker: Sathyawageeswar Subramanian (University of Warwick) |
| Title: Sublinear quantum algorithms for estimating von Neumann entropy |
|
| Abstract: Entropy is a fundamental property of both classical and quantum systems, having numerous theoretical and practical applications in physics and computer science. In this talk, I will discuss the problem of obtaining estimates to within a multiplicative factor γ > 1 of the Shannon entropy of probability distributions, and the von Neumann entropy of mixed quantum states. Working with the purified quantum query access input model popularised by recent works such as [2] and [3], we build on the classical work on multiplicative estimation of Shannon entropy pioneered by Batu et al. [1], obtaining |
|
| (1) an O(n^{1/2γ^2})-query quantum algorithm that outputs a γ-multiplicative approximation of the Shannon entropy H(p) of a classical probability distribution p=(p1,…,pn), which is quadratically faster than the best possible classical algorithm for this task; |
| (2) an O(n^{1/2 + 1/2γ^2})-query quantum algorithm that outputs a γ-multiplicative approximation of the von Neumann entropy S(ρ) of a density matrix ρ ∈ C^{n×n}. |
|
| The quantum purified query access model can handle both classical probability distributions and mixed quantum states, and is the most general input model considered in the literature. I will give an overview of our techniques, which build on polynomial approximations, quantum singular value estimation, and quantum singular value transformations [4-5]. If time permits, I will also discuss an O(n^{1/3γ^2}) lower bound on the query complexity of γ-multiplicative estimation of Shannon and von Neumann entropies. |
|
| This talk is based on unpublished work with Tom Gur and Min-Hsiu Hsieh. |
|
| [1]: The Complexity of Approximating the Entropy |
| [2]: Distributional property testing in a quantum world |
| [3]: Quantum Algorithms for Classical Probability Distributions |
| [4]: Implementing smooth functions of a Hermitian matrix on a quantum computer |
| [5]: Quantum singular value transformation and beyond |
|
| Bio: Sathya completed his PhD in quantum computing at the University of Cambridge under the supervision of Prof. Richard Jozsa, and is currently a Research Fellow in the Department of Computer Science at the University of Warwick (UK), on the “Foundations of classical and quantum verifiable computing” project, which is led by Dr. Tom Gur. His primary interests are quantum algorithms and computational complexity theory. |
|
| Video: https://www.youtube.com/watch?v=VFJFsl2KC5M&list=PLRv5VlacpLeHNob2T12NK3DNNpGbtJ_M5&index=25 |
