A common presumption in cryptography is that quantum key search effectively halves the level of bit security compared to the classical setting, leading, for example, to the recommendation to use AES with 256-bit keys instead of 128-bit keys. From a very coarse point of view, this is perspicuous by the speed-up obtained via Grover’s search algorithm. On closer inspection, however, it lacks a formal justification, especially if the AES key is not perfectly random but only statistically close to uniform if generated by a quantum key distribution scheme. In other words, the question is how the statistical distance influences the quantum key search, or, viewed from an implementation point of view, how one should choose the statistical distance to achieve the best security bounds. Our starting points are the recent works about bit security of Micciancio and Walter (Eurocrypt 2018), Watanabe and Yasunaga (Asiacrypt 2021), and Lee (Communication in Cryptology 2024) in the classical setting. We transfer them to the quantum setting and discuss the security against quantum key search if the keys are close to uniform. We then argue that to achieve an optimal bit security level of \(\lambda /2\) bits for \(\lambda \) -bit keys against quantum search, it is advisable to set the statistical distance of the keys from uniform to a value in the range from \(2^{-\lambda }\) to \(2^{-\lambda /2}\) . Going below these bounds does not yield any advantage for the bit security, and going above this range gives worse bit security guarantees.