Welcome to Quantum Magazine's podcast.

Each episode we bring you stories about developments in science and mathematics.

I'm Susan Vallett.

Imagine someone came along and told you that they had an oracle,

and that this oracle could reveal the deep secrets of the universe.

Well, you might be intrigued.

You'd probably have a hard time trusting it, right?

You'd want some way to verify that what the oracle told you was true. This is the heart of one of the central problems in computer science. Some problems are too hard

to solve in any reasonable amount of time, but their solutions are easy to check. Given

that, computer scientists want to know how complicated can a problem be while

still having a solution that can be verified? Turns out, the answer is almost unimaginably

complicated.

In a paper released last year, two computer scientists dramatically increased the number of problems

that fall into the hard-to-solve but easy to verify category.

They describe a method that makes it possible to check answers to problems of almost

incomprehensible complexity.

The research applies to quantum computers. Those are computers that perform calculations

according to the non-intuitive rules of quantum mechanics. Quantum computers barely exist now,

but they have the potential to revolutionize computing in the future.

The new work essentially gives us leverage over that powerful Oracle. Even if the Oracle promises

to tell you answers to problems that are far beyond your own ability to solve, there's still a way to

make sure the Oracle is telling the truth. When a problem is hard to solve, there's still a way to make sure the Oracle is telling the truth.

...