We develop a full characterization of abelian quantum statistics on graphs. We explain how the number of anyon phases is related to connectivity. For 2-connected graphs the independence of quantum statistics with respect to the number of particles is proven. For non-planar 3-connected graphs we identify bosons and fermions as the only possible statistics, whereas for planar 3-connected graphs we show that one anyon phase exists. Our approach also yields an alternative proof of the structure theorem for the first homology group of n -particle graph configuration spaces. Finally, we determine the topological gauge potentials for 2-connected graphs.We develop a full characterization of abelian quantum statistics on graphs. We explain how the number of anyon phases is related to connectivity. For 2-connected graphs the independence of quantum statistics with respect to the number of particles is proven. For non-planar 3-connected graphs we identify bosons and fermions as the only possible statistics, whereas for planar 3-connected graphs we show that one anyon phase exists. Our approach also yields an alternative proof of the structure theorem for the first homology group of n -particle graph configuration spaces. Finally, we determine the topological gauge potentials for 2-connected graphs.

arXiv:1304.5781Communications in Mathematical PhysicsJun 5, 201426 citations

Quantum Connectivity Graphs

Jincheng Zhang

Quantum Connectivity Graphs (QCGs) represent a novel approach to modeling complex systems by utilizing the unique properties of quantum entanglement. This paper explores the design and application of QCGs, proposing a framework that leverages entanglement to enable efficient computation and prediction. The core claim is that QCGs offer a significant advancement over traditional graph-based models, particularly in the context of describing intricate interactions and potentially facilitating quantum computation.Quantum Connectivity Graphs (QCGs) represent a novel approach to modeling complex systems by utilizing the unique properties of quantum entanglement. This paper explores the design and application of QCGs, proposing a framework that leverages entanglement to enable efficient computation and prediction. The core claim is that QCGs offer a significant advancement over traditional graph-based models, particularly in the context of describing intricate interactions and potentially facilitating quantum computation.

Sep 5, 20260 citations

Quantum graphs

Peter Kuchment

Waves in Random MediaJan 1, 200411 citations

A Quantum Algorithm for $st$ -Transport on Flat Connection GraphsA Quantum Algorithm for $st$-Transport on Flat Connection Graphs

Stacey Jeffery, Tobias J. Osborne, Galina Pass

