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

arXiv:1009.5216 · Physics Letters A

Tripartite connection condition for a quantum graph vertex

Taksu Cheon, Pavel Exner, Ondřej Turek

Published Nov 7, 2010• 9 citations
arXivHTMLPDF
DOI
10.1016/j.physleta.2010.11.011

Related papers

On transparent vertex boundary conditions for quantum graphs

A. A. Lavrukhine, A. I. Popov, I. Yu. Popov

Indian Journal of Physics•Jan 4, 2023•0 citations

Entanglement of multi-qubit quantum graph states and studies structural properties of tripartite graphs with quantum computing

Kh. P. Gnatenko

We propose a method for constructing multi-qubit entangled quantum states that represent weighted tripartite graphs, and develop approaches for investigating their structural properties using quantum computing. In the general case of multi-qubit states corresponding to arbitrary tripartite graph structures, we derive an expression for the entanglement distance. We establish a connection between entanglement and properties of the corresponding tripartite graphs. Namely, we show that the entanglement of a qubit with the rest of the system in a quantum tripartite graph state depends on the weights of the arcs in the neighborhood of the corresponding vertex, as well as on its degree with respect to the vertex sets of the tripartite graph. As an illustrative example, we consider a tripartite graph forming a triangle and evaluate the entanglement distance with quantum computing. We also compute quantum correlators for the general case of tripartite quantum graph states and relate these quantities to structural features of the underlying graphs, including the number of non-overlapping neighbors, the number of common neighbors of the corresponding vertices, and the number of 4-cycles. Obtained relationships between the quantum properties of multi-qubit states and the structural features of tripartite graphs opens up the possibility of investigating classical systems, such as tripartite graphs, using quantum computing. It is worth emphasizing that tripartite graphs have applications in practical problems, including resource allocation, scheduling, and database and hypergraph modeling.

quant-pharXiv:2604.27829•May 1, 2026•0 citations

Connectivity for quantum graphs

Javier Alejandro Chávez‐Domínguez, Andrew T. Swift

arXiv:1911.00446•Linear Algebra and its Applications•Aug 20, 2020•7 citations

Multipartite Separability of Laplacian Matrices of Graphs

Chai Wah Wu

Recently, Braunstein et al. introduced normalized Laplacian matrices of graphs as density matrices in quantum mechanics and studied the relationships between quantum physical properties and graph theoretical properties of the underlying graphs. We provide further results on the multipartite separability of Laplacian matrices of graphs. In particular, we identify complete bipartite graphs whose normalized Laplacian matrix is multipartite entangled under any vertex labeling. Furthermore, we give conditions on the vertex degrees such that there is a vertex labeling under which the normalized Laplacian matrix is entangled. These results address an open question raised in Braunstein et al. Finally, we show that the Laplacian matrix of any product of graphs (strong, Cartesian, tensor, lexicographical, etc.) is multipartite separable, extending analogous results for bipartite and tripartite separability.

arXiv:0809.0827•The Electronic Journal of Combinatorics•May 15, 2009•11 citations

When the parity bound is tight for graph scenarios

Igor Postanovskyi

For a k-regular graph of odd order n we study the edge-ray scenario (contexts = vertices, rays = edges, uniform one-hot rows, each outcome bit flipped with probability η/2). A parity argument gives η*_F ≥ η_par = 1 − (1 − 2/n)^(1/k); we ask when it is tight. We prove tightness, even in the strong form (every S_k-symmetric row law on the parity slice), for locally set-transitive graphs containing all (a, b)-subgraphs, among them the odd graph K(7, 3) (for odd cycles this also follows from the complete set of n-cycle noncontextuality inequalities of Araújo et al.). For vertex-transitive graphs we reduce tightness to reachability of k/2 explicit staircase vertices of a weight polytope, show that the first one is reachable iff a balancing condition on perfect matchings holds, and prove this condition for every connected vertex-transitive graph of odd order; the proof uses the theorem of Zhang and Sun that such graphs of degree ≥ 4 are 3-factor-critical. Since the last staircase vertex is always reachable, tightness follows for every connected vertex-transitive graph of odd order and degree 4; for the middle staircase vertices we give a reduction to random regular spanning subgraphs with uniform rows and an odd-cut condition. Among the 406 connected vertex-transitive graphs of odd order n ≤ 21 we certify tightness exactly for 312, including all 287 of degree k ≤ 10; without vertex transitivity the bound can fail. An exact matching criterion shows that the strong form fails for 163 of the 406 graphs. For the edge scenario of K_n we prove η*_F = 1 − (2⌈n/2⌉ − 1)^(−1/2) for all n ≥ 2 (formalised in Lean), and show that the sufficient condition of our earlier paper (paper 6, 10.5281/zenodo.23481180) fails for n ≥ 6 and for the two-qubit doily, although equality holds there.

