Support for single-qubit Clifford group

[cgranade]

New operations, functions, and UDTs for single-qubit Clifford operators

Abstract and conceptual overview

By analogy to the built-in Pauli type, it would be nice to have a new type for representing single-qubit Clifford operators. These operators are common to a wide variety of different tasks, including quantum characterization and error correction, such that having support for these operators would make it easier to write Q# applications in these domain areas.

To provide a single-qubit Clifford type, this proposal uses the "EXS" presentation first proposed by the newsynth project; please see QInfer documentation for a full example of how to use this presentation of the single-qubit Clifford group.

Current status

Q# provides built-in support for single-qubit Pauli operators with the Pauli type, and multi-qubit Pauli operators with Pauli[], but does not provide similar support for single-qubit or multi-qubit Clifford operators. This proposal concerns the single-qubit case, leaving the multi-qubit case for a future proposal.

Proposal

New and modified UDTs

/// # Summary
/// An element of the single-qubit Clifford group.
///
/// # Description
/// Each element is represented as as $E^{i} S^{j} X^{k} \omega^{\ell}$, where $\omega^8 = 1$ and where $E = H S^3 \omega^3$.
///
/// # Named Items
/// ## E
/// The power to which $E$ should be raised to generate this element.
/// ## S
/// The power to which $S$ should be raised to generate this element.
/// ## X
/// The power to which $X$ should be raised to generate this element.
/// ## Omega
/// The power to which $\omega$ should be raised to generate this element.
///
/// # Example
/// ```Q#
/// let identity = SingleQubitClifford((0, 0, 0, 0));
/// let xClifford = SingleQubitClifford((0, 0, 1, 0));
/// ```
newtype SingleQubitClifford = (
    E: Int,
    S: Int,
    X: Int,
    Omega: Int
);

New and modified functions and operations

This proposal introduces new functions to represent the group product and group inverse on the single-qubit Clifford group, to quickly define common single-qubit Clifford operators, and to apply single-qubit Clifford operators as operations.

In doing so, this proposal uses currently existing concepts such as Microsoft.Quantum.Times★. This proposal also introduces a new concept Apply for applying operators as operations, and proposes renaming existing instances of this concept in a consistent fashion.

Note that this proposal uses 1C as the type suffix to denote instances of concepts applicable to the newly proposed SingleQubitClifford type. For future multi-qubit Clifford types, this proposal reserves NC as a suffix.

• namespace Microsoft.Quantum.Canon

  • ApplyP : (Pauli, Qubit) => Unit is Adj + Ctl
  • ApplyPauli : (Pauli, Qubit) => Unit is Adj + Ctl: keep, but as thin alias for ApplyP.

• namespace Microsoft.Quantum.Diagnostics

  • EqualityFact1C : (SingleQubitClifford, SingleQubitClifford, String) -> Unit: represents the fact that two single-qubit Clifford operators are equal to each other.
  • IdentityFact1C : (SingleQubitClifford, String) -> Unit: represents the fact that a given single-qubit Clifford operator is the identity.

• namespace Microsoft.Quantum.Random

  • DrawRandomSingleQubitClifford : Unit => SingleQubitClifford: returns a single-qubit Clifford operator uniformly at random.

• namespace Microsoft.Quantum.Synthesis

  • Action1C : (SingleQubitClifford, Pauli) -> Pauli: Returns the group action of a single-qubit Clifford operator on a single-qubit Pauli operator, 𝐶⁺𝑃𝐶.
  • Apply1C : (SingleQubitClifford, Qubit) => Unit is Adj + Ctl: Applies a single-qubit Clifford operator as an operation.
  • Identity1C : Unit -> SingleQubitClifford: returns a representation of the identity as a single-qubit Clifford operator.
  • Inverse1C : SingleQubitClifford -> SingleQubitClifford: returns the group inverse of a single-qubit Clifford operator.
  • PauliAsSingleQubitClifford : Pauli -> SingleQubitClifford: converts a single-qubit Pauli operator to a single
  • SingleQubitCliffordAsOperation: SingleQubitClifford -> (Qubit => Unit is Adj + Ctl): converts a single-qubit Clifford operator to a single-qubit operation.
  • Times1C : (SingleQubitClifford, SingleQubitClifford) -> SingleQubitClifford: returns the product of two single-qubit Clifford operators.

