Comment by programjames | Hacker News Reader

Comment by programjames | Hacker News Reader

Parent Full thread

The reason it doesn't list what the computer is "useful" for is because quantum computers currently don't have a lot of uses. Right now, it's mostly:

- Fourier transform in log(n)^2 rather than nlog(n) time. Shor's algorithm uses this---the numbers 2^0, 2^1, 2^2, ..., 2^n (modulo n) are periodic for some factor of phi(n) (Euler-totient function). A Fourier transform will have a peak around that period, which you can quickly find on a quantum computer.

- Speeding up database queries (e.g. Grover's algorithm).

You can also make communications more secure with some quantum stuff, but that isn't computing. In the future, some more interesting computer applications will be:

- Physical simulations, e.g. how do proteins fold, or chemical reactions take place.

- Bayesian neural networks. After training, there's some distribution the weights could be in based on the initialization. Choosing a fixed set of weights results in overfitting, but if you instead take the expected output given that distribution, you get the most likely answer. That's obviously infeasible on a classical computer (though dropout approximates this), but possible on a quantum one.

> You can also make communications more secure with some quantum stuff, but that isn't computing.

Care to elaborate? The only thing that I can think of is avoiding the current crop of side channel attacks, but I admit to only giving quantum computers cursory glances: still, I am very curious!

There was a section of IBM's quantum computing challenge that had you encrypt/decrypt logical qbits by transforming their phase state to a known degree. If the state was altered in-transit, than the inverse transform will not cancel out correctly.

the challenge also mentioned that for it to work in practice, the qbits themselves would have to be transported somehow.

You send a photon with the polarization giving the bit:

Basis +: | = 0, — = 1,

Basis x: / = 0, \ = 1

You randomly choose a basis for each photon, but don't tell the receiver which basis it is until they receive the photon. They randomly choose a basis to decode on, and once learning the correct one discard the bit if they mismatch.

The key thing is an eavesdropper wouldn't know the correct basis either. If they try to "pass along the photon" they'll re-encode it in the wrong basis half the time, so the receiver will end up with the wrong bit when it should be correct (25% of the time). The sender can share some of the correct bits, and if the receiver has too many errors it's likely someone is eavesdropping.

Now, what bits do you actually send? Probably something like a "Learning With Errors" (LWE) cryptography key (as quantum computers kill RSA). Then you can transfer your actually data over classical communications. The quantum part is just the handshake at the beginning. If you detect eavesdropping you just send a new key over.

The current limitations are:

1. It's really slow. It can take seconds to send a 1,000 bit key just 1km (figure 4, 10.1109/PHOTONICS49561.2019.00010).

2. You need a single photon source so the eavesdropper cannot pass along photons while reading the message. It also has to be "heralded", i.e. you need to know when that photon gets sent. Right now these are pretty slow to generate.

3. The error rate has to be really low, otherwise you can't detect eavesdropping.

4. Your detection system can't have backscattering/other side-channel attacks. To detect single photons, people usually use "avalanche detectors", where the photon excites an electron, which goes on to excite many more due to a potential difference in a p-n junction. However this also creates small flashes every time a photon hits it.

Just to drop the name, we're talking about quantum key distribution (QKD).

> Now, what bits do you actually send?

You just send random bits and get a key. Then use the key however you want (AES, one-time-pad if you're crazy...). I guess that's actually the same as what you were saying...

> It can take seconds to send a 1,000 bit key just 1km

Toshiba marketing claims "13.7 Mb/s over a fiber distance of 10 km" [1]. I'm sure they also have a paper somewhere.

> You need a single photon source

No, people use "Decoy States", which allows you to use a "normal" weak pulsed laser. There is also continuous variable QKD which does not need single photons. You can use single photons (and some implementations do) but it's not mandatory.

[1]: https://www.global.toshiba/ww/products-solutions/security-ic...

Thanks for the corrections

Are these things it actually does, or more “quantum computing might be useful for this in the future!” hype?

Because OP was asking the former

Shor's algorithm and chemical simulations have been implemented on quantum computers, albeit very simple cases (factoring twenty-one, observing conical intersections). I don't think Grover's has been yet, but it's not much different than Shor's. Bayesian neural networks are purely hype.

Reply on news.ycombinator.com