# Quantum algorithms on Graphs VS Quantum Graphs

1. Jul 13, 2012

### fedonman

Hello people,

i am an undergraduate student on computer science (so i don't have a strong background in physics) and i am very interested in quantum mechanics and its affection the way we see information. I am studying for my "thesis" (well it's not exactly thesis when you talk about undergraduate level) which is about quantum information/computation and quantum algorithms for several graph problems.

The thing is, i fell upon some lecture slide notes of Peter Kuchment about quantum graphs defining them as: "A quantum graph Γ is a metric graph equipped with a self-adjoint operator H." I must admit i find it very hard to understand his notes since it has some first encountered words like "Sobolev spaces".

My question is: What are the differences of quantum graph over the graphs we all know defined by graph theory? For example, can you say a quantum graph is Hamiltonian or traverse it? Any help would be appreciated!

2. Jul 13, 2012

### Physics Monkey

Hi fedonman,

Welcome to PF.

First off, it would be useful if you can give a link to these slides since it will probably help us decipher them.

Without knowing anything else, it sounds like "quantum graph" is here meant to be some kind of quantum system system where the degrees of freedom reside on the graph and interact in a way determined by the graph connectivity. However, that's still pretty vague, so details will be useful. In this way of speaking a quantum graph is a structure built on top of an ordinary graph.

3. Jul 13, 2012

### fedonman

Hi and thanks for the welcoming.

The notes can be found here. I have already seen the wiki page, but doesn't help much since the main reference of the article is the same notes...

4. Jul 13, 2012

### Physics Monkey

OK, well I can already decipher some of the notes.

You take a graph with a length assigned to each edge. You should think of each edge as like a square well of the given length. Then at each vertex you impose some kind of boundary condition. That could be that all wavefunctions vanish at the vertex so that each edge is like an infinite square well. More generally, you can consider various boundary conditions that couple the edges entering a given vertex together. For example, you could require that the probability current $\psi^\star \nabla \psi + ...$ for each edge, summed over all edges, vanishes at each vertex. A quantum graph is then a metric graph with the hilbert space defined as above from the edges, with hamiltonians for each edge, and finally with boundary conditions at all the vertices.

5. Jul 14, 2012