4
$\begingroup$

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...

Improve this question
$\endgroup$
1
  • $\begingroup$ I would look at Grover's algorithm or super dense coding to see the "parallelization" in Quantum Computing. Beware, there is a lot of linear algebra :) $\endgroup$
    – LeWoody
    Jan 28, 2020 at 2:27

2 Answers 2

Reset to default
1
$\begingroup$

The reason that a quantum computer is faster in same tasks is given by different computational paradigm based on quantum mechanics laws. They mainly exploit superposition (i.e. state of qubit is linear combination of zero state and one state) and quantum entanglement (i.e. two or more qubits are connected and they behave as one system, or in other words there is some dependency among qubits values).

It is not easy, or even impossible, to explain in plain words, hence mathematical proof for each task is needed to evaluate speed-up and decide wheter there is any.

Commnon misunderstanding is that quantum computers are based on paralelism and provide exponential speed-up always as they process all possible values in $n$ qubits (i.e. $2^n$ values) at once. This is not true. If it was, all tasks would record exponential speed-up but this is not the case. While some tasks are speeded up exponentially (i.e. Shor algorithm for integer factoring), for others the speed-up is quadratic (i.e. Grover algorithm for searching in database).

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks @martinvesely for clarifying. I understand that different scales of speedup are achieved for different tasks. However, would we be able to achieve ANY speedup if we input qbit values sequentially? For example, the classical multi-string match problem (en.wikipedia.org/wiki/String-searching_algorithm) is usually solved by feeding bytes to a state-machine one-at-a-time - hence most practical algorithms achieve O(n) running time. Would we have to devise a new kind of algorithm to solve this problem in the quantum domain? $\endgroup$
    – Erez Buchnik
    Jan 28, 2020 at 6:17
  • 1
    $\begingroup$ @ErezBuchnik: Nice question. If you input qubits in same manner as on a classical computer, i.e. they will be either in state $|0\rangle$ or $|1\rangle$ and the computer will be fed sequentially, it seems logical that a quantum computer will behave as classical counterpart. But I am not completely sure about it. Sorry that I cannot give you better answer. $\endgroup$
    – Martin Vesely
    Jan 28, 2020 at 10:38
2
$\begingroup$

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?

Generally speaking yes, you need to come up with different algorithms. You cannot simply take a classical algorithm and "quantize it" in a straightforward way. Quantum algorithms work in a fundamentally different way than their classical counterparts.

I don't think the "sequential" aspect in the question is really the important point though. What's important is to have a bunch of qubits/states in a coherent superposition, and this is where most (all?) quantum algorithms draw their speed-ups from. You can input qubits sequentially and still have them interact using quantum memories or other such device (the specifics would depend on the way you define your model).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.