Add three qubit `AND` operation to public API

[swernli]

The change in https://github.com/microsoft/qsharp/pull/1202 adds an AND internal helper for use with decomposition of multi-controlled operations that is more efficient than PhaseCCX and is very similar to ApplyAndAssuming0Target internal helper from the unstable arithmetic namespace. Both of these are capturing a common pattern, which is to use an optimized decomposition of a reversible AND on three qubits that is better for resource estimation and simulation. Further, there is interest in making AND a body intrinsic operation that generates to a gate in QIR so that backend providers are free to implement the operation in whatever way is most efficient on their hardware. We need to coordinate the effort here and make sure we have a cohesive plan for how to expose AND publicly from the standard library and how to expand the set of QIR intrinsics to include the notion of AND as distinct from a Toffoli/CCNOT.

Let's use this issue to discuss requirements, concerns, and staging for the change.

[swernli]

@DmitryVasilevsky @tcNickolas @msoeken for FYI. I want to find the right way to get this public so it's easier to use in algorithms without having to redefine it in each program/namespace. And based on previous discussions, it sounds like we also need to expose it as intrinsic in QIR, but that might require a staged approach so that we don't start generating QIR with a new instruction before partners or the service can correctly handle it.

I'm concerned about the measurement-based adjoint though; this seems to be a very clever uncomputation that is useful for optimizing algorithms when properly invoked but not really an operation in its own right. For example, the documentation on ApplyAndAssuming0Target says it "Applies AND gate between control1 and control2 and stores the result in target assuming target is in the |0⟩ state." But that restriction on the target does not (and must not) apply to the adjoint, right? To work as the reverse operation, Adjoint ApplyAndAssuming0Target doesn't assume the target is in the zero state but instead has a different, far more subtle assumption: that the three qubits it's operating on are the same two controls and target that were operated on by ApplyAndAssuming0Target. That means that AND and Adjoint AND must always be used together, which is hard to explain in a comment and not really how Q# functors work. Adjoint S can be invoked anytime and is expected to always be the equivalent of applying the adjoint of the unitary operation S, but Adjoint AND breaks that convention and any use of Adjoint AND outside of uncomputing AND on the same qubits is technically wrong. I know we can't enforce that, and I'm not even sure how to describe that to users in a succinct fashion.

Thinking about how we would eventually expose this in QIR, it makes me wonder whether it really needs to become two operations: __quantum__qis__and__body and __quantum__qis__and__adj. This allows the choice of adjoint implementation (Toffoli, measurement based, or otherwise) to be something the provider links in. But there we have the same problem, in that the and_adj variant is a function in its own right that can be called any time and is not restricted to "correct" usages where it applies to qubits that have already gone through and__body.

Perhaps I'm overthinking it, but it feels odd to have an operation whose body follows the restriction in the doc comment but whose adjoint doesn't and where the adjoint has restrictions that differ from almost all other Q# operations that correspond to gates.

[msoeken]

@DmitryVasilevsky @tcNickolas @msoeken for FYI. I want to find the right way to get this public so it's easier to use in algorithms without having to redefine it in each program/namespace. And based on previous discussions, it sounds like we also need to expose it as intrinsic in QIR, but that might require a staged approach so that we don't start generating QIR with a new instruction before partners or the service can correctly handle it.

I'm concerned about the measurement-based adjoint though; this seems to be a very clever uncomputation that is useful for optimizing algorithms when properly invoked but not really an operation in its own right. For example, the documentation on ApplyAndAssuming0Target says it "Applies AND gate between control1 and control2 and stores the result in target assuming target is in the |0⟩ state." But that restriction on the target does not (and must not) apply to the adjoint, right? To work as the reverse operation, Adjoint ApplyAndAssuming0Target doesn't assume the target is in the zero state but instead has a different, far more subtle assumption: that the three qubits it's operating on are the same two controls and target that were operated on by ApplyAndAssuming0Target. That means that AND and Adjoint AND must always be used together, which is hard to explain in a comment and not really how Q# functors work. Adjoint S can be invoked anytime and is expected to always be the equivalent of applying the adjoint of the unitary operation S, but Adjoint AND breaks that convention and any use of Adjoint AND outside of uncomputing AND on the same qubits is technically wrong. I know we can't enforce that, and I'm not even sure how to describe that to users in a succinct fashion.

Thinking about how we would eventually expose this in QIR, it makes me wonder whether it really needs to become two operations: __quantum__qis__and__body and __quantum__qis__and__adj. This allows the choice of adjoint implementation (Toffoli, measurement based, or otherwise) to be something the provider links in. But there we have the same problem, in that the and_adj variant is a function in its own right that can be called any time and is not restricted to "correct" usages where it applies to qubits that have already gone through and__body.

Perhaps I'm overthinking it, but it feels odd to have an operation whose body follows the restriction in the doc comment but whose adjoint doesn't and where the adjoint has restrictions that differ from almost all other Q# operations that correspond to gates.

The body variant assumes that the target is in state |0⟩ before the operation is called. The adjoint variant assumes that the target is in state |0⟩ after the operation is called. Therefore, both parts of the operation are consistent with respect to the assumptions, we just need to make it more clear in the documentation.

Measurement-based uncomputation is not an uncommon operation. See the implementation of Select (https://github.com/microsoft/qsharp/blob/5758cb19cacc39f57e94569bf31fc372f16e5324/library/std/unstable_table_lookup.qs#L48), in which the adjoint variant is implemented using the operation Unlookup, which uses mid-circuit measurement for an optimized operation.

[swernli]

Thanks for the additional details, I think this explanation is exactly what I was looking for. Given that, I think we can find the right way to document this and get it added to Microsoft.Quantum.Intrinsic. Then either with this issue or a follow up take on the longer task of having it become a QIR intrinsic instruction.

[minestarks]

@Manvi-Agrawal I want to assign this issue to you, but I think you need to comment on this post first. Could you just comment on this post so GitHub will let me assign to you?

[Manvi-Agrawal]

@minestarks commenting so that you can assign issue to me. Thanks

[minestarks]

Congrats on closing our first UnitaryHACK bounty issue @Manvi-Agrawal ! :)

[Manvi-Agrawal]

Nice to close this issue. Thanks @swernli @minestarks @tcNickolas for the support.