This paper proposes using Dicke states to improve Grover’s quantum search algorithm for solving the k-vertex cover problem in a given graph with n vertices, a well-known NP-complete problem. A Dicke state $\left| {D_k^n} \right\rangle $ is a special entangled quantum state representing the symmetric superposition of all n-qubit states where exactly k qubits are in |1⟩. It is used to prepare the initial quantum state to reduce the quantum search space from 2nto C(n,k). Consequently, the operations required by Grover’s algorithm are reduced from ${\mathbf{O}}\left({\sqrt {{2^n}} }\right)$ to ${\mathbf{O}}(\sqrt {C(n,k)} )$, which is ${\mathbf{O}}\left({\sqrt {{n^k}} }\right)$ for 1 ≤ k ≪ n/2 or n − k ≪ n/2.
This paper proposes using Dicke states to improve Grover’s quantum search algorithm for solving the k-vertex cover problem in a given graph with n vertices, a well-known NP-complete problem. A Dicke state ∣Dkn⟩ is a special entangled quantum state representing the symmetric superposition of all n-qubit states where exactly k qubits are in |1⟩. It is used to prepare the initial quantum state to reduce the quantum search space from 2nto C(n,k). Consequently, the operations required by Grover’s algorithm are reduced from O(2n) to O(C(n,k)), which is O(nk) for 1 ≤ k ≪ n/2 or n − k ≪ n/2.
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.
The Dicke-state-initialized Grover’s algorithm is used for the hitting set problem (DSIGA-HSP) to efficiently solve the NP-Complete HSP. By initializing the working qubits in the Dicke state Dkn , the algorithm restricts the search domain to subsets of fixed size k, thereby avoiding the use of quantum counters and reducing the search space from 2n to n k . A Dicke-state-based diffuser and quantum-flag oracle are designed to achieve selective amplitude amplification of valid hitting sets. Experimental results based on the IBM Qiskit Aer Simulator confirm that the quantum circuit generated by DSIGA-HSP can successfully solve the HSP.
Quantum computing offers an accelerated mechanism for solving combinatorial optimization problems that could be hardly solvable with classical tools, in this context, this paper highlights the utility of quantum computing in solving NP-complete problems efficiently and shows up the importance of employing quantum algorithms achieving parallel calculation in the purpose of reducing the algorithmic complexity and simplifying the development of optimization applications. Within this publication, an optimized version of quantum circuit conception for developing the oracle of the Grover's search algorithm is introduced for solving the vertex cover problem, and it was also tested using the Qiskit library and applied to a set of instances to evaluate its performance.
This paper addresses the problem of finding the densest k-vertex subgraph in an arbitrary graph. This problem is NP-hard and has important applications in social network analysis, fraud detection, recommendation systems, and bioinformatics. We propose two quantum approaches to solve this problem: reduction to Quadratic Unconstrained Binary Optimization (QUBO) and using Grover's quantum search algorithm. For the latter approach, we present an explicit gate-based oracle circuit utilizing Dicke states and Quantum Fourier Transform for edge counting. Numerical simulations demonstrate a quadratic speedup over classical Brute-force search.
An algorithm called Dicke state quantum search for the hitting set problem (DSQS-HSP), generates quantum circuits to solve the k-hitting set problem (k-HSP), by initializing the working qubits in an n-qubit Dicke state Dkn of exactly k qubits in 1. The quantum circuit reduces the search space size from 2n to D = nk, the number of symmetric superposition states in Dkn. A quantum-flag oracle checks the hitting condition, and a mirror-readout mechanism projects valid solutions to the output register. The circuit yields two outcome types: the all-zero string with probability (D−M)/D and solution strings, each with probability 1/D, where M is the number of solutions. The resource growth of qubits, gates, circuit depth, and circuit execution repetitions is O(nk), which remains polynomial in the best case for min(k, n − k) ≪ n/2. Experimental results using IBM Qiskit Aer Simulator confirm that the DSQS-HSP can produce quantum circuits to successfully solve the k-HSP.
We introduce Transition states (T states), denoted by $\left \vert { T_{k}^{n}}\right \rangle $ , as multipartite entangled states characterized by a fixed number of state transitions between adjacent qubits. For nontrivial values of n and k , these states form equal-amplitude superpositions over all computational basis states with a specified transition count. We establish a one-to-one correspondence between T states and Dicke states, which are characterized by fixed numbers of excitations, and show that T states can be generated from Dicke states through a chain of CX (controlled-X) operations. An illustrative Schmidt-rank analysis highlights differences in bipartite entanglement between corresponding T and Dicke states. We propose a T-state preparation circuit that is constructed from a Dicke-state preparation circuit using only n−1 additional CX gates while preserving O(n) circuit depth and requiring no ancilla qubits. Qiskit simulations validate the proposed preparation circuit. We further propose T-state initialized Grover search (TSIGS), which restricts Grover search to transition-constrained subspaces, reducing the search space size from 2n to (kn) . For a fixed k satisfying min(k,n−k)≪n/2 , the search space size scales as O(nk) , which grows polynomially with n , simplifying oracle design and reducing Grover iterations. As a case study, an algorithm named TSIGS-HSP-FT is developed to construct a quantum circuit using TSIGS to solve the hitting set problem with fixed transitions (HSP-FT). Qiskit simulations validate the constructed quantum circuit.