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

Bitcoin’s race to outrun the quantum computer

decrypt.co

Post reply on HN
Print view View original

71–80 of 90 posts

Re: Bitcoin’s race to outrun the quantum computer

#71

Post by mensetmanusman »

anm89 wrote: post #20

"The amount of time the universe itself has left—around 0.65 billion billion years." Is this true?? I've never heard this claimed before.

You can estimate this because there is a known amount of energy around in the visible universe (energy, mass, etc.). We know from inflation that this number changes at a given rate. We also know that time and entropy are connected, so when entropy of the known universe is at the maximum, it would be essentially meaningless to say time could continue, i.e ‘the end of time.’

Re: Bitcoin’s race to outrun the quantum computer

#72

Post by _7fvc »

I get that quantum computer can run faster with more states. But can someone with quantum computing experience explain how quantum computer can address exponential computation? Does it reduce exponential computation into polynomial?

My answer to the above question is no. Assuming a quantum computer has 10 states. Its running time for exponential algorithms is still exponential. A simple example: 2^10 is about 10^3. Still exponential.

Re: Bitcoin’s race to outrun the quantum computer

#73

Post by rolltiide »

sroussey wrote: post #58
rolltiide wrote: post #24

Earlier quoted context omitted.

Its not much harder for bitcoin... The community will just do a blockchain snapshot of balances at an agreed upon block and start a new distributed ledger with quantum resistant encryption Snapshots have been done hundreds of times

> The community will just do ... This is the funny thing about decentralized services. They require centralized action. Not saying it is good or bad, but it is... different.

It requires community consensus thats the opposite of centralized

Anyone can make a snapshot, assigning value to it is not centralized

Re: Bitcoin’s race to outrun the quantum computer

#74

Post by The_rationalist »

McTossOut wrote: post #68
The_rationalist wrote: post #57

Earlier quoted context omitted.

> which seems probable, as we are progressing fast in the number of qubits we can keep together Probable? Ridiculous: ×there are still no hardware implementation of a single logic gate despite what? 40 years of research? ×stability of qubits are pathetic. ×no software stack (almost) ×Number of qubits are ridiculous and 40 years of research can't even make a consensus on how much qubits are needed for beating a CPU on…

There's a very intuitive inductive argument that places quantum computers ahead of classical computers. Basically that quantum interactions are more fundamental to the universe than more terse ones, stochastic randomness or presence/absence. If a computing device (in a universe) is built to compute using more fundamental substance (to that universe) it should stand to reason it is more efficient. If you model a photo…

I would like to understand what you mean but I can't, could you rephrase / exemplify?

"Basically that quantum interactions are more fundamental to the universe than more terse ones, stochastic randomness or presence/absence." What does more fundamental means? Presence, absence and randomness are included in the set of quantum interactions they are not of a different nature.

" If a computing device (in a universe) is built to compute using more fundamental substance (to that universe) it should stand to reason it is more efficient." What does fundamental substance mean? I don't understand this paragraph.

"If you model a photon, does your model ever move as fast as the photon?" My model does not move. If you meant that my mental visual simulation of a photon moving is slower than a photon moving, yes obviously, it's slowness and lack of accuracy is just a limitation of my brain. How is that related to quantum speedup?

Help me understanding you, I would really like to believe in quantum speedup but the explanation needs to be sound.

Re: Bitcoin’s race to outrun the quantum computer

#75

Post by tialaramex »

bhouston wrote: post #53

Will breaking classic computer public key encryption reveal any secrets that were encoded prior to them being obsolete? Should we be recording encrypted streams and saving them for a few years until we can break them? Is there any value in that?

Yes, if this ever works and is affordable.

Suppose our adversaries have a machine which can do Shor's algorithm at the scale needed to break modern public keys for say $1M and an hour, and they have been recording encrypted sessions.

For sessions encrypted using RSA key exchange, it is enough for them to spend $1M and wait one hour and then they can decrypt everything that they've recorded, using one particular key. So e.g. a typical HTTPS site only has one key for months or even years, if they've recorded the encrypted data they can read all of it for $1M.

Where Forward Secrecy (e.g. ECDHE) was used, the cost is $1M (and an hour) for each session, because the keys change each time so each fresh session needs the expensive algorithm.

Re: Bitcoin’s race to outrun the quantum computer

#76

Post by solveit »

mlyle wrote: post #45
krastanov wrote: post #39

Earlier quoted context omitted.

