We propose definitions of $\QAC^0$, the quantum analog of the classical class $\AC^0$ of constant-depth circuits with AND and OR gates of arbitrary fan-in, and $\QACC^0[q]$, the analog of the class $\ACC^0[q]$ where $\Mod_q$ gates are also allowed. We show that it is possible to make a `cat' state on ... more >>>

We give a dichotomy theorem for the problem of counting homomorphisms to directed acyclic graphs. $H$ is a fixed directed acyclic graph. The problem is, given an input digraph $G$, how many homomorphisms are there from $G$ to $H$. We give a graph-theoretic classification, showing that for some digraphs $H$, ... more >>>

It has been shown that for every perfect matching $M$ of the $d$-dimensional $n$-vertex hypercube, $d\geq 2, n=2^d$, there exists a second perfect matching $M'$ such that the union of $M$ and $M'$ forms a Hamiltonian circuit of the $d$-dimensional hypercube. We prove a generalization of a special case of ... more >>>