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

IEEE Access

Transition-Based Multipartite Entangled States and Their Applications to Transition-Constrained Quantum Search

Jehn‐Ruey Jiang

Published Jan 1, 2026• 0 citations
Publisher

Abstract

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 $\mathrm {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 $2^{n}$ to $\binom {n}{k}$ . For a fixed $k$ satisfying $\min (k, n-k)\ll n/2$ , the search space size scales as $\mathrm {O}(n^{k})$ , 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.

DOI
10.1109/access.2026.3710914

Related papers

A Class of Multipartite Entangled States Based on State Transitions

Jehn-Ruey Jiang

We introduce Transition states (T states), denoted by $\ket{T_k^n}$, as a class of multipartite entangled states characterized by a fixed number of state transitions between adjacent qubits. These states form equal-amplitude superpositions over all states with a specified transition count. Unlike Bell states based on two-qubit correlations, GHZ states characterized by global correlations among all qubits, and W and Dicke states based on fixed numbers of qubit excitations, T states are defined by transition counts along an ordered sequence of qubits. We prove that T states are unitarily equivalent to Dicke states through a chain of CX (controlled-X) operations, thereby establishing a direct correspondence between transition-based and excitation-based representations of multipartite entanglement.

quant-pharXiv:2606.05579•Jun 5, 2026•0 citations

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•2 citations

Two-Step Quantum Search Algorithm for Solving Traveling Salesman Problems

Rei Sato, Cui Gordon, Kazuhiro Saito +3 more

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.

arXiv:2405.07129•IEEE Transactions on Quantum Engineering•Jan 1, 2025•6 citations

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•0 citations

Multipartite entanglement and Grover's search algorithm

Ri Qu, Juan Wang, Zong-shang Li +3 more

We firstly investigate the multipartite entanglement features of the quantum states, including the iteration states achieved by repeated application of Grover iteration and the Oracle ones into which the above iteration states evolve by applying single Oracle operation, employed in Grover's search algorithm by means of the separable degree and the entanglement measure. Then we give the quantitative and qualitative descriptions of the entanglement dynamics in Grover's search algorithm. Our results show that for most instances (i) the separable degrees of these states and ranges of their maximum Schmidt numbers are invariable by following the dynamics of Grover's search algorithm; (ii) the dynamics of Grover's search algorithm is almost "filled" by the fully entangled states.

arXiv:1210.3418•Oct 12, 2012•3 citations

Short-Depth Circuits for Dicke State Preparation

Andreas Bärtschi, Stephan Eidenbenz

We present short-depth quantum circuits to deterministically prepare any Dicke state $\left| {D_k^n} \right\rangle $, which is the equal-amplitude superposition of all n-qubit computational basis states with Hamming Weight k. Dicke states are an important class of entangled quantum states with a large variety of applications, and a long history of experimental creation in physical systems. On the other hand, not much is known regarding efficient scalable quantum circuits for Dicke state preparation on realistic quantum computing hardware connectivities.Concretely, we present preparation circuits for Dicke states $\left| {D_k^n} \right\rangle $ with (i) depth of $\mathcal{O}\left( {k\log \frac{n}{k}} \right)$ for all-to-all connectivity (such as on current ion trap devices); (ii) depth of $\mathcal{O}\left( {k\surd \frac{n}{k}} \right) = \mathcal{O}(\sqrt {nk} )$ for Grid connectivity on grids of size $\Omega \left( {\surd \frac{n}{s}} \right) \times \mathcal{O}(\sqrt {ns} )$ with s ≤ k (such as on most current superconducting qubit devices).Both approaches have a total gate count of $\mathcal{O}(kn)$, need no ancilla qubits, and generalize to preparation and compression of those symmetric pure states, in which all non-zero amplitudes correspond to states with Hamming weight at most k. Our work significantly improves and expands previous state-of-the art circuits which had depth $\mathcal{O}(n)$ on a Linear Nearest Neighbor connectivity for arbitrary k (FCT 2019 [4]) and depth $\mathcal{O}(\log n)$ on all-to-all connectivity for k = 1 (AQT 2019 [9]).

arXiv:2207.09998•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 1, 2022•43 citations
We introduce Transition states (T states), denoted by ∣Tkn⟩\left \vert { T_{k}^{n}}\right \rangle ∣Tkn​⟩ , as multipartite entangled states characterized by a fixed number of state transitions between adjacent qubits. For nontrivial values of nnn and kkk , 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−1n-1n−1 additional CX gates while preserving O(n)\mathrm {O}(n)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 2n2^{n}2n to (nk)\binom {n}{k}(kn​) . For a fixed kkk satisfying min⁡(k,n−k)≪n/2\min (k, n-k)\ll n/2min(k,n−k)≪n/2 , the search space size scales as O(nk)\mathrm {O}(n^{k})O(nk) , which grows polynomially with nnn , 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.
We introduce Transition states (T states), denoted by ∣Tkn⟩\ket{T_k^n}∣Tkn​⟩, as a class of multipartite entangled states characterized by a fixed number of state transitions between adjacent qubits. These states form equal-amplitude superpositions over all states with a specified transition count. Unlike Bell states based on two-qubit correlations, GHZ states characterized by global correlations among all qubits, and W and Dicke states based on fixed numbers of qubit excitations, T states are defined by transition counts along an ordered sequence of qubits. We prove that T states are unitarily equivalent to Dicke states through a chain of CX (controlled-X) operations, thereby establishing a direct correspondence between transition-based and excitation-based representations of multipartite entanglement.
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.
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.
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 firstly investigate the multipartite entanglement features of the quantum states, including the iteration states achieved by repeated application of Grover iteration and the Oracle ones into which the above iteration states evolve by applying single Oracle operation, employed in Grover's search algorithm by means of the separable degree and the entanglement measure. Then we give the quantitative and qualitative descriptions of the entanglement dynamics in Grover's search algorithm. Our results show that for most instances (i) the separable degrees of these states and ranges of their maximum Schmidt numbers are invariable by following the dynamics of Grover's search algorithm; (ii) the dynamics of Grover's search algorithm is almost "filled" by the fully entangled states.
We present short-depth quantum circuits to deterministically prepare any Dicke state $\left| {D_k^n} \right\rangle $, which is the equal-amplitude superposition of all n-qubit computational basis states with Hamming Weight k. Dicke states are an important class of entangled quantum states with a large variety of applications, and a long history of experimental creation in physical systems. On the other hand, not much is known regarding efficient scalable quantum circuits for Dicke state preparation on realistic quantum computing hardware connectivities.Concretely, we present preparation circuits for Dicke states $\left| {D_k^n} \right\rangle $ with (i) depth of O(klog⁡nk)\mathcal{O}\left( {k\log \frac{n}{k}} \right)O(klogkn​) for all-to-all connectivity (such as on current ion trap devices); (ii) depth of O(k√nk)=O(nk)\mathcal{O}\left( {k\surd \frac{n}{k}} \right) = \mathcal{O}(\sqrt {nk} )O(k√kn​)=O(nk​) for Grid connectivity on grids of size Ω(√ns)×O(ns)\Omega \left( {\surd \frac{n}{s}} \right) \times \mathcal{O}(\sqrt {ns} )Ω(√sn​)×O(ns​) with s ≤ k (such as on most current superconducting qubit devices).Both approaches have a total gate count of O(kn)\mathcal{O}(kn)O(kn), need no ancilla qubits, and generalize to preparation and compression of those symmetric pure states, in which all non-zero amplitudes correspond to states with Hamming weight at most k. Our work significantly improves and expands previous state-of-the art circuits which had depth O(n)\mathcal{O}(n)O(n) on a Linear Nearest Neighbor connectivity for arbitrary k (FCT 2019 [4]) and depth O(log⁡n)\mathcal{O}(\log n)O(logn) on all-to-all connectivity for k = 1 (AQT 2019 [9]).