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

Quantum Resistance and the Signal Protocol

signal.org

Post reply on HN
Print view View original

81–90 of 135 posts

Re: Quantum Resistance and the Signal Protocol

#81

Post by ahelwer »

wolverine876 wrote: post #50

That is very well-written, as someone else pointed out, though this common explanation for laypeople needs work (I'm not blaming Signal's blogger, who wrote it more carefully than most): "Instead of bits as in a classical computer, quantum computers operate on qubits. Rather than 0 or 1, qubits can exist in a superposition of states, in some sense allowing them to be both values at once." 'Instead of beads as in a cl…

The shortest possible answer is that qubit states are modeled as two-dimensional vectors on the complex unit sphere. We arbitrarily designate two orthonormal vectors on this sphere as corresponding to classical states 0 and 1. If the qubit vector isn't in the 0 or 1 state, it's in some linear combination of them. This is called superposition. Since most people don't know what linear combination means, superposition is explained as "sort of both at the same time". Upon measurement the qubits are collapsed to 0 or 1 with some probability proportional to how close they are to the 0 and 1 states. The precise probabilities are given by something called the Born rule. I gave a longer talk aimed at computer scientists if you're interested beyond this explanation: https://youtu.be/F_Riqjdh2oM

Re: Quantum Resistance and the Signal Protocol

#82

Post by blincoln »

andyferris wrote: post #59
krastanov wrote: post #23

Earlier quoted context omitted.

Doesn't your argument apply to classical bits too? The more interconnected a classical bit is, the more parasitic coupling it will experience. That used to be an argument used against the feasibility of classical computers in the 40s (until von Neumann published work on fault tolerant classical computing). Both classical and quantum computers (1) can not "scale" without error correction because of analog noise (altho…

To add to the sibling comment, the reason our classical computers work is because the individual transistor errors in your CPU are basically zero. We do use “error correction” on storage (and do see bit errors creep into data stored on disk and in RAM over time) but not “fault tolerance” on the compute. In fact there is no such thing as fault-tolerant classical compute - the CPU only works if it “perfect” or “near pe…

There have actually been a surprising number of computing platforms that implement fault-tolerant processing. It's often called "lock-step" execution.

https://www.vmware.com/content/dam/digitalmarketing/vmware/e... (throughout)

https://en.wikipedia.org/wiki/Tandem_Computers

https://www.intel.sg/content/dam/doc/product-brief/high-perf... (page 5)

Re: Quantum Resistance and the Signal Protocol

#83

Post by abdullahkhalids »

wolverine876 wrote: post #50

That is very well-written, as someone else pointed out, though this common explanation for laypeople needs work (I'm not blaming Signal's blogger, who wrote it more carefully than most): "Instead of bits as in a classical computer, quantum computers operate on qubits. Rather than 0 or 1, qubits can exist in a superposition of states, in some sense allowing them to be both values at once." 'Instead of beads as in a cl…

You are correct. That is a horrible explanation. And incomplete.

* The state of a qubit has two basis states. Arbitrary states are linear combinations (=superposition) of these basis states. Importantly, the coefficients in the linear combination can be positive or negative.

* The state of N qubits has 2^N basis states. poly(N) gate can put the state of the N qubits in which each of the 2^N basis states has a non-zero coefficient.

* In quantum algorithms, we play with the coefficients. Basically, certain problems (like factoring) have structure such that you can change the coefficients so that the ones corresponding to the correct answer have magnitude approximately 1, while other coefficients have magnitude 0. This is enabled by the fact that coefficients are positive and negative, and so by mixing them, you can cancel some out.

* When you measure the qubits, the random answer you get is proportional to the coefficients squared. Hence, with high probability you get the right answer.

Where does the speed up come from? When you put the state of N qubits in the linear combination of 2^N basis states, and run it through the problem, that is akin to computing all answers in parallel. Like for factoring, checking all possible divisors to see which ones work. But to extract the answer out in the way described above, you have to do additional processing. This only works for some problems, with the right structure.

Re: Quantum Resistance and the Signal Protocol

#84

Post by andyferris »

vhcr wrote: post #77
andyferris wrote: post #59

Earlier quoted context omitted.

To add to the sibling comment, the reason our classical computers work is because the individual transistor errors in your CPU are basically zero. We do use “error correction” on storage (and do see bit errors creep into data stored on disk and in RAM over time) but not “fault tolerance” on the compute. In fact there is no such thing as fault-tolerant classical compute - the CPU only works if it “perfect” or “near pe…

> Team member Raphael Some of JPL explains: "One way to use faster, consumer CPUs in space is simply to have three times as many CPUs as you need: The three CPUs perform the same calculation and vote on the result. If one of the CPUs makes a radiation-induced error, the other two will still agree, thus winning the vote and giving the correct result." https://science.nasa.gov/science-news/science-at-nasa/2005/1...

