One approach to get the expectation value $\langle\psi|P\psi\rangle$ of a pauli string $P\in \{I, X, Y, X\}^{\otimes n}$ is the following.

  1. Let $(a_i, |\lambda_i\rangle)$ be eigenvalue-eigenvector pair of $P$ where $a_i\in \{0, 1\}$ as $P$ is unitary. We may write $$P = \sum_i a_i|\lambda_i\rangle\langle\lambda_i|$$ so it follows that $$\langle\psi|P\psi\rangle = \sum_i a_i|\langle\lambda_i|\psi\rangle|^2.$$
  2. We can thus perform a change of basis measure in the $|\lambda_i\rangle$ basis to recover the coefficients $|\langle\lambda_i|\psi\rangle|^2$ via repeated sampling.
  3. Evaluate the sum in step 1.

My questions about this are:

  1. How are we sampling? ie. Do we measure each of the $n$ qubits "separately" and estimate $p_0, p_1$ in $p_0|0\rangle + p_1|1\rangle$? This would lead to us adding $2^n$ numbers in step 3, so I don't think this is the case. Do we measure each outcome $|x_1\dots x_n\rangle$ and estimate its probability $|\langle\lambda_i|\psi\rangle|^2$ directly?
  2. If we measure each outcome and estimate $|\langle\lambda_i|\psi\rangle|^2$ directly, how many repeated measurements do we need to obtain accuracy within $\epsilon$? If we perform a polynomial number of measurements, most of our estimates for $|\langle\lambda_i|\psi\rangle|^2$ will be $0.$

1 Answer 1


I think we could get the estimate of $\langle \psi | P | \psi \rangle $ using your method in the following way.

Let's assume that we know the eigenvalue decomposition (https://en.wikipedia.org/wiki/Eigendecomposition_of_a_matrix) of the Pauli chain, i.e we know $Q$ and $\Lambda$ in :

$$ P = Q \Lambda Q^{\dagger}$$

where $\Lambda$ is a diagonal matrix with the eigenvalues and $Q$ is a unitary matrix with the eigenvectors. The expected value over the state $|\psi\rangle$ becomes:

$$ \langle \psi | P | \psi \rangle = \langle \psi | Q \Lambda Q^{\dagger} | \psi \rangle $$

This is what I think you have written in equation $⟨ψ|P|ψ⟩=\sum_i a_i|⟨\lambda_i|ψ⟩|^2$. In order to answer your questions:

  1. Let's define $|\varphi \rangle = Q^\dagger |\psi\rangle $, the expected value becomes:

$$ \langle \psi | Q \Lambda Q^{\dagger} | \psi \rangle = \langle \varphi |\Lambda|\varphi \rangle$$

Now, given that we know $Q$ we can create a circuit that applies $Q^\dagger$ to the state $|\psi\rangle$. Then we should sample the outcome of this circuit, i.e measure all the n qubits and estimate the probability of outcome of each state $|i\rangle$ with $i = 0, 1, \dots, 2^n - 1$. Each probability would be in fact the coefficient $|⟨\lambda_i|ψ⟩|^2$ that we were looking for. You would get indeed $2^n$ numbers. Finally, it would be enough to compute the sum $\sum_i a_i|⟨\lambda_i|ψ⟩|^2$ to get the expected value.

  1. You can find information about the precision in the estimation of these coefficients as a function of the number of samples in these questions:

When increase the shot, why the result is different?

How many shots should one take to get a reliable estimate in a quantum program?

Now, having said this. There is a more efficient method to estimate the expected value of a unitary operator. The Hadamard test (https://en.wikipedia.org/wiki/Hadamard_test_(quantum_computation) ). It uses this circuit:


In short, it allows you to compute the real part of the expected value $\langle \psi |U | \psi \rangle$ using the difference between the probabilities of measurement of the ancilla qubit (the one at the top), i.e:

$$ \mathcal{Re}{\langle \psi |U|\psi \rangle } = p_0 - p_1$$

It is also possible to compute the imaginary part by adding a phase gate with angle $-\pi/2$ in the ancilla qubit. So, if you replace U in the circuit with your Pauli chain P, you can compute $ \langle \psi | P | \psi \rangle$ without sampling $2^n$ probabilities. You would only have to sample 4, 2 for the real part, and 2 for the imaginary part.

  • $\begingroup$ Is doing a Hadamard test more efficient? Wouldn't doing a controlled-P operation be messy and use a lot more gates? $\endgroup$ Commented May 20, 2022 at 0:29
  • 1
    $\begingroup$ In order to implement the controlled-P operator, you would only have to apply a control Pauli gate for each qubit. So $n$ controlled Pauli gates for each operator control-P. The other option is to apply the circuit $Q^\dagger$ to the state $\psi$, this presents a couple of problems: 1. You would have to do classically the decomposition $P = Q\Lambda Q^\dagger$ and then find a circuit that implements $Q^\dagger$ which could be quite expensive to implement. 2. The bigger the $n$ the more measurements you would have to do in order to obtain a meaningful estimation of the probabilities. $\endgroup$ Commented May 20, 2022 at 8:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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