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


  • $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?

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.


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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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