Zhong-Xia Shang Zhong-Xia Shang is currently a postdoc at Hong Kong University. He received his PhD degree from University of Science and Technology of China in 2024 under the supervision of Prof. Chao-Yang Lu. He got his BS degree from University of Science and Technology of China, School of the Gifted Young. He has been previously working on superconducting quantum computing and later changed his research interest into designing quantum algorithms and looking for quantum-classical separations. 报告摘要 In this talk, I will introduce a new primitive for quantum algorithms called non-diagonal density matrix encoding (NDME). By encoding information into a non-diagonal block of a density matrix and manipulate the density matrix by a technique called channel block encoding, novel and powerful quantum algorithms emerge. I will introduce two quantum algorithms based on this new primitive.The first one [arXiv:2408.13721] is an improved amplitude estimation algorithm which is realized by transforming pure states into their matrix forms and encoding them into density matrices and unitary operators. This approach significantly reduces the complexity of amplitude estimation when states exhibit specific entanglement properties. A minimum of superpolynomial improvement can be achieved whenever the depth of the state preparation circuit has a polylogarithmic dependence on the number of qubits. Moreover, in certain extreme cases, an exponential improvement can be realized.The second algorithm is a near-optimal linear ordinary differential equation (ODE) solver. Specifically, we utilize the natural non-unitary dynamics of Lindbladians with the aid of NDME to encode general linear ODEs into non-diagonal blocks of density matrices. This framework enables us to provide a quantum algorithm that has both theoretical cleanness and good performance. Combined with the state-of-the-art Lindbladian simulation quantum algorithms, our algorithm, under a plausible input model, can give a complexity that outperforms all existing quantum algorithms of ODEs with near-optimal dependence on all parameters.
