Conditional results implying difficulty of improving upper/lower bounds for permanent
An upper bound of $O(2^{n^{\epsilon}})$ may not be possible for any $\epsilon&lt;1$ unless the Exponential Time Hypothesis (ETH) is false, see

Holger Dell, Thore Husfeldt, and Martin Wahlén.
Exponential time complexity of the permanent and the Tutte polynomial.
Full paper at ECCC TR10-78. http://eccc.hpi-web.de/report/2010/078/

That is, if your embedding of the $n\times n$ permanent into a determinant of size $O(2^{n^{\epsilon}})\times O(2^{n^{\epsilon}})$ is fast enough, you could

Transform a 3SAT-instance to a permanent as in the paper above

Transform the permanent to a determinant over the larger matrix

Compute the determinant to find the number of solutions to the
original 3SAT-instance.


The running time for an $n$-variate 3SAT instance would be $O(2^{n^{\epsilon'}})$ for some $\epsilon'&lt;1$ depending on $\epsilon$ if step (2) is fast enough (say polynomial in n for each entry of the larger matrix). This would contradict the ETH.