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:

enter image description here

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

  • 2
    $\begingroup$ 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. $\endgroup$
    – Mark S
    Apr 24 at 15:26
  • $\begingroup$ @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. $\endgroup$ Apr 24 at 15:30

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

The problem of calculating additive approximations of the Jones polynomial at the kth 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.

  • 1
    $\begingroup$ Also note that certain problems related to the Jones polynomial are DQC1-complete as well. $\endgroup$
    – Mark S
    Apr 29 at 1:48
  • $\begingroup$ Very good, thanks a lot. I thought that you needed a mixed-state for this kind of problem (hence using DQC1) but apparently you can also use a pure-state (hence Hadamard test). $\endgroup$ Apr 29 at 10:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.