AideNo621 t1_j2hdaas wrote
Quantum computers are not better computers. They are good for different tasks. They are good to solve tasks that current computers take very long to compute. It's almost impossible to explain how they work in layman terms, because it's quantum technology, which is complete weird shit. Most likely we will never see quantum home computers, maybe we could see some quantum capabilities added to the normal classical computers, but currently the tech is mostly run in lab environment. Because there's lots of interference that will break the function. Also needs to be supercooled to almost absolute zero. An example of a task that is very tedious for a normal computer but easy for a quantum computer is so called "traveling salesman problem". You have a bunch of cities on a map that you want to visit and you need to compute the most optimal route. This problem is easy to solve, but extremely hard to solve to be sure, that your solution is really the most optimal. For normal computers, the more points you have on the map, the longer it will take to compute. And this growth is probably around exponential, so you get to a point where it's simply not practical to even try to compute it, because it would take weeks, months, years. But quantum computers can somehow calculate all the possibilities at the same time and thus making the total time quite short. At least that's how I understand it. Problem with this is, that current computer security and cryptography is based on this, that it is extremely difficult to calculate some things for normal computers. But there will be a point of development in quantum computing where the quantum computer can break through the best current security in minutes. So new security algorythm will have to be developed, and are currently being worked on.
suvlub t1_j2hpza8 wrote
>An example of a task that is very tedious for a normal computer but easy for a quantum computer is so called "traveling salesman problem".
Not true. Travelling salesman is an NP-complete problem, quantum computers can't solve those any better than classical computers. See this diagram. P is what traditional computers are good at, BQP is quantum computers.
An example of a problem that quantum computers can solve (and classical probably can't) is prime factorization.
hbrthree t1_j2hviol wrote
So previous poster is full of shit lol?
suvlub t1_j2hwusy wrote
They were largely right until the example. To be fair, this is a common mistake, for sake of simplicity, or out of laziness, P and NP-complete problems are often explained as two opposite categories without mentioning all the other ones, so when people then hear that quantum computers can (easily) solve problems outside of P, they jump to the conclusion that they can solve NP-complete problems.
Oatz3 t1_j2hwcc7 wrote
Yes, quantum still can't solve traveling salesmen
AunKnorrie t1_j2huhwx wrote
Ah, You must have had professional training in the field ;)
suvlub t1_j2hwyfk wrote
Am programmer with masters in software engineering. Quantum computing is just something I'm vaguely interested in. I'd like to learn more about it, but shit's mind-boggling.
AunKnorrie t1_j2ilrrj wrote
Perhaps I should read up myself. I have an engineering degree in IT, so I had to read about Church’ thesis. Quantum is something new to me though.
PepperMill_NA t1_j2hy886 wrote
With that comes facility at cracking encryption keys
coolthesejets t1_j2i3e3w wrote
Would you say the existence of Shors means prime factorization is definitely not in np complete?
suvlub t1_j2ibswe wrote
It's a strong indication, but we still don't have a proof that P != NP, so no, not definitely.
coolthesejets t1_j2iyep1 wrote
Oh right! Interesting thank-you.
AideNo621 t1_j2ih99i wrote
Thanks for the correction. I was only reproducing what I read about the topic.
Yamidamian t1_j2j39b2 wrote
How is prime factorization ‘unsolvable’ on a classic computer? It seems like something any programmer could pound out a simple program to do pretty easily.
It would be slow as heck for really big values, due to recursion involved, but it would eventually give a solution.
Is there some kind of math definition of ‘solved’ that I’m unfamiliar with?
suvlub t1_j2j4qhu wrote
Sorry, I was sloppy. "Solve in polynomial time" is what I meant.
lunaticloser t1_j2hmghe wrote
Isn't there already a quantum-computer-safe encryption algorithm?
I seem to recall the problem with that algorithm was it was easily solved by regular computers 😅
sterexx t1_j2hnr7k wrote
NIST has been running a competition for quantum resistant encryption algos and somewhat recently announced some finalists for upcoming standards. They wouldn’t have any interest in ones not resistant to classical methods. If you can recall which algo you’re thinking of, though, I’d be interested to see
lunaticloser t1_j2ho8ox wrote
I can't. I might be misremembering but I thought some mathematician had devised such an algorithm even before the first quantum computer ever existed. Like way back in the 80s or so.
sterexx t1_j2hootb wrote
Ah okay! Yeah it’s fascinating how long they’ve been able to work on this stuff without having any actual hardware. Kinda like Turing’s machine!
If you can imagine how the machine works, you can design programs for it. Shor’s algorithm, which breaks RSA and other venerable public key cryptography systems (if you had a quantum computer to run it on), was made in 1994
lunaticloser t1_j2i2032 wrote
Yeah that's what I was thinking of
Cryptizard t1_j2hyxko wrote
The algorithms behind the new NIST standards have mostly been known for a long time (since the 90s) but it took a while to refine them and be confident in their security.
Loko8765 t1_j2hzz0z wrote
Probably Shor’s algorithm.
lunaticloser t1_j2i1x4a wrote
Yeah that was it!
warren_stupidity t1_j2i0a3a wrote
Things I learned: governments have archives of encrypted communications that they will decrypt as soon as they have a viable QC up to the task. It’s sort of the encryption apocalypse.
fenton7 t1_j2i53oi wrote
The largest prime number ever factored by a real quantum computer using Shor's algorithm was 21 back in 2012 so don't hold your breath. In 2019 an attempt was made to factor the number 35 using Shor's algorithm on an IBM Q System One, but the algorithm failed because of accumulating errors. It's tech that sounds great in science fiction but actually building a working quantum computer with enough qbits and low enough noise to do anything useful may be an impossible engineering problem.
warren_stupidity t1_j2iermh wrote
right - it might be in the 'fusion reactor' mode of breakthroughs that never actually pan out into something functional. Or not.
thecoat9 t1_j2irs6z wrote
>which is complete weird shit.
I move that "weird shit" be generally used in place of "quantum technology" world wide.
ThePaperBoy88 t1_j2hzla0 wrote
Actually quantum computers are getting easier to make there is a desktop version now being produced. It’s nothing special just something to learn with but it’s still moving from the lab only environment. https://www.notebookcheck.net/SpinQ-presents-world-s-first-portable-quantum-computers.675200.0.html
Viewing a single comment thread. View all comments