Exponential advantage with Hadamard test

Question

My question is the following:

Let's assume that the only algorithm a quantum computer would be able to implement is the Hadamard test, which circuit is represented below, would we say that compared to the best known classical algorithms, the quantum computer would provide an exponential speedup to estimate $\langle \psi | U_n | \psi \rangle$, where $n$ is the number of qubits on which $U_n$ acts? I assume that the number of gates in $U_n$ grows polynomially with $n$.

If the answer is a "yes", I would be interested by some ref that claims it (i.e. that provides "convincing" arguments of why it is expected to be an exponentially hard problem classically). I know that it is nearly impossible to prove rigorously that a quantum computer solves in polynomial time a problem that will be exponential in time classically, this is why I am looking for "reasonable" arguments that for instance show that if a classical algorithm would be able to solve this task, it would imply that P=NP (which is unlikely to be true).

[edit]: As suggested in the comments, the one clean qubit model of computation (DQC1) is an example where the second register is a mixed state and there is an advantage "shown" (given my criteria) in this case. This is a good point, however, I am mainly interested in the case where the second register is pure.

I remind the Hadamard test circuit:

The circuit doing an Hadamard test is the following:

The density matrix of the first qubit before measurement is:

$$\rho=\frac{1}{2}(\sigma_0 + R_e(\langle \psi | U | \psi \rangle)\sigma_x + Im(\langle \psi | U | \psi \rangle) \sigma_y) $$

Hence, by repeating a polynomial number of time the experiment, one can access with a good accuracy the real and imaginary part of $\langle \psi | U | \psi \rangle$. (More precisely, we access it with accuracy $\epsilon$ for a number of runs being $\approx 1/\epsilon^2$).

Answer 1

The Aharonov–Jones–Landau (AJL) algorithm^[1] calculates an additive approximates of the Jones polynomial of the plat closure of a braid on $n$ strands with $m$ crossings at a k^th root of unity $e^{2\pi i/k}$ by encoding the braid structure into a unitary matrix that can be implemented as a quantum circuit whose size is polynomial in $n$, $m$, and $k$ then applying the Hadamard test on it.

The problem of calculating additive approximations of the Jones polynomial at the k^th root of unity is BQP-hard^{[2, 3]}. Which means that applying Hadamard test to a unitary implemented by a polynomial size circuit exhibits the full power of a quantum computer.