It is commonly assumed that Grover’s quantum search algorithm halves the security level of cryptographic keys. Recently, Fischlin and Gkoumas (Selected Areas in Cryptography 2025) investigated the bit security of quantum key search more formally, especially if the keys are only statistically close to uniform. Their result confirmed that for a small statistical distance, the bit security matches the expected bound due to Grover’s algorithm: If the statistical distance of \(\lambda \) -bit keys from uniform is smaller than \(2^{-\lambda /2}\) , then the bit security against key search equals \(\lambda /2\) . However, for larger statistical distances, their result yields much looser bounds, leaving the exact bit security undetermined in such cases. In this work, we demonstrate that a small Chebyshev distance can compensate for a larger statistical distance in the context of key search, thereby improving the result of Fischlin and Gkoumas. The Chebyshev distance measures the maximum difference of any outcomes (as opposed to the sum of absolute differences, as in statistical distance), and can be exponentially smaller than the statistical distance. We show that with a small Chebyshev distance, we obtain the expected bit security bound of \(\lambda /2\) for quantum key search, even if the statistical distance is large.