Impact of breaking changes

All breaking changes made by this proposal are minimal, and can be immediately mitigated by using the existing @Deprecated() attribute.

Examples

Example 1: Twirling a quantum operation

The following snippet implements a 3-design twirl of an arbitrary single-qubit quantum operation:

operation Twirl(op : (Qubit => Unit), target : Qubit) : Unit {
    let clifford = DrawRandomSingleQubitClifford();
    within {
        Apply1C(clifford, target);
    } apply {
        op(target);
    }
}

Relationship to Q# language feature proposals

Bounded polymorphism (microsoft/qsharp-language#149)

// NB: Similar concepts should allow for Adjoint and Controlled application.
concept 'TOperation is ApplicableTo<'TInput> when {
    operation Apply(op : 'TOperation, input : 'TInput) : Unit;
}

function AsOperation<'TOperation, 'TInput where 'TOperation is ApplicableTo<'TInput>>(op : 'TOperation, input : 'TInput) : ('TInput => Unit) {
    return Apply(op, _);
}

example <'T> ('T => Unit) is ApplicableTo<'T> {
    operation Apply(op : ('T => Unit), input : 'T) : Unit {
        return op(input);
    }
}

example Pauli is ApplicableTo<Qubit> {
    operation Apply(op : Pauli, input : Qubit) : Unit {
        if   op == PauliX { X(input); }
        elif op == PauliX { Y(input); }
        elif op == PauliZ { Z(input); }
    }
}

example Pauli[] is ApplicableTo<Qubit[]> {
    operation Apply(op : Pauli[], input : Qubit[]) : Unit {
        ApplyToEachCA(Apply, Zipped(op, input));
    }
}

example SingleQubitClifford is ApplicableTo<Qubit> {
    operation Apply(op : SingleQubitClifford, input : Qubit) : Unit {
        // implementation of Apply1C as in this proposal would go here instead
    }
}

Similar concepts could be used to represent the property that the single-qubit Clifford operators form a multiplicative group. Using similar notation to that discussed in replies to microsoft/qsharp-language#149:

concept 'T is MultiplicativeMonoid where 'T is EquatableTo<'T> {
    function Times(left : 'T, right : 'T) : 'T;
    function Identity() : 'T;
}
concept 'T is MultiplicativeGroup where 'T is MultiplicativeMonoid when {
    function Inverse(element : 'T) : 'T;
}

concept 'TGroup is GroupAction<'TTarget>
where 'TGroup is MultiplicativeGroup
where 'TTarget is EquatableTo<'TTarget> when {
    function Action(element : 'TGroup, target : 'TTarget) : 'TTarget;

    invariant Associative(left : 'TGroup, right : 'TGroup, target : 'TTarget) : Unit {
        EqualityFact(
            Action(Times(left, right), target),
            Action(left, Action(right, target))
        );
    }

    invariant RespectsIdentity(target : 'TTarget) : Unit {
        EqualityFact(
            Action(Identity<'TGroup>(), target),
            target
        );
    }
}

Multidimensional arrays (microsoft/qsharp-language#49)

For a future extension to multi-qubit Clifford operators, multidimensional arrays would be a very useful tool in representing the binary symplectic form of these operators. For example, while the copy-and-update operator w/ works well to replace rows in a jagged matrix (e.g.: Bool[][]), replacing columns is more difficult without the proposed multidimensional array feature:

function WithColumn<'T>(mtx : 'T[][], idxColumn : Int, column : 'T[]) : 'T[][] {
    mutable newMtx = mtx;
    for (idxRow, element) in Enumerated(column) {
        set newMtx w/= idxRow <- newMtx[idxRow] w/ idxColumn <- element;
    }
    return newMtx;
}

Following the design at microsoft/qsharp-language#49, the above could be simplified significantly:

function WithColumn<'T>(mtx : 'T[,], idxColumn : Int, column : 'T[]) : 'T[,] {
    return mtx w/ (..., idxColumn) <- column;
}

This implementation would also more closely follow using w/ to update rows:

function WithRow<'T>(mtx : 'T[,], idxRow : Int, column : 'T[]) : 'T[,] {
    return mtx w/ (idxRow, ...) <- column;
}

Open design questions and considerations

Updates

• Modified in accordance with action item from Show no more than one internal error per minute qsharp-compiler#410.