Entanglement is the workhorse enabling quantum algorithms that offer substantial computational speedups over their classical counterparts. However, a quantitative understanding of how the amount and type of available entanglement relates to the performance of quantum algorithms remains elusive. In this project, we employ the ingredients of generic states and entanglement estimation to uncover the deep connection between entanglement and algorithm performance. This is achieved by systematically studying the behavior of certain algorithms across major generic states ensembles as measured by different entanglement estimators. The new framework will be applied to examine the performance of quantum algorithms and studied in the context of quantum simulation and quantum circuit cutting methods. As an integral part of the project, some of the project results will be evaluated, verified, and benchmarked by making use of IBM Quantum Simulators and Argonne Leadership Computing Facility (ALCF) resources in collaboration with the co-PI at Argonne National Laboratory (ANL). The synergy of the PI's effort on entanglement estimation and the co-PI's current focus on quantum algorithms is necessary to advance the understanding on the role of entanglement in quantum algorithm analysis. In addition to making scientific progress, the active collaboration will help build sustained capacity for the PI and his institution by leveraging expertise of the co-PI and unique resources at ANL.

In entanglement estimation, we consider entropy-based estimation, where the exact moments of the entanglement entropies over different models of generic (random) states will be derived. Based on the results, we will investigate entanglement phase transitions between separable and entangled states and identify the corresponding critical system parameters. We also consider metric-based estimation, where the key entanglement metrics of fidelity and volumes in quantum computing will be studied. The ultimate goal is to develop a rigorous but non-asymptotic entanglement estimation theory based on recent progress, including these of the PI's group, in understanding the statistical behavior of finite-size quantum systems.

In applications to quantum algorithms, the project progress on entanglement estimation will be utilized to establish the framework connecting the performance of quantum algorithms to the degree of entanglement of quantum states. The proposed framework will lead to new perspectives in quantum algorithm development. As case studies, we will focus on quantum simulation algorithms in the context of quantum approximate optimization algorithms and quantum circuit cutting methods in the context of state tomography, an area the co-PI is actively contributing to.