How do I efficiently implement a POVM using a fixed universal gate set and the ability to measure in the standard basis?

Question

Let's say I am given a Hamiltonian

\begin{equation} H = \sum_{i = 1}^{m} H_{i}, \end{equation}

where $H$ acts on $n$-qubits, and each $H_{i}$ acts non-trivially on at most $k$ qubits. The eigenvalues of $H$ are between $0$ and $1$. As can be seen, $H$ is a $k$-local Hamiltonian. Now, let's say I am given any quantum state $|\psi\rangle$ over $n$ qubits. I want to implement the POVM

\begin{equation} \{H_{i}, \mathbb{1} - H_{i}\}. \end{equation}

1. How do I implement this POVM using a fixed universal gate set and the ability to measure in the standard basis? What is the unitary that I have to apply before measuring in the standard basis and how much error can I tolerate?
2. What is the guarantee this implementation is efficient?
3. Is there any rule regarding when implementing such POVMs is efficient?

Answer 1

What is the guarantee this implementation is efficient? Is there any rule regarding when implementing such POVMs is efficient?

The implementation of such a gate will only depend on the parameter $k$ (which I assume you mean to be fixed), not $n$. Since efficiency is generally phrased in terms of scaling with $n$, and you have no dependence on that, it is efficient.

How do I implement this POVM using a fixed universal gate set and the ability to measure in the standard basis? What is the unitary that I have to apply before measuring in the standard basis

Let $H_i=UDU^\dagger$, where $D$ is diagonal (with entries between 0 and 1 on the diagonal) and $U$ is a unitary. Apply $U^\dagger$ to the appropriate set of qubits. This now reduces you to the problem of performing the measurement $\{D,1-D\}$.

You'll need to introduce a single ancilla qubit, prepared in the $|0\rangle$ state. It is this ancilla that you will measure in the computational basis, with the two outcomes corresponding to the two different measurement operators. But before that, we need to construct a unitary between the original system (S) and the ancilla (A). Let $D=\sum_id_i|i\rangle\langle i|$, and let $V|i\rangle_S|0\rangle_A=\sqrt{d_i}|i\rangle|0\rangle+\sqrt{1-d_i}|i\rangle|1\rangle$. You can decompose this unitary via standard techniques. Apply $V$, and measure the ancilla.

To see that this works, let your input state be $|\psi\rangle=U\sum_i\alpha_i|i\rangle$. You sould get the measurement outcome with probaility $$ \langle\psi|H_i|\psi\rangle=\sum_i|\alpha_i|^2d_i. $$ This is what we need to check that we get. So, our simulation first applies $U^\dagger$, so we have $$ \sum_i\alpha_i|i\rangle_S|0\rangle_A. $$ We apply $V$ to prepare $$ |\Psi\rangle=\sum_i\alpha_i|i\rangle_S(\sqrt{d_i}|0\rangle_A+\sqrt{1-d_i}|1\rangle_A). $$ We calculate the probability of the 0 outcome: $$ \langle\Psi| 1_S\otimes|0\rangle\langle 0|_A|\Psi\rangle=\sum_i|\alpha_i|^2d_i, $$ as required.

Note that I've not worried about the state after the measurement because you've only specified a POVM, which immediately implies you're only interested in the measurement probability, not the output state.

and how much error can I tolerate?

This depends on what you mean, and is probably an entirely separate question to do justice to.