The AutoSubstitution rewrite step

Mathias Soeken

The June 2021 release comes with a new NuGet package called Microsoft.Quantum.AutoSubstitution which provides a rewrite step that allows you to substitute some Q# operations with alternatives dynamically depending on which simulator you use to execute them. This feature has been requested by users through feedback in Github.

This is best explained with a small example. Assume you have an implementation that swaps two qubits, in which all the CNOT operations have the target on the same qubit. Such an operation can be useful in an architecture that constrains the direction in which CNOT operations can be executed. This can be achieved in the following way:

operation ApplySingleDirectionSWAP(a : Qubit, b : Qubit) : Unit is Adj + Ctl {
    within {
        CNOT(a, b);
        H(a);
        H(b);
    } apply {
        CNOT(a, b);
    }
}

The operation is functionally equivalent to Microsoft.Quantum.Intrinsic.SWAP, however, the Toffoli simulator cannot execute it due to the non-classical Hadamard operation, whereas it can execute the SWAP operation. That means that we also cannot execute other classical operations (e.g., arithmetic operations) with the Toffoli simulator, if they make use of the ApplySingleDirectionSWAP operation.

In these situations, Microsoft.Quantum.AutoSubstitution can help by allowing us to instruct the Q# compiler to use the original SWAP operation as an alternative for our custom ApplySingleDirectionSWAP operation, whenever we execute the program with the Toffoli simulator. We simply need to add this information using an annotation:

open Microsoft.Quantum.Targeting;

@SubstitutableOnTarget("Microsoft.Quantum.Intrinsic.SWAP", "ToffoliSimulator")
operation ApplySingleDirectionSWAP(a : Qubit, b : Qubit) : Unit is Adj + Ctl {
    // ...
}

You need to add the dependency to Microsoft.Quantum.AutoSubstitution into your project file as a Q# reference

<PackageReference Include="Microsoft.Quantum.AutoSubstitution" Version="0.18.2106148911" IsQscReference="true" />

and open the Microsoft.Quantum.Targeting, which contains the SubstitutableOnTarget attribute. Note that for now, you must ensure that the alternative operation is referenced somewhere in the code. To be sure, you could add

let _ = Microsoft.Quantum.Intrinsic.SWAP;

as the first line of your operation ApplySingleDirectionSWAP. (This limitation will be resolved in our next release.) You can find a sample project that uses the new rewrite step in our samples repository.

Of course, this attribute is not limited to Toffoli simulator, but can be used with the other simulators from the QDK or using custom simulators. (Make sure to address custom simulators with their fully classified names.) Replacing operations with alternatives is also referred to as emulation. The new rewrite step makes this scenario much more accessible.

The package makes use of custom compilation steps, a technique that you can use to extend the compiler. If you are interested in the underlying techniques that support this new NuGet package, you find more information on extending the Q# compiler in this blog post.

Mathias Soeken Senior Software Engineer, Quantum

Follow