  We introduce the problem of determining if the mode of the output
distribution of a quantum circuit (given as a black-box) is larger than a given
threshold, named HighDist, and a similar problem based on the absolute values
of the amplitudes, named HighAmp. We design quantum algorithms for promised
versions of these problems whose space complexities are logarithmic in the size
of the domain of the distribution, but the query complexities are independent.
  Using these, we further design algorithms to estimate the largest probability
and the largest amplitude among the output distribution of a quantum black-box.
All of these allow us to improve the query complexity of a few recently studied
problems, namely, $k$-distinctness and its gapped version, estimating the
largest frequency in an array, estimating the min-entropy of a distribution,
and the non-linearity of a Boolean function, in the $\tilde{O}(1)$-qubits
scenario. The time-complexities of almost all of our algorithms have a small
overhead over their query complexities making them efficiently implementable on
currently available quantum backends.
