TraceSimulator and ResourcesEstimator depth is incorrect with measurements

[sam-jaques]

Describe the bug

Measurements can create an ordering on operations. If a gate is to be applied to qubit 2 based on the outcome of measuring qubit 1, all gates on qubit 1 prior to that measurement must be completed before the gate is applied to qubit 2. This means measurements can have large dependencies in the call graph of a quantum program.

The depth counter in the trace simulator does not detect such dependencies. My guess: the call graph it constructs based on quantum gates treats a measurement as a single-qubit gate, and classical operations in Q# are not incorporated into the call graph.

To Reproduce

This code demonstrates the phenomenon (the assertion is to ensure that the trace simulator knows that the measurement outcome is unknown).

operation MeasureDepth() : Unit {
        use qubits = Qubit[3] {
            T(qubits[0]);
            let m = M(qubits[0]);
            Microsoft.Quantum.Diagnostics.AssertMeasurementProbability([PauliZ], [qubits[0]], Zero, 1.0, "Must measure 0", 1e-10);

            if m == One {
                T(qubits[1]);
            } else {
                T(qubits[2]);
            }
        }
    }

Expected behavior

The T-depth should be 2, since the operation cannot decide which qubit to apply the second T-gate onto until the measurement is finished.

Actual behavior

The TraceSimulator, when using the depth counter with optimizeDepth set to false, outputs a T-depth of 1. The ResourcesEstimator (when giving the same config as the TraceSimulator) does the same thing.

System information

• OS: Ubuntu 20.04

• Quantum SDK Version: 0.27.23833

• .NET Core Version: 6.0.300

Additional context
Q#, especially with the sparse simulator, could be the best tool available for prototyping, testing, and resource counting for optimized circuit methods like measurement-based uncomputation, coset representations, "ghost" pebbling, etc. However, many of these have measurement feedback. If the resource estimator is incorrect for these circuits in particular, then Q# doesn't help.

In this paper¹using Q# for resource estimates, the T-depth for AES-192 is less than AES-128, despite AES-192 using 12 rounds and AES-128 using only 10. This may be a consequence of this bug: these circuits depend on a measurement-based uncomputation of an AND gate, as follows:

H(target);
AssertMeasurementProbability([PauliZ], [target], One, 0.5, "Probability of the measurement must be 0.5", 1e-10);
if (IsResultOne(M(target))) {
    S(control1);
    S(control2);
    CNOT(control1, control2);
    Adjoint S(control2);
    CNOT(control1, control2);
    X(target);
}

Given this bug, the trace simulator could commute the clean-up on the two controls to a point long before this uncomputation, leading to these results.

This is already referenced on page 74 of ². However, the issue could be even worse than that. Consider

use qubits = qubit[5] {
   AND(qubits[0], qubits[1], qubits[2]);
   AND(qubits[2], qubits[3], qubits[4]);
  (Adjoint AND)(qubits[0], qubits[1], qubits [2]);
}

The depth of this circuit (counting all gates as depth 1) should be twice the depth of a forward AND, plus the depth of an adjoint AND. However, the operations on the control could commute backwards and run in parallel to the other operations. See the following circuit diagrams, with dotted lines to represent time steps when all gates have equal depth:

compared to the depth when the measurement dependencies are ignored:

The correct depth should be 18 (the top circuit), but the trace simulator outputs 15 (the bottom circuit).

Also, these dependencies could get arbitrarily complicated, if the Q# code proceeded to compute many variables based on the output of a measurement and then conditioned different gates on these other variables. It seems to me like the depth counter's call graph needs to extend to all variables in a Q# operation.

References

Footnotes

1. Samuel Jaques, Michael Naehrig, Martin Roetteler, and Fernando Virdia, "Implementing Grover oracles for quantum key search on AES and LowMC".
   Preprint available at https://eprint.iacr.org/2019/1146. ↩

2. Fernando Virdia. "Post-quantum cryptography: Cryptanalysis and Implementaiton". Available at https://fundamental.domains/2021virdiafphd.pdf. ↩