Shared abstraction for booleans and qubits

[bamarsha]

From microsoft/qsharp-language#58:

Suggestion

When writing arithmetic code, there is a tendency to repeat the same method multiple times based on whether certain inputs are quantum or classical. For example, you would have one method for xoring a LittleEndian into another LittleEndian, and a separate method for xoring a BigInt into a LittleEndian. It would be convenient if there was instead a xor method that accepted a BigIntOrLittleEndian and handled both cases.

This doesn't just apply at the level of designing methods. It also occurs when writing methods. For example, suppose you are creating a binary tree of qubits representing the AND of leaf input qubits as follows:

let n = Length(input_qubits);
using (work_qubits = Qubit[n-1]) {
    let qs = input_qubits + work_qubits;
    for (i in 0..n-2) {
        CCX(qs[2*i], qs[2*i+1], qs[n+i]);
    }

One of the problems you will run into is that if n is not guaranteed to be a power of 2, then the qubit at position n+n/2 is talking about a mix of leaf qubits at the end of the input and intermediate node qubits representing leaf qubits at the start of the input. To fix this, you can pad out to a power of 2:

let n = CeilPow2(Length(input_qubits));
using (work_qubits = Qubit[2*n-Length(input_qubits)]) {
    let qs = input_qubits + work_qubits;
    for (i in 0..n-2) {
        CCX(qs[2*i], qs[2*i+1], qs[n+i]);
    }

The problem now is that you are allocating unnecessary qubits to simplify your code. But if you were able to make an array of qubits-or-bits, and CCX understood that when one of its controls was a bit it should become a CX or no-op as appropriate, then you could do this:

let n = CeilPow2(Length(input_qubits));
let padding = RepeatArray(n - Length(input_qubits), False);
using (work_qubits = Qubit[n-1) {
    let qs = input_qubits + padding + work_qubits;
    for (i in 0..n-2) {
        CCX(qs[2*i], qs[2*i+1], qs[n+i]);
    }

And everything would just work. Although to be fair this is still not perfect; the unnecessary allocation is half as large but still there.

Considerations

This is a bit tricky to add to the language because at the moment the language is very picky about types. There's no way to say "this array contains a mix of qubits and bits", or "the control of this method can be a qubit or a bit".