Quantum algorithms solve new challenges

Quantum computers can tackle a new sort of issue faster than classical ones.

In 1994, a mathematician figured out how to make a quantum computer do something that a regular classical computer couldn't. The work showed that, in theory, a machine based on the rules of quantum mechanics could break a large number into its prime factors quickly and easily. This is a task that is so hard for a classical computer to do that it is the basis for a lot of internet security today.

Then there was a rush of hope. Researchers thought that maybe we could come up with quantum algorithms that could solve a wide range of problems.

But progress stalled. Ryan O'Donnell of Carnegie Mellon University said, "It's been a bit of a sad story." "People were like, 'This is great! I'm sure we'll get lots of other great algorithms.'" Nope.” Scientists only found dramatic speedups for a small group of problems in a standard set called NP. These problems had solutions that could be easily checked, like factoring.

For almost 30 years, this was the case. Then, in April, researchers came up with a completely new kind of problem that a quantum computer should be able to solve exponentially faster than a classical one. It requires figuring out what goes into a complicated math process by looking at its jumbled results. It's not clear yet if the problem stands on its own or if it's the first of many more to come.

Vinod Vaikuntanathan, a computer scientist at the Massachusetts Institute of Technology, said, "There is a sense of excitement." "A lot of people are wondering what else there is."

By looking at mathematical models that show what quantum computers can do, computer scientists try to learn more about what they can do. Most of the time, they think of a model of a quantum or classical computer paired with an oracle, which is an idealised computer. Oracles are like simple mathematical functions or computer programmes that take an input and give out a predetermined output. They might act in a random way, saying "yes" if the input number is between, say, 12 and 67, and "no" if it isn't. Or, they could be set up so that a number between 1 and 10 means "yes," a number between 11 and 20 means "no," a number between 21 and 30 means "yes," and so on.

Let's say you have one of these periodic oracles, but you don't know the period. You can only put numbers into it and see what it comes up with. How fast could a computer find the period if it had to work with those rules? Daniel Simon, who was at the University of Montreal at the time, discovered in 1993 that a quantum algorithm could solve a closely related problem exponentially faster than any classical algorithm.

Because of this, Simon was able to get one of the first hints about where quantum computers might be dramatically better. But when he sent it to a major conference, the paper was turned down. Peter Shor, who was working at Bell Laboratories in New Jersey at the time and was a younger member of the conference's programme committee, was interested in the paper. Shor then found that, if an oracle had a period, he could use Simon's algorithm to figure it out. Then he realised he could change the algorithm again to solve an equation that works like a periodic oracle. This equation is the one that describes factoring, which happens over and over again.

The result Shor got was a big deal. The quantum algorithm he found could quickly break down huge numbers into their prime factors, which is something no known classical algorithm can do. Researchers found other good quantum algorithms in the years that followed. Some of them, like Shor's algorithm, even gave an exponential advantage, but no one could prove a big quantum advantage on any NP problem that wasn't periodic.

Two computer scientists, Scott Aaronson of the University of Texas at Austin and Andris Ambainis of the University of Latvia, noticed that there wasn't much progress being made. Proofs of quantum advantage have always seemed to depend on oracles that had some kind of structure that wasn't random, like being able to be used over and over again. In 2009, they thought that random or unstructured NP problems couldn't get much faster in a big way. No one was able to find a way out.

Their guess put a limit on how powerful quantum computers could be. But it only said that there were no big speedups for a certain kind of unstructured NP problem: those with yes or no answers. The conjecture didn't work for "search problems," which are problems where you have to find more specific answers with numbers.

With this in mind, Takashi Yamakawa of NTT Social Informatics Laboratories and Mark Zhandry of NTT Research and Princeton University decided to try out a search problem that Oded Regev came up with in 2005.

Imagine a group of weather vanes that are all pointing in the same direction. Give each one a gentle push, and then let a gusty wind change where they go. Regev wanted to know, based on where they all ended up pointing, where they all pointed at first. People started calling problems like this "learning with errors" because the push and the wind make the original direction change randomly. There is evidence that both classical and quantum algorithms are hard to solve.

The setup was changed by Yamakawa and Zhandry. They changed how hard those first shoves were, which made them easier to predict. They also made the wind depend on a random oracle, so that sometimes it was even more random and sometimes it was completely still.

With these changes, the researchers found that a quantum algorithm could find the original direction well. They also showed that any traditional algorithm must be slower by a factor that grows with time. Then, like Shor, they changed their algorithm to solve a real-world version of the problem in which the oracle is replaced by a real math equation.

Computer scientists are still trying to figure out what's going on and how to fix it. Vaikuntanathan compares it to another problem that comes up when compressing data: When information is being squeezed down, it is possible for two bits to end up in the same place and be overwritten. It's a bit like trying to figure out how to predict those collisions in advance so you can avoid them. He said, "That's a group of problems that mostly look like this." "These problems might be able to be solved in a quantum way."

There was hope that quantum computers, which are still in their early stages, might be able to solve a problem like the new one, which would be a good way to test them. The idea was that since unstructured problems are already random, it might take less time to programme them or they might be less affected by noise. But so far, it looks like the new problem is still too hard for quantum computers to solve. "It's a strange issue. "I didn't think to define it," Aaronson said. "But looking back, it does have some very nice things about it."

The result shows for the first time that a quantum advantage can make a big difference on an unstructured NP problem. Could there be a lot of other problems that the quantum world makes go from being almost impossible to solve to being easy to solve? Now there's even more reason to believe that.

"It's changed some of our ideas about what kinds of problems quantum computers could solve well," O'Donnell said.