Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Mathematics

Dicke State Quantum Search for Solving the Vertex Cover Problem

Jehn‐Ruey Jiang

Published Sep 17, 2025• 5 citations
Publisher

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.

DOI
10.3390/math13183005

Related papers

Solving the k-Hitting Set Problem with Dicke State Quantum Search

Jehn‐Ruey Jiang

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.

IEEE Eurasia Conference on IOT, Communication and Engineering (ECICE)•Apr 10, 2026•1 citation

Novel Quantum Circuit Designs for the Oracle of Grover’s Algorithm to Solve the Vertex Cover Problem

Jehn‐Ruey Jiang, Wei-Han Yan

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 $\mathrm{O}(\sqrt{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.

IEEE Eurasia Conference on IOT, Communication and Engineering (ECICE)•Oct 27, 2023•6 citations

Dicke-State-Initialized Grover’s Algorithm for Solving the Hitting Set Problem

Jehn‐Ruey Jiang, Qiao-Yi Lin

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.

IEEE Eurasia Conference on IOT, Communication and Engineering (ECICE)•May 13, 2026•1 citation

Improving Grover’s Algorithm with Dicke States

Jehn‐Ruey Jiang, Qiao-Yi Lin

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.

IEEE International Conference on Consumer Electronics - Taiwan (ICCE-Taiwan)•Jul 16, 2025•4 citations

Qubit-Efficient Quantum Circuit for the Minimum Vertex Cover Problem Using Grover's Algorithm

Krissada Sarawit, Kamonluk Suksen

The Minimum Vertex Cover (MVC) problem is a fundamental NP-hard combinatorial optimization problem with applications in network security, resource allocation, and scheduling. As quantum computing moves toward fault-tolerant operation, developing qubit-efficient algorithms remains a critical challenge. This paper presents three quantum circuit architectures for solving MVC and its weighted variant using Grover's search algorithm: a Dicke-state restricted search that uses Generalized Dicke State Preparation to filter the search space, an arithmetic-based binary counter using the Cuccaro comparator for edge validation, and a weighted arithmetic solver supporting heterogeneous vertex weights. Our results demonstrate that while Dicke-state preparation offers the fastest convergence in terms of Grover iterations with minimal qubit overhead when the optimal cover size$k^\star$is much smaller than the number of vertices$n$(i.e.,$k^\star \ll n$), which occurs in graphs with small vertex covers such as star graphs, the arithmetic-based approaches provide superior scaling for dense graphs by reducing edge validation from$O(m)$to$O(\log m)$ancilla qubits. The weighted arithmetic solver is the only architecture capable of handling heterogeneous vertex weights. We also introduce Skip-K, a classical optimization shared by all three architectures that exploits measurement outcomes to skip intermediate pivot values, reducing the number of Grover executions from$O(\sum _{i} w_{i})$to$O(\log |\mathcal {C}|) \subseteq O(n)$in expectation, where$\mathcal {C}$is the set of feasible covers, and to two executions in the best case. We analyze the trade-offs between qubit requirements and circuit depth across all three architectures, providing a roadmap for implementing these solvers on fault-tolerant quantum hardware.

IEEE Transactions on Quantum Engineering•Jan 1, 2026•0 citations

Utilizing Novel Quantum Counters for Grover's Algorithm to Solve the Dominating Set Problem

Jehn‐Ruey Jiang, Qiao-Yi Lin

Grover's algorithm is a well-known unstructured quantum search algorithm run on quantum computers. It constructs an oracle and calls the oracle O($\sqrt N$) times to locate specific data out of N unsorted data. This represents a quadratic speedup compared to the classical unstructured data sequential search algorithm, which requires to call the oracle O(N) times. We are currently 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 components with three good properties: (i) a reduced number of qubits, (ii) shorter quantum depth, and (iii) fewer gates. This paper utilizes novel quantum counters with the above-mentioned three good properties to construct the oracle of Grover's algorithm to efficiently solve the dominating set problem (DSP), as defined below. For a given graph G=(V, E), a dominating set (DS) D is a subset of the vertex set V, such that every vertex is in D or has an adjacent vertex in D. The DSP is to decide for a given graph G and an integer k whether there exists a DS with size k. Algorithms solving the DSP have many applications. For example, they can be applied to check whether k routers suffice to connect all computers in a computer network. The DSP is an NP-complete problem, indicating that no classical algorithm exists to solve the DSP with polynomial time complexity in the worst case. Therefore, using quantum algorithms, such as Grover's algorithm, to exploit the potent computational capabilities of quantum computers to solve the DSP is highly promising. We execute the whole quantum circuit of Grover's algorithm using novel quantum counters through the IBM Quantum Lab service to validate that the circuit can solve the DSP efficiently and correctly.

arXiv:2312.09388•Dec 14, 2023•5 citations
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.
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 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)\mathrm{O}(\sqrt{N})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.
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.
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 O(2n){\mathbf{O}}\left({\sqrt {{2^n}} }\right)O(2n​) to O(C(n,k)){\mathbf{O}}(\sqrt {C(n,k)} )O(C(n,k)​), which is O(nk){\mathbf{O}}\left({\sqrt {{n^k}} }\right)O(nk​) for 1 ≤ k ≪ n/2 or n − k ≪ n/2.
The Minimum Vertex Cover (MVC) problem is a fundamental NP-hard combinatorial optimization problem with applications in network security, resource allocation, and scheduling. As quantum computing moves toward fault-tolerant operation, developing qubit-efficient algorithms remains a critical challenge. This paper presents three quantum circuit architectures for solving MVC and its weighted variant using Grover's search algorithm: a Dicke-state restricted search that uses Generalized Dicke State Preparation to filter the search space, an arithmetic-based binary counter using the Cuccaro comparator for edge validation, and a weighted arithmetic solver supporting heterogeneous vertex weights. Our results demonstrate that while Dicke-state preparation offers the fastest convergence in terms of Grover iterations with minimal qubit overhead when the optimal cover sizek⋆k^\stark⋆is much smaller than the number of verticesnnn(i.e.,k⋆≪nk^\star \ll nk⋆≪n), which occurs in graphs with small vertex covers such as star graphs, the arithmetic-based approaches provide superior scaling for dense graphs by reducing edge validation fromO(m)O(m)O(m)toO(log⁡m)O(\log m)O(logm)ancilla qubits. The weighted arithmetic solver is the only architecture capable of handling heterogeneous vertex weights. We also introduce Skip-K, a classical optimization shared by all three architectures that exploits measurement outcomes to skip intermediate pivot values, reducing the number of Grover executions fromO(∑iwi)O(\sum _{i} w_{i})O(∑i​wi​)toO(log⁡∣C∣)⊆O(n)O(\log |\mathcal {C}|) \subseteq O(n)O(log∣C∣)⊆O(n)in expectation, whereC\mathcal {C}Cis the set of feasible covers, and to two executions in the best case. We analyze the trade-offs between qubit requirements and circuit depth across all three architectures, providing a roadmap for implementing these solvers on fault-tolerant quantum hardware.
Grover's algorithm is a well-known unstructured quantum search algorithm run on quantum computers. It constructs an oracle and calls the oracle O(N\sqrt NN​) times to locate specific data out of N unsorted data. This represents a quadratic speedup compared to the classical unstructured data sequential search algorithm, which requires to call the oracle O(N) times. We are currently 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 components with three good properties: (i) a reduced number of qubits, (ii) shorter quantum depth, and (iii) fewer gates. This paper utilizes novel quantum counters with the above-mentioned three good properties to construct the oracle of Grover's algorithm to efficiently solve the dominating set problem (DSP), as defined below. For a given graph G=(V, E), a dominating set (DS) D is a subset of the vertex set V, such that every vertex is in D or has an adjacent vertex in D. The DSP is to decide for a given graph G and an integer k whether there exists a DS with size k. Algorithms solving the DSP have many applications. For example, they can be applied to check whether k routers suffice to connect all computers in a computer network. The DSP is an NP-complete problem, indicating that no classical algorithm exists to solve the DSP with polynomial time complexity in the worst case. Therefore, using quantum algorithms, such as Grover's algorithm, to exploit the potent computational capabilities of quantum computers to solve the DSP is highly promising. We execute the whole quantum circuit of Grover's algorithm using novel quantum counters through the IBM Quantum Lab service to validate that the circuit can solve the DSP efficiently and correctly.