Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Quantum algorithms conquer a new kind of problem

quantamagazine.org

Post reply on HN
Print view View original

11–20 of 35 posts

Re: Quantum algorithms conquer a new kind of problem

#11

Post by fio_ini »

_Microft wrote: post #8
fio_ini wrote: post #3

Will quantum computing destroy blockchain and classical encryption algorithms as we know? So there will be a need for quantum blockchain and quantum encryption.

Post-quantum cryptography is a thing: https://en.wikipedia.org/wiki/Post-quantum_cryptography

wow this is pretty interesting stuff thanks for the link. I'm not sure why I get such a negative response to my question since I'm seriously asking and not sure I should be concerned if this is like a alan turing enigma type of situation we're dealing with.

Re: Quantum algorithms conquer a new kind of problem

#12

Post by DennisP »

_Microft wrote: post #8
fio_ini wrote: post #3

Will quantum computing destroy blockchain and classical encryption algorithms as we know? So there will be a need for quantum blockchain and quantum encryption.

Post-quantum cryptography is a thing: https://en.wikipedia.org/wiki/Post-quantum_cryptography

I'm wondering whether it avoids this new type of problem that QCs should be able to solve.

Re: Quantum algorithms conquer a new kind of problem

#14

Post by atwood22 »

fio_ini wrote: post #3

Will quantum computing destroy blockchain and classical encryption algorithms as we know? So there will be a need for quantum blockchain and quantum encryption.

Classical asymmetric encryption algorithms like RSA and ECDSA (which Bitcoin uses) can be easily broken by a quantum computer. Brute-forcing symmetric algorithms like AES gets a speed up on a quantum computer, but not enough to consider the algorithms broken.

Re: Quantum algorithms conquer a new kind of problem

#15

Post by gxiv »

DennisP wrote: post #12
_Microft wrote: post #8

Earlier quoted context omitted.

Post-quantum cryptography is a thing: https://en.wikipedia.org/wiki/Post-quantum_cryptography

I'm wondering whether it avoids this new type of problem that QCs should be able to solve.

Going by their description of the problem, it looks like it's distinct from how all the mainstream post quantum algos (LWE, NTRU, SIDH, etc) work.

Edit: I've finished the article lol. Now I'm not so certain that this is 100% distinct from something like LWE.

Re: Quantum algorithms conquer a new kind of problem

#16

Post by gxiv »

> It involves calculating the inputs to a complicated mathematical process, based solely on its jumbled outputs.

Without going any deeper, this description of the problem is interesting because quantum algorithms are (by design) fully reversible, which isn't the case for classical computers (you lose information about the input when going through an OR gate, for example). Knowing that, it almost seems like a no-brainer that quantum computers would be better at this kind of problem than classical ones.

Re: Quantum algorithms conquer a new kind of problem

#17

Post by zitterbewegung »

TLDR; This is showing that a regular probabilistic computer can't do certain cryptographic problems faster than a quantum computer ( BPP Others have commented here that this is due to the fact that Quantum computers must be fully reversible operations which is in correct.

Re: Quantum algorithms conquer a new kind of problem

#18

Post by zitterbewegung »

gxiv wrote: post #16

> It involves calculating the inputs to a complicated mathematical process, based solely on its jumbled outputs. Without going any deeper, this description of the problem is interesting because quantum algorithms are (by design) fully reversible, which isn't the case for classical computers (you lose information about the input when going through an OR gate, for example). Knowing that, it almost seems like a no-brain…

That's incorrect its a proof of probabilistic computers are unable to be faster than quantum computers for certain cryptographic problems (BPP < BQP) and has nothing to do with reversibility. The reason quantum computers must be reversible is quantum systems must be reversible.

Re: Quantum algorithms conquer a new kind of problem

#19

Post by tsimionescu »

zitterbewegung wrote: post #17

TLDR; This is showing that a regular probabilistic computer can't do certain cryptographic problems faster than a quantum computer ( BPP Others have commented here that this is due to the fact that Quantum computers must be fully reversible operations which is in correct.

I think you mistyped, but just to be clear: it's showing that a regular probabilistic classical computer can't do certain cryptographic problems faster than a quantum computer.
Post reply on HN