2026-07-20T14:51:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24519 2025-12-16T14:00:17Z ddc:004 open_access

Quantum Approximate k-Minimum Finding Gao, Minbo Ji, Zhengfeng Wang, Qisheng Quantum Computing Quantum Algorithms Quantum Minimum Finding Quantum k-minimum finding is a fundamental subroutine with numerous applications in combinatorial problems and machine learning. Previous approaches typically assume oracle access to exact function values, making it challenging to integrate this subroutine with other quantum algorithms. In this paper, we propose an (almost) optimal quantum k-minimum finding algorithm that works with approximate values for all k ≥ 1, extending a result of van Apeldoorn, Gilyén, Gribling, and de Wolf (FOCS 2017) for k = 1. As practical applications, we present efficient quantum algorithms for identifying the k smallest expectation values among multiple observables and for determining the k lowest ground state energies of a Hamiltonian with a known eigenbasis. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Minbo Gao and Zhengfeng Ji and Qisheng Wang 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.51 urn:nbn:de:0030-drops-245192 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.51 eng https://creativecommons.org/licenses/by/4.0/legalcode