We propose new quantum circuit designs for the Grover oracle, i.e., the oracle of Grover’s algorithm, to solve the vertex cover problem (VCP) efficiently. Grover’s algorithm is an unstructured quantum search algorithm to search a target data item out of N data pieces by calling the oracle O(N) times. It represents a quadratic speedup compared to the classical unstructured data sequential search algorithm, which requires O(N) oracle calls. We are in the noisy intermediate-scale quantum (NISQ) era in which quantum computers have a limited number of qubits, short decoherence time, and low gate fidelity. It is thus desirable to design quantum circuits with three properties: (1) a reduced number of qubits, (2) shorter quantum depth, and (3) fewer gates. We created novel designs of a quantum counter and a quantum semaphore to be applied to the Grover oracle to have the three properties. Through the IBM Quantum Lab service, we executed Grover’s algorithm with the novel quantum circuit designs to solve the VCP to validate the design correctness.
In this paper we study quantum algorithms for NP-complete problems whose best classical algorithm is an exponential time application of dynamic programming. We introduce the path in the hypercube problem that models many of these dynamic programming algorithms. In this problem we are asked whether there is a path from 0n to 1n in a given subgraph of the Boolean hypercube, where the edges are all directed from smaller to larger Hamming weight. We give a quantum algorithm that solves path in the hypercube in time O∗(1.817n). The technique combines Grover's search with computing a partial dynamic programming table. We use this approach to solve a variety of vertex ordering problems on graphs in the same time O∗(1.817n), and graph bandwidth in time O∗(2.946n). Then we use similar ideas to solve the travelling salesman problem and minimum set cover in time O∗(1.728n).