(Press-News.org) CAMBRIDGE, MA — The most recent email you sent was likely encrypted using a tried-and-true method that relies on the idea that even the fastest computer would be unable to efficiently break a gigantic number into factors.
Quantum computers, on the other hand, promise to rapidly crack complex cryptographic systems that a classical computer might never be able to unravel. This promise is based on a quantum factoring algorithm proposed in 1994 by Peter Shor, who is now a professor at MIT.
But while researchers have taken great strides in the last 30 years, scientists have yet to build a quantum computer powerful enough to run Shor’s algorithm.
As some researchers work to build larger quantum computers, others have been trying to improve Shor’s algorithm so it could run on a smaller quantum circuit. About a year ago, New York University computer scientist Oded Regev proposed a major theoretical improvement. His algorithm could run faster, but the circuit would require more memory.
Building off those results, MIT researchers have proposed a best-of-both-worlds approach that combines the speed of Regev’s algorithm with the memory-efficiency of Shor’s. This new algorithm is as fast as Regev’s, requires fewer quantum building blocks known as qubits, and has a higher tolerance to quantum noise, which could make it more feasible to implement in practice.
In the long run, this new algorithm could inform the development of novel encryption methods that can withstand the code-breaking power of quantum computers.
“If large-scale quantum computers ever get built, then factoring is toast and we have to find something else to use for cryptography. But how real is this threat? Can we make quantum factoring practical? Our work could potentially bring us one step closer to a practical implementation,” says Vinod Vaikuntanathan, the Ford Foundation Professor of Engineering, a member of the Computer Science and Artificial Intelligence Laboratory (CSAIL), and senior author of a paper describing the algorithm.
The paper’s lead author is Seyoon Ragavan, a graduate student in the MIT Department of Electrical Engineering and Computer Science. The research will be presented at the 2024 International Cryptology Conference.
Cracking cryptography
To securely transmit messages over the internet, service providers like email clients and messaging apps typically rely on RSA, an encryption scheme invented by MIT researchers Ron Rivest, Adi Shamir, and Leonard Adleman in the 1970s (hence the name “RSA”). The system is based on the idea that factoring a 2,048-bit integer (a number with 617 digits) is too hard for a computer to do in a reasonable amount of time.
That idea was flipped on its head in 1994 when Shor, then working at Bell Labs, introduced an algorithm which proved that a quantum computer could factor quickly enough to break RSA cryptography.
“That was a turning point. But in 1994, nobody knew how to build a large enough quantum computer. And we’re still pretty far from there. Some people wonder if they will ever be built,” says Vaikuntanathan.
It is estimated that a quantum computer would need about 20 million qubits to run Shor’s algorithm. Right now, the largest quantum computers have around 1,100 qubits.
A quantum computer performs computations using quantum circuits, just like a classical computer uses classical circuits. Each quantum circuit is composed of a series of operations known as quantum gates. These quantum gates utilize qubits, which are the smallest building blocks of a quantum computer, to perform calculations.
But quantum gates introduce noise, so having fewer gates would improve a machine’s performance. Researchers have been striving to enhance Shor’s algorithm so it could be run on a smaller circuit with fewer quantum gates.
That is precisely what Regev did with the circuit he proposed a year ago.
“That was big news because it was the first real improvement to Shor’s circuit from 1994,” Vaikuntanathan says.
The quantum circuit Shor proposed has a size proportional to the square of the number being factored. That means if one were to factor a 2,048-bit integer, the circuit would need millions of gates.
Regev’s circuit requires significantly fewer quantum gates, but it needs many more qubits to provide enough memory. This presents a new problem.
“In a sense, some types of qubits are like apples or oranges. If you keep them around, they decay over time. You want to minimize the number of qubits you need to keep around,” explains Vaikuntanathan.
He heard Regev speak about his results at a workshop last August. At the end of his talk, Regev posed a question: Could someone improve his circuit so it needs fewer qubits? Vaikuntanathan and Ragavan took up that question.
Quantum ping-pong
To factor a very large number, a quantum circuit would need to run many times, performing operations that involve computing powers, like 2 to the power of 100.
But computing such large powers is costly and difficult to perform on a quantum computer, since quantum computers can only perform reversible operations. Squaring a number is not a reversible operation, so each time a number is squared, more quantum memory must be added to compute the next square.
The MIT researchers found a clever way to compute exponents using a series of Fibonacci numbers that requires simple multiplication, which is reversible, rather than squaring. Their method needs just two quantum memory units to compute any exponent.
“It is kind of like a ping-pong game, where we start with a number and then bounce back and forth, multiplying between two quantum memory registers,” Vaikuntanathan adds.
They also tackled the challenge of error correction. The circuits proposed by Shor and Regev require every quantum operation to be correct for their algorithm to work, Vaikuntanathan says. But error-free quantum gates would be infeasible on a real machine.
They overcame this problem using a technique to filter out corrupt results and only process the right ones.
The end-result is a circuit that is significantly more memory-efficient. Plus, their error correction technique would make the algorithm more practical to deploy.
“The authors resolve the two most important bottlenecks in the earlier quantum factoring algorithm. Although still not immediately practical, their work brings quantum factoring algorithms closer to reality,” adds Regev.
In the future, the researchers hope to make their algorithm even more efficient and, someday, use it to test factoring on a real quantum circuit.
“The elephant-in-the-room question after this work is: Does it actually bring us closer to breaking RSA cryptography? That is not clear just yet; these improvements currently only kick in when the integers are much larger than 2,048 bits. Can we push this algorithm and make it more feasible than Shor’s even for 2,048-bit integers?” says Ragavan.
###
This work is funded by an Akamai Presidential Fellowship, the U.S. Defense Advanced Research Projects Agency, the National Science Foundation, the MIT-IBM Watson AI Lab, a Thornton Family Faculty Research Innovation Fellowship, and a Simons Investigator Award.
END
Toward a code-breaking quantum computer
Building on a landmark algorithm, researchers propose a way to make a smaller and more noise-tolerant quantum factoring circuit for cryptography
2024-08-23
ELSE PRESS RELEASES FROM THIS DATE:
New imaging device improves ear disease diagnosis
2024-08-23
In the realm of ear health, accurate diagnosis is crucial for effective treatment, especially when dealing with conditions that can lead to hearing loss. Traditionally, otolaryngologists have relied on the otoscope, a device that provides a limited view of the eardrum’s surface. This conventional tool, while useful, has its limitations, particularly when the tympanic membrane (TM) is opaque due to disease.
Enter a groundbreaking advancement from the University of Southern California's Caruso Department of Otolaryngology: a portable OCT otoscope that integrates optical coherence tomography (OCT) with ...
Langbeinites show talents as 3D quantum spin liquids
2024-08-23
A 3D quantum spin liquid has been discovered in the vicinity of a member of the langbeinite family. The material's specific crystalline structure and the resulting magnetic interactions induce an unusual behaviour that can be traced back to an island of liquidity. An international team has made this discovery with experiments at the ISIS neutron source and theoretical modelling on a nickel-langbeinite sample.
When spins in a crystal lattice cannot align to reach a minimum energy together, this is called magnetic frustration. ...
VA funds IU School of Medicine research projects relevant to veterans’ health
2024-08-23
INDIANAPOLIS – Indiana University School of Medicine researchers have cumulatively been awarded nearly $4 million in grant funding through the U.S. Department of Veterans Affairs' Merit Review Award and Career Development programs to support research on diabetes, skin inflammation, cancer and aging.
The Merit Review Award Program supports investigator-initiated research conducted by eligible VA investigators at either VA medical centers or approved sites. This program serves as the VA's primary method for funding basic, preclinical, ...
Researchers identify effective materials for protecting astronauts from harmful cosmic radiation on Mars
2024-08-23
Abu Dhabi, August 23, 2024: Researchers have identified specific materials, including certain plastics, rubber, and synthetic fibers, as well as Martian soil (regolith), which would effectively protect astronauts by blocking harmful space radiation on Mars. These findings could inform the design of protective habitats and spacesuits, making long-duration Mars missions more feasible. Because Mars lacks Earth’s thick atmosphere and magnetic field, astronauts exploring the planet would be exposed to dangerous levels of radiation.
Dimitra Atri, Investigator, ...
People seen as wise share these characteristics, according to a new study
2024-08-23
What makes someone seem wise? People view wisdom through the lens of applying knowledge and thinking logically as well as considering others’ feelings and perceptions, finds a new study led by University of Waterloo researchers who looked at perceptions of wisdom across 12 countries and five continents.
Researchers examined the underlying principles guiding who we perceive as wise in political leadership, science, and daily life. Across different cultures, participants’ judgements converged on two dimensions: reflective orientation and ...
Activated bamboo charcoal’s slow-release properties for enhanced anti-acne formulations containing bamboo vinegar
2024-08-23
Bamboo vinegar is a concentrated liquid obtained from bamboo under high temperature and anaerobic conditions. It contains more than 200 organic components, including organic acids, phenols, ketones, alcohols, and esters, among which acetic acid is the main component. Although bamboo vinegar has been approved by the China Food and Drug Administration as a cosmetic raw material, commercially available bamboo vinegar often contains impurities whose efficacy is not clear, and phenolic compounds and aromatic hydrocarbons ...
When is the best time of day for cancer treatment?
2024-08-23
How effective medications are depends on various factors, including the time of day when they are administered. Why? Because our bodies don’t always function exactly the same. Instead, they follow the cycle set by their internal clock, otherwise known as circadian rhythm. But since each person’s circadian rhythm is different and depends on a number of different factors, it is difficult to tailor medication schedules to an individual patient’s body clock. Researchers at Charité – Universitätsmedizin Berlin have now developed a method for determining the optimum time of cancer treatment based on certain breast cancer ...
Rates of obesity-related cancer are rising sharply in young Chinese people
2024-08-23
Obesity-related cancer rates in China were rising at an alarming 3.6% every year between 2007 and 2021 while non-obesity-related cancers remained stable, according to the first comprehensive study published August 22 in the Cell Press journal Med. The increase is particularly pronounced among young people, highlighting the urgent need for better public health policies to address China’s growing overweight and obesity rates.
“If we don’t drastically change the obesity epidemic, the rates of cancer associated with obesity will inevitably continue to rise,” says Jin-Kui Yang, the paper’s corresponding author and an endocrinologist ...
Neighborhood-level disparities in hypertension prevalence and treatment among middle-aged adults
2024-08-23
About The Study: Researchers found corresponding increases in hypertension prevalence as neighborhood disadvantage and the percentage of Black patients residing in a neighborhood increased in this cross-sectional study. A higher burden of midlife hypertension was identified in Black adults compared with other racial and ethnic groups that persisted across levels of socioeconomic disadvantage. This study also found that living in socioeconomically disadvantaged neighborhoods was associated with higher hypertension ...
Strength training activates cellular waste disposal
2024-08-23
The elimination of damaged cell components is essential for the maintenance of the body’s tissues and organs. An international research team led by the University of Bonn has made significant findings on mechanisms for the clearing of cellular wastes, showing that strength training activates such mechanisms. The findings could form the basis for new therapies for heart failure and nerve diseases, and even afford benefits for manned space missions. A corresponding article has been published in the latest issue of the journal Current Biology. EMBARGOED: Do not publish until 5 pm CEST ...
LAST 30 PRESS RELEASES:
Reality check: making indoor smartphone-based augmented reality work
Overthinking what you said? It’s your ‘lizard brain’ talking to newer, advanced parts of your brain
Black men — including transit workers — are targets for aggression on public transportation, study shows
Troubling spike in severe pregnancy-related complications for all ages in Illinois
Alcohol use identified by UTHealth Houston researchers as most common predictor of escalated cannabis vaping among youths in Texas
Need a landing pad for helicopter parenting? Frame tasks as learning
New MUSC Hollings Cancer Center research shows how Golgi stress affects T-cells' tumor-fighting ability
#16to365: New resources for year-round activism to end gender-based violence and strengthen bodily autonomy for all
Earliest fish-trapping facility in Central America discovered in Maya lowlands
São Paulo to host School on Disordered Systems
New insights into sleep uncover key mechanisms related to cognitive function
USC announces strategic collaboration with Autobahn Labs to accelerate drug discovery
Detroit health professionals urge the community to act and address the dangers of antimicrobial resistance
3D-printing advance mitigates three defects simultaneously for failure-free metal parts
Ancient hot water on Mars points to habitable past: Curtin study
In Patagonia, more snow could protect glaciers from melt — but only if we curb greenhouse gas emissions soon
Simplicity is key to understanding and achieving goals
Caste differentiation in ants
Nutrition that aligns with guidelines during pregnancy may be associated with better infant growth outcomes, NIH study finds
New technology points to unexpected uses for snoRNA
Racial and ethnic variation in survival in early-onset colorectal cancer
Disparities by race and urbanicity in online health care facility reviews
Exploring factors affecting workers' acquisition of exercise habits using machine learning approaches
Nano-patterned copper oxide sensor for ultra-low hydrogen detection
Maintaining bridge safer; Digital sensing-based monitoring system
A novel approach for the composition design of high-entropy fluorite oxides with low thermal conductivity
A groundbreaking new approach to treating chronic abdominal pain
ECOG-ACRIN appoints seven researchers to scientific committee leadership positions
New model of neuronal circuit provides insight on eye movement
Cooking up a breakthrough: Penn engineers refine lipid nanoparticles for better mRNA therapies
[Press-News.org] Toward a code-breaking quantum computerBuilding on a landmark algorithm, researchers propose a way to make a smaller and more noise-tolerant quantum factoring circuit for cryptography