Quantum Cellular Automata on Riemannian manifolds and geometric group theory 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
http://arxiv.org/abs/1306.1934). 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}]$$ 
where


*

*$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_+)$).
Questions:


*

*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}$.]

*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}$.]

*Do there exist nontrivial IQCA qie in a $d$-dimensional manifold with $d=2,3$ and constant nonzero curvature?

 A: 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.
A: The structure you seek will not be represented clearly in matrices unless you have generated an ordering that imparts a quantum concept of distance; beyond that, so long as your basis is orthonormal, you can traverse all pairwise interactions. They can be described many ways...
You aren’t building a quasicrystalline quantum computer by any chance, are you?
