Normalized-Laplacian perfect state transfer on a tree

Abstract

A seventeen-vertex tree admits normalized-Laplacian perfect state transfer at time three pi.

Definition 1.1 (The normalized Laplacian).

$$\forall (n:\mathbb{N}),(\forall (G:\mathrm{SimpleGraph}\left(\mathrm{Fin}\left(n\right)\right)),([\mathrm{DecidableRel}\left(SimpleGraph.Adj\left(G\right)\right)],((D5.S3.Quantum.Dynamics.NormalizedLaplacianTreeStateTransfer.normalizedLaplacian\left(G\right):\mathrm{Matrix}\left(\mathrm{Fin}\left(n\right),\mathrm{Fin}\left(n\right),\mathbb{C}\right))=Matrix.diagonal\left(\lambda (i:\mathrm{Fin}\left(n\right))\mapsto (Inv.inv\left((Complex.ofReal\left(Real.sqrt\left((Nat.cast\left(SimpleGraph.degree\left(G,i\right)\right):\mathbb{R})\right)\right):\mathbb{C})\right))\right)\cdot SimpleGraph.lapMatrix\left(\mathbb{C},G\right)\cdot Matrix.diagonal\left(\lambda (i:\mathrm{Fin}\left(n\right))\mapsto (Inv.inv\left((Complex.ofReal\left(Real.sqrt\left((Nat.cast\left(SimpleGraph.degree\left(G,i\right)\right):\mathbb{R})\right)\right):\mathbb{C})\right))\right))))$$

Formalization. D5/S3/Quantum/Dynamics/NormalizedLaplacianTreeStateTransfer.normalizedLaplacian (✓ std3).

Citation. Gabriel Coutinho; Pedro Ferreira Baptista (2023). Quantum walks in the normalized Laplacian. DOI: 10.1080/03081087.2023.2236282. URL: https://arxiv.org/abs/2209.04668v1.

Commentary.

For a finite simple graph G, the combinatorial Laplacian is its degree matrix minus its adjacency matrix. Multiplication on both sides by the diagonal inverse square roots of the degrees gives the normalized Laplacian. This is the source’s definition preceding equation (1), expressed as a complex matrix. The natural-valued degree is cast to a real number before taking its square root; the square root is then cast to a complex number before inversion. The displayed definition extends to every finite simple graph, with inverse zero at an isolated vertex; the source assumes connected graphs on at least two vertices.

Definition 1.2 (The positive-sign continuous quantum walk).

$$\forall (n:\mathbb{N}),(\forall (G:\mathrm{SimpleGraph}\left(\mathrm{Fin}\left(n\right)\right)),([\mathrm{DecidableRel}\left(SimpleGraph.Adj\left(G\right)\right)],(\forall (t:\mathbb{R}),((D5.S3.Quantum.Dynamics.NormalizedLaplacianTreeStateTransfer.walk\left(G,t\right):\mathrm{Matrix}\left(\mathrm{Fin}\left(n\right),\mathrm{Fin}\left(n\right),\mathbb{C}\right))=NormedSpace.exp\left((Complex.I\cdot Complex.ofReal\left(t\right))\cdot (D5.S3.Quantum.Dynamics.NormalizedLaplacianTreeStateTransfer.normalizedLaplacian\left(G\right))\right)))))$$

Formalization. D5/S3/Quantum/Dynamics/NormalizedLaplacianTreeStateTransfer.walk (✓ std3).

Citation. Gabriel Coutinho; Pedro Ferreira Baptista (2023). Quantum walks in the normalized Laplacian. DOI: 10.1080/03081087.2023.2236282. URL: https://arxiv.org/abs/2209.04668v1.

Commentary.

Equation (1) defines the walk generated by the normalized Laplacian with the positive sign in the exponential. The real time t is included in the complex scalars, Complex.I is the imaginary unit, and NormedSpace.exp is the matrix exponential.

Definition 1.3 (Perfect state transfer).

$$\forall (n:\mathbb{N}),(\forall (G:\mathrm{SimpleGraph}\left(\mathrm{Fin}\left(n\right)\right)),([\mathrm{DecidableRel}\left(SimpleGraph.Adj\left(G\right)\right)],(\forall (a:\mathrm{Fin}\left(n\right)),(\forall (b:\mathrm{Fin}\left(n\right)),((D5.S3.Quantum.Dynamics.NormalizedLaplacianTreeStateTransfer.PST\left(G,a,b\right))\iff (\exists (\tau :\mathbb{R}),(\exists (c:\mathbb{C}),((\Vert c\Vert =(1:\mathbb{R}))\wedge (Matrix.mulVec\left(D5.S3.Quantum.Dynamics.NormalizedLaplacianTreeStateTransfer.walk\left(G,\tau \right),Pi.single\left(a,(1:\mathbb{C})\right)\right)=(c)\cdot (Pi.single\left(b,(1:\mathbb{C})\right)))))))))))$$

Formalization. D5/S3/Quantum/Dynamics/NormalizedLaplacianTreeStateTransfer.PST (✓ std3).

Citation. Gabriel Coutinho; Pedro Ferreira Baptista (2023). Quantum walks in the normalized Laplacian. DOI: 10.1080/03081087.2023.2236282. URL: https://arxiv.org/abs/2209.04668v1.

