Move `CX`, `CY`, and `CZ` operations into qsharp-runtime repo

[swernli]

Proposal title

Move CX, CY, and CZ operations into qsharp-runtime repo

Conceptual overview

Currently these operations are implemented as convenience wrappers around the operations available in Microsoft.Quantum.Intrinsic. However, moving them into the qsharp-runtime repo would allow for overriding them in target packages with target specific implementations that can be more direct and simpler. In particular, while CX and CNOT are equivalent such that a target that supports CNOT as a native intrinsic can just advise callers to use that, there is no equivalent for CZ and CY that allows a target to provide access to the native singly controlled Z and Y available on their platform. See below for more info.

Proposal

The optimization possible here has to do with the creation of an array of controls. Because the X, Y, and Z operations in Microsoft.Quantum.Intrinsic support an arbitrary number of controls, their controlled specializations accept an array of qubits. For targets that do not natively support arbitrary controls to a gate, these specializations must check the length of the array in order to decide which decomposition to utilize. This presupposes support for more complex runtime functionality and prevents certain kinds of optimization by existing LLVM tools when compiling for QIR. If the right alternatives are present, such as CNOT, they can be utilized in cases where the exact number of controls is known and map directly to underlying native hardware capabilities. This inspired the change to the decomposition of CNOT in microsoft/qsharp-runtime#773. However, CX still uses Controlled X([control], target) which necessarily involves creation of an array and then invocation of the more complex decomposition. Even more so, there is no CNOT equivalent for controlled Z or controlled Y, so such optimization is not available.

Alternatives considered

One alternative we could consider is leaving the existing operations in Microsoft.Quantum.Canon, deprecating them in favor of equivalent operations in Microsoft.Quantum.Intrinsic. This would be an API surface change, but since the two signatures would be the same it would be a very easy adjustment for users to make. The deprecated operations in Canon could be updated to just call the new operations in Intrinsic such that callers of either get the benefit of the target specific implementations mentioned above. Other than the low cost of fixing a deprecation warning and us remembering to remove the old operations after the appropriate time, this is an equivalent approach that I would be happy with. If this approach is preferable, a companion Issue can be filed in qsharp-runtime to implement the operations there and this Issue can be used to track adding the deprecation and redirect to the Canon operations.

[swernli]

@cgranade @bettinaheim FYI. The more I think about it, the more I start to prefer the option listed in Alternatives considered, but I'd appreciate your perspective and preferences here.