Aha! I found something that indeed seems suspicious about quantum computing. First I looked at the simplest quantum algorithm I could find:
"For the Deutsch–Jozsa algorithm to work, the oracle computing f(x) from x has to be a quantum oracle which doesn't decohere x." -- https://en.wikipedia.org/wiki/Deutsch%E ... _algorithm
Preventing quantum decoherence is really tricky, but okay let's assume that it can be solved in practice for a large number of qubits (quantum bits). And this is already commonly known, such as the extremely low temperatures needed for quantum computing today. The more suspicious part in the quote is the "oracle" needed. One programmer writes in a blog post:
"In this blog post, I tackle my perplexity at what seems to be a common practice of using quantum oracles without worrying about their time-complexity. Am I the only quantum computer programmer worried about this? Is there some important point that I’m missing?"
And from one of the comments: "Yes, it’s obvious that almost all quantum oracles on n qubits require exponential circuit size."
Do they just put the classical computation stuff in a black box and call it a quantum oracle? I also found this Quora question page:
"How does one create the Oracle required in the Deutsch-Jozsa algorithm?" -- https://www.quora.com/How-does-one-crea ... -algorithm
And the answer from an expert:
"Your question is an excellent one! You are revealing the soft underbelly of quantum computing!
An oracle is simply a memory lookup table with a mind boggling twist!
I call it the soft underbelly of quantum computing because this monsterous challenge is totally ignored in complexity counts of computation" -- Allan Steinhardt, PhD, Author "Radar in the Quantum Limit",Formerly DARPA's Chief Scientist,Fellow