Researchers at Waseda University in Japan, including Assistant Professor Tatsuhiko Shirai and Professor Nozomu Togawa, have developed a new quantum algorithm to solve complex combinatorial optimization problems (COPs) more efficiently. The algorithm, called post-processing variationally scheduled quantum algorithm (pVSQA), combines variational scheduling with a post-processing method to transform infeasible solutions into feasible ones. This approach allows for near-optimal solutions for constrained COPs on both quantum annealers and gate-based quantum computers. The algorithm could have significant applications in fields such as logistics, supply chain management, machine learning, material design, and drug discovery.
Quantum Algorithm for Combinatorial Optimization Problems
Researchers have proposed a new quantum algorithm that efficiently solves combinatorial optimization problems (COPs) with constraints in a short time. Traditional quantum algorithms have struggled to solve COPs with constraints within the operation time of quantum computers. To address this, researchers have developed a new algorithm called post-processing variationally scheduled quantum algorithm (pVSQA). This algorithm combines a post-processing technique with variational scheduling to achieve high-quality solutions to COPs in a short time.
Combinatorial Optimization Problems and Quantum Computing
COPs have applications in various fields such as logistics, supply chain management, machine learning, material design, and drug discovery. These problems are computationally intensive using classical computers, and thus solving COPs using quantum computers has attracted significant attention. Quantum computers use the quantum property of superposition, using specialized qubits, to quickly solve large problems. However, when COPs involve constraints, traditional quantum algorithms struggle to obtain a near-optimal solution within the operation time of quantum computers.
The Challenge of Noise in Quantum Devices
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. However, these devices 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 Waseda University in Japan have developed the pVSQA.
The Post-Processing Variationally Scheduled Quantum Algorithm
The pVSQA algorithm uses a quantum device to first generate a variational quantum state via quantum computation. This state 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. The post-processing method then 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 Performance and Potential Applications of the pVSQA
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 traditional quantum algorithms without post-processing on real quantum devices. Dr. Shirai highlights the potential applications of the algorithm, stating that efficiently solving COPs is at the heart of achieving social transformations such as the realization of a carbon-neutral society and sustainable development goals.
External Link: Click Here For More
