Novel quantum algorithm for high-quality solutions to combinatorial optimization problems
Researchers have proposed an innovative quantum algorithm that effectively solves combinatorial optimization problems with constraints in a short time
2024-03-25
(Press-News.org)
Combinatorial optimization problems (COPs) have applications in many different fields such as logistics, supply chain management, machine learning, material design and drug discovery, among others, for finding the optimal solution to complex problems. These problems are usually very computationally intensive using classical computers and thus solving COPs using quantum computers has attracted significant attention from both academia and industry.
Quantum computers take advantage of the quantum property of superposition, using specialized qubits, that can exist in an infinite yet contained number of states of 0 or 1 or any combination of the two, to quickly solve large problems. However, when COPs involve constraints, conventional quantum algorithms like adiabatic quantum annealing struggle to obtain a near-optimal solution within the operation time of quantum computers. Recent advances in quantum technology have led to devices such as quantum annealers and gate-type quantum devices that provide suitable platforms for solving COPs. Unfortunately, they are susceptible to noise, which limits their applicability to quantum algorithms with low computational costs.
To address this challenge, Assistant Professor Tatsuhiko Shirai and Professor Nozomu Togawa from the Department of Computer Science and Communications Engineering at Waseda University in Japan have recently developed a groundbreaking post-processing variationally scheduled quantum algorithm (pVSQA). “The two main methods for solving COPs with quantum devices are variational scheduling and post-processing. Our algorithm combines variational scheduling with a post-processing method that transforms infeasible solutions into feasible ones, allowing us to achieve near-optimal solutions for constrained COPs on both quantum annealers and gate-based quantum computers,” explains Dr. Shirai. Their study was published in the journal IEEE Transactions on Quantum Engineering on 13 March 2024.
The innovative pVSQA algorithm uses a quantum device to first generate a variational quantum state via quantum computation. This is then used to generate a probability distribution function which consists of all the feasible and infeasible solutions that are within the constraints of the COP. Next, the post-processing method transforms the infeasible solutions into feasible ones, leaving the probability distribution with only feasible solutions. A classical computer is then used to calculate an energy expectation value of the cost function using this new probability distribution. Repeating this calculation results in a near-optimal solution.
The researchers analyzed the performance of this algorithm using both a simulator and real quantum devices such as a quantum annealer and a gate-type quantum device. The experiments revealed that pVSQA achieves a near-optimal performance within a predetermined time on the simulator and outperforms conventional quantum algorithms without post-processing on real quantum devices.
Dr. Shirai highlights the potential applications of the algorithm, stating: “Drastic social transformations are urgently needed to address various social issues. Examples include the realization of a carbon-neutral society to solve climate change issues and the realization of sustainable development goals to address issues such as increased energy demand and food shortage. Efficiently solving combinatorial optimization problems is at the heart of achieving these transformations. Our new method will play a significant role in realizing these long-term social transformations.”
In conclusion, this study marks a significant step forward for using quantum computers for solving COPs, holding promise for addressing complex real-world problems across various domains.
***
Reference
DOI: https://doi.org/10.1109/TQE.2024.3376721
Authors: Tatsuhiko Shirai1 and Nozomu Togawa1
Affiliations: Department of Computer Science and Communications Engineering, Waseda University
About Waseda University
Located in the heart of Tokyo, Waseda University is a leading private research university that has long been dedicated to academic excellence, innovative research, and civic engagement at both the local and global levels since 1882. The University has produced many changemakers in its history, including nine prime ministers and many leaders in business, science and technology, literature, sports, and film. Waseda has strong collaborations with overseas research institutions and is committed to advancing cutting-edge research and developing leaders who can contribute to the resolution of complex, global social issues. The University has set a target of achieving a zero-carbon campus by 2032, in line with the Sustainable Development Goals (SDGs) adopted by the United Nations in 2015.
To learn more about Waseda University, visit https://www.waseda.jp/top/en
About Assistant Professor Tatsuhiko Shirai
Tatsuhiko Shirai is currently an Assistant Professor at the Department of Computer and Communications Engineering at Waseda University in Japan. He obtained his master’s and Ph.D. in Physics from the University of Tokyo in 2013 and 2016 respectively. In 2022, he obtained the SLDM Research Group Excellent Paper Award. His research interests include quantum algorithms, quantum open systems, and quantum computing. He is a member of The Physical Society of Japan.
END
ELSE PRESS RELEASES FROM THIS DATE:
2024-03-25
A new study combining genetic, palaeoecological, and archaeological evidence has unveiled the Persian Plateau as a pivotal geographic location serving as a hub for Homo sapiens during the early stages of their migration out of Africa.
This revelation sheds new light on the complex journey of human populations, challenging previous understandings of our species' expansion into Eurasia.
The study, published in Nature Communications, highlights a crucial period between approximately 70,000 to 45,000 years ago when human populations did not uniformly spread across Eurasia, ...
2024-03-25
PULLMAN, Wash. – The famous work ethic of honey bees might spell disaster for these busy crop pollinators as the climate warms, new research indicates.
Flying shortens the lives of bees, and worker honey bees will fly to find flowers whenever the weather is right, regardless of how much honey is already in the hive. Using climate and bee population models, researchers found that increasingly long autumns with good flying weather for bees raises the likelihood of colony collapse in the spring.
The study, published in Scientific Reports, focused on the Pacific Northwest but holds implications for hives across the U.S. The researchers ...
2024-03-25
All present day non African human populations are the result of subdivisions that took place after their ancestors left Africa at least 60.000 years ago. How long did it take for these separations to take place? Almost 20.000 years, during which they were all part of a single population. Where did they live for all this time? We don’t know, yet.
This is a conversation that could have taken place one year ago, now it is possible to give clearer answers to these questions thanks to the study recently published in Nature Communications (1) led by the researchers from the University ...
2024-03-25
MISSOULA – The escalation of extreme wildfires globally has prompted a critical examination of wildfire management strategies. A new study from the University of Montana reveals how fire suppression ensures that wildfires will burn under extreme conditions at high severity, exacerbating the impacts of climate change and fuel accumulation.
The study used computer simulations to show that attempting to suppress all wildfires results in fires burning with more severe ecological impacts, with accelerated increases in burned area beyond those expected from fuel accumulation or climate change.
“Fire suppression has unintended consequences,” said lead author Mark Kreider, a Ph.D. ...
2024-03-25
(Santa Barbara, Calif.) — While Hollywood and Silicon Valley love the limelight, California is an agricultural powerhouse, too. Agricultural products sold in the Golden State totaled $59 billion in 2022. But rising temperatures, declining precipitation and decades of over pumping may require drastic changes to farming. Legislation to address the problem could even see fields taken out of cultivation.
Fortunately, a study out of UC Santa Barbara suggests less extreme measures could help address California’s water issues. Researchers combined remote sensing, big data and machine ...
2024-03-25
Humans pass on more viruses to domestic and wild animals than we catch from them, according to a major new analysis of viral genomes by UCL researchers.
For the new paper published in Nature Ecology & Evolution, the team analysed all publicly available viral genome sequences, to reconstruct where viruses have jumped from one host to infect another vertebrate species.
Most emerging and re-emerging infectious diseases are caused by viruses circulating in animals. When these viruses cross over from animals into humans, a process known as zoonosis, they can cause disease outbreaks, epidemics and pandemics such as Ebola, flu or Covid-19. Given the enormous impact ...
2024-03-25
Understanding the behavior of matter is crucial for advancing scientific fields like biology, chemistry, and materials science. X-ray crystallography has been instrumental in this pursuit, allowing scientists to determine molecular structures with precision. In traditional X-ray crystallography experiments, a single crystal is exposed to X-rays multiple times to obtain diffraction signals. This poses a problem, where the sample has its structure altered or damaged by X-ray exposure.
In recent years, advances in technology have allowed for the development of “time-resolved serial femtosecond crystallography” (TR-SFX). In serial ...
2024-03-25
More efficient use of phosphorus could see limited stocks of the important fertiliser last more than 500 years and boost global food production to feed growing populations.
But these benefits will only happen if countries are less wasteful with how they use phosphorus, a study published today in Nature Food shows.
Around 30-40 per cent of farm soils have over-applications of phosphorus, with European and North American countries over-applying the most.
The global population is due to hit nearly 10 billion by 2050 and it is estimated that to feed ...
2024-03-25
RICHLAND, Wash.— A commonplace chemical used in water treatment facilities has been repurposed for large-scale energy storage in a new battery design by researchers at the Department of Energy’s Pacific Northwest National Laboratory. The design provides a pathway to a safe, economical, water-based, flow battery made with Earth-abundant materials. It provides another pathway in the quest to incorporate intermittent energy sources such as wind and solar energy into the nation’s electric grid.
The researchers report ...
2024-03-25
Scientists from The Australian National University (ANU) have discovered a gene mutation is responsible for causing psoriasis – a chronic inflammatory skin disease that causes patients to develop red, scaly and itchy patches across their body.
According to ANU researcher Dr Chelisa Cardinez, if two copies of this mutated gene (known as IKBKB) are present, patients with psoriasis may go on to develop psoriatic arthritis, leaving them with joint pain, stiffness and swelling. Thanks to the world-first discovery from ANU, scientists now know what causes the progression from a skin-only disease to a skin and joint disease.
It’s hoped the findings will lead ...
LAST 30 PRESS RELEASES:
[Press-News.org] Novel quantum algorithm for high-quality solutions to combinatorial optimization problems
Researchers have proposed an innovative quantum algorithm that effectively solves combinatorial optimization problems with constraints in a short time