•Nov 9, 2026•0 citations

Basics of Quantum Graphs

Sovan Samanta, Antonios Kalampakas, Tofigh Allahviranloo

Studies in computational intelligence•Jan 1, 2025•0 citations
We propose a method for constructing multi-qubit entangled quantum states that represent weighted tripartite graphs, and develop approaches for investigating their structural properties using quantum computing. In the general case of multi-qubit states corresponding to arbitrary tripartite graph structures, we derive an expression for the entanglement distance. We establish a connection between entanglement and properties of the corresponding tripartite graphs. Namely, we show that the entanglement of a qubit with the rest of the system in a quantum tripartite graph state depends on the weights of the arcs in the neighborhood of the corresponding vertex, as well as on its degree with respect to the vertex sets of the tripartite graph. As an illustrative example, we consider a tripartite graph forming a triangle and evaluate the entanglement distance with quantum computing. We also compute quantum correlators for the general case of tripartite quantum graph states and relate these quantities to structural features of the underlying graphs, including the number of non-overlapping neighbors, the number of common neighbors of the corresponding vertices, and the number of 4-cycles. Obtained relationships between the quantum properties of multi-qubit states and the structural features of tripartite graphs opens up the possibility of investigating classical systems, such as tripartite graphs, using quantum computing. It is worth emphasizing that tripartite graphs have applications in practical problems, including resource allocation, scheduling, and database and hypergraph modeling.
Recently, Braunstein et al. introduced normalized Laplacian matrices of graphs as density matrices in quantum mechanics and studied the relationships between quantum physical properties and graph theoretical properties of the underlying graphs. We provide further results on the multipartite separability of Laplacian matrices of graphs. In particular, we identify complete bipartite graphs whose normalized Laplacian matrix is multipartite entangled under any vertex labeling. Furthermore, we give conditions on the vertex degrees such that there is a vertex labeling under which the normalized Laplacian matrix is entangled. These results address an open question raised in Braunstein et al. Finally, we show that the Laplacian matrix of any product of graphs (strong, Cartesian, tensor, lexicographical, etc.) is multipartite separable, extending analogous results for bipartite and tripartite separability.
For a k-regular graph of odd order n we study the edge-ray scenario (contexts = vertices, rays = edges, uniform one-hot rows, each outcome bit flipped with probability η/2). A parity argument gives η*_F ≥ η_par = 1 − (1 − 2/n)^(1/k); we ask when it is tight. We prove tightness, even in the strong form (every S_k-symmetric row law on the parity slice), for locally set-transitive graphs containing all (a, b)-subgraphs, among them the odd graph K(7, 3) (for odd cycles this also follows from the complete set of n-cycle noncontextuality inequalities of Araújo et al.). For vertex-transitive graphs we reduce tightness to reachability of k/2 explicit staircase vertices of a weight polytope, show that the first one is reachable iff a balancing condition on perfect matchings holds, and prove this condition for every connected vertex-transitive graph of odd order; the proof uses the theorem of Zhang and Sun that such graphs of degree ≥ 4 are 3-factor-critical. Since the last staircase vertex is always reachable, tightness follows for every connected vertex-transitive graph of odd order and degree 4; for the middle staircase vertices we give a reduction to random regular spanning subgraphs with uniform rows and an odd-cut condition. Among the 406 connected vertex-transitive graphs of odd order n ≤ 21 we certify tightness exactly for 312, including all 287 of degree k ≤ 10; without vertex transitivity the bound can fail. An exact matching criterion shows that the strong form fails for 163 of the 406 graphs. For the edge scenario of K_n we prove η*_F = 1 − (2⌈n/2⌉ − 1)^(−1/2) for all n ≥ 2 (formalised in Lean), and show that the sufficient condition of our earlier paper (paper 6, 10.5281/zenodo.23481180) fails for n ≥ 6 and for the two-qubit doily, although equality holds there.