A quantum algorithm, capable of providing high-quality solutions to complex combinatorial optimization problems (COPs) in record time, has been developed by researchers, reports Rebellion Research. This new method, known as the post-processing variationally scheduled quantum algorithm (pVSQA), addresses the limitations of conventional quantum algorithms in solving constrained COPs within the operation time of current quantum computers.
Combinatorial optimization problems are central to a wide range of fields, including logistics, supply chain management, machine learning, material design, and drug discovery. These problems, characterized by their computational intensity, are notoriously challenging for classical computers. The advent of quantum computing, with its ability to process vast amounts of data using quantum bits (qubits), promised a new horizon. However, applying quantum computing to COPs, especially those with constraints, has been hindered by issues like computational cost and noise susceptibility in quantum devices.
Pioneered by assistant professor Tatsuhiko Shirai and professor Nozomu Togawa of Waseda University’s Department of Computer Science and Communications Engineering, the pVSQA is a novel approach that marries variational scheduling with a post-processing technique. This combination effectively transforms infeasible solutions into feasible ones, enabling near-optimal solutions for constrained COPs on various quantum platforms.
Published in the IEEE Transactions on Quantum Engineering recently, the study describes how the pVSQA algorithm first uses a quantum device to generate a quantum state. This state forms the basis of a probability distribution function, encompassing all potential solutions within the COP’s constraints. The innovative post-processing step refines this distribution, filtering out infeasible solutions. A classical computer then calculates the energy expectation value of the cost function from this refined distribution, iteratively approaching a near-optimal solution.
The efficacy of pVSQA demonstrated through extensive testing on simulators and real quantum devices like quantum annealers and gate-type quantum computers. The results showed that the new algorithm not only achieved near-optimal performance within a set time frame but also surpassed existing quantum algorithms that do not incorporate post-processing techniques.
Dr. Shirai emphasizes the broader implications of their research: “In the face of urgent global challenges, like climate change and sustainable development, efficient resolution of combinatorial optimization problems is crucial. Our algorithm not only advances the field of quantum computing but also has the potential to catalyze significant social transformations.”
This breakthrough marks a pivotal advancement in the use of quantum computing for solving real-world COPs and offers promising prospects for a myriad of applications across diverse sectors.