(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:
UT Health San Antonio ranks at the top 5% globally among universities for clinical medicine research
Fayetteville police positive about partnership with social workers
Optical biosensor rapidly detects monkeypox virus
New drug targets for Alzheimer’s identified from cerebrospinal fluid
Neuro-oncology experts reveal how to use AI to improve brain cancer diagnosis, monitoring, treatment
Argonne to explore novel ways to fight cancer and transform vaccine discovery with over $21 million from ARPA-H
Firefighters exposed to chemicals linked with breast cancer
Addressing the rural mental health crisis via telehealth
Standardized autism screening during pediatric well visits identified more, younger children with high likelihood for autism diagnosis
Researchers shed light on skin tone bias in breast cancer imaging
Study finds humidity diminishes daytime cooling gains in urban green spaces
Tennessee RiverLine secures $500,000 Appalachian Regional Commission Grant for river experience planning and design standards
AI tool ‘sees’ cancer gene signatures in biopsy images
Answer ALS releases world's largest ALS patient-based iPSC and bio data repository
2024 Joseph A. Johnson Award Goes to Johns Hopkins University Assistant Professor Danielle Speller
Slow editing of protein blueprints leads to cell death
Industrial air pollution triggers ice formation in clouds, reducing cloud cover and boosting snowfall
Emerging alternatives to reduce animal testing show promise
Presenting Evo – a model for decoding and designing genetic sequences
Global plastic waste set to double by 2050, but new study offers blueprint for significant reductions
Industrial snow: Factories trigger local snowfall by freezing clouds
Backyard birds learn from their new neighbors when moving house
New study in Science finds that just four global policies could eliminate more than 90% of plastic waste and 30% of linked carbon emissions by 2050
Breakthrough in capturing 'hot' CO2 from industrial exhaust
New discovery enables gene therapy for muscular dystrophies, other disorders
Anti-anxiety and hallucination-like effects of psychedelics mediated by distinct neural circuits
How do microbiomes influence the study of life?
Plant roots change their growth pattern during ‘puberty’
Study outlines key role of national and EU policy to control emissions from German hydrogen economy
Beloved Disney classics convey an idealized image of fatherhood
[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