#### Re: SciFi Toasts BRAIN

I don't know the details of AES etc, but it's a much greater class of problems than just asymmetric crypto-breaking that could in theory be tackled by a quantum computer.

Basically, N qubits can represent all numbers from 0 to 2^N-1 **at once!**. You then perform a series of operations on those qubits that if performed on a single number, would tell you (yes or no) that it was a member of the set of solutions smaller than 2^N-1 of your problem. For asymmetric cryptography, that search is for one of two large prime factors. You then observe your system in the quantum sense. It must collapse into one of the possible solutions of your problem - one of the two prime factors, which is all you need to break a code. For other problems there might be a known or unknown number of solutions larger than two, but provided the number of solutions is smallish, repeated runs of your quantum computer would statistically guarantee you'd find all of them ... even if knowing just one isn't all you need to get the rest conventionally.

As the number N of coupled qubits becomes large, quantum computing becomes exponentially closer to magic. That, or we discover a reason why it stops working when N is bigger than some new-physics-determined number.

The observable universe contains something of the order of (only!) 2^84 hadrons. This is why I find it inconcievable that a quantum computer could work with N qubits in the hundreds or thousands, let alone all the way up to millions, trillions and beyond. (Avogadro's number is ~10^26! )

Greg Egan writes the hardest of hard SF. For one possible implication of a working quantum computer for large N, read "Luminous"!