> In your last sentence, you compare future quantum computers to “today’s” non-quantum computers, which might be a false dichotomy.
Ah, good point.
Though I was more thinking of Shor's algorithm and Grover's algorithm that tells us the theoretical expected performance that could be achieved with quantum computers. Normally these are described as showing the speedup provided by a possible quantum computer (in relation to non-quantum computers).
So, when reading the Wolfram Model paper I cited, I read the statement regarding quantum computers as dismissing the possibility of achieving qantum computers capable of realising Shor's and Grover's.
But one could of course read it in a flip-side way, that there are algorithms out there to be discovered that achieves the same lower bound complexities on non-quantum machines.
Considering that the Wolfram Model is all about graphs and cellular automata, the statement should probably be considered not based on a RAM complexity model, but something like PRAM that considers parallelism.
Ah, good point.
Though I was more thinking of Shor's algorithm and Grover's algorithm that tells us the theoretical expected performance that could be achieved with quantum computers. Normally these are described as showing the speedup provided by a possible quantum computer (in relation to non-quantum computers).
So, when reading the Wolfram Model paper I cited, I read the statement regarding quantum computers as dismissing the possibility of achieving qantum computers capable of realising Shor's and Grover's.
But one could of course read it in a flip-side way, that there are algorithms out there to be discovered that achieves the same lower bound complexities on non-quantum machines.
Considering that the Wolfram Model is all about graphs and cellular automata, the statement should probably be considered not based on a RAM complexity model, but something like PRAM that considers parallelism.