Dependencies for unused specializations are pruned, causing compilation failures

[swernli]

The call graph design includes the functionality to trim to a concrete call graph that includes only those callables that are part of the entrypoint dependency tree. However, this means that if a given callable has a specialization that is unused, any callables only referred to in that specialization will have no edges and will not be included in the concrete graph, even though the specialization itself is not pruned. The end result is that the specialization will use types corresponding to callabes that are not generated, resulting in a compilation failure.

To see this in action, create a stand-along executable project using the latest release (0.14.2011120240), and the following code:

    @EntryPoint()
    operation Test() : Result {
        using (q = Qubit()) {
            ApplyPauli([PauliX], [q]);
            return M(q);
        }
    }

If you add an execution target to the project file that triggers classical control lifting and monomorphization, such as <ExecutionTarget>honeywell.test</ExecutionTarget>, the compilation of the generated C# will fail due to missing type definitions:

obj\qsharp\src\Microsoft.Quantum.Standard.g.cs(282,19): error CS0246: The type or namespace name '_dc509b171dd743d58d632169c29726fe_ApplyPauli' could not be found (are you missing a using directive or an assembly reference?)

This is because ApplyPauli has if-statements that turn into multiple callables via classical control lifting, and then because the controlled, adjoint, and controlled-adjoint specializations are unused, those generated callabes are removed. This leaves the call locations in place (the specializations themselves are not pruned, by design), while the dependent types for the lifted callables are missing.

The code that handles adding edges for a call (found in ConcreteCallGraphWalker.cs) will only add an edge to the specialization actually used in a call. If instead it is a non-call usage, like setting the callable to a variable, then all specializations get an edge. So if the above code is changed to:

    @EntryPoint()
    operation Test() : Result {
        using (q = Qubit()) {
            let op = ApplyPauli;
            op([PauliX], [q]);
            return M(q);
        }
    }

the compilation will succeed.

[ScottCarda-MS]

One of the assumptions given during the design discussions for the call graph was that all specializations of the same callable would refer to the same callables. At the time, it was said that if this was violated, then the specialization wasn't valid. Are we now seeing a case where this assumption is not true but in a case that we still need to support? If that assumption is no longer valid, than the design of the call graph needs to be carefully thought through to accommodate the change to the design.

[swernli]

That's a good question. With decompositions, it's certainly possible the controlled specialization will involve callables that are not used by the body or adjoint, and there would be no reason to call them anywhere but the controlled (see ZFromSinglyControlled.cs as an example of this). If that is not valid, then we would need to rethink our approach to decomposition.

But even without explicitly different implementations, the combination with other rewrite steps may cause the implementations to deviate, though perhaps that is a different bug. Take the example from the issue, ApplyPauli. That operation has a single body and is declared adjoint invert. But when combined with classical control lifting, the conditionals in the body get lifted into one set of callables while the conditionals in the generated adjoint get lifted into different callables. Now an operation whose body and adjoint originally had the same dependency graph actually have different sets of dependencies because of how a rewrite step was applied.

[ScottCarda-MS]

Fix merged into main with #809.