Exponential quantum space advantage in random data streamsResearch Paper
A streaming algorithm receives its input one record at a time and retains a limited working memory between records. The memory needed to find an answer can depend on how the records arrive. A lower bound for an adversarial order therefore does not automatically apply when the order is chosen uniformly at random. The question here is whether quantum memory…