Short version: quantum computing changes the balance of difficulty between encryption and decryption, but it's likely to swing back. The transition period will be interesting.

Spoiler

Google is not the only company investing in quantum computers, of course - it's what everyone thinks is the next thing, but nobody really knows how, when, or if it's going to show up as a deployable. I expect that this will happen, and when it happens it'll feel quite sudden, and it'll be the thing that makes cloud computing make sense, at least for some period of about a decade.

If you think of encryption as a constant swaying back and forth between encryption and cryptanalysis, the encryption side has a definite advantage today, in that the only way to crack modern crypto is to take advantage of a mistake in encryption. There are many mistakes to make, so implementation is hugely important, but if the encryption is done perfectly, then there is simply no way to break it within the time frames that anyone is interested in.

Quantum computing changes that dynamic, and by all accounts, destroys the world as we know it: public-key encryption as we know it goes away, meaning essentially that all secrets on the web go away. E-commerce, secure protocols, and the rest of it are no longer secure when there is someone interested in knowing your secrets and that person has a quantum computer. This is not because quantum computing is particularly fast, it's because it's inherently massively parallel. The problem of factoring in reasonable time is hard because you have to conduct many, many, many operations, but those operations are computationally independent. If a quantum computer can do huge numbers of divisions simultaneously - which is what people are looking for in that technology - then the actual computations don't have to be especially fast.

However, I think it's quite likely that there are other trap-door functions out there that will not be vulnerable to the massive parallelism that quantum computing gives us access to - you need, basically, a function that can't be broken into discrete sub-problems in this fashion. I'm not a mathematician, but I think that such a function can and will be devised, especially since the encrypters will also have access to the quantum computers.

The interesting part will be the period when quantum computing is available but hugely expensive. And this is where I get to cloud computing: salesforce, amazon, and google will all have these machines, and they'll be fighting tooth and nail to capture the market for secure web services.

My prediction is that the big issue will be the quantum public-key encryption protocol, and, when it's found, whether it's made open or kept as proprietary IP. This is potentially a real problem - apparently there are some encryption protocols which are quite good, but are not deployed due to IP issues. (they rely on proprietary algorithms)

Google is not the only company investing in quantum computers, of course - it's what everyone thinks is the next thing, but nobody really knows how, when, or if it's going to show up as a deployable. I expect that this will happen, and when it happens it'll feel quite sudden, and it'll be the thing that makes cloud computing make sense, at least for some period of about a decade.

If you think of encryption as a constant swaying back and forth between encryption and cryptanalysis, the encryption side has a definite advantage today, in that the only way to crack modern crypto is to take advantage of a mistake in encryption. There are many mistakes to make, so implementation is hugely important, but if the encryption is done perfectly, then there is simply no way to break it within the time frames that anyone is interested in.

Quantum computing changes that dynamic, and by all accounts, destroys the world as we know it: public-key encryption as we know it goes away, meaning essentially that all secrets on the web go away. E-commerce, secure protocols, and the rest of it are no longer secure when there is someone interested in knowing your secrets and that person has a quantum computer. This is not because quantum computing is particularly fast, it's because it's inherently massively parallel. The problem of factoring in reasonable time is hard because you have to conduct many, many, many operations, but those operations are computationally independent. If a quantum computer can do huge numbers of divisions simultaneously - which is what people are looking for in that technology - then the actual computations don't have to be especially fast.

However, I think it's quite likely that there are other trap-door functions out there that will not be vulnerable to the massive parallelism that quantum computing gives us access to - you need, basically, a function that can't be broken into discrete sub-problems in this fashion. I'm not a mathematician, but I think that such a function can and will be devised, especially since the encrypters will also have access to the quantum computers.

The interesting part will be the period when quantum computing is available but hugely expensive. And this is where I get to cloud computing: salesforce, amazon, and google will all have these machines, and they'll be fighting tooth and nail to capture the market for secure web services.

My prediction is that the big issue will be the quantum public-key encryption protocol, and, when it's found, whether it's made open or kept as proprietary IP. This is potentially a real problem - apparently there are some encryption protocols which are quite good, but are not deployed due to IP issues. (they rely on proprietary algorithms)