1 of 39

Graph-inspired structures and results in Quantum Information

Youming Qiao

University of Technology Sydney

​

Quantum Maths Seminar

The University of New South Wales

24 June 2026

2 of 39

Graphs

  • Vertices connected by edges
  • Useful for modelling networks, relations, and computational processes
  • A prime object in combinatorics and discrete mathematics

 

 

 

 

 

 

 

 

 

 

3 of 39

Quantum information

  •  

4 of 39

From graphs to quantum states or channels

Despite different temperaments, it is possible to “transfer” problems and methods from graphs to quantum states/channels

  1. From graph isomorphism �to quantum state equivalence relations
  2. From expander graphs �to quantum expanders (and more)
  3. From graphs to operator systems

​

​

​

​

5 of 39

From quantum states and channels to tensors

  •  

 

 

6 of 39

Graph isomorphism

  • Graph isomorphism: whether two graphs are the same up to relabelling the vertices

​

​

​

​

​

7 of 39

Graph isomorphism

  • Graph isomorphism: whether two graphs are the same up to relabelling the vertices

​

​

​

​

​

8 of 39

A technique in graph isomorphism

  • Coloured Graph Iso: some vertices have prescribed colours, and isomorphisms should respect the colours
  • Coloured Graph Iso is no harder than ordinary Graph Iso: colouring gadgets

9 of 39

Quantum state equivalence relations

  •  

10 of 39

Quantum state equivalence relations

  •  

11 of 39

LOCC/SLOCC equivalence: group-theoretic characterisation

  •  
  1. Bennett–Popescu–Rohrlich–Smolin–Thapliyal, Phys. Rev. A 63, 012307 (2000/2001)
  2. Dür–Vidal–Cirac, Phys. Rev. A 62, 062314 (2000)
  3. Acín-Andrianov-Costa-Jané-Latorre-Tarrach, Phys. Rev. Lett. 85, 1560, (2000)

12 of 39

LOCC/SLOCC equivalence: group-theoretic characterisation

  •  

13 of 39

From graphs to quantum states

 

1

3

2

1

3

2

1

3

2

1

3

2

 

1

3

2

1

3

2

 

1

3

2

1

3

2

 

1

3

2

1

3

2

 

1

3

2

1

3

2

 

 

 

 

 

1

3

2

1

3

2

 

14 of 39

From graph iso to quantum state equivalences

  •  

 

 

 

 

 

 

15 of 39

 

  •  

16 of 39

From k-partite states to 3-partite states

  •  

17 of 39

From k-partite states to 3-partite states

  •  

18 of 39

From k-partite states to 3-partite states

  •  

19 of 39

An illustration of the linear algebraic colouring gadget

Graph colouring gadget

  •  

Tensor “colouring” gadget

  •  

Ranks of U2 slices

are much larger, so

they do not mix with

U1 slices

20 of 39

Summary for Graph Iso to Quantum State Equivalence

  •  

21 of 39

Expander graphs

  •  

22 of 39

Expander graphs

  •  

23 of 39

Expander graphs

  •  

24 of 39

Expander graphs

  •  

Dodziuk 84, Alon-Milman 85

25 of 39

Expander graphs: a central object in discrete maths

  • Explicit constructions
    • Magulis, Lubotzky-Phillips-Sarnak, Kassabov, Reingold-Vadhan-Wigderson, Bourgain-Gamburd…
  • Applications (see [Hoory-Linial-Wigderson, Bull. AMS, 2006]):
    • Design and analysis of communication networks
    • Error correcting codes (good LDPC codes)
    • Pseudorandomness (randomness extraction)
    • Complexity theory
    • Markov chains and Monte-Carlo algorithms

​

26 of 39

From graph expansion to quantum expansion

  •  
  •  

27 of 39

From graph expansion to quantum expansion

  •  
  •  

28 of 39

From graph expansion to quantum expansion

  •  
  •  

29 of 39

From graph expansion to quantum expansion

  •  
  •  

30 of 39

Background on quantum expansion notions

Dimension expansion

  • Explicit constructions
    • Dvir-Shpilka, Bourgain, Lubotzky-Zelmanov…
  • Applications
    • Algebraic pseudorandomness
    • Tensor rank lower bounds

Quantum and edge expansion

  • Explicit constructions
    • Lubotzky-Zelmanov, Harrow, Ben-Aroya–Ta-Shma…
  • Applications
    • Quantum pseudorandomness
    • Thermalization and open quantum systems

​

31 of 39

Relations between three quantum expansion notions

  •  

32 of 39

Independent sets and cliques in graphs

  • Independent sets: a set of vertices with no edges between them
  • Cliques: a set of fully connected vertices
  • Key structures in graph theory

​

​

​

​

​

33 of 39

From graphs to operator systems

  •  

34 of 39

Operator systems, quantum relations, and “quantum graphs”

  •  

35 of 39

Operator systems as quantum graphs

  • Some recent works by Nik Weaver
    • Quantum Turán and Ramsey theorems
    • Triangle-free quantum graphs
  • Some recent works by Mateusz Wasilewski
    • Connectivity for quantum graphs
    • Random quantum graphs
  • In 2025, Workshop on Quantum Graphs Saarland University, Saarbrücken, Germany
    • https://sites.google.com/view/quantum-graphs-25/home

36 of 39

Classical Ramsey theorem

  •  

R(3, 3)=6

R(3, 3)>5

37 of 39

A “quantum Ramsey” theorem

  •  

38 of 39

Summary

  • From graphs to quantum states or channels

Despite different temperaments, it is possible to “transfer” problems and methods from graphs to quantum states/channels

  1. From graph isomorphism �to quantum state equivalence relations
  2. From expander graphs �to quantum expanders (and more)
  3. From graphs to operator systems
  4. Many questions remain; please let me know (Youming.Qiao@uts.edu.au) if you want to discuss ☺

​

​

​

​

39 of 39

Thank you!

Questions please ☺