Exécution de notre outil de synthèse sur un nouvel article
Vérifiez l’article ci-dessous, puis lancez sa synthèse.
Optimal Joint Bounds for Sparse Ground-State Energy Estimation and Ground-State Preparation
Dhrumil Patel
Résumé : Ground-state energy estimation (GSEE) and ground-state preparation (GSP) are fundamental problems in quantum computing. Given a Hamiltonian $H$ with $\|H\|\le1$ and a guiding state $|ψ\rangle$ with overlap at least $γ>0$ with the ground space of $H$, the goal in GSEE is to estimate the ground-state energy of $H$ to additive error $δ$ with failure probability at most $\varepsilon$, while in GSP it is to prepare a state with ground-space weight at least $1-\varepsilon$, given a gap lower bound $Δ$. Their costs are measured by quantum query complexity, i.e., the number of oracle calls needed to access $H$. Recent work proved optimal bounds $Θ(\log(1/\varepsilon)/(γδ))$ for GSEE and $Θ(\log(1/\varepsilon)/(γΔ))$ for GSP in the time-evolution and block-encoding models. However, these models do not directly account for the sparsity of $H$, measured by the maximum number $s$ of nonzero entries in any row or column. In the sparse-access model, oracles instead return the locations and values of these entries. This introduces the additional parameter $s$, and it remained open how query complexity depends jointly on $s$, $γ$, $δ$ or $Δ$, and $\varepsilon$. We resolve this by proving sparse-query lower bounds $Ω(\sqrt{s}\log(1/\varepsilon)/(γδ))$ for GSEE and $Ω(\sqrt{s}\log(1/\varepsilon)/(γΔ))$ for GSP, even for stoquastic Hamiltonians. We also show that these constructions recover the earlier time-evolution and block-encoding lower-bound scalings. We then give matching upper-bound algorithms in the reversible in-place sparse-location model. Thus, we obtain $Θ(\sqrt{s}\log(1/\varepsilon)/(γδ))$ for GSEE and $Θ(\sqrt{s}\log(1/\varepsilon)/(γΔ))$ for GSP, showing that $\sqrt{s}$ is necessary and sufficient and completing the joint dependence on all problem parameters.