Skolkovo Researchers Discover Limit on Quantum Computing Algorithms to Solve Certain Problems

(AZoQuantum) Researchers at the Skolkovo Institute of Science and Technology, Moscow, have discovered a limit on the ability of quantum computing algorithms to solve certain kinds of problems. In a paper entitled “Reachability Deficits in Quantum Approximate Optimization”, V. Akshay, H. Philathong, M.E.S. Morales, and J.D. Biamonte study the ability of the Quantum Approximate Optimization Algorithm (QAOA) to solve constraint satisfaction problems. In these problems, values of boolean variables must be found that satisfy several logical constraints.
QAOA is important because it is implementable with current quantum computing hardware and can be applied to a variety of different problems. However, previous work has shown that it does not outperform classical methods for small circuit depths, and the work of Askay et al. shows that large circuit depths are necessary to ensure that the correct solution is reached. While quantum computing has the potential to solve hard problems faster than classical computing, it is necessary to thoroughly understand the limitations of the algorithms to ensure they give correct answers in practice.