Before revision:  Then, as an application, we prove strong direct product theorems for K-Search under a natural product distribution not considered in previous works, and for finding K distinct collisions in a uniform random function ]  . Finally, we use the latter result to obtain the first quantum time-space tradeoff that is not based on a reduction to K-Search.
After revision:  Then, as an application, we prove strong direct product theorems for K-Search under a natural product distribution not considered in previous works, and for finding K distinct collisions in a uniform random function ] by using a quantum computer. We prove that the number of queries to the function in the quantum random oracle model must increase significantly when the size of the available memory is limited . Finally, we use the latter result to obtain the first quantum time-space tradeoff that is not based on a reduction to K-Search.