Visualizing quantum walks on small graphs

This page has all the Julia code necessary for creating the images; as such, it must begin with a couple of trivialities, as loading the dependencies and defining the adjacency matrix of a graph.

31.4 μs

xxxxxxxxxx
 
begin
    using LinearAlgebra
    using LightGraphs
    using Plots
    using Printf
end

47.7 s

adjacency_matrix (generic function with 2 methods)

xxxxxxxxxx
 
begin
    
    function adjacency_matrix(n :: Int64, e :: AbstractEdge)
        f(i :: Int64) = [ convert(Float64, i == j) for j in 1:n ]
        f(src(e)) .* f(dst(e))' + f(dst(e)) .* f(src(e))'
    end
    
    function adjacency_matrix(G :: SimpleGraph)
        f(e) = adjacency_matrix(nv(G), e)
        sum(f.(edges(G)))
    end
​
end

258 μs

Quantum Walk representation

I am representing a quantum walk as the adjacency matrix of the graph.

25.5 μs

QuantumWalk

 
begin
    struct QuantumWalk
        A :: Matrix
    end
    
    function QuantumWalk(G :: SimpleGraph)
        QuantumWalk(adjacency_matrix(G))
    end
end

9.8 ms

I also created a custom heatmap function for displaying the matrices.

25.9 μs

heatmap (generic function with 1 method)

xxxxxxxxxx
 
function heatmap(A :: Matrix; kargs...)
    Plots.heatmap(A;
            clim=(0.0, 1.0),
            framestyle = :none,
            ticks = false,
            aspectratio = :equal,
            c = :thermal,
            kargs...
        )
end

160 μs

Then it is easy to create an animation: Just iterate over a bunch of times and display the component-wise absolute value of $\exp (i t A)$ .

27.9 μs

animate (generic function with 1 method)

x
 
function animate(walk :: QuantumWalk, t0 :: Float64, t1 :: Float64)
    step = (t1 - t0)/200
    animation = @animate for t in t0:step:t1
        heatmap(abs.(exp(im * t * walk.A)), title= @sprintf("t = %.2f", t),)
    end
    gif(animation, fps=10)
end

233 μs

Plots.GRBackend

14.4 ms

Visualizations

I can now display some quantum walks. I will show for $P_{2}$ and for $P_{3}$ at their respective periods.

34.1 μs

xxxxxxxxxx
 
animate(QuantumWalk(path_graph(2)), 0.0, 2.0 * pi)

31.5 s

x
 
animate(QuantumWalk(path_graph(3)), 0.0, sqrt(2) * pi)

20.5 s

We can also observe the instantaneous uniform mixing of the claw graph at

$t = \frac{2 π}{3 \sqrt{3}} \approx 1.21$

24.3 μs

xxxxxxxxxx
 
begin
    claw_graph = SimpleGraph(4)
    for i in 2:4
        add_edge!(claw_graph, 1, i)
    end
    animate(QuantumWalk(claw_graph), 0.0, 4.0 * pi / (3 * sqrt(3)))
end

20.3 s

Cartesian product

There are two interesting things to do with the cartesian product. The first one is to watch how the quantum walk on the cartesian product reduces to the kronecker product in each matrix.

35.6 μs

visualize_product (generic function with 1 method)

xxxxxxxxxx
 
function visualize_product(G :: SimpleGraph, H :: SimpleGraph, t0 :: Float64, t1 :: Float64)
    step = (t1 - t0)/200
    custom_heatmap(graph, t) =
        heatmap(abs.(exp(im * t * adjacency_matrix(graph))), colorbar = false, title = "")
    animation = @animate for t in t0:step:t1
        plot(
            custom_heatmap(cartesian_product(G, H), t),
            custom_heatmap(H, t),
            custom_heatmap(G, t),
            layout=3,
            plot_title = "t = $(t)"
        )
    end
    gif(animation, fps=10)
end

291 μs

xxxxxxxxxx
 
visualize_product(path_graph(2), path_graph(2), 0.0, 2 * pi)

21.7 s

xxxxxxxxxx
 
visualize_product(path_graph(3), path_graph(3), 0.0, sqrt(2) * pi)

21.7 s

xxxxxxxxxx
 
visualize_product(path_graph(2), path_graph(3), 0.0, 2.0 * pi)

21.4 s

We may also consider the cartesian powers of a graph, and visualize the behavior of the quantum walks on them.

19.3 μs

cartesian_power (generic function with 1 method)

xxxxxxxxxx
 
function cartesian_power(G :: SimpleGraph, k :: Int64)
    if k == 0
        SimpleGraph(1)
    else
        cartesian_product(G, cartesian_power(G, k - 1))
    end
end

91.7 μs

xxxxxxxxxx
 
animate(QuantumWalk(cartesian_power(path_graph(2), 2)), 0.0, 2.0 * pi)

20.7 s

xxxxxxxxxx
 
animate(QuantumWalk(cartesian_power(path_graph(3), 4)), 0.0, sqrt(2) * pi)

69.2 s