Being a newbie in this field, I'm trying to understand what types of real-life workloads are suitable for migrating to Quantum computers. Intuitively, it seems to me that if a Quantum computer ingests data by reading symbols one-by-one from a tape, exactly like a classical Turing machine, it would be impossible for it to outperform the Turing machine. It seems that optimization can be achieved only if a parallel method of ingesting the input is implemented. Is this true? Does this mean that, if I want to migrate a workload to a Quantum computer for better performance, I should first try to parallelize it as much as possible?
I'd like to clarify my question with an example:
The classical multiple string-match problem - namely, "Given a string-set $L \subseteq \Sigma∗$ and an input stream $W \in \Sigma∗$, find all occurrences of any of the strings in $L$ that are substrings of $W$" - is considered a 'solved problem', where many algorithms solve it in $O(n)$. However, almost all of these algorithms have a hidden constraint - they assume that the input is fed to them sequentially.
It is obvious that when a cell extracts information from its DNA strand, or when a person reads a newspaper, they do not read the 'symbols' from left to right, or in any strict order for that matter. Still, strict order is usually enforced both in DNA analysis algorithms and in text analysis algorithms.
So my question is: do we need to come up with completely different quantum-based solutions for such problems, or is there a way to 'interpret' existing algorithms to the quantum domain and still expect some speedup?
Edit (and some thoughts):
Arguing that speedup requires handling parallelized input may lead to the following (pretty radical) conclusion: Order is overrated.
Computer Science 101 is all about for()
loops - maybe out of habit. Yet multithreading, hyperthreading, multicore, SIMD, DPDK, FPGA, and Quantum Computing, all considered major advancements, are all about parallelizing workloads and breaking the 'serial computing' paradigm. But at the moment we are stuck with cloud servers running endless loops and contributing to 'Pollution-as-a-Service'.
The next generation of programmers should probably learn Parallel and Quantum Computing in Computer Science 101, and treat for()
loops as a last resort...