  The nonrecursive Bernstein-Vazirani algorithm was the first quantum algorithm
to show a superpolynomial improvement over the corresponding best classical
algorithm. Here we define a class of circuits that solve a particular case of
this problem for second-level recursion. This class of circuits simplifies the
number of gates $T$ required to construct the oracle by making it grow linearly
with the number of qubits in the problem. We find an application of this scheme
to quantum homomorphic encryption (QHE) which is an important cryptographic
technology useful for delegated quantum computation. It allows a remote server
to perform quantum computations on encrypted quantum data, so that the server
cannot know anything about the client's data. Liang developed QHE schemes with
perfect security, $\mathcal{F}$-homomorphism, no interaction between server and
client, and quasi-compactness bounded by $O(M)$ where M is the number of gates
$T$ in the circuit. Precisely these schemes are suitable for circuits with a
polynomial number of gates $T/T^{\dagger}$. Following these schemes, the
simplified circuits we have constructed can be evaluated homomorphically in an
efficient way.
