$\DeclareMathOperator{\rk}{rk}$

Suppose that $A$ is a square matrix of order $n$. If, for any polynomials $P$ and $Q$ with $\deg P+\deg Q\le 2$, we have $$ P(A)\circ Q(A^t) = P(1)Q(1)\, I_n \tag{$\ast$} $$ (pointwise / Hadamard / Schur product in the left-hand side), then the basic inequality $\rk(B\circ C)\le\rk(B)\rk(C)$ readily gives $\rk(A)\ge\sqrt{n}$.

Notice that the present assumption "($\ast$) holds whenever $\deg P+\deg Q\le 2$" simply means that $A_{ii}=1$ and $A_{ij}A_{ji}=0$ for all $i,j\in[1,n],\ i\ne j$.

Assuming now that ($\ast$) actually holds true for any polynomials $P$ and $Q$ with $\deg P+\deg Q\le 3$, does it follow that $\rk(A)\ge n^{2/3}$?

A down-to-earth form of this question is as follows:

Suppose that $A$ is a square matrix of order $n$ with each element on the main diagonal equal to $1$. Given that for any $1\le i,j\le n$ with $i\ne j$ and $A_{ij}\ne 0$ we have $A_{ji}=0$ and also $(A^2)_{ji}=0$, does it follow that $\rk(A)\ge n^{2/3}$?

If $\rk(A)\ge n^{2/3}$ fails to hold, what is the smallest possible rank of $A$ under the stated condition?

For an upper bound, observe that if $A$ is a tensor power of the matrix $$ \begin{pmatrix} 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{pmatrix} $$ then $\rk(A)=n^c$ with $c=\log_43\approx 0.792$. (The fact that these tensor powers satisfy the assumptions follows from the identities $(B\otimes C)\circ(D\otimes E)=(B\circ D)\otimes(C\circ E)$ and $(B\otimes C)(D\otimes E)=(BD)\otimes(CE)$.)

In case it matters, the matrices I am interested in have all their elements in the set $\{0,\pm1\}$.