Instantaneous noise-based logic can avoid time-averaging, which implies significant potential for low-power parallel operations in beyond-Moore-law-chips. However, in its random-telegraph-wave representation, the complete uniform superposition (superposition of all N-bit binary numbers) will be zero with high probability, that is, non-zero with exponentially low probability, thus operations with the uniform superposition would require exponential time-complexity. To fix this deficiency, we modify the amplitudes of the signals of L and H states and achieve an exponential speedup compared to the old situation. Another improvement concerns the identification of a single product-string (hyperspace vector). We introduce "time shifted noise-based logic", which is constructed by shifting each reference signal with a small time delay. This modification implies an exponential speedup of single hyperspace vector identification compared to the former case and it requires the same, O(N) complexity as in quantum computing.