Exact result is #P-Hard, so we are looking for bounds.
Let $G$ be simple graph or simple digraph and $A$ its adjacency matrix. $A$ is $n \times n$ with entries only zeros or ones.
Let $K=\mathbb{Z}[x_1,x_2,\ldots x_n]$.
Define the Hamiltonian matrix of $G$ to be the matrix $M$ over $K$ with entries row $i$ of $A$ multiplied by $x_i$: $M_{1 \le i,j\le n}=x_i A_{i,j}$.
Let $f(x_1,...x_n)=(M^n)_{1,1}$.
If you prefer take $f_2=\frac1n \mathrm{tr}(M^n)$.
$f,f_2$ are homogeneous polynomials of degree $n$ and all the coefficients are nonnegative, so there is no cancellation.
$f,f_2$ are prohibitively large to be computed as sums of monomial, but it has succinct representation as arithmetic circuit. In addition CAS can compute it over other domains, including finite fields and possibly setting some of the variables to constants.
Let $H(G)$ the coefficient of $x_1 \cdot x_2 \cdots x_n$ in $f$ (or in $f_2$)
$H(G)$ counts the number of directed Hamiltonian cycles in $G$, if $G$ is undirected it is twice the number of undirected cycles.
Except for the monomial of $H(G)$, all other monomials are divisible by square.
If we could work efficiently in $K/[x_1^2,x_2^2...,x_n^2]$ $H$ will be the coefficient of the only remaining monomial, but many commuting nilpotent elements with efficient computations don't appear to exists.
Another approach, disproved by @Peter Taylor is to convert the multivariate case to univariate by setting $x_i= y^{g(i)}$ for some function $g(i)$.
It is tempting to try to use some case of "distinguished" property like purely real over the complex numbers.
Q1 What properties and bound can we get about $H(G)$ in subexponential in $n$ time and space?
Observe that this need not contradict Exponential Time Hypotheses (ETH) since the reduction SAT to Hamiltonian cycle need not be linear.
To clarify about subexponential comment. Assume $G$ is planar graph. Then the Treewidth of $G$ is $O(\sqrt{n})$ and Hamiltonian cycle ($H(G)>0$) can be solved in $O(\exp{\sqrt{n}})$. To our knowledge this doesn't contradict widely believed conjectures, it implies that there is no $o(n^2)$ reduction from SAT to HC in planar graph.
One very crude upper bound on $H(G)$ is setting $x_i=1$ and then take the integer result.
