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

Willow, Our Quantum Chip

blog.google

Post reply on HN
Print view View original

391–400 of 557 posts

Re: Willow, Our Quantum Chip

#391

Post by IanCal »

adastra22 wrote: post #315
IanCal wrote: post #264

Earlier quoted context omitted.

Doing 2^76 iterations is huge . That's a trillion operations a second for two and a half thousand years if I've not slipped up and missed a power of ten.

Google's SHA-1 collision took 2^63.1 hash operations to find. Given that a single hash operation takes more than 1000 cycles, that's only less than three doublings away. Cryptographers worry about big numbers. 2^80 is not considered secure.

It's early so I'm thinking out loud here but I don't think the algorithm scales like this, does it?

We're talking about something that can search a list of size N in sqrt(N) iterations. Splitting the problem in two doesn't halve the compute required for each half. If you had to search 100 items on one machine it's taken 10x iterations but split over two it'd take ~7x on each or ~14 in total.

Re: Willow, Our Quantum Chip

#392

Post by ramchip »

kortilla wrote: post #332
qnleigh wrote: post #249

Earlier quoted context omitted.

You need to distinguish between "physical qubits" and "logical qubits." This paper creates a single "first-of-a-kind" logical qubit with about 100 physical qubits (using Surface Code quantum error correction). A paper from Google in 2019 estimates needing ~20 million physical qubits ("How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits" - https://arxiv.org/abs/1905.09749 ), though recent adva…

> quantum computers would be able to retroactively break any public keys that were stored Use a key exchange that offers perfect forward secrecy (e.g. diffie Hellman) and you don’t need to worry about your RSA private key eventually being discovered.

> Forward secrecy is designed to prevent the compromise of a long-term secret key from affecting the confidentiality of past conversations. However, forward secrecy cannot defend against a successful cryptanalysis of the underlying ciphers being used, since a cryptanalysis consists of finding a way to decrypt an encrypted message without the key, and forward secrecy only protects keys, not the ciphers themselves.[8] A patient attacker can capture a conversation whose confidentiality is protected through the use of public-key cryptography and wait until the underlying cipher is broken (e.g. large quantum computers could be created which allow the discrete logarithm problem to be computed quickly). This would allow the recovery of old plaintexts even in a system employing forward secrecy.

https://en.wikipedia.org/wiki/Forward_secrecy#Attacks

Re: Willow, Our Quantum Chip

#393

Post by AlexCoventry »

thrance wrote: post #71
vessenes wrote: post #18

I’m a quantum dabbler so I’ll throw out an armchair reaction: this is a significant announcement. My memory is that 256 bit keys in non quantum resistant algos need something like 2500 qubits or so; and by that I mean generally useful programmable qubits. To show a bit over 100 qubits with stability, meaning the information survives a while, long enough to be read, and general enough to run some benchmarks on is some…

The error rates given are still horrendous and nowhere near low enough for the Quantum Fourier Transform used by Shor's algorithm. Taking qubit connectivity into account, a single CX between 2 qubits that are 10 edges aways gives an error rate of 1.5%. Also, the more qubits you have/the more instructions are in your program, the faster the quantum state collapses. Exponentially so. Qubit connectivity is still ridicul…

In addition to that, the absolutely enormous domains that the Fourier Transform sums over (essentially, one term in the sum for each possible answer), and the cancellations which would have to occur for that sum to be informative, means that a theoretically-capable Quantum Computer will be testing the predictions of Quantum Mechanics to a degree of precision hundreds of orders of magnitude greater than any physics experiment to date. (Or at least dozens of orders of magnitude, in the case of breaking Discrete Log on an Elliptic Curve.) It demands higher accuracy in the probability distributions predicted by QM than could be confirmed by naive frequency tests which used the entire lifetime of the entire universe as their laboratory!

Imagine a device conceived in the 17th century, the intended functionality of which would require a physical sphere which matches a perfect, ideal, geometric sphere in Euclidean space to thousands of digits of precision. We now know that the concept of such a perfect physical sphere is incoherent with modern physics in a variety of ways (e.g., atomic basis of matter, background gravitational waves.) I strongly suspect that the cancellations required for the Fourier Transform in Shor's algorithm to be cryptographically relevant will turn out to be the moral equivalent of that perfect sphere.

We'll probably learn some new physics in the process of trying to build a Quantum Computer, but I highly doubt that we'll learn each others' secrets.

Re: Willow, Our Quantum Chip

#394

Post by bawolff »

sizzle wrote: post #390
bawolff wrote: post #328

Earlier quoted context omitted.

Long enough you don't need to panic or worry. Short enough that its reasonable to start r&d efforts on post quantum crypto.

Is there a way to fork and add a quantum-proof encryption layer on the existing cryptocurrency paradigm i.e. Bitcoin 2.0?

You could replace ECDSA with a post quantum algorithm. Keep in mind that many crypto primitives are safe, so there are large parts of bitcoin where you don't have to do anything. Digital signatures is going to be where the main problem is for bitcoin. But thinks like the hash algorithm should be fine (at most quantum gives a square root speed up for hashing, which isn't enough to be really concerning).