We study a generalization of undirected $st$ -connectivity to graphs whose edges carry quantum operations. Let $G=(V,E)$ be an undirected graph on $n$ vertices in which each edge $\{u,v\}$ is labeled by a unitary $U_{uv}\in\mathbb{C}^{k\times k}$ , with $U_{vu}=U_{uv}^\dagger$ . We assume the labels form a \emph{flat} connection: the ordered product of labels along any path between a pair of vertices $u$ and $v$ is independent of the path. Equivalently, the connection is pure gauge, i.e., gauge-equivalent to the trivial connection; such graphs are exactly the consistent connection graphs of spectral graph theory and the noiseless instances of group synchronization. Consequently, whenever $s$ and $t$ are connected, transporting a state from $s$ to $t$ defines a unique unitary $U_s(t)$ . Given states $|ψ_s\rangle,|ψ_t\rangle\in\mathbb{C}^k$ and an oracle that returns the neighbours of a vertex while coherently applying the corresponding edge unitaries, the \emph{ $st$ -transport problem} is to decide whether $s$ and $t$ are connected and, if so, to estimate the squared overlap between $U_s(t)|ψ_s\rangle$ and $|ψ_t\rangle$ to additive error $\varepsilon$ . When $k=1$ and all labels are trivial, this is exactly undirected $st$ -connectivity. We give a bounded-error quantum algorithm for $st$ -transport that runs in time $\widetilde{O}(n/\varepsilon)$ and uses $O(\log n+\log k+\log(1/\varepsilon))$ space. We do this by designing a transducer and applying a Metropolis-Hastings reweighting to the input graph. We also prove an $Ω(n)$ quantum query lower bound that holds even when $s$ and $t$ are promised to be connected, so for constant $\varepsilon$ our algorithm is optimal up to polylogarithmic factors.We study a generalization of undirected $st$-connectivity to graphs whose edges carry quantum operations. Let $G=(V,E)$ be an undirected graph on $n$ vertices in which each edge $\{u,v\}$ is labeled by a unitary $U_{uv}\in\mathbb{C}^{k\times k}$, with $U_{vu}=U_{uv}^\dagger$. We assume the labels form a \emph{flat} connection: the ordered product of labels along any path between a pair of vertices $u$ and $v$ is independent of the path. Equivalently, the connection is pure gauge, i.e., gauge-equivalent to the trivial connection; such graphs are exactly the consistent connection graphs of spectral graph theory and the noiseless instances of group synchronization. Consequently, whenever $s$ and $t$ are connected, transporting a state from $s$ to $t$ defines a unique unitary $U_s(t)$. Given states $|ψ_s\rangle,|ψ_t\rangle\in\mathbb{C}^k$ and an oracle that returns the neighbours of a vertex while coherently applying the corresponding edge unitaries, the \emph{$st$-transport problem} is to decide whether $s$ and $t$ are connected and, if so, to estimate the squared overlap between $U_s(t)|ψ_s\rangle$ and $|ψ_t\rangle$ to additive error $\varepsilon$. When $k=1$ and all labels are trivial, this is exactly undirected $st$-connectivity. We give a bounded-error quantum algorithm for $st$-transport that runs in time $\widetilde{O}(n/\varepsilon)$ and uses $O(\log n+\log k+\log(1/\varepsilon))$ space. We do this by designing a transducer and applying a Metropolis-Hastings reweighting to the input graph. We also prove an $Ω(n)$ quantum query lower bound that holds even when $s$ and $t$ are promised to be connected, so for constant $\varepsilon$ our algorithm is optimal up to polylogarithmic factors.

quant-pharXiv:2609.40231Oct 1, 20260 citations

On the properties of simple quantum graphs

Pavel Hejčík

Jan 1, 20080 citations

A Quantum Algorithm for

st

-Transport on Flat Connection Graphs

We study a generalization of undirected

st

-connectivity to graphs whose edges carry quantum operations. Let

G=(V,E)

be an undirected graph on

n

vertices in which each edge

\{u,v\}

is labeled by a unitary

U_{uv}\in\mathbb{C}^{k\times k}

, with

U_{vu}=U_{uv}^\dagger

. We assume the labels form a \emph{flat} connection: the ordered product of labels along any path between a pair of vertices

u

and

v

is independent of the path. Equivalently, the connection is pure gauge, i.e., gauge-equivalent to the trivial connection; such graphs are exactly the consistent connection graphs of spectral graph theory and the noiseless instances of group synchronization. Consequently, whenever

s

and

t

are connected, transporting a state from

s

t

defines a unique unitary

U_s(t)

. Given states

|ψ_s\rangle,|ψ_t\rangle\in\mathbb{C}^k

and an oracle that returns the neighbours of a vertex while coherently applying the corresponding edge unitaries, the \emph{

st

-transport problem} is to decide whether

s

and

t

are connected and, if so, to estimate the squared overlap between

U_s(t)|ψ_s\rangle

and

|ψ_t\rangle

to additive error

\varepsilon

. When

k=1

and all labels are trivial, this is exactly undirected

st

-connectivity. We give a bounded-error quantum algorithm for

st

-transport that runs in time

\widetilde{O}(n/\varepsilon)

and uses

O(\log n+\log k+\log(1/\varepsilon))

space. We do this by designing a transducer and applying a Metropolis-Hastings reweighting to the input graph. We also prove an

Ω(n)

quantum query lower bound that holds even when

s

and

t

are promised to be connected, so for constant

\varepsilon

our algorithm is optimal up to polylogarithmic factors.