It's also important to note that quantum computers are just faster classical computers, they are still Turing machines. Many people who are looking for some non-computable element of consciousness in quantum effects in microtubules seem to forget that.
They can encode exponentially many states simultaneously, and are non-deterministic.
But what is clear is that there is no computation that can be done on a QC that can't be done on a TM.
The role of non-determinism in computation is more debatable. There is even a notable MIT professor (who coined the term Actor model) who claims that real computers, like the Android phone I'm writing this on, are in fact not Turing machines, because of non-determinism / parallelism. He also claims that Godel's incompleteness theorem doesn't apply to actual mathematics, so I would take his words with a huge spoonful of salt.
so for a 8 bit key for example you would need to run the same operation 256 times 65536 for a 16 bit key and 4,294,967,296 for a 32 bit. so in essence quantum computation just lets you cheat on massively parallel processes but is not a hyper-turring machine or a turring oracle. in fact there are many algorithms that you get no gain from using qubit other than i higher energy bill
https://en.wikipedia.org/wiki/Quantum_computing#Computabilit...
Qubits aren't magic either and the amount of data they can store is well known, it's just a complex bit instead of a real one.
It's important to note that probabilistic Turing machines are different from quantum Turing machines in terms of efficiency, as far as it is known today. But still, that doesn't change the fact that they can (inefficiently) simulate each other.
However, Feynman does not claim what you say he claims. His whole article is about efficiently simulating QM on a classical computer, and he shows that is not possible given what we understand of quantum probability today, at least (he does this by explicitly asking for a computer which does not grow exponentially in size with the size of the physical system it wants to simulate).
In modern CS terms, what he is discussing is whether the complexity classes BPP and BQP are equal or not (as far as we know today, just as he claims, BPP seems to be a smaller subset of BQP, but this is not proven).
This is all perfectly in line with my claim, and is in fact explicitly there in Feynman's paper: a classical computer can perfectly simulate a quantum system/computer, but requires exponential time/space to do so (as far as we know).
Isn't there a point where we could say we can't really simulate powerful enough quantum computers because they can "decode" the patterns behind any psuedorandom computation so quickly?
Like no one in the right mind would be using classical computers at that point except for anything except basic computation and word processing. We might as well say humans and pen and papers can simulate quantum computers. Quantum computer capabilities may outstrip classical computers nearly as much as they do humans with pen and paper.
"Simulation" kind of loses it's meaning when taken far enough.
But then I also see that "classical computers can never be built big enough to explore more than 400, actually more than, probably 100 qubits, 100 qubits doesn’t seem like very much. No classical computer can do the calculation of following what 100 qubits do" https://blog.ycombinator.com/leonard-susskind-on-richard-fey...
Are we really in no danger of quantum computers being able decipher patterns behind these traditional sources of noise? There is no pattern to quantum randomness. Aren't we going to have switch to truly random sources of noise eventually, instead of pseudorandom ones (anything non quantum)?
But this chaos is deterministic. Chaos means highly sensitive to initial conditions and involves nonlinearity, but it is still entirely classical and deterministic. In the real world we do not measure things precise enough to keep track of a lava lamp's deterministic evolution, but it is there within the chaos.
So I am wondering if a quantum computer, which Susskind says takes only 100 qubits to outperform any Turing Machine constructable ever, may one day do better at picking out the deterministic patterns behind the chaos of things like lava lamps. And if that happens, we may need more extreme versions of chaotic systems to keep secrets. And since quantum randomness is the only true randomness in the universe, forever indiscernable in principle; will one day all deterministic, chaotic means of adding "randomness" be replaced with quantum sources of randomness, due to how powerful quantum computers are?
*Now you could say even the lava lamp involves quantum randomness because everything is ultimately quantum. But because it is so macroscopic, it behaves more classically the a smaller quantum system.
It's very important to understand that this only applies for a limited set of algorithms. QCs are not universal accelerators. In particular, if picking out this deterministic patterns from the apparent chaos were an NP problem, the QC would be just as slow as any other computing machine that we know so far.
You're also misunderstanding how chaotic systems work. With a chaotic system, even if you know the precise time evolution rules, you're not going to be able to predict the outcome at time T, because a tiny difference in the initial conditions, or a tiny interference from the outside world, will mean vastly different outcomes.
In fact, QCs would be particularly BAD at predicting the outcome of a chaotic system, because QCs can only give answers up to some error bound, unlike classical computers which can perform exact calculations. But the error introduced by the QC itself is probably going to compound the imprecision in the initial measurements of your chaotic system.
One final note that is important to state: the problem with predicting chaotic systems is not physical or computational, it is mathematical. You can have even simple systems whose solution can vary orders of magnitude more than a variance in the parameters. Solving such a system is easy and fast, but the solution is physically meaningless: a 0.01% error in the measurements can mean that you solution is off by a factor of 100.
I was thinking along the lines of running current observed data backwards to fine tuned initial conditions. That must require lots of computational power. Are we sure quantum computers and quantum algorithms wont speed this part up. That has to be somwewhat isomorphic to factoring large numbers, which I thought QC does have a potential advantage. But maybe chaos is distinct from factoring, I don't know much about how it would be modeled computationally. I realize most of the battle is getting proper initial conditions. But quantum computing is also coming at time when quantum sensing is growing. To me with quantum computing speed ups and quantum sensors, we have the two ingredients necessary to make progress on chaotic systems. Better initial conditions and better computational methods. That was my thought. Sorry for the ramble
I don't think argument is about efficiency. "a classical computer can perfectly simulate a quantum system/computer" is not explicitily there, it's an argument against that. It seems to me you're saying anything that's not strictly proving BQP > BPP supports something else.
> The rule of simulation that I would like to have is that the number of computer elements required to simulate a large physical system is only to be proportional to the space-time volume of the physical system. I don't want to have an explosion. That is, if you say I want to explain this much physics, I can do it exactly and I need a certain-sized computer. If doubling the volume of space and time means I'll need an exponentially larger computer, I consider that against the rules (I make up the rules, I'm allowed to do that).
He emphasizes this again in the section about computing the probabilities:
> We emphasize, if a description of an isolated part of nature with N variables requires a general function of N variables and if a computer stimulates this by actually computing or storing this function then doubling the size of nature (N->2N) would require an exponentially explosive growth in the size of the simulating computer. It is therefore impossible, according to the rules stated, to simulate by calculating the probability. [emphasis mine]
So when he uses the term 'computer' he doesn't mean 'abstract Turing machine', he explicitly means 'realizable/efficient Turing machine'.