Dicke State Quantum Search for Solving the Vertex Cover Problem

Jehn-Ruey Jiang ()
Additional contact information
Jehn-Ruey Jiang: Department of Computer Science and Information Engineering, National Central University, Taoyuan 320317, Taiwan

Mathematics, 2025, vol. 13, issue 18, 1-28

Abstract: This paper proposes a quantum algorithm, named Dicke state quantum search (DSQS), to set qubits in the Dicke state | D k n ⟩ of D states in superposition to locate the target inputs or solutions of specific patterns among 2 n unstructured input instances, where n is the number of input qubits and D = n k = O ( n k ) 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( 2 n ) 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( n k ) 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 = n k = O ( n k ) , 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.

Keywords: Dicke state; Grover’s algorithm; NP-complete problem; oracle; quantum search; vertex cover problem (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/18/3005/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/18/3005/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:13:y:2025:i:18:p:3005-:d:1751676

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().