What is the smartest way of calculating the expectation value of some unitary $U$ in some state $|\psi\rangle$?

There are two ways I know:

  1. quantum phase estimation algorithm;
  2. Hadamard test.

Are there more efficient techniques to do that?

  • $\begingroup$ What are your conditions? Do you know what the state is? If not, how many copies of it do you have? $\endgroup$
    – DaftWullie
    Apr 30 '19 at 5:35
  • $\begingroup$ @DaftWullie The state $|\psi\rangle$ and the unitary $U$ are known, and it is assumed that we can prepare the infinite number of the copies of $|\psi\rangle$. $\endgroup$ Apr 30 '19 at 11:49

Since the state $|\psi\rangle$ is known, we can assume that we have a preparation procedure that takes some standard state (call it $|0\rangle$, although in general it will be composed of many qubits). Thus, there is a unitary $V$ such that $$ V|0\rangle=|\psi\rangle. $$

In that case, to measure $|\langle\psi|U|\psi\rangle|^2$, we simply follow the procedure

  1. Prepare $|0\rangle$
  2. Apply $V$
  3. Apply $U$
  4. Apply $V^\dagger$
  5. Measure in a basis for which $0\rangle$ is one of the elements
  6. Repeat until you have a suitably accurate estimate of the probability of getting the answer $|0\rangle$.

This probability is your answer.

If you want $\langle\psi|U|\psi\rangle$, the Hadamard test is probably your best bet. Yes, it requires controlled-$U$, but you're going to need something like that. This is because there's no observable difference between $U$ and $e^{i\theta}U$, so nothing you do can access the phase of $\langle\psi|U|\psi\rangle$ (but there is a difference between controlled-$U$ and controlled-$e^{i\theta}U$).


To find modulus of that expectation value you can use swap test on $|\psi\rangle \otimes U|\psi\rangle$.
I doubt there are simpler ways since $\langle \psi |U|\psi\rangle$ is complex in general.

Also note, that both algorithms you mentioned require access to the controlled version of $U$. But you can't construct circuit for controlled $U$ if $U$ is given as blackbox. Though there are ways to physically implement controlled version. See here.

  • $\begingroup$ Thanks for the answer! But as I know there is a technique to control an arbitrary unitary operation by using the qudits of dimension 4 instead of qubits. Please see this. $\endgroup$ Apr 30 '19 at 11:49

A bit late on this question, but for what it's worth, I recently put a paper on the arXiv which shows how to estimate $\langle\psi|U|\psi\rangle$ quadratically faster than the Hadamard test. https://arxiv.org/abs/2102.04975

A quick summary of the relevant part of the paper (without providing much intuition):

The algorithm uses two registers, one containing a single ancilla qubit and the other is the main quantum system. Let's define the following operations on the two-register system: $$\textbf{U} = |0\rangle\langle0| \otimes U + |1\rangle\langle1| \otimes U^\dagger$$ $$\textbf{S} = 2|+,\psi\rangle\langle+,\psi| - \textbf{I}$$ $$\textbf{Q} = [X\otimes I] \textbf{S} \textbf{U}$$ The $\textbf{U}$ operation acts $U$ on the system if the ancilla is $0$, and $U^\dagger$ if the ancilla is 1. The operation $\textbf{Q}$ can be implemented using $\mathcal{O}(1)$ calls to controlled-$U$ and the circuit that creates $|\psi\rangle$.

Let $\cos(\theta) \equiv \mathrm{Re}[\langle\psi|U|\psi\rangle]$. The key idea is that running QPE with $\textbf{Q}$ as the unitary and $|+,\psi\rangle$ as the input state, will return either $\theta$ or $2\pi-\theta$. SInce, $\cos(\theta) = \cos(2\pi-\theta) = \mathrm{Re}[\langle\psi|U|\psi\rangle]$, this completes the estimation of the real part. One can also get the imaginary part using the same algorithm by noting that $Im[\langle\psi|U|\psi\rangle] = Re[\langle\psi|e^{-i\pi/2}U|\psi\rangle]$.

This algorithm inherits the quadratic speedup of QPE. The error in the estimate scales as $\mathcal{O}(1/q)$ in the number of calls $q$ to the operation $\textbf{Q}$.


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.