Bug in the internal SpreadZ operation (used in Exp decomposition)

[jond01]

Describe the bug

I think that the internal SpreadZ operation has a bug in it:

qsharp-runtime/src/Simulation/TargetDefinitions/Decompositions/Utils.qs

Lines 7 to 16 in 70c881d

	internal operation SpreadZ (from : Qubit, to : Qubit[]) : Unit is Adj {
	if (Length(to) > 0) {
	CNOT(to[0], from);
	if (Length(to) > 1) {
	let half = Length(to) / 2;
	SpreadZ(to[0], to[half + 1 .. Length(to) - 1]);
	SpreadZ(from, to[1 .. half]);
	}
	}
	}

TL;DR: The CNOT in L9 should be called AFTER the recursive SpreadZ calls in L12-13.

This operation intends to sum up the parities from all the qubits to into the first qubit from. However, the second half of the to register (to[half + 1 .. Length(to) - 1] in L12) is summed up into to[0], and to[0] does not carry information into the from qubit after this stage.

I think that L9, which "transfers" the information from to[0] into from, should appear after L12, to sum up all the qubit parities correctly.

Here is an image of the SpreadZ circuit with four qubits in total:

We see that at the end of the circuit, q0 contains the parities of q0 + q1 + q2, but not q3.
If the first CNOT gate (=L9) is applied last, q0 would contain the parities from all the qubits - q0 + q1 + q2 + q3, as it should.

This image depicts a correct implementation:

The parity of q3 is transferred into q0 indirectly through the first and last CNOT gates.

---

Some context for this issue - I was interested in how Q# implements the Exp operation. I found out that:

1. When using a simulator (dotnet run, for example), the Exp operation is directly simulated, and the above decomposition isn't used. That's probably why this issue was unnoticed.
2. There is a possible implementation in this repository (qsharp-runtime):
   Exp -> ExpUtil -> SpreadZ.
   I suspect the SpreadZ operation is incorrect.

This issue may gain more importance in light of #999.

To Reproduce

As a toy problem, let's consider the following quantum algorithm with four qubits and one Exp operation with $Z\otimes Z\otimes Z\otimes Z$:

$$ \ket{0000} \xrightarrow{H_0} \frac{\ket{0000} + \ket{1000}}{\sqrt{2}} \xrightarrow{C_0 NOT_3} \frac{\ket{0000} + \ket{1001}}{\sqrt{2}} = \ket{\psi_0} $$

Now, let's apply the Exp([PauliZ, PauliZ, PauliZ, PauliZ], theta, _) operation $e^{i\theta Z\otimes Z\otimes Z\otimes Z} = Exp$ on $\ket{\psi_0}$.

$$ \ket{\psi_0} \xrightarrow{Exp} \frac{e^{i\theta_0}\ket{0000} + e^{i\theta_1}\ket{1001}}{\sqrt{2}} = \ket{\psi_1} $$

Expected behavior

Since both states in $\ket{\psi_0}$ (0000 and 1001) have even parity, we expect $\theta_0 = \theta_1 = \theta$.
Therefore,

$$ \ket{\psi_1} = e^{i\theta}\frac{\ket{0000} + \ket{1001}}{\sqrt{2}} \xrightarrow{C_0 NOT_3} e^{i\theta}\frac{\ket{0000} + \ket{1000}}{\sqrt{2}} = e^{i\theta} \ket{+000} \xrightarrow{H_0} e^{i\theta} \ket{0000} \xRightarrow{Measure_0} 0 $$

The first qubit is always measured to be 0.

Actual behavior

The parity of the last qubit isn't summed up - the states of $\ket{\psi_0}$ gain an opposite phase: $\theta_0 = \theta$ but $\theta_1 = -\theta$.
Specifically, for $\theta = \pi/2$:

$$ \ket{\psi_1} = e^{i\theta}\frac{\ket{0000} + e^{-2i\theta}\ket{1001}}{\sqrt{2}} = i\frac{\ket{0000} - \ket{1001}}{\sqrt{2}} \xrightarrow{C_0 NOT_3} i\frac{\ket{0000} - \ket{1000}}{\sqrt{2}} = i \ket{-000} \xrightarrow{H_0} i \ket{1000} \xRightarrow{Measure_0} 1 $$

And the first qubit is always measured to be 1.
Indeed, when abiding to the current SpreadZ implementation, the qubit is measured in the 1 state.

Q# code example

The following GitHub gist provides a Q# code that demonstrates the above problem:
https://gist.github.com/jond01/de5753e23542cead2786481f82d694a7

System information

• OS: macOS
• .NET Core Version: 6.0.202
• IQ# Version: 0.24.208024

[bettinaheim]

@msoeken @cgranade Could you please advice on this?

[cgranade]

On first glance, I'd agree this looks a bit wrong. Let me check with @swernli as well.

[swernli]

Yes, @jond01 is correct, this is a bug in SpreadZ that will affect any use of Exp on more than 3 qubits. @bettinaheim we should fix this and update the tests, which currently all test Exp using two qubits.