Quantum Bits and Cracking RSA – #16

How will quantum computing change the future of security? What does a quantum computer look like? Mike and Daniel sit down with Lee Barford to get some answers.

Video Version:

Audio version

Last time we looked at “what is quantum computing” and talked about quantum bits and storing data in superstates.

00:40 Lee talks about how to crack RSA and Shor’s algorithm (wikipedia)

00:50 The history of quantum computing (wiki). The first person to propose it was Richard Feynman in the mid 1960s. There was some interest, but it died out.

In the 1990s, Peter Shor published a paper pointing out that if you could build a quantum computer with certain operational properties (machine code instructions), then you could find one factor of a number no matter how long it is.

Then, he outlined another number of things he would need, like a quantum Fast Fourier Transform (FFT).

Much of the security we use every day is both the RSA public key system and the Diffie Hellman Key Exchange algorithm.

HTTPS connections use the Diffie Hellman Key Exchange algorithm. RSA stands for “really secure algorithm” “Rivest, Shamir, and Adelman.”

4:00

RSA only works if the recipients know each other, but Diffie Hellman works for people who don’t know each other but still want to communicate securely. This is useful because it’s not practical for everyone to have their own RSA keys.

5:00

Factoring numbers that are made up of large prime numbers is the basis for RSA. The processing power required for factoring is too large to be practical. People have been working on this for 2500 years.

6:45

Shor’s algorithm is theoretically fast enough to break RSA. If you could build a quantum computer with enough quantum bits and operate with a machine language cycle time that is reasonable (us or ms), then it would be possible to factor thousand bit numbers.

7:50

Famous professors and famous universities have a huge disparity of opinion as to when a quantum computer of that size could be built. Some say 5-10 years, others say up to 50.

8:45

What does a quantum computer look like? It’s easier to describe architecturally than physically. A quantum computer isn’t that much different from a classical computer, it’s simply a co-processor that has to co-exist with current forms of digital electronics.

9:15

If you look at Shor’s algorithm, there are a lot of familiar commands, like “if statements” and “for loops.” But, quantum gates, or quantum assembly language operations, are used in the quantum processor. (more about this)

10:00

Lee thinks that because a quantum gate operates in time instead of space, the term “gate” isn’t a great name.

10:30

What quantum computers exist today? Some have been built, but with only a few quantum bits. The current claim is that people have created quantum computers with up to 21 quantum bits. But, there are potentially a lot of errors and noise. For example, can they actually maintain a proper setup and hold time?

11:50

Continuing the Schrodinger’s Cat analogy…

In reality, if you have a piece of physics that you’ve managed to put into a superimposed quantum state, any disturbance of it (photon impact, etc.) will cause it to collapse into an unwanted state or to collapse too early.

13:15

So, quantum bits have to be highly isolated from their environments. So, in vacuums or extreme cold temperatures (well below 1 degree Kelvin!).

13:45

The research companies making big claims about the quantity of bits are not using solid state quantum computers.

The isolation of a quantum computer can’t be perfect, so there’s a limited lifetime for the computation before the probability of getting an error gets too high.

14:35

Why do we need a superposition of states? Why does it matter when the superimposed states collapse to one state? If it collapses at the wrong time you’ll get a wrong answer. With Shor’s algorithm it’s easy to check for the right answer. And, you get either a remainder of 0 or your don’t. If you get 0, the answer is correct. The computation only has to be reliable enough for you to check the answer.

16:15

If the probability of getting the right answer is high enough, you can afford to get the wrong answer on occasion.

16:50

The probability of the state of a quantum bit isn’t just 50%, so how do you set the probability of the state? It depends on the physical system. You can write to a quantum bit by injecting energy into the system, for example using a very small number of photons as a pulse with a carefully controlled timing and phase.

18:15

Keysight helps quantum computer researchers generate and measure pulses with metrological levels of precision.

The pulses have to be very carefully timed and correlated with sub nanosecond accuracy. You need time synchronization between all the bits at once for it to be useful.

19:40

What is a quantum bit? Two common kinds of quantum bits are

1: Ions trapped in a vacuum with laser trapping . The ions can’t move because they are held in place by standing waves of laser beams. The vacuum can be at room temperature but the ions are low temperature because they can’t move.

2. Josephson junctions in tank circuits (a coil capacitor) produce oscillations at microwave frequencies. Under the right physical conditions, those can be designed to behave like an abstract two state quantum system. You just designate zero and one to different states of the system.

Probabilities are actually a wrong description, it should be complex quantum amplitudes.

23:00

Josephson junctions were talked about in an earlier electrical engineering podcast discussing SI units.

23:40

After working with quantum computing, it’s common to walk away feeling a lot less knowledgeable.

24:30

Stupid question section:

“If you had Schrodinger’s cat in a box, would you look or not?”

Lee says the cat’s wave function really collapsed as it started to warm up so the state has already been determined.