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).

: 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$$).

• Perhaps search for the one clean qubit model of computation. There are complete problems to calculate the real and imaginary trace of some unitary- the clean qubit isn’t entangled with the other target qubits, but nonetheless stores in its amplitudes a likely classically intractable computation. Apr 24 at 15:26
• @MarkS thank you for your answer. Actually I know DQC1 and there are such kinds of arguments indeed. However here I am interested in the case where the second register is pure. Apr 24 at 15:30

The Aharonov–Jones–Landau (AJL) algorithm calculates an additive approximates of the Jones polynomial of the plat closure of a braid on $$n$$ strands with $$m$$ crossings at a kth 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.