We definitely are getting closer. Look at any graph of "qubit lifetime" and you will see how we have orders of magnitude improvements. (a quick google search gives me page 9 of https://hpcuserforum.com/presentations/tuscon2018/QCOverview... ). We still need a couple more orders of magnitude before the qubits are useful, but the signs of exponential progress are unmistakable. I would not take any experiment performing…

So if we extrapolate out the current curve 2 more orders of magnitude, it looks good. Therefore we can conclude it's looking possible? ;)

We conclude it's looking possible because fundamental physics says it should be possible.

Re: Bitcoin’s race to outrun the quantum computer

#77

Post by rolltiide »

gruez wrote: post #40
zazagura wrote: post #30

Earlier quoted context omitted.

Everybody will need new private keys. What do you do with old coins? Satoshi's one for example? Or lost coins that nobody has the key for? Do you set a threshold day, after which all unclaimed coins are just marked destroyed forever? If not, how do you know someone claiming some coins didn't use a quantum computer to get the key?

>Do you set a threshold day yeah pretty much. >What do you do with old coins? Satoshi's one for example? Or lost coins that nobody has the key for? If those coins hasn't been touched for decades, despite widespread announcements of pre-quantum cryptography (presumably it wouldn't happen overnight), it's safe to say that nobody is going to claim them.

Dont treat any address differently

Re: Bitcoin’s race to outrun the quantum computer

#78

Post by jeromebaek »

> Ah, but with the right quantum computer, able to process information at speeds exponentially faster than today’s supercomputers? Suddenly, what seems uncrackable becomes child’s play, able to be broken in under 10 minutes.

Cringe. Quantum computers are not "able to process information at speeds exponentially faster than today's supercomputers". They're able to solve a very specific subset of problems which are hard for classical computers. A very specific subset, called BQP, mostly having to do with finding prime factors. NP hard problems are probably uncrackable with quantum computers.

Re: Bitcoin’s race to outrun the quantum computer

#79

Post by McTossOut »

The_rationalist wrote: post #74
McTossOut wrote: post #68

Earlier quoted context omitted.

There's a very intuitive inductive argument that places quantum computers ahead of classical computers. Basically that quantum interactions are more fundamental to the universe than more terse ones, stochastic randomness or presence/absence. If a computing device (in a universe) is built to compute using more fundamental substance (to that universe) it should stand to reason it is more efficient. If you model a photo…

I would like to understand what you mean but I can't, could you rephrase / exemplify? "Basically that quantum interactions are more fundamental to the universe than more terse ones, stochastic randomness or presence/absence." What does more fundamental means? Presence, absence and randomness are included in the set of quantum interactions they are not of a different nature. " If a computing device (in a universe) is…

I'll reiterate that I was just hoping to share my intuition behind the subject but I'll try and point you in the right direction.

I mean that the relationship between Newtonian mechanics and Quantum mechanics is such that the matter described by Newtonian mechanics is composed of matter whose precise behavior is exclusively described by quantum mechanics, that is that underlying matter is fundamental to the macro behavior.

I'm by no means a physicist, but a formal treatment of this kind of relationship (and predicted consequences) is captured in Constructor Theory (as David Deutsch who may have been early in identifying this was able to formalize this in the much more precise language of physics)

Intuitively, if you took a whiffle ball (or pair of whiffle balls, or some other ensembleoof whiffle balls sufficient to represent a system's state) in your hands, and a little obstacle course representing, say, beam splitters, and with each in your hands somehow made these classical implements behave like photons, you would have little hope of doing this at light speed.

Re: Bitcoin’s race to outrun the quantum computer

#80

Post by mlyle »

krastanov wrote: post #69
mlyle wrote: post #45

Earlier quoted context omitted.

So if we extrapolate out the current curve 2 more orders of magnitude, it looks good. Therefore we can conclude it's looking possible? ;)

Yes, two or more orders of magnitude of improvement are very much expected by most researchers in this field, simply because the current state of the hardware is infantile compared to what we know is possible (it just takes a lot of work to put all the different improvements in a single experiment).

That's a completely different argument. "Researchers think we'll get two more orders of magnitude in a reasonable time" is quite different from saying "if we extrapolate this curve, we'll get there in 5 years". After all, exponents describe growth until they don't-- eventually we reach physical or economic limits (Moore's law has tapered off; bacteria in a dish of agar show exponential growth until they don't anymore, etc.)

I highly doubt we'll get there in 5 years, myself.

Post reply on HN