MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

We try to motivate our question. We have a certain logical/operational structure that has an emergent physical interpretation. We are giving this structure a geometric setting via quasi-isometries. We wonder what restrictions the structure places on the possible geometric settings. We know that the set of solutions to our problem is not empty (see preprint The question seems relevant in connecting a new topic in physics (emergent space-time from discrete Planck scale) with a new topic in math: geometric-group-theory. Quantum cellular automata seem to "physically" achieve the quasi-isometric embedding of geometric-group theory. If you are interested in the physics, look at the link above.

In the following $\mathbb{C}$ denotes the set of complex numbers, $\mathbb{M}_n(\mathbb{C})$ the $n\times n$ complex matrices, $A^\dagger$ the adjoint of matrix $A$.

Let's call Isotropic Quantum Cellular Automaton (IQCA) the set $$[G,S_+,L,T,U, [A_h]_{h\in S}]$$


  • $G$ is a (countable generally infinite) group that is finitely generated
  • $S_+$ is a finite set of generators for a $G$ (we will denote by $S_-:=S_+^{-1}$, and we let $S=S_+\sqcup S_-\sqcup\{e\}$, with $e$ the identity of $G$)
  • $L$ is a finite subgroup of the automorphism group of $G$. The action of $L$ preserves $S_+$ as a set, and is transitive on $S_+$
  • $T$ is a faithful irreducible unitary representation of $G$ on the separable Hilbert space ${\ell}^2(G)$
  • $V$ is a faithful irreducible unitary representation of $L$ on the Hilbert space $\mathbb{C}^n$, for some $n<\infty$ (for $n=1$ the IQCA is called trivial)
  • $\{A_h\}_{h\in S}\subseteq\mathbb{M}_n(\mathbb{C})$ (called transition matrices)
  • the following operator is unitary over ${\ell}^2(G)\otimes\mathbb{C}^n$: \begin{equation} A=\sum_{h\in S}T(h)\otimes A_h \end{equation} and is covariant under $V(L)$, namely \begin{equation} \sum_{h\in S}T(h)\otimes A_h=\sum_{h\in S}T(lh)\otimes V(l)A_hV(l)^\dagger,\quad\forall l\in L. \end{equation}

We are interested only in nontrivial IQCA. We say that the IQCA is quasi-isometrically embeddable (qie) in a $d$-dimensional Riemannian manifold $M^d$ if the Cayley graph $\Gamma(G,S_+)$ has a one-to-one quasi-isometry to $M^d$ (we use the word metric on $\Gamma(G,S_+)$).


  1. Are there necessary conditions so that for a given $G,S_+,L$ there exists a non trivial IQCA? [Simpler: replace $M^d$ by $\mathbb{R^3}$.]
  2. Are there sufficient conditions so that for a given $G,S_+,L$ there exists a non trivial IQCA? [Simpler: replace $M^d$ by $\mathbb{R^3}$.]
  3. Do there exist nontrivial IQCA qie in a $d$-dimensional manifold with $d=2,3$ and constant nonzero curvature?
share|cite|improve this question

Here is an answer to question 1; the answer is conditional on the following three assumptions: (i) IQCA's provide a framework for quantum gravity, as suggested in G.M. D'Ariano, "The Dirac quantum automaton: a preview" (arXiv:1211.2479); (ii) the quantum gravity path integral takes the form of a CFT partition function, as in A. Castro et al., "The gravity dual of the Ising model" (arXiv:1111.1987); and (iii) the existence of Hilbert-space representations of G and L is a necessary or essential feature of IQCA's (which is suggested by the definitions of T and V in the above question).

If (i)-(iii) hold, then a necessary condition for a non-trivial IQCA is that p<5, for the (integer) parameter p of the relevant conformal field theory (CFT). This is so because for p>4, the CFT lacks a consistent Hilbert-space interpretation: see arXiv:1111.1987 (pg. 4).

The above condition strongly restricts the allowable CFT's. Therefore, it might be a good idea to define IQCA's in a more general way that does not make reference to Hilbert space.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.