Dicke State Quantum Search for Solving the Vertex Cover Problem

Abstract

This paper proposes a quantum algorithm, named Dicke state quantum search (DSQS), to set qubits in the Dicke state |Dkn⟩ of D states in superposition to locate the target inputs or solutions of specific patterns among 2n unstructured input instances, where n is the number of input qubits and D=nk=O(nk) for min(k,n−k)≪n/2. Compared to Grover’s algorithm, a famous quantum search algorithm that calls an oracle and a diffuser O(2n) times, DSQS requires no diffuser and calls an oracle only once. Furthermore, DSQS does not need to know the number of solutions in advance. We prove the correctness of DSQS with unitary transformations, and show that each solution can be found by DSQS with an error probability less than 1/3 through O(nk) repetitions, as long as min(k,n−k)≪n/2. Additionally, this paper proposes a classical algorithm, named DSQS-VCP, to generate quantum circuits based on DSQS for solving the k-vertex cover problem (k-VCP), a well-known NP-complete (NPC) problem. Complexity analysis demonstrates that DSQS-VCP operates in polynomial time and that the quantum circuit generated by DSQS-VCP has a polynomial qubit count, gate count, and circuit depth as long as min(k,n−k)≪n/2. We thus conclude that the k-VCP can be solved by the DSQS-VCP quantum circuit in polynomial time with an error probability less than 1/3 under the condition of min(k,n−k)≪n/2. Since the k-VCP is NP-complete, NP and NPC problems can be polynomially reduced to the k-VCP. If the reduced k-VCP instance satisfies min(k,n−k)≪n/2, then both the instance and the original NP/NPC problem instance to which it corresponds can be solved by the DSQS-VCP quantum circuit in polynomial time with an error probability less than 1/3. All statements of polynomial algorithm execution time in this paper apply only to VCP instances and similar instances of other problems, where min(k,n−k)≪n/2. Thus, they imply neither NP ⊆ BQP nor P = NP. In this restricted regime of min(k,n−k)≪n/2, the Dicke state subspace has a polynomial size of D=nk=O(nk), and our DSQS algorithm samples from it without asymptotic superiority over exhaustive enumeration. Nevertheless, DSQS may be combined with other quantum algorithms to better exploit the strengths of quantum computation in practice. Experimental results using IBM Qiskit packages show that the DSQS-VCP quantum circuit can solve the k-VCP successfully.