Yes. In practice it can be worthwhile doing this in distributed compute. These methods (and those from sibling comments) do rely on the error rate being low, and the data compared being much smaller than the amount of compute (eg bytes in final answer What we can’t do is have a set of CPUs where roughly every 1000th instruction fails and hope that plugging together a bunch of computers together to check each other’s progress will work. The specific issue is that the checking is wrong so frequently that you can’t “win” to solve a problem involving trillions of instructions by adding more computers. The overhead of “checking the checkers” just blows up.

What’s interesting about quantum computation is this is exactly what is proposed - have qubit error rates of (I think) around 0.1% and lots of measurement, classical compute, and feedback control to keep the computation “on track”. The whole scheme relies on the error rate for all of that classical compute step to be negligible.

Re: Quantum Resistance and the Signal Protocol

#85

Post by andyferris »

eigenket wrote: post #35
krastanov wrote: post #23

Earlier quoted context omitted.

Doesn't your argument apply to classical bits too? The more interconnected a classical bit is, the more parasitic coupling it will experience. That used to be an argument used against the feasibility of classical computers in the 40s (until von Neumann published work on fault tolerant classical computing). Both classical and quantum computers (1) can not "scale" without error correction because of analog noise (altho…

Yes. In fact the proofs that quantum error correction works as long as you're below a certain error rate (so-called "threshold theorems" are very, very similar to the same proofs that error correction works in classical computers.

Yes, the same as classical error correction but distinct from classical fault tolerance. It’s fascinating (to me) how these are different!

Re: Quantum Resistance and the Signal Protocol

#86

Post by JBits »

upofadown wrote: post #60
eigenket wrote: post #32

Earlier quoted context omitted.

People have already said here most of what I want to say in this comment, but just to make it as explicit as possible: Essentially the only reason anyone thinks that useful quantum computation is possible is because of things called threshold theorems, which state that as long as the noise in each qubit is less than some small but non-zero error rate you can add more qubits and use quantum error correction to make yo…

>...as long as you're below the threshold rate quantum computers scale well. Last I heard, getting below that threshold was going to take one or two orders of magnitude of noise improvement. That seems unlikely. Say you were at a VC presentation and the company said that they had this really great system and the only thing stopping their immense success was the requirement to reduce the noise by an order or two of ma…

I don't necessarily disagree with what you're saying but multiple research teams do already have error rates below the threshold. It's still early days for the most promising QC platforms, so it's too early to tell if making a QC is possible or not.

Re: Quantum Resistance and the Signal Protocol

#87

Post by anigbrowl »

ccooffee wrote: post #80
m3kw9 wrote: post #79

Doing quantum resistant algorithm right now is straight up posturing and signaling

If your threat model includes someone breaking your encrypted communications X years from now, quantum resistance can be important. Signal markets itself as for reporters and whistleblowers who may have state-level adversaries.

If you're seriously worried about that you're already using disappearing messages, and the maximum retention period is 4 weeks. It's good that they're doing this but it also feels a little bit like hype, while very basic UI problems remain unfixed.

For example, you can do backups or media exports from signal, but the user isn't given any control over where they are stored. If you want to dump them to an SD card in your phone, for example, you'll have to find them in your primary storage and then copy them manually to the SD card. Bizarrely, voice messages are dumped into a 'music' folder even though they're labeled as 'audio' within the Signal UI.

Re: Quantum Resistance and the Signal Protocol

#88

Post by inhumantsar »

Obscurity4340 wrote: post #57
JanisErdmanis wrote: post #18

It is good that they kept the classical crypto along. However, the general tendency towards quantum-resistant cryptography leaves me puzzled. From my perspective as a physics PhD graduate, I firmly believe that a quantum computer capable of breaking public key crypto will never be built. This is because as you add more qubits, there's increased interference between them due to the additional connections required. It'…

Can you explain how qubits are physically implemented in a real-world computer? I just cannot wrap my mind around what they're made of and how they operate in the physical reality.

Disclaimer: No where close to an expert.

My understanding of the more popular superconducting types is that a bit of superconductor is connected up to a junction that allows quantum tunneling of electron pairs. The number of electron pairs that tunnel through the junction determines the state and the state is read out by an exotic electrometer.

As for how the chip itself is made, as far as I know it's a relative standard lithography process except with added superconducting layers.

Re: Quantum Resistance and the Signal Protocol

#90

Post by wolverine876 »

abdullahkhalids wrote: post #83
wolverine876 wrote: post #50

That is very well-written, as someone else pointed out, though this common explanation for laypeople needs work (I'm not blaming Signal's blogger, who wrote it more carefully than most): "Instead of bits as in a classical computer, quantum computers operate on qubits. Rather than 0 or 1, qubits can exist in a superposition of states, in some sense allowing them to be both values at once." 'Instead of beads as in a cl…

You are correct. That is a horrible explanation. And incomplete. * The state of a qubit has two basis states. Arbitrary states are linear combinations (=superposition) of these basis states. Importantly, the coefficients in the linear combination can be positive or negative. * The state of N qubits has 2^N basis states. poly(N) gate can put the state of the N qubits in which each of the 2^N basis states has a non-zer…

Thanks.

> In quantum algorithms, we play with the coefficients.

Is it accurate to say, more simply (simplicity being a high priority here), that 'we play with the probabilities' of collapse to one basis state or to the other - thus skipping the need to explain linear combinations or coefficients?

Post reply on HN