{"id":1577387,"date":"2022-07-11T10:57:51","date_gmt":"2022-07-11T14:57:51","guid":{"rendered":"https:\/\/wordpress-1016567-4521551.cloudwaysapps.com\/?post_type=station&p=1577387"},"modified":"2022-07-16T23:43:18","modified_gmt":"2022-07-17T03:43:18","slug":"quantum-algorithms-conquer-a-new-kind-of-problem","status":"publish","type":"station","link":"https:\/\/platodata.io\/plato-data\/quantum-algorithms-conquer-a-new-kind-of-problem\/","title":{"rendered":"Quantum Algorithms Conquer a New Kind of Problem"},"content":{"rendered":"
<\/div>\n
\n
\n

In 1994, a mathematician figured out how to make a quantum computer do something that no ordinary classical computer could. The work revealed that, in principle, a machine based on the rules of quantum mechanics could efficiently break a large number into its prime factors \u2014 a task so difficult for a classical computer that it forms the basis for much of today\u2019s internet security.<\/p>\n

A surge of optimism followed. Perhaps, researchers thought, we\u2019ll be able to invent quantum algorithms that can solve a huge range of different problems.<\/p>\n

But progress stalled. \u201cIt\u2019s been a bit of a bummer trajectory,\u201d said Ryan O\u2019Donnell<\/a> of Carnegie Mellon University. \u201cPeople were like, \u2018This is amazing, I\u2019m sure we\u2019re going to get all sorts of other amazing algorithms.\u2019 Nope.\u201d Scientists discovered dramatic speedups only for a single, narrow class of problems from within a standard set called NP<\/a>, meaning they had efficiently verifiable solutions \u2014 such as factoring.<\/p>\n

<\/div>\n

That was the case for nearly three decades. Then in April, researchers invented<\/a> a fundamentally new kind of problem that a quantum computer should be able to solve exponentially faster than a classical one. It involves calculating the inputs to a complicated mathematical process, based solely on its jumbled outputs. Whether the problem stands alone or is the first in a new frontier of many others has yet to be determined.<\/p>\n

\u201cThere is a sense of excitement,\u201d said Vinod Vaikuntanathan<\/a>, a computer scientist at the Massachusetts Institute of Technology. \u201cA lot of people are thinking about what else is out there.\u201d<\/p>\n

Computer scientists try to understand what quantum computers do better by studying mathematical models that represent them. Often, they imagine a model of a quantum or classical computer paired with an idealized calculating machine called an oracle. Oracles are like simple mathematical functions or computer programs, taking in an input and spitting out a predetermined output. They might have a random behavior, outputting \u201cyes\u201d if the input falls within a certain random range (say, 12 to 67) and \u201cno\u201d if it doesn\u2019t. Or they might be periodic, so that an input between 1 to 10 returns \u201cyes,\u201d 11 to 20 yields \u201cno,\u201d 21 to 30 produces \u201cyes\u201d again, and so on.<\/p>\n

Let\u2019s say you have one of these periodic oracles and you don\u2019t know the period. All you can do is feed it numbers and see what it outputs. With those constraints, how fast could a computer find the period? In 1993, Daniel Simon, then at the University of Montreal, found that a quantum algorithm could calculate the answer to a closely related problem exponentially faster than any classical algorithm.<\/p>\n

<\/div>\n

The result enabled Simon to determine one of the first hints of where dramatic superiority for quantum computers could be expected. But when he submitted his paper to a leading conference, it was rejected. The paper did, however, interest a junior member of the conference\u2019s program committee \u2014 Peter Shor<\/a>, who at the time was at Bell Laboratories in New Jersey. Shor went on to find that he could adapt Simon\u2019s algorithm to calculate the period of an oracle, if it had one. Then he realized he could adapt the algorithm once again, to solve an equation that behaves similarly to a periodic oracle: the equation that describes factoring, which is periodic.<\/p>\n

Shor\u2019s result was historic. The quantum algorithm he discovered could rapidly reduce gigantic numbers into their constituent prime factors, something that no known classical algorithm can do. In the years that followed, researchers discovered other efficient quantum algorithms. Some of them, like Shor\u2019s algorithm, even provided exponential advantage, but no one could prove a dramatic quantum advantage on any NP problem that wasn\u2019t periodic.<\/p>\n

This dearth of progress led two computer scientists, Scott Aaronson<\/a> of the University of Texas, Austin, and Andris Ambainis<\/a> of the University of Latvia, to make an observation. Proofs of quantum advantage always seemed dependent on oracles that had some kind of nonrandom structure, such as periodicity. In 2009, they conjectured<\/a> that there couldn\u2019t be dramatic speedups on NP problems that were random, or unstructured. No one could find an exception.<\/p>\n

Their conjecture put a bound on the powers of quantum computers. But it said only that there were no dramatic speedups for a specific type of unstructured NP problem \u2014 those with yes or no answers. If a problem involved figuring out more specific, quantitative answers, which is known as a search problem, the conjecture didn\u2019t apply.<\/p>\n<\/div>\n<\/div>\n

\n
\n

With that in mind, researchers Takashi Yamakawa<\/a> of NTT Social Informatics Laboratories and Mark Zhandry<\/a> of NTT Research and Princeton University decided to experiment with a specific search problem, introduced in 2005 by Oded Regev<\/a>.<\/p>\n

Imagine a set of weather vanes that are all pointing in the same direction. Give each of them a measured shove, then let a gusty wind influence their direction. Regev wanted to determine, based on their final directions, where they all pointed initially. Problems like this came to be called \u201clearning with errors,\u201d because the shove and the wind act like a source of random error on the original direction. There is evidence that it is hard to solve for both classical and quantum algorithms.<\/p>\n

Yamakawa and Zhandry tweaked the setup. They modified the strength of those starting shoves, making them more predictable. They also caused the wind to be determined by a random oracle so that it was even more random in certain cases but completely dormant in others.<\/p>\n

With these modifications, the researchers discovered that a quantum algorithm could efficiently find the initial direction. They also proved that any classical algorithm must be slower by an exponential factor. Like Shor, they then adapted their algorithm to solve a real-world version of the problem, which replaces the oracle with an actual mathematical equation.<\/p>\n

Computer scientists are still working to understand and build on the problem. Vaikuntanathan compares it to a different one that arises when doing data compression: When information is being squeezed down, two bits can accidentally be squeezed into the same place, overwriting them. The problem of predicting those collisions in advance, so that you can avoid them, bears some resemblance. \u201cThat\u2019s a class of problems which basically look like this,\u201d he said. \u201cMaybe these problems can be solved quantumly.\u201d<\/p>\n

There were hopes that an unstructured problem like the new one might be solvable even on today\u2019s fledgling versions of quantum computers, thereby providing a means to test them. The thinking was that unstructured problems might take fewer resources to program, or be less sensitive to noise, since they are already random. But so far, the new problem still appears too advanced for existing quantum computers to solve. \u201cIt\u2019s a weird problem. I had not thought to define it,\u201d said Aaronson. \u201cBut in retrospect, it has some very nice features.\u201d<\/p>\n

The result provides the first example of dramatic quantum advantage on an unstructured NP problem. Could there be many other problems that the quantum world changes from practically unsolvable to solvable? There is now more reason to think so.<\/p>\n

\u201cIt\u2019s somewhat overturned our beliefs about what kinds of problems quantum computers could be good at,\u201d said O\u2019Donnell.<\/p>\n<\/div>\n<\/div>\n","protected":false},"author":1,"featured_media":1577389,"template":"","meta":{"_eb_attr":"","type":"","auto_type":false,"post":"","stream":"","stream_url":"","waveform_data":[],"duration":0,"start":0,"end":0,"bpm":0,"downloadable":false,"download_url":"","purchase_title":"","purchase_url":"","post-count-all":0,"like_count":0,"download_count":0,"editor_note":"","copyright":"","captions":[],"sources":[]},"genre":[10730],"station_tag":[15764,15668,3884,14557,7013,4247,15684,15666,7457,14558,8453,15312,9642,14556,15678,5057,15670,6579,15672,14555],"artist":[15728],"mood":[],"activity":[],"_links":{"self":[{"href":"https:\/\/platodata.io\/wp-json\/wp\/v2\/station\/1577387"}],"collection":[{"href":"https:\/\/platodata.io\/wp-json\/wp\/v2\/station"}],"about":[{"href":"https:\/\/platodata.io\/wp-json\/wp\/v2\/types\/station"}],"author":[{"embeddable":true,"href":"https:\/\/platodata.io\/wp-json\/wp\/v2\/users\/1"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/platodata.io\/wp-json\/wp\/v2\/media\/1577389"}],"wp:attachment":[{"href":"https:\/\/platodata.io\/wp-json\/wp\/v2\/media?parent=1577387"}],"wp:term":[{"taxonomy":"genre","embeddable":true,"href":"https:\/\/platodata.io\/wp-json\/wp\/v2\/genre?post=1577387"},{"taxonomy":"station_tag","embeddable":true,"href":"https:\/\/platodata.io\/wp-json\/wp\/v2\/station_tag?post=1577387"},{"taxonomy":"artist","embeddable":true,"href":"https:\/\/platodata.io\/wp-json\/wp\/v2\/artist?post=1577387"},{"taxonomy":"mood","embeddable":true,"href":"https:\/\/platodata.io\/wp-json\/wp\/v2\/mood?post=1577387"},{"taxonomy":"activity","embeddable":true,"href":"https:\/\/platodata.io\/wp-json\/wp\/v2\/activity?post=1577387"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}