Which graphs are suitable for quantum teleportation: graph-structural characterization of teleportation resources in quantum-walk protocols

The question "what graphs are suitable for teleportation" was posed in the paper that introduced generalized teleportation by discrete-time coined quantum walks, Wang, Shang and Xue (Quantum Information Processing 16, 221 (2017)), and is relayed as an open question in the Introduction of Bordbar, Naderi and Alimoradi Chamgordani (Indian Journal of Physics 95, 901 (2021)). At its primary source the question concerns the graph structures on which coined quantum walks implement teleportation, not stabilizer graph states. Known partial answers: the line, the 4-cycle, complete graphs, d-regular graphs and N-cycles admit protocols, and the one-dimensional case is completely classified by a necessary-and-sufficient condition (Yamagami, Segawa and Konno 2021); a 2025 preprint still treats the question as open, contributing only one further positive family (an irregular graph on 10 vertices). A complete characterization for walks on general graphs remains open as of August 2026. A distinct graph-state channel problem — which graph topologies yield faithful teleportation channels — is itself only partially resolved: Huang, Yu, Lin and Hsu (2009) proved that a 2n-qubit graph state supports their faithful one-to-many teleportation scheme if and only if the sender-receiver adjacency submatrix has full rank over GF(2). That problem is related background here, not part of the target.

Background

Quantum teleportation transmits an unknown quantum state between two distant parties using a shared entangled resource plus classical communication; a protocol is faithful when the state is recovered with unit fidelity. The original protocol consumes a two-qubit Bell pair, and much of quantum information theory concerns which larger entangled structures can substitute for it. A graph state is a pure multi-qubit state built from a graph $G(V,E)$: each vertex carries a qubit initialized in the $|+\rangle$ state and each edge applies a controlled-phase entangling gate. Equivalently, the state is the common eigenstate of stabilizer generators $g_i = X_i \prod_{j \in N(i)} Z_j$ (operators that leave it invariant), where $N(i)$ is the set of neighbors of vertex $i$ and $X$, $Z$ are Pauli operators. Graph states are the resource of measurement-based quantum computation, quantum error-correcting codes and quantum secret sharing, and every stabilizer state is equivalent to some graph state under local Clifford operations (single-qubit unitaries mapping Pauli operators to Pauli operators). Which graph topologies are usable teleportation resources is therefore an operationally meaningful question.

Independently, a second notion of "graphs for teleportation" arose in the quantum-walk literature. A discrete-time coined quantum walk evolves a system whose Hilbert space is a position space spanned by the vertices of a graph tensored with a finite coin space; one step applies a coin operator (a unitary acting on the coin) followed by a shift that moves the walker along the graph's edges. Wang, Shang and Xue showed that such walks implement "generalized teleportation": the walk itself builds the entanglement resource from an unentangled input, and an unknown qubit or $d$-level state is recovered at a target vertex with unit fidelity, so no pre-shared entanglement is required. They gave protocols on the line (two-step walk), the 4-cycle, complete graphs and $d$-regular graphs, and posed the question: what other graphs are suitable for teleportation?

