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.
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.
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 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.
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.
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) to O(C(n,k)), which is O(nk) for 1 ≤ k ≪ n/2 or n − k ≪ n/2.
Quantum search algorithms, such as Grover's algorithm, are anticipated to efficiently solve constrained combinatorial optimization problems. However, applying these algorithms to the traveling salesman problem (TSP) on a quantum circuit presents a significant challenge. Existing quantum search algorithms for the TSP typically assume that an initial state—an equal superposition of all feasible solutions satisfying the problem's constraints—is pre-prepared. The query complexity of preparing this state using brute-force methods scales exponentially with the factorial growth of feasible solutions, creating a significant hurdle in designing quantum circuits for large-scale TSPs. To address this issue, we propose a two-step quantum search (TSQS) algorithm that employs two sets of operators. In the first step, all the feasible solutions are amplified into their equal superposition state. In the second step, the optimal solution state is amplified from this superposition state. The TSQS algorithm demonstrates greater efficiency compared to conventional search algorithms that employ a single oracle operator for finding a solution within the encoded space. Encoded in the higher order unconstrained binary optimization representation, our approach significantly reduces the qubit requirements. This enables efficient initial state preparation through a unified circuit design, offering a quadratic speedup in solving the TSP without prior knowledge of feasible solutions.
Constraint satisfiability problems, crucial to several applications, are solved on a quantum computer using Grover's search algorithm, leading to a quadratic improvement over the classical case. The solutions are obtained with high probability for several cases and are illustrated for the cases involving two variables for both 3- and 4-bit numbers. Methods are defined for inequality comparisons, and these are combined according to the form of the satisfiability formula, to form the oracle for the algorithm. The circuit is constructed using IBM Qiskit and is verified on an IBM simulator. It is further executed on one of the Noisy Intermediate-Scale Quantum (NISQ) processors from IBM on the cloud. Noise levels in the processor at present are found to be too high for successful execution. Running the algorithm on the simulator with a custom noise model lets us identify the noise threshold for successful execution.