Quantum AND gates (a.k.a. CCNOT with constant target)

[msoeken]

Is your feature request related to a problem? Please describe.

By using CCNOT gates when the target is known to be in a zero state, one looses optimization potential to reduce the number of T gates, as described in arXiv:1212.5069 and arXiv:1709.06648.

Describe the solution you'd like

I suggest to add operations

operation ANDOp (control1 : Qubit, control2 : Qubit, target : Qubit) : Unit

and

operation ANDOpLowDepth (control1 : Qubit, control2 : Qubit, target : Qubit) : Unit

which implement the circuits described in Fig. 3 in arXiv:1709.06648 and Fig. 1(a) in arXiv:1212.5069, respectively.

The signature allows the gates to be wrapped inside the CCNOTop type.

ANDOp requires 4 T gates, T depth 2, and no ancilla. ANDOpLowDepth requires 4 T gates, T depth 1, and one ancilla. No T gate is required in the adjoint operation due to measurement based uncomputation.

Describe alternatives you've considered

Implementing the operations as private operations.

Additional context

A possible implementation is illustrated in https://github.com/microsoft/Quantum/issues/121#issuecomment-461890337.

[christopherkang]

@msoeken I'd be happy to take this on! I think we definitely should consider putting this as a private operation - thinking about long-term hardware realizations, the final selection of CCNOT implementation will depend on the quantum chip itself. For the meantime, users shouldn't need to worry about the hardware level implementation.

[emzatos]

@christopherkang Could you describe how the implementation would change based on the underlying hardware?

[christopherkang]

@emzatos Sure! (full disclosure, definitely have less of a background on the realizations of gates on specific architectures.) Specifically, I'm thinking of quantum chips that may be able to more directly implement the Toffoli gate, in which case the above implementation is unnecessary. For example, arxiv:0804.0082 describes how an ion-trap computer can apply the Toffoli gate without needing to implement T gates.

[emzatos]

This is fascinating, thank you so much. Do you know how prevalent this sort of thing is? It may be useful to have some notion of an environment variable so we can cater to specific architectures within a method.

[christopherkang]

Right now, there aren't any clear 'winners' for quantum chips - the architectures we end up could be far different from the architectures we have now. I'm not familiar with how the available hardware differs in gate realizations, but creating that environment variable could be interesting! It might allow for comparison of algorithms on different quantum chips with constraints

[msoeken]

The different implementations of the Toffoli and AND gates may not only target different hardware architectures but also provide cost tradeoffs within the same architecture, e.g., trading qubits for circuit depth. Especially for the purpose of resource estimation it is convenient to be able to pass different implementations of Toffoli gates, even in the same algorithm. This can be done if the operation to call accepts a parameter of type CCNOTop to describe which implementation to use.

[christopherkang]

Could we alternatively designate different architectures with different types of simulators? I remember somewhere in the source code functionality for choosing different implementations based on the operation being called / type of simulator

[msoeken]

Fixed in #186.