Optimize MPS simulator Pauli expectation value

[yaelbh]

Several suggestions to optimize Pauli expectation value in the MPS simulator:

1. Ignore identity gates.
2. Suppose that the Pauli term involves qubits 1 and 3. Currently there is a swap operation that brings them together, which may increase the tensors. Possibly better to insert identity on qubit 2 and calculate the expectation value on qubits 1, 2, 3 together.
3. Order the Pauli terms to minimize the swap operations between consecutive terms. For example, all terms with the same qubits should be processed in a sequence.
4. Consider saving the state before the expectation value, and returning it to the saved state after each Pauli term. This has the cost of copying the state for each term, on the other hand can save run time because each term may increase the state's size.

[yaelbh]

We tried (1) and (4) on a few benchmarks, and they were slow. Since (1) is slow, this implies that (2) is expected to improve. We also tried (3) and saw a speed-up, but it may become less important once (2) is done.

[merav-aharoni]

The current implementation in the code is (4). When I compared this to the original code, I saw no difference. I preferred this implementation for a few reasons. One of them is that it may allow parallelization of the terms of the expectation value.

[yaelbh]

Yes, I was wrong: (4) gave the same run time, (1) was much slower. Since (4) is selected, (3) is not relevant anymore.

[chriseclectic]

For a snapshot approach the Pauli expectation value should be able to be computed with an efficient local contraction on the MPS tensor without any copies or swaps.

Starting from one end of the tensor you would take inner product over each qubit tensor index with its conjugate tensor contracting with a Pauli (or just tracing for identity terms). Something like this (but with Pauli's added in)

[chriseclectic]

Here is some documentation for doing it in iTensor: http://itensor.org/docs.cgi?vers=julia&page=formulas/measure_mps

[merav-aharoni]

@chriseclectic , thanks for the suggestion, but this is already what we implemented in PR#344. The reason we do a copy of the MPS structure is because computing the expectation value destroys the structure of the MPS. This is needed because we may need to compute several expectation values (as in VQE), or for any case that computing the expectation value is not the last operation on the circuit.

[merav-aharoni]

A couple more suggestions for improvement:

1. Instead of swapping qubits to bring them together, add I gates on qubits that do not participate in the expectation value.
2. Check if rather than copying the MPS structure, we can only store the tensor computed during the contraction.

[yaelbh]

The first one is already listed above as (2): Suppose that the Pauli term involves qubits 1 and 3. Currently there is a swap operation that brings them together, which may increase the tensors. Possibly better to insert identity on qubit 2 and calculate the expectation value on qubits 1, 2, 3 together.

[chriseclectic]

I believe this was fixed by #812. Feel free to reopen @yaelbh @merav-aharoni if you think there are further optimizations to implement