NP-Intermediate Problems and Quantum Algorithms

Masanori Ohya, Natsuki Masuda

Tetsuro Nishino

Amit Saha, Debasri Saha, Amlan Chakrabarti

Nowadays in Quantum Computing, the implementation of quantum algorithm has created a stir since Noisy Intermediate-Scale Quantum (NISQ) devices are out in the market. Researchers are mostly interested in solving NP-complete problems with the help of quantum algorithms for its speedup. As per the work on computational complexity by Karp [1], if any of the NP-complete problem can be solved then any other NP-complete problem can be reduced to that problem in polynomial time. In this Paper, K-coloring problem (NP-complete problem) has been considered to solve using Grover's search. A comparator-based approach has been used to implement K-coloring problem which enables the reduction of the qubit cost compared to the state-of-the-art. An end-to-end automated framework has been proposed to implement the K-coloring problem for any unweighted and undirected graph on any available Noisy Intermediate-Scale Quantum (NISQ) devices, which helps in generalizing our approach.

Takashi Mihara, Tetsuro Nishino

Henrique Hepp, Murilo V. G. da Silva, Leandro M. Zatesko

The complexity class of the problems that can be solved by a quantum algorithm in a non-adaptive collapse-free model is called naCQP. This class was introduced in 2016 by Aaronson et al. intended to be a slightly larger class than BQP: larger enough to include important NP-intermediate candidate problems, but likely not to include NP-complete problems. Aaronson et al. (2016) showed that there is an oracle A for which NPA ⊈ naCQPA; and Hepp et al. (2025) showed that relative to an oracle A chosen uniformly at random, (UP ∩ coUP)A ⊈ naCQPA with probability 1, being UP ∩ coUP a subclass of NP. Amongst the NP-intermediate candidate problems in naCQP is the entire class SZK, of the problems that admit a statistical zero-knowledge interactive proof system. The relation between QSZK, which is the class of the problems that admit a quantum zero-knowledge interactive proof system, and naCQP is unknown, with some believing that there is an oracle A for which QSZKA ⊈ naCQPA. A promise problem complete for QSZK is the trace distance distinguishability of mixed quantum states. We show that this problem, when restricted to pure quantum states, is in naCQP.

Jehn‐Ruey Jiang, Chun-Wei Chu

Quadratic unconstrained binary optimization (QUBO) formulas of quantum annealing (QA) algorithms are classified into four categories. QA algorithms using different QUBO formulas solve specific NP-hard problems as examples of the classification. The NP-hard problems solved are the subset sum, the vertex cover, the graph coloring, and the traveling salesperson problems. The QA algorithms are compared with their classical counterparts in terms of the quality of the solution and the time to the solution. Based on the comparison results, observations and suggestions are given for each QUBO formula category, so that proper actions can be adopted to improve the performance of QA algorithms. Compared with classical algorithms, QA algorithms are competitive in the current noisy intermediate-scale quantum (NISQ) era and beyond.