One thing that might be problematic for a blockchain where everything has to go on the blockchain forever is that some post quantum schemes have really large signatures or key sizes.

I'm not that familiar with the details of bitcoin, but i had the impression that p2pkh is more secure against quantum computers.

[I should emphasize, im not a cryptographer and only somewhat familiar with bitcoin]

Re: Willow, Our Quantum Chip

#395

Post by inasio »

vessenes wrote: post #18

I’m a quantum dabbler so I’ll throw out an armchair reaction: this is a significant announcement. My memory is that 256 bit keys in non quantum resistant algos need something like 2500 qubits or so; and by that I mean generally useful programmable qubits. To show a bit over 100 qubits with stability, meaning the information survives a while, long enough to be read, and general enough to run some benchmarks on is some…

They showed a logical qubit that can last entangled for an hour, but to do that they had to combine their hundred or so physical qubits into a single one, so in some sense they have, right now, a single (logical) qubit

Re: Willow, Our Quantum Chip

#396

Post by tsimionescu »

goatking wrote: post #51
vessenes wrote: post #18

I’m a quantum dabbler so I’ll throw out an armchair reaction: this is a significant announcement. My memory is that 256 bit keys in non quantum resistant algos need something like 2500 qubits or so; and by that I mean generally useful programmable qubits. To show a bit over 100 qubits with stability, meaning the information survives a while, long enough to be read, and general enough to run some benchmarks on is some…

How can I, a regular software engineer, learn about quantum computing without having to learn quantum theory? > Worth spending a little time doing some long tail strategizing I’d say any tips for starters?

If you want to learn about what theoretical quantum computers might be able to do faster than classical ones and what they might not, you can try to read about quantum complexity theory, or some of what Scott Aaronson puts out on his blog if you don't want to go that in depth.

But the key thing to know about quantum computing is that it is all about the mathematical properties of quantum physics, such as the way complex probabilities work.

Re: Willow, Our Quantum Chip

#397

Post by [deleted] »

vangamoZX wrote: post #300
codeulike wrote: post #60

They opened the API for it and I'm sending requests but the response always comes back 300ms before I send the request, is there a way of handling that with try{} predestined{} blocks? Or do I need to use the Bootstrap Paradox library?

Write the catch clause before the try block

[deleted]

Re: Willow, Our Quantum Chip

#398

Post by tsimionescu »

adastra22 wrote: post #248
cwillu wrote: post #245

Earlier quoted context omitted.

O(sqrt(N)) is easily dominated by the relative ease of constructing much bigger classical computers though.

Uh, no? Not for large N. There are about 2^152 possible legal chess states. You cannot build a classical computer large enough to compute that many states. Cryptography is generally considered secure when it involves a search space of only 2^100 states. But you could build a computer to search though sqrt(2^152) = 2^76 states. I mean it'd be big--that's on the order of total global storage capacity. But not "bigger t…

That only helps for a relative small range of N. Chess happens to sort of fit into this space. Go is way out, even a sqrt(N) is still in the "galaxy-sized computer" range. So again, there are few problems for which Grover's algorithms really takes us from practically uncomputable to computable.

Even for chess, 2^76 operations is still waaaaay more time than anyone will ever wait for a computation to finish, even if we assumed quantum computers could reach the OPS of today's best classical computers.

Re: Willow, Our Quantum Chip

#399

Post by not_a_bot_4sho »

zelon88 wrote: post #135

> It lends credence to the notion that quantum computation occurs in many parallel universes, in line with the idea that we live in a multiverse, a prediction first made by David Deutsch. Can someone explain to me how he made the jump from "we achieved a meaninful threshold in quantum computing performance" to "The multiverse is probably real."

My money is on edibles.
Post reply on HN