Reduction loops

[cgranade]

Suggestion

Currently, Q# provides several looping structures (for, repeat/until, and while) that specify specific control flow ordering, but does not provide any looping structures allow developers to specify data flow dependencies instead. This proposal introduces a new kind of loop, reduce, in which iterations do not have a strict execution order, but that each contribute values to a larger calculation.

By analogy to existing classical approaches such as OpenMP, such reduction loops can be used to help take advantage of parallelism with respect to classical processors, or even with respect to quantum devices.

Considerations

This proposal extends control-flow loops to include data-flow, allowing Q# to include concepts such as list comprehensions and the flatmap monad, as well as concepts unique to quantum computing such as "shots" of circuit-like subroutines.

There are a number of alternatives one could consider as well:

• Conventional for loops, decorated with attributes or #pragma-like metadata
• Loops with hard-coded reduction functions (e.g.: sum, mean, etc.)

This proposal advances a more general version of the above based on ideas from OpenMP- and MapReduce-style parallelism. The suggestion made in this proposal can be made either as a statement that includes a new form of binding (adding to let, mutable, use, and borrow), or as an expression that can be used with existing let and mutable bindings as well as with return. Using expression-based notation would be more difficult to implement given Q#'s current statement-driven focus, but would be more parsimonious with other existing syntax such as let and return.

Context

The syntax used in these examples assumes QEP #4 as well as a way of indicating device qubit literals (i.e.: #0).

This proposal recommends that custom reduction functions must be denoted either @AssociativeReduction or @BatchReduction, in either case allowing for parallelism to be split across multiple devices. The examples below present a few custom reduction functions, with more details to be written in a formal proposal.

Examples

Example 1:
Summing over the first 𝑛 squares (statement-based notation).

function SumOfSquares(n : Int) : Int {
    reduce sum = PlusI over _ in 1..n {
        yield idx * idx;
    }
    return sum;
}

Example 2:
Summing over the first 𝑛 squares (expression-based notation).

function SumOfSquares(n : Int) : Int {
    return reduce PlusI over _ in 1..n {
        yield idx * idx;
    };
}

Example 3:
Using reduction expressions as list comprehensions.

// Assuming the following library code, and using QEP 5 syntax:
@BatchReduction()
function Collected<'TElement>(prevStates : [['TElement]], newBatch : ['TElement]) : 'TElement {
    return newBatch + reduce PlusA over state in prevStates { yield state; };
}

// # Basic list comprehension
let ys = reduce Collected over x in 1..10 { yield x * x; };
// Equivalent to Python:
// ys = [x ** 2 for x in range(10)]

// # List comprehension with filtering
let ys = reduce Collected over x in 1..10 { if x % 2 == 0 { yield x * x; } };
// Equivalent to Python:
// ys = [x ** 2 for x in range(10) if x % 2 == 0]

// # Flatmap list comprehensions
let ys = reduce Collected over x in 1..10 {
    yield x * x;
    yield x * x * x;
};
// Equivalent to Python:
// ys = sum([[x ** 2, x ** 3] for x in range(10)], [])

Example 4:
Using statement notation as circuit-like expectation value estimation.

reduce estZExpectation = ExpectationReduction(true) over _ in 1..nShots {
    use qs = Qubit[nQubits];
    Prepare(qs);
    yield Measure(basis, qs);
    ResetAll(qs);
}

// Assuming library code:
function CountReduction<'TYield>(prevBatches : [Int], newBatch : ['TYield]) : Int {
    return SumI(prevBatches) + Length(newBatch);
}

internal function ExpectationReductionStateUpdate(prevBatches : [(Int, Int)], newBatch : [Result]) : (Int, Int) {
    reduce prevNZeros = PlusI over (n, _) in prevBatches { yield n; }
    reduce prevNShots = PlusI over (_, n) in prevBatches { yield n; }

    reduce nZeros = CountReduction over result in newBatch {
        if result == Zero {
            yield; // ← Yields ().
        }
    }
    let nShots = Length(newBatch);
    return (nZeros + prevNZeros, nShots + prevNShots);
}

internal function ExpectationReductionResult(normalizeAsEigenvalue : Bool, finalState : (Int, Int)) : Double {
    let estPr = (IntAsDouble(Fst(finalState)) / IntAsDouble(Snd(finalState)));
    return normalizeAsEigenvalue
           ? 2.0 * estPr - 1.0
           | estPr;
}

@BatchReduction()
function ExpectationReduction(normalizeAsEigenvalue : Bool) : (
    (([(Int, Int)], (Int, Int)) -> (Int, Int)),
    ((Int, Int), Double)
) {
    return (
        ExpectationReductionStateUpdate,
        ExpectationReductionResult(normalizeAsEigenvalue, _)
    );
}

Example 5:
Using statement notation to express QCVV-style applications

operation EstimateSurvivalProbabilityAtLength(nQubits : Int, nShots : Int, nOperations : Int) : Double {
    reduce estPr = ExpectationReduction(false) over _ in 1..nShots {
        use qs = Qubit[nQubits];
        let sequence = DrawRandomSequence(nQubits, nOperations);
        for gate in sequence {
            ApplyGate(gate, qs);
        }
        yield Measure([PauliZ, size=nQubits], qs);
        ResetAll(qs);
    }
    return estPr;
}

Example 6:
Using device qubit literals from within reduction bodies

reduce estZExpectation = ExpectationReduction(true) over _ in 1..nShots {
    Prepare([#0, #1]);
    yield Measure(basis, [#0, #1]);
    ResetAll([#0, #1]);
}

Open questions

• Can blocks be elided in expression-based notation when a single expression is always yielded?
• Can commutativity of associative functions be opted-out from?

Affidavit (please fill out)

Please add ticks by placing a cross in the box:

• [x] I have searched both open and closed suggestions and proposals on this site and believe this is not a duplicate.
• [x] I believe that the spirit of this suggestion is aligned with the design principles and general vision for Q#.

Please tick all that apply:

• [x] This is not a breaking change to the Q# language design
• [x] I or my organization would be willing to help implement and/or test this