This article has been reviewed according to Science X's editorial process and policies. Editors have highlighted the following attributes while ensuring the content's credibility:

fact-checked

trusted source

proofread

Novel quantum algorithm proposed for high-quality solutions to combinatorial optimization problems

Novel quantum algorithm for high-quality solutions to combinatorial optimization problems
The proposed algorithm combines variational scheduling with post-processing to achieve near-optimal solutions to combinatorial optimization problems with constraints within the operation time of quantum computers. Credit: Tatsuhiko Shirai / Waseda University

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 post-processing variationally scheduled quantum (pVSQA). Their study was published in the journal IEEE Transactions on Quantum Engineering.

"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.

Novel quantum algorithm for high-quality solutions to combinatorial optimization problems
The probability distribution p'({si}) obtained by a quantum computer is updated to p({si}) through a post-processing. Credit: Tatsuhiko Shirai / Waseda University

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 . 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 said, "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 and food shortage.

"Efficiently solving 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.

More information: Tatsuhiko Shirai et al, Post-Processing Variationally Scheduled Quantum Algorithm for Constrained Combinatorial Optimization Problems, IEEE Transactions on Quantum Engineering (2024). DOI: 10.1109/TQE.2024.3376721

Provided by Waseda University
Citation: Novel quantum algorithm proposed for high-quality solutions to combinatorial optimization problems (2024, March 25) retrieved 28 May 2024 from https://techxplore.com/news/2024-03-quantum-algorithm-high-quality-solutions.html
This document is subject to copyright. Apart from any fair dealing for the purpose of private study or research, no part may be reproduced without the written permission. The content is provided for information purposes only.

Explore further

Shortcut to success: Toward fast and robust quantum control through accelerating adiabatic passage

33 shares

Feedback to editors