Two lines of subsequent work sharpen the question. In the walk setting, the one-dimensional case is settled: Yamagami, Segawa and Konno introduced a rigorous definition of when a walk "accomplishes teleportation" and a necessary and sufficient condition that classifies the one-dimensional parameters; N-cycles also admit protocols (with a correction dispute over the N-line claim). In the graph-state setting, for the $2n$-qubit schemes of Huang, Yu, Lin and Hsu — in their faithful one-to-many teleportation scheme one sender holds the second half of the qubits together with the unknown input states, and $n$ receivers each hold one qubit of the first half, while their dense-coding scheme reverses the roles — a graph state is a faithful teleportation channel exactly when the reduced adjacency matrix of the "Tanner-type" subgraph (the bipartite subgraph of the edges crossing the sender/receiver cut) is invertible over $\mathrm{GF}(2)$, the field of arithmetic modulo 2; for example, the 4-qubit cluster state (a line graph, the standard lattice-like graph-state resource) qualifies whereas the GHZ (Greenberger-Horne-Zeilinger) state, whose graph is a star, does not, and graphs related by local complementation (the graph operation that, at a chosen vertex, complements every edge among that vertex's neighbors; it generates the local-Clifford equivalence classes of graph states) share viability. Neither line of work possesses a characterization for general graphs; the target of this problem is the walk setting, the one posed at the primary source. Bordbar, Naderi and Alimoradi Chamgordani quantified the entanglement of complete, tree, chain and loop graph states with 3 to 8 qubits, using the generalized concurrence and the Meyer–Wallach measure $Q$ and its variants (multipartite entanglement measures based on single-qubit purities of reduced states), but explicitly did not address teleportation, referencing the open question as motivation.

Problem Statement

The question posed at the primary source and relayed by Bordbar, Naderi and Alimoradi Chamgordani is: what graphs are suitable for teleportation? The objective is a graph-structural classification — necessary and sufficient graph-theoretic conditions — of the graphs on which discrete-time coined quantum walks implement generalized teleportation, with 'suitable' judged by perfect (unit-fidelity) recovery of an arbitrary unknown input state.

Protocol model (fixed by the source scheme): a discrete-time coined quantum walk on a finite graph $G$ with two coin degrees of freedom acting as sender and receiver systems; the unknown input state is encoded in the sender's coin at a starting vertex; the walk (at least one step) generates the entanglement resource from an unentangled input, so no pre-shared entanglement is used; the sender performs coin and position measurements and communicates the outcomes; the receiver applies an outcome-dependent unitary correction to its own, distinct coin. Teleportation is accomplished if and only if, for every measurement outcome and every unknown input state, the receiver's coin equals the input. Degenerate "protocols" with zero steps, or with recovery inside the sender's own system, do not count: the output must appear in the receiver's coin for every outcome, which is impossible when the receiver's coin is independent of the input. Yamagami, Segawa and Konno formulated this accomplishment condition rigorously for the one-dimensional two-step scheme and classified its parameters; that is the settled special case a general classification must reproduce in one dimension.

Determine, as necessary and sufficient graph-theoretic conditions on $G$, for which finite graphs such a protocol exists. The one-dimensional case is classified, and the line, the 4-cycle, complete graphs, $d$-regular graphs and N-cycles are known positives; the answer for general graphs — two-dimensional lattices and trees — is open, with no general necessary condition or construction technique known. The objective in brief: given only a graph, decide from its structure whether it can support quantum-walk teleportation.

References

1. Mahmoud Bordbar, Negar Naderi, Mohammad Alimoradi Chamgordani, 'The relation of entanglement to the number of qubits and interactions between them for different graph states', Indian Journal of Physics 95, 901-909 (2021), DOI: 10.1007/s12648-020-01755-x, https://doi.org/10.1007/s12648-020-01755-x
2. Charles H. Bennett, Gilles Brassard, Claude Crépeau, Richard Jozsa, Asher Peres, William K. Wootters, 'Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels', Physical Review Letters 70, 1895-1899 (1993), DOI: 10.1103/PhysRevLett.70.1895, https://doi.org/10.1103/PhysRevLett.70.1895
3. Yu Wang, Yun Shang, Peng Xue, 'Generalized teleportation by quantum walks', Quantum Information Processing 16, 221 (2017), DOI: 10.1007/s11128-017-1675-y, https://doi.org/10.1007/s11128-017-1675-y
4. Yu-Guang Yang, Sheng-Nan Cao, Wei-Feng Cao, Dan Li, Yi-Hua Zhou, Wei-Min Shi, 'Generalized teleportation by means of discrete-time quantum walks on N-lines and N-cycles', Modern Physics Letters B 33, 1950070 (2019), DOI: 10.1142/S0217984919500702, https://doi.org/10.1142/S0217984919500702
5. Duc Manh Nguyen, Sunghwan Kim, 'The fog on: Generalized teleportation by means of discrete-time quantum walks on N-lines and N-cycles', Modern Physics Letters B 33, 1950270 (2019), DOI: 10.1142/S0217984919502701, https://doi.org/10.1142/S0217984919502701
6. Yun Shang, Yu Wang, Meng Li, Ruqian Lu, 'Quantum communication protocols by quantum walks with two coins', EPL (Europhysics Letters) 124, 60009 (2019), DOI: 10.1209/0295-5075/124/60009, https://doi.org/10.1209/0295-5075/124/60009
7. Tomoki Yamagami, Etsuo Segawa, Norio Konno, 'General condition of quantum teleportation by one-dimensional quantum walks', Quantum Information Processing 20, 224 (2021), DOI: 10.1007/s11128-021-03155-4, https://doi.org/10.1007/s11128-021-03155-4
8. Markus Hein, Wolfgang Dür, Jens Eisert, Robert Raussendorf, Maarten van den Nest, Hans J. Briegel, 'Entanglement in graph states and its applications', arXiv:quant-ph/0602096 (2006), https://arxiv.org/abs/quant-ph/0602096
9. Ching-Yu Huang, I-Ching Yu, Feng-Li Lin, Li-Yi Hsu, 'Deterministic dense coding and faithful teleportation with multipartite graph states', Physical Review A 79, 052306 (2009), DOI: 10.1103/PhysRevA.79.052306, arXiv:0806.4289, https://arxiv.org/abs/0806.4289
10. Lijie Ren, Guangqiang He, Guihua Zeng, 'Universal teleportation via continuous-variable graph states', Physical Review A 78, 042302 (2008), DOI: 10.1103/PhysRevA.78.042302, https://doi.org/10.1103/PhysRevA.78.042302
11. Guoming Wang, Mingsheng Ying, 'Perfect many-to-one teleportation with stabilizer states', Physical Review A 77, 032324 (2008), DOI: 10.1103/PhysRevA.77.032324, https://doi.org/10.1103/PhysRevA.77.032324
12. Yi Ding, Yuzheng Wei, Zongyi Li, Min Jiang, 'Quantum teleportation based on non-maximally entangled graph states', Quantum Information Processing 22, 400 (2023), DOI: 10.1007/s11128-023-04157-0, https://doi.org/10.1007/s11128-023-04157-0
13. Dafa Li, 'The necessary and sufficient condition for perfect teleportation and superdense coding and all the suitable states for teleportation and superdense coding', Annals of Physics 488, 170377 (2026), DOI: 10.1016/j.aop.2026.170377, arXiv:2602.11293, https://arxiv.org/abs/2602.11293
14. Nada Ikken, Pankaj Kumar, Abdallah Slaoui, Binayak Kar, R. Ahl Laamara, M. Zomorodi, A. A. Abd El-Latif, 'Bidirectional multi-nodes quantum teleportation using discrete-time quantum walk', Scientific Reports 15, 44798 (2025), DOI: 10.1038/s41598-025-28524-2, https://doi.org/10.1038/s41598-025-28524-2
15. Rachana Soni, Neelam Choudhary, Navneet Pratap Singh, 'Quantum communication scheme to teleport arbitrary quantum state via discrete time quantum walks', arXiv:2501.11785 (2025), https://arxiv.org/abs/2501.11785