6 ms·

I have a question. Please excuse my ignorance but I thought that once the world has a working quantum computer, the world as we know it will be destroyed. Since

by furqs 8y ago

I have a question. Please excuse my ignorance but I thought that once the world has a working quantum computer, the world as we know it will be destroyed. Since a quantum computer can solve any NP hard problem in a polynomial time, it would mean it could break any kind of crypto, any kind of security and can brute force anything. Why hasn't that happened yet since its 2018 and we already have quantum computers?

vtomole 8y ago
A quantum computer can't solve any NP hard problem in polynomial time as far as we know.
0xbxd 8y ago
That's not how quantum computers work. They ("quantum networking") significantly increase security as you can tell whether a qubit has already been observed (eavesdropped) or not. Also, there are proven asymmetric cryptographic algorithms that work with quantum computers. Algorithms based on factorization (RSA) won't be safe any more but you still need a large amount of qubits (around 1000s - don't cite me on this please) to break them, which has not been achieved yet. Definitely not the end of the world. edit:// And they can not solve any NP-complete problem in polynomial time. That is a common misconception and not based on facts. edit2:// Researchers working on quantum computers actually don't believe that they will make it mainstream (partially due to their complexity like cooling them down to near zero Kelvin) but instead be specialized systems available via the internet for rent - or something similar. More on the side of predicting complex systems like the weather than powering your smartphone. Then again, who thought the PC would make it mainstream.
throwaway37585 8y ago
> Since a quantum computer can solve any NP hard problem in a polynomial time You are confusing https://en.wikipedia.org/wiki/BQP https://en.wikipedia.org/wiki/BQP with NP.
throwaway37585 8y ago
Also, keep in mind that NP hard ≠ NP complete. By saying 'solve any NP hard problem in polynomial time', you're also saying 'solve any NEXPTIME hard problem in polynomial time', which is known to be false.
currymj 8y ago
First, they only work on really specific problems. They aren’t just a magic tool for brute force. Current public-key crypto (both RSA and elliptic curve) happens to be one of those problems. However, there are systems where we don’t know how to break them with quantum computers, and it probably isn’t possible. These aren’t in wide use but have been tested in production e.g. by Google. If it becomes a problem, people can switch. Second, actual existing quantum computers are too small to do much of anything. We are just hitting the point where they could start to become interesting. There are still engineering and theoretical challenges in making them really work. All these quantum programming languages let you simulate a quantum computer, but doing so demands exponentially more resources as you add qubits. The advantage of a real quantum computer is that this would not be the case.

by furqs 8y ago

vtomole 8y ago

A quantum computer can't solve any NP hard problem in polynomial time as far as we know.

0xbxd 8y ago

That's not how quantum computers work. They ("quantum networking") significantly increase security as you can tell whether a qubit has already been observed (eavesdropped) or not. Also, there are proven asymmetric cryptographic algorithms that work with quantum computers. Algorithms based on factorization (RSA) won't be safe any more but you still need a large amount of qubits (around 1000s - don't cite me on this please) to break them, which has not been achieved yet. Definitely not the end of the world. edit:// And they can not solve any NP-complete problem in polynomial time. That is a common misconception and not based on facts. edit2:// Researchers working on quantum computers actually don't believe that they will make it mainstream (partially due to their complexity like cooling them down to near zero Kelvin) but instead be specialized systems available via the internet for rent - or something similar. More on the side of predicting complex systems like the weather than powering your smartphone. Then again, who thought the PC would make it mainstream.

throwaway37585 8y ago

> Since a quantum computer can solve any NP hard problem in a polynomial time You are confusing https://en.wikipedia.org/wiki/BQP https://en.wikipedia.org/wiki/BQP with NP.

throwaway37585 8y ago

Also, keep in mind that NP hard ≠ NP complete. By saying 'solve any NP hard problem in polynomial time', you're also saying 'solve any NEXPTIME hard problem in polynomial time', which is known to be false.

currymj 8y ago

First, they only work on really specific problems. They aren’t just a magic tool for brute force. Current public-key crypto (both RSA and elliptic curve) happens to be one of those problems. However, there are systems where we don’t know how to break them with quantum computers, and it probably isn’t possible. These aren’t in wide use but have been tested in production e.g. by Google. If it becomes a problem, people can switch. Second, actual existing quantum computers are too small to do much of anything. We are just hitting the point where they could start to become interesting. There are still engineering and theoretical challenges in making them really work. All these quantum programming languages let you simulate a quantum computer, but doing so demands exponentially more resources as you add qubits. The advantage of a real quantum computer is that this would not be the case.