Commentary.

Perfect state transfer from a to b means that at some real time τ the coordinate vector at a evolves to the coordinate vector at b multiplied by a complex scalar c of norm one. Pi.single a 1 denotes the coordinate vector at a. The source defines transfer at a specified time; the predicate quantifies over that time. The definition itself does not require a and b to be distinct or τ to be positive.

Definition 1.4 (The conjecture for trees with at least four vertices).

$$(D5.S3.Quantum.Dynamics.NormalizedLaplacianTreeStateTransfer.claim)\iff (\forall (n:\mathbb{N}),((4\le n)\to (\forall (G:\mathrm{SimpleGraph}\left(\mathrm{Fin}\left(n\right)\right)),([\mathrm{DecidableRel}\left(SimpleGraph.Adj\left(G\right)\right)],((SimpleGraph.IsTree\left(G\right))\to (\forall (a:\mathrm{Fin}\left(n\right)),(\forall (b:\mathrm{Fin}\left(n\right)),((a\ne b)\to (\neg (D5.S3.Quantum.Dynamics.NormalizedLaplacianTreeStateTransfer.PST\left(G,a,b\right)))))))))))$$

Formalization. D5/S3/Quantum/Dynamics/NormalizedLaplacianTreeStateTransfer.claim (✓ std3).

Citation. Gabriel Coutinho; Pedro Ferreira Baptista (2023). Quantum walks in the normalized Laplacian. DOI: 10.1080/03081087.2023.2236282. URL: https://arxiv.org/abs/2209.04668v1.

Commentary.

The Discussion conjectures that no tree except the paths on two and three vertices admits normalized-Laplacian perfect state transfer. The statement excludes transfer between every pair of distinct vertices in every tree on n vertices, for every natural n at least four. The only trees on two and three vertices are those paths. A tree with a single vertex has no pair of distinct vertices.

Theorem 1.5 (A seventeen-vertex counterexample).

$$\neg (D5.S3.Quantum.Dynamics.NormalizedLaplacianTreeStateTransfer.claim)$$

Proof. Machine-checked in Lean as D5/S3/Quantum/Dynamics/NormalizedLaplacianTreeStateTransfer.result (✓ std3). ∎

Resolves. Problems/coutinho-baptista-2023-normalized-laplacian-tree-state-transfer-refutation (refuted) by D5/S3/Quantum/Dynamics/NormalizedLaplacianTreeStateTransfer.result.

Source. Repository-derived.

Acknowledgement. Gabriel Coutinho; Pedro Ferreira Baptista (2023). Quantum walks in the normalized Laplacian. DOI: 10.1080/03081087.2023.2236282. URL: https://arxiv.org/abs/2209.04668v1.

Commentary.

Let c be adjacent to the leaves u and v and to seven vertices x₁,…,x₇, with each xᵢ adjacent to a further leaf yᵢ. These are all the edges. Every vertex is connected to c, and there are 9 + 7 = 16 edges on 17 vertices, so the graph is a tree. The degrees are 9 at c, 2 at each xᵢ and 1 at u, v and each yᵢ.

Write L for its normalized Laplacian and eᵤ, eᵥ for the two leaf coordinate vectors. The vector eᵤ − eᵥ is an eigenvector of L with eigenvalue 1. Four symmetric eigenvectors are specified by their values at (u,v; c; xᵢ; yᵢ), constant over the seven arms: w₀ = (1,1; 3; √2; 1), w₂ = (1,1; −3; √2; −1), w₂⁄₃ = (1,1; 1; −√2/7; −3/7) and w₄⁄₃ = (1,1; −1; −√2/7; 3/7). Their eigenvalues are respectively 0, 2, 2/3 and 4/3.

The symmetric endpoint vector decomposes as eᵤ + eᵥ = w₀/16 + w₂/16 + 7w₂⁄₃/16 + 7w₄⁄₃/16. At t = 3π the exponential phases of these four modes are exp(0), exp(6πi), exp(2πi) and exp(4πi), all equal to 1. The antisymmetric mode has phase exp(3πi) = −1.

Consequently U(3π) fixes eᵤ + eᵥ and negates eᵤ − eᵥ. Since eᵤ is half their sum, U(3π)eᵤ = ((eᵤ + eᵥ) − (eᵤ − eᵥ))/2 = eᵥ. Thus the distinct leaves admit perfect state transfer with phase 1 in a tree on at least four vertices.

References

• Truth anchor: D5/S3/Quantum/Dynamics/NormalizedLaplacianTreeStateTransfer.PST
• Truth anchor: D5/S3/Quantum/Dynamics/NormalizedLaplacianTreeStateTransfer.claim
• Truth anchor: D5/S3/Quantum/Dynamics/NormalizedLaplacianTreeStateTransfer.normalizedLaplacian
• Truth anchor: D5/S3/Quantum/Dynamics/NormalizedLaplacianTreeStateTransfer.result
• Truth anchor: D5/S3/Quantum/Dynamics/NormalizedLaplacianTreeStateTransfer.walk
• Dependency: D5/S3/Quantum/Dynamics/EnergyEigenstateStationarity