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.
Greenberger-Horne-Zeilinger (GHZ) states are multipartite entangled quantum states that play a central role in quantum information theory, with applications in quantum communication, cryptography, and distributed quantum computing. A major experimental goal is to create high-dimensional GHZ states using multiple entangled parties. Krenn, Gu and Zeilinger discovered a surprising bridge between these quantum-optical experiments and graph theory: certain photonic experiments can be represented by edge-coloured, edge-weighted graphs, and the dimension of the produced GHZ state equals the number of feasible monochromatic inherited vertex colourings. This led Krenn and Gu to conjecture that every GHZ graph with more than four vertices has dimension at most 2. A counterexample would give a new high-dimensional multipartite GHZ construction, while a proof would clarify fundamental resource limitations in quantum optics. It is known that the conjecture holds for graphs of vertex connectivity at most 2 [MFCS 2024], and that simple GHZ graphs with n>4 vertices have dimension less than n/2 [Quantum 2024]. However, no general upper bound depending only on vertex connectivity was known. We prove that every simple connected GHZ graph G with at least four vertices has dimension at most 2κ(G)−1+(2κ(G)), where κ(G) is the vertex connectivity of G. We also prove new bounds in terms of edge connectivity and maximum degree.
Public mathematical preprint by Yongxian Zhang. We prove Fuentes–Keeler–Munizzi–Pollack, arXiv:2511.19585v1, Conjecture 1: for every finite qubit graph state, positive tripartite information implies that a locally equivalent graph contains an induced four-vertex claw. The proof gives the complete claw-vertex-minor-free component classification by K1, K2, P3, P4, C5 and the six-vertex W5, and the sharp connected threshold seven. The unbounded step is a connected-graph induction; the finite step checks all 120 nonempty one-vertex extensions with independent exact checkers. The certificate package verifies all 120 extensions, 1,511 orbit transitions and 5,460 labeled four-block assignments. These finite checks supplement the written entropy and induction proof; the theorem is not claimed as a complete Lean formalization. No external human peer review or historical-priority claim is made. Research and manuscript preparation used AI assistance; no external funding. Original material is reserved unless a file states another license. DOI registration does not certify correctness, novelty, or priority.