Home · SDiagonalizability.jl

GraphQuantum logo by Madiha Waqar

Metadata
Documentation
Continuous integration
Code coverage
Static analysis with

Overview

SDiagonalizability.jl implements the first non-naïve deterministic algorithm to minimize the $S$-bandwidth of an undirected graph with integer edge weights. Capabilities also exist for determining whether a graph has $S$-bandwidth less than or equal to a fixed integer $k \ge 1$ without necessarily caring about the true minimum value.

Given an undirected, possibly weighted graph $G$ and finite set of integers $S \subset \mathbb{Z}$, $G$ is said to be "$S$-diagonalizable" if there exists some diagonal matrix $D$ and matrix $P$ with all entries from $S$ such that $G$'s Laplacian matrix $L(G) = PDP^{-1}$. If $G$ is $S$-diagonalizable, then its "$S$-bandwidth" is the minimum integer $k \in \{1, 2, \ldots, |V(G)|\}$ such that there exists some diagonal matrix $D$ and matrix $P$ with all entries from $S$ such that $L(G) = PDP^{-1}$ and $[P^\mathsf{T}P]_{i,j} = 0$ whenever $|i - j| \geq k$; otherwise, its $S$-bandwidth is simply $\infty$.

For specific choices of $S$ (namely $\{-1, 1\}$ and $\{-1, 0, 1\}$), the $S$-bandwidth of a quantum network has been shown to be an indicator of high state transfer fidelity due to automorphic properties of the graph. As such, the nascent study of $S$-diagonalizability and $S$-bandwidth is of interest in the broader context of quantum information theory.

Installation

The only prerequisite is a working Julia installation (v1.10 or later). First, enter Pkg mode by typing ] in the Julia REPL, then run the following command:

pkg> add SDiagonalizability

Basic use

SDiagonalizability.jl offers capabilities for $S$-bandwidth minimization, $S$-bandwidth recognition, and plain old $S$-diagonalizability checking. To compute the $S$-bandwidth of a graph, you can use the s_bandwidth function:

julia> using Graphs

julia> g = complete_graph(14)
{14, 91} undirected simple Int64 graph

julia> res_01neg = s_bandwidth(g, (-1, 0, 1))
Results of S-Bandwidth Minimization
 * S: (-1, 0, 1)
 * S-Bandwidth: 2
 * Graph Order: 14

julia> res_01neg.s_diagonalization
LinearAlgebra.Eigen{Int64, Int64, Matrix{Int64}, Vector{Int64}}
values:
14-element Vector{Int64}:
  0
 14
 14
 14
 14
 14
 14
 14
 14
 14
 14
 14
 14
 14
vectors:
14×14 Matrix{Int64}:
 1   0   0   0   0   1   1   1   1   1   1   0   0   0
 1   0   0   0   0  -1   0  -1   1   1   1   0   0   0
 1   0   0   0   0   0  -1   1   0   1   1   0   0   0
 1   0   0   0   0   0   0  -1   0   1  -1   0   0   0
 1   0   0   0   0   0   0   0  -1  -1   1   1   1   1
 1   0   0   0   0   0   0   0  -1  -1   1  -1  -1  -1
 1   1   1   0   0   0   0   0   0  -1   0   0  -1   1
 1  -1  -1   0   0   0   0   0   0  -1   0   0   0  -1
 1   0  -1   1   1   0   0   0   0   0  -1   0   0   0
 1   0   0  -1  -1   0   0   0   0   0  -1   0   0   0
 1   0   0   0  -1   0   0   0   0   0  -1   0   0   0
 1   0   1   0   1   0   0   0   0   0  -1   0   0   0
 1  -1  -1   0   0   0   0   0   0   0   0   0   0   1
 1   1   1   0   0   0   0   0   0   0   0   0   1  -1

julia> res_1neg = s_bandwidth(g, (-1, 1))
Results of S-Bandwidth Minimization
 * S: (-1, 1)
 * S-Bandwidth: 13
 * Graph Order: 14

julia> res_1neg.s_diagonalization
LinearAlgebra.Eigen{Int64, Int64, Matrix{Int64}, Vector{Int64}}
values:
14-element Vector{Int64}:
  0
 14
 14
 14
 14
 14
 14
 14
 14
 14
 14
 14
 14
 14
vectors:
14×14 Matrix{Int64}:
 1   1   1   1   1   1   1   1   1   1   1   1   1   1
 1  -1  -1  -1  -1  -1  -1   1   1   1   1   1   1   1
 1  -1  -1  -1   1   1   1  -1  -1  -1   1   1   1   1
 1  -1  -1  -1   1   1   1   1   1   1  -1  -1  -1   1
 1  -1  -1  -1   1   1   1   1   1   1   1   1   1  -1
 1  -1   1   1  -1  -1   1  -1  -1   1  -1  -1   1  -1
 1  -1   1   1  -1   1  -1  -1   1  -1  -1   1  -1  -1
 1  -1   1   1   1  -1  -1   1  -1  -1   1  -1  -1   1
 1   1  -1   1  -1  -1   1  -1   1  -1   1  -1  -1   1
 1   1  -1   1  -1   1  -1   1  -1  -1  -1  -1   1  -1
 1   1  -1   1   1  -1  -1  -1  -1   1  -1   1  -1  -1
 1   1   1  -1  -1  -1   1   1  -1  -1  -1   1  -1  -1
 1   1   1  -1  -1   1  -1  -1  -1   1   1  -1  -1   1
 1   1   1  -1   1  -1  -1  -1   1  -1  -1  -1   1  -1

Alternatively, to determine whether a graph has $S$-bandwidth less than or equal to some fixed integer $k \ge 1$ without necessarily caring about the true (minimum) value, you can take advantage of has_s_bandwidth_at_most_k:

julia> using Graphs

julia> g = PetersenGraph()
{10, 15} undirected simple Int64 graph

julia> res_01neg = has_s_bandwidth_at_most_k(g, (-1, 0, 1), 4)
Results of S-Bandwidth Recognition
 * S: (-1, 0, 1)
 * S-Bandwidth Threshold k: 4
 * Has S-Bandwidth ≤ k: true
 * Graph Order: 10

julia> res_01neg.s_diagonalization
LinearAlgebra.Eigen{Int64, Int64, Matrix{Int64}, Vector{Int64}}
values:
10-element Vector{Int64}:
 0
 5
 5
 5
 5
 2
 2
 2
 2
 2
vectors:
10×10 Matrix{Int64}:
 1   1   1   0   0   1   1   1   1   1
 1  -1  -1   1   1   0   0   0   0   1
 1   0   1  -1  -1   0  -1   0  -1  -1
 1   0   0   0   1   0   0   0  -1  -1
 1   0  -1   0  -1   1   1   0   0   0
 1  -1   0  -1   0   0   0   1   1   0
 1   1   0  -1  -1  -1   0  -1   0   1
 1   1  -1   1   0   0  -1   0   0  -1
 1   0   0   1   0  -1   0   0   0   0
 1  -1   1   0   1   0   0  -1   0   0

julia> res_1neg = has_s_bandwidth_at_most_k(g, (-1, 1), 10)
Results of S-Bandwidth Recognition
 * S: (-1, 1)
 * S-Bandwidth Threshold k: 10
 * Has S-Bandwidth ≤ k: false
 * Graph Order: 10

julia> isnothing(res_1neg.s_diagonalization)
true

Lastly, the is_s_diagonalizable function can be used to simply determine whether a graph is $S$-diagonalizable:

julia> using Graphs

julia> L = laplacian_matrix(complete_multipartite_graph([1, 1, 2, 2, 3]))
9×9 SparseArrays.SparseMatrixCSC{Int64, Int64} with 71 stored entries:
  8  -1  -1  -1  -1  -1  -1  -1  -1
 -1   8  -1  -1  -1  -1  -1  -1  -1
 -1  -1   7   ⋅  -1  -1  -1  -1  -1
 -1  -1   ⋅   7  -1  -1  -1  -1  -1
 -1  -1  -1  -1   7   ⋅  -1  -1  -1
 -1  -1  -1  -1   ⋅   7  -1  -1  -1
 -1  -1  -1  -1  -1  -1   6   ⋅   ⋅
 -1  -1  -1  -1  -1  -1   ⋅   6   ⋅
 -1  -1  -1  -1  -1  -1   ⋅   ⋅   6

julia> res_01neg = is_s_diagonalizable(L, (-1, 0, 1))
Results of S-Diagonalizability Check
 * S: (-1, 0, 1)
 * S-Diagonalizable: true
 * Graph Order: 9

julia> res_01neg.s_diagonalization
LinearAlgebra.Eigen{Int64, Int64, Matrix{Int64}, Vector{Int64}}
values:
9-element Vector{Int64}:
 0
 6
 6
 7
 7
 9
 9
 9
 9
vectors:
9×9 Matrix{Int64}:
 1   0   0   0   0   1   1   1   1
 1   0   0   0   0   0  -1  -1   1
 1   0   0   1   1  -1  -1   1  -1
 1   0   0  -1  -1  -1  -1   1  -1
 1   0   0  -1   1  -1   1  -1   0
 1   0   0   1  -1  -1   1  -1   0
 1   1   1   0   0   1   0   0   0
 1  -1   0   0   0   1   0   0   0
 1   0  -1   0   0   1   0   0   0

julia> res_1neg = is_s_diagonalizable(L, (-1, 1))
Results of S-Diagonalizability Check
 * S: (-1, 1)
 * S-Diagonalizable: false
 * Graph Order: 9

julia> isnothing(res_1neg.s_diagonalization)
true

(As demonstrated in this last example, you can supply the Laplacian matrix of a graph as an alternative to the Graph object itself from the Graphs.jl package.)

Documentation

The full documentation is available at GitHub Pages. Documentation for methods and types is also available via the Julia REPL. (Note that as we have just completed development of the core API, many symbols lack complete documentation at this time—we aim to rectify this by the release of v0.2.0.)

Citing

We encourage you to cite our work if you have used our algorithm in your research. Starring the SDiagonalizability.jl repository on GitHub is also appreciated.

The latest citation information may be found in the CITATION.bib file within the repository.

Project status

The latest stable release of SDiagonalizability.jl is v0.1.2. Although a good chunk of documentation and tests is still missing, the core API is fully functional and the package is ready for use. We are currently working on filling in the gaps and aim to release a more polished update (v0.2.0) in the near future.

Credits

Created by Luis M. B. Varona, Dr. Nathaniel Johnston, and Dr. Sarah Plosker.

Insights from Benjamin Talbot, Logan Pipes, and Dr. Liam Keliher are gratefully acknowledged.

Additional thanks to Madiha Waqar for the GraphQuantum logo and Luc Campbell for code review.