Ryan Peterman

are few.

We don't know many, so we know this.

I mentioned the factor in discrete log.

In the 90s, Aytai and Dwork created another type of step or function from problems on lattices in high dimensions.

I will not describe it, but it's another problem that people refined and got a few more of similar nature.

And it turned out when Peter Shaw discovered this, people immediately tried to solve other problems with quantum computers.

In fact, even today we cannot solve too many other problems with quantum computers.

These are special.

The special thing about them is that somehow you can reduce them to

finding periods in a signal, and periods is like Fourier transform.

A Fourier transform turns out to be in exponential space, but Fourier transform you can do somehow with quantum computers with interference.

The lattice problems and problems related to it, some called learning with arrows and similar, to this day nobody found an efficient quantum algorithm for them.

So there's no even theory.

Forget building random computers.

We don't know how to solve them.

And so what the world is not just complexity theory.

The whole physical world of security systems

And also governments like the NSA is supporting or asking the world to produce assumptions that may be resilient to quantum attacks.

And so this is a huge change.

This is a major change in the interaction between computer scientists and physicists, which grew tremendously since this discovery.