Cloud Hosting

Optimization problems cover a wide range of applications and are often cited as good candidates for quantum computing. However, the execution time for constrained combinatorial optimization applications on quantum devices can be problematic. Researchers from Waseda University report developing a new algorithm post-processing variationally scheduled quantum algorithm (pVSQA) that speeds performance.

Therea brief account of the work posted today on the Waseda University website. Constrained combinatorial problems (COP) are common in logistics, supply chain management, machine learning, material design, and drug discovery. The researchers report the novelty of their algorithm is its use of a post-processing technique combined with variational scheduling to achieve high-quality solutions to COPs in a short time.

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, said Tatsuhiko Shirai, a leader in the work, which was published in EEE Transactions on Quantum Engineering this month.

Heres a brief excerpt from the article:

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.

Given the limits of current quantum devices (adiabatic annealers and gate-based systems), the researchers suggest the new algorithm is a significant step forwards particularly given the wider applicability of constrained combinatorial optimization.

They note in the papers abstract:

COPs are typically transformed into ground-state search problems of the Ising model on a quantum annealer or gate-based quantum device. Variational methods are used to find an optimal schedule function that leads to high-quality solutions in a short amount of time. Post-processing techniques convert the output solutions of the quantum devices to satisfy the constraints of the COPs.

pVSQA combines the variational methods and the post-processing technique. We obtain a sufficient condition for constrained COPs to apply pVSQA based on a greedy post-processing algorithm. We apply the proposed method to two constrained NP-hard COPs: the graph partitioning problem and the quadratic knapsack problem. pVSQA on a simulator shows that a small number of variational parameters is sufficient to achieve a (near-)optimal performance within a predetermined operation time. Then building upon the simulator results, we implement pVSQA on a quantum annealer and a gate-based quantum device. The experimental results demonstrate the effectiveness of our proposed method.

Link to Waseda University article, https://www.waseda.jp/top/en/news/80146

Link to IEEE paper, https://ieeexplore.ieee.org/document/10472069

Read the original:
Waseda U. Researchers Reports New Quantum Algorithm for Speeding Optimization - HPCwire