wp-plugin-hostgator domain was triggered too early. This is usually an indicator for some code in the plugin or theme running too early. Translations should be loaded at the init action or later. Please see Debugging in WordPress for more information. (This message was added in version 6.7.0.) in /home4/scienrds/scienceandnerds/wp-includes/functions.php on line 6114ol-scrapes domain was triggered too early. This is usually an indicator for some code in the plugin or theme running too early. Translations should be loaded at the init action or later. Please see Debugging in WordPress for more information. (This message was added in version 6.7.0.) in /home4/scienrds/scienceandnerds/wp-includes/functions.php on line 6114Source:https:\/\/www.quantamagazine.org\/thirty-years-later-a-speed-boost-for-quantum-factoring-20231017\/#comments<\/a><\/br> Quantum computers derive their power from the peculiar way they process information. Classical computers use bits, each of which must always be in one of two states, labeled 0 and 1. Quantum bits, or \u201cqubits,\u201d can additionally be in combinations of their 0 and 1 states \u2014 a phenomenon called superposition. It\u2019s also possible to coax multiple qubits into a collective superposition state: A two-qubit superposition has four components that can perform different computations simultaneously, and the number of such components grows exponentially as the number of qubits increases. That allows quantum computers to effectively perform exponentially many different computations in parallel.<\/p>\n But there\u2019s a catch<\/a>: Reading the result of a computation performed in superposition only reveals the answer to the part computed by one random component. To reap the benefits of computing in superposition, you must somehow map the end result onto a simpler state where it\u2019s safe to read the result. That\u2019s not possible in most cases, and at first nobody knew how to make it work for any problem. \u201cThere were very few people who even had the courage to think about quantum computations,\u201d Regev said.<\/p>\n Then in 1994, Shor read a paper<\/a> by the computer scientist Daniel Simon that showed how to exploit quantum superposition to solve a contrived problem. Shor figured out how to extend Simon\u2019s result to a more general and practical problem called period finding. A mathematical function is said to be periodic when its output cycles repeatedly through the same values as the input increases; the length of a single cycle is known as the function\u2019s period.<\/p>\n To find the period of a given function using a quantum computer, start by setting up a very large superposition in which each component computes the function\u2019s output for a different input. Then use Shor\u2019s method to convert that large superposition into a simpler state and read the result. At that point, a classical computer can take over and finish the calculation quickly. Overall, Shor\u2019s period-finding algorithm runs exponentially faster than any classical alternative because it computes different outputs of the periodic function simultaneously using superposition.<\/p>\n As Shor looked for applications for his quantum period-finding algorithm, he rediscovered a previously known but obscure mathematical theorem: For every number, there exists a periodic function whose periods are related to the number\u2019s prime factors. So if there\u2019s a number you want to factor, you can compute the corresponding function and then solve the problem using period finding \u2014 \u201cexactly what quantum computers are so good at,\u201d Regev said.<\/p>\n On a classical computer, this would be an agonizingly slow way to factor a large number \u2014 slower even than trying every possible factor. But Shor\u2019s method speeds up the process exponentially, making period finding an ideal way to construct a fast quantum factoring algorithm.<\/p>\n Shor\u2019s algorithm was one of a few key early results that transformed quantum computing from an obscure subfield of theoretical computer science to the juggernaut it is today. But putting the algorithm into practice is a daunting task, because quantum computers are notoriously susceptible to errors: In addition to the qubits required to perform their computations, they need many others doing extra work<\/a> to keep them from failing. A recent paper<\/a> by Eker\u00e5 and the Google researcher Craig Gidney<\/a> estimates that using Shor\u2019s algorithm to factor a security-standard 2,048-bit number (about 600 digits long) would require a quantum computer with 20 million qubits. Today\u2019s state-of-the-art machines have at most a few hundred.<\/p>\n That\u2019s why some critical internet protocols still rely on how hard it is to factor large numbers, but researchers don\u2019t want to get too complacent. Theoretical<\/a> and technological innovations could bring the required qubit count down further, and there\u2019s no proof that Shor\u2019s algorithm is optimal \u2014 there might be a better quantum factoring algorithm out there that nobody\u2019s discovered.<\/p>\n If so, Regev said, \u201cwe should know as early as possible, before it\u2019s too late.\u201d<\/p>\n Regev began his academic career in the late 1990s, when cryptographers were searching for a new form of public-key cryptography that wasn\u2019t vulnerable to Shor\u2019s algorithm. The most promising approach, called lattice-based cryptography<\/a>, relies on the apparent difficulty of computational problems involving high-dimensional arrays of points, or lattices. One such problem is akin to the task of locating the tree closest to a random point in a forest.<\/p>\n \u201cIf it\u2019s a hundred-dimensional forest, then that\u2019s much more complicated than if it\u2019s a two-dimensional forest,\u201d said Greg Kuperberg<\/a>, a mathematician at the University of California, Davis.<\/p>\n Regev began studying lattice-based cryptography as a postdoc, initially as an attacker \u2014 he wanted to stress-test the new approach by finding weaknesses that a quantum computer could exploit. But he couldn\u2019t make any progress, and he soon wondered if there was a deeper reason for that. In 2005, he found a way to parlay those failed attacks into a form of lattice-based cryptography<\/a> superior to all other variants.<\/p>\n \u201cOded is absolutely brilliant with lattices,\u201d Kuperberg said.<\/p>\n Over the years, as Regev taught Shor\u2019s algorithm to successive generations of students, he found himself wondering whether the techniques he\u2019d used for attacking lattice-based cryptography might actually prove useful in factoring algorithms. That\u2019s because one step in the final, classical stage of Shor\u2019s algorithm amounts to finding the nearest point in a one-dimensional lattice. That one-dimensional problem is trivially easy, but the resemblance to the analogous problem in hundreds of dimensions whose hardness underpins lattice-based cryptography was unmistakable.<\/p>\n \u201cIf you\u2019re someone that does lattices like me, you think, \u2018OK, there\u2019s some lattice going on here,\u2019\u201d Regev said. \u201cBut it wasn\u2019t clear to me how to make use of that.\u201d For years he toyed with other ideas for new quantum factoring algorithms, but he never got anywhere. Then last winter he returned to the problem and resolved to pin down that tantalizing connection between factoring and lattice-based cryptography. This time, he found success.<\/p>\n Regev knew he needed to start by generalizing the periodic function at the heart of Shor\u2019s algorithm from one dimension to many dimensions. In Shor\u2019s algorithm, that function involves repeatedly multiplying a random number, dubbed g<\/em>, with itself. But the period of this function \u2014 the number of times you must multiply by g<\/em> before the output of the function starts repeating \u2014 can be very large, and that means that a quantum computer must multiply large numbers in some components of the superposition it uses to compute the periodic function. Those large multiplications are the most computationally costly part of Shor\u2019s algorithm.<\/p>\n The analogous two-dimensional function instead uses a pair of numbers, g<\/em>1<\/sub> and g<\/em>2<\/sub>. It involves multiplying g<\/em>1<\/sub> with itself many times and then repeatedly multiplying by g<\/em>2<\/sub>. The period of this function is also two-dimensional \u2014 it\u2019s defined by the number of g<\/em>1<\/sub> multiplications and g<\/em>2<\/sub> multiplications that together make the function\u2019s output start repeating. There are many different combinations of g<\/em>1<\/sub> and g<\/em>2<\/sub> multiplications that will do the trick.<\/p>\n Regev worked through the technical details to generalize the algorithm to an arbitrary number of dimensions, not just two, but his initial results weren\u2019t encouraging. To compute the periodic function in many dimensions, the quantum computer would still have to multiply many numbers together. Each number wouldn\u2019t need to get multiplied as many times as in the one-dimensional case, but there were more distinct numbers to multiply. The whole thing seemed to be a wash.<\/p>\n \u201cYou think, \u2018Great, I just did everything in high dimensions, and it\u2019s exactly the same running time as Shor\u2019s,\u2019\u201d Regev said. \u201cI was stuck with that for a while.\u201d Then he realized he could get around the problem by changing the order of the multiplications. Instead of repeatedly tacking numbers onto a single product that would grow progressively larger over the course of the quantum computation, he started with pairs of small numbers, multiplied the resulting products together, and proceeded upward. The total number of multiplications didn\u2019t change much, but now nearly all of them involve relatively small numbers, making the calculation faster.<\/p>\n \u201cThat makes all the difference in the world,\u201d said Vinod Vaikuntanathan<\/a>, a cryptographer at MIT.<\/p>\n At first, it looked as though Regev had just replaced one problem with another. He\u2019d sped up the quantum computation of the periodic function by increasing the number of dimensions, but the subsequent classical computation required to extract the period was now similar to locating the nearest lattice point in a high-dimensional space \u2014 a task widely believed to be hard. The analogy to lattice-based cryptography that motivated his new approach seemed to doom it to failure.<\/p>\n One cold morning in March before a trip to a seminar at Princeton University, Regev found himself waiting for the colleague he was carpooling with. \u201cI arrived early, and he was late to pick up the car,\u201d he said. While he was sitting around waiting, the last piece of the puzzle suddenly came to him. \u201cThat\u2019s the moment when things fell into place, but it was baking for a while.\u201d<\/p>\n It all came down to the right number of dimensions. When the lattice dimension was too low, his algorithm couldn\u2019t take full advantage of the speedup from multiplying smaller numbers. When it was too high, the quantum computation was fast, but the classical part required solving a prohibitively hard lattice problem. Regev had known from the beginning that to have any hope of success, he would have to work somewhere in between, but it wasn\u2019t clear whether a sweet spot existed. That morning in March, he realized how he could tweak the details of the algorithm to make it run quickly in a few dozen dimensions.<\/p>\n The improvement was profound. The number of elementary logical steps in the quantum part of Regev\u2019s algorithm is proportional to n<\/em>1.5<\/sup> when factoring an n<\/em>-bit number, rather than n<\/em>2<\/sup> as in Shor\u2019s algorithm. The algorithm repeats that quantum part a few dozen times and combines the results to map out a high-dimensional lattice, from which it can deduce the period and factor the number. So the algorithm as a whole may not run faster, but speeding up the quantum part by reducing the number of required steps could make it easier to put it into practice.<\/p>\n Of course, the time it takes to run a quantum algorithm is just one of several considerations. Equally important is the number of qubits required, which is analogous to the memory required to store intermediate values during an ordinary classical computation. The number of qubits that Shor\u2019s algorithm requires to factor an n<\/em>-bit number is proportional to n<\/em>, while Regev\u2019s algorithm in its original form requires a number of qubits proportional to n<\/em>1.5<\/sup> \u2014 a big difference for 2,048-bit numbers.<\/p>\n In classical computing, speed is usually a more important consideration than memory, because classical bits are extremely robust: You can save a file on your computer and not worry about it randomly changing when you open it again later. Quantum computing researchers aren\u2019t always so lucky.<\/p>\n \u201cOur qubits are constantly trying to fall apart, and we\u2019re trying to stop them from falling apart,\u201d Gidney said. \u201cIt\u2019s like you\u2019re trying to write in the sand and the wind is blowing it away.\u201d That means the extra qubits required by Regev\u2019s algorithm could be a major drawback.<\/p>\n But Regev\u2019s paper isn\u2019t the end of the story. Two weeks ago, Vaikuntanathan and his graduate student Seyoon Ragavan found a way to reduce the algorithm\u2019s memory use. Their variant<\/a> of Regev\u2019s algorithm, like Shor\u2019s original algorithm, requires a number of qubits proportional to n<\/em> rather than n<\/em>1.5<\/sup>. Eker\u00e5 wrote in an email that the work \u201cbrings us a lot closer to an implementation that would be more efficient in practice.\u201d<\/p>\n The broader lesson of Regev\u2019s new algorithm, beyond the implications for factoring, is that quantum computing researchers should always be open to surprises, even in problems that have been studied for decades.<\/p>\n \u201cThis variant of my algorithm was undiscovered for 30 years and came out of the blue,\u201d Shor said. \u201cThere\u2019s still probably lots of other quantum algorithms to be found.\u201d<\/p>\n Editor\u2019s note: Oded Regev receives funding from the <\/em>Simons Foundation<\/em><\/a>, which also funds this editorially independent magazine. Simons Foundation funding decisions have no influence on our coverage. More details are <\/em>available here<\/em><\/a>.<\/em><\/p>\n Quanta is conducting a series of surveys to better serve our audience. Take our\u00a0<\/i>computer science reader survey<\/a><\/i>\u00a0and you will be entered to win free <\/i>Quanta merch.<\/i><\/p>\n<\/div>\n <\/br><\/br><\/br><\/p>\n
\nThirty Years Later, a Speed Boost for Quantum Factoring<\/br>
\n2023-10-18 21:58:15<\/br><\/p>\nFinding Factors
<\/strong><\/h2>\nLost in the Trees <\/strong><\/h2>\n
Extra Dimensions<\/strong><\/h2>\n
Writing in the Sand<\/strong><\/h2>\n