My question basically boils down whether Quantum Computers are better computers or are they only different computers?
Is there a quantum algorithm for every problem which is at least as fast as the classical algorithm? If yes, then the fact that it has faster algorithms for some stuff like Factoring/Discrete Log etc means that it's a better computer. If no, then it's a different computer rather than a better computer
TL;DR: Different computers.
One of the main advantages behind quantum computers is that they are reversible computers, however there are irreversible functions, that classical computers can compute, that are difficult to port to quantum computers.
An example of a function that a classical algorithm can solve far better would be the modulo operator, e.g. $15\pmod7~=~1\pmod7$, in a classical computer we can just 'throw away' everything above the 3'rd bit, after calculating the modular operation.
Assuming we would want to implement said function in the quantum world, then we cannot just simply throw away qubits. (See $^1$ for a slight detail). If we do not restrict the input, and input, let's say $15$ and $22$, then the result should be $1$, but if two inputs have the same output, then it is clearly not reversible. And so, we need extra qubits (ancillas) or extra input assumptions to implement this 'irreversible' function. At this point it depends on your definition of 'fast', but it is likely safe to assume that both in temporal time and the amount of operations, this will be out scaled by the classical algorithm.
One can also think about it like this, assuming one were to implement said modular function, you could not use it in superposition, since you would need to measure or reset some qubits to make all the higher bits be $0$ again, hence collapsing a superposition and the main way to get any form of 'quantum advantage'.
Just for the sake of completeness, the input assumption done to implement modular exponentiation in Shor's Algorithm is that the input state is in $[1, p-1]$, this makes the creation of the operator 'easier'. Throughout the algorithm the modular operations are kept in $[1, p-1]$.
So where is the advantage in quantum computation?
The clear advantage is that we are no longer computing in the discrete space, with access to the Hilbert space, we can compute with the reals and hence complex numbers, though only to a certain degree, since we can only do so in superposition and can only extract 1 state from said superposition. (This is a very broad oversimplification)
This allows, e.g. Shor's Algorithm to solve certain problems exponentially faster than a classical computer.
What about quantum speedups for classical algorithms?
There are in-fact a wide-range of quantum speedups for classical algorithms, often classed as 'Grover's algorithms', but not only limited to them. The classic example is searching in an unstructured list. Assuming you have your list encoded in a quantum computer, then you can search for an element in it, in $O(\sqrt{N})$ time. And you can apply this to a wide range of search and oracle problems to gain square root speedups. This means that there are problems that if we scale them into very large numbers, then the quantum computer does beat a classical computer in the amount of operations, this also highly depends on the type of problem: decision problem, functional problem and if said problem can be converted into a search problem one can apply Grover's on.
The caveat on (some) quantum speedups
They assume you have your input encoded in a quantum computer. If we wanted to search through a classically stored list, then we would first need to encode that list in a quantum computer, which would take $O(N)$ time, you might as well search through the list at that point. The real question is then, can you encode the data you want to search through in less than $O(N)$ time, if you are e.g. searching over all the numbers from $0 \dots 2^n-1$, then you can, other cases may not be so easy.
$^1$: Theoretically, this is not a hard constraint, if we do not take advantage of superposition (then we can simply reset the qubits), however then we have no advantage at all over classical computation (it would be identical and likely slower on a quantum computer)
This is my first attempt at answering questions in the QCSE, some answers might not be completely accurate, feel free to correct me.
This is an area of ongoing research and debate. There are two aspects to the question: theoretical quantum advantage and demonstrated quantum advantage. Not every known classical algorithm has a known quantum alternative. But new algorithms are being devised in both areas. For example, this article: "A Moving Target for Quantum Advantage" discusses a problem which was considered an example of a quantum approach clearly showing an advantage over classical methods but then later shown to have a more accurate classical solution that didn't require special equipment. This isn't a general solution, though and doesn't imply that all similar problems are also classically solvable.
To be clear about what I mean by quantum algorithm, I am using the term as explained on wikipedia:
Although all classical algorithms can also be performed on a quantum computer, the term quantum algorithm is generally reserved for algorithms that seem inherently quantum, or use some essential feature of quantum computation such as quantum superposition or quantum entanglement.
In other words, a quantum algorithm is not simply any algorithm that runs on a quantum computer but one that takes advantage of the unique capabilities of quantum computers that classical computers lack.
It seems unlikely to me that all problems that have classical algorithms would have a superior quantum approach given that quantum algorithms are inherently probabilistic. Many classical algorithms are very fast and give an exact result in one pass. The areas where quantum computing is believed to have great potential is for problems where the classical algorithm doesn't scale. And even for those problems that have a theoretically faster quantum algorithm, the classical approach is likely to be faster at small scales for many problems.
My insights on quantum computers are limited, but quantum computers work completely different than "regular" computers.
I guess you will always have a combination of a regular computer with a quantum computer.
To my understandig quantum algorithms are good for the type of problem where you search for a needle in a haystack and have a way to break the search criteria down to a quantum algorithm.
The benefit of quantum computers is that you can test all or at least many single elements in parallel and don't have to test each element one after another.
I am not too familiar with quantum algorithms, but I am sure there are some restrictions.
I am pretty sure you can't (completely) solve problems where you actually have to compare the elements agains each other, e.g. search for the sharpest needle among all needles in the entire haystack, but you may search for the one needle which matches a predefined criteria.
Every problem which cannot be broken down into a parallel search operation cannot be optimized by a quantum algorithm.
One example would be when you calculate your taxes:
You start at the beginning and have a clear sequence how to calculate every step (as long as you know how to calculate taxes). You don't have to search and you cannot skip steps, it is a clear step by step aproach where you know how to calculate.
