Skip to content
This repository was archived by the owner on Jan 12, 2024. It is now read-only.
This repository was archived by the owner on Jan 12, 2024. It is now read-only.

Enhancements to UDTs for representing numeric data in quantum registers #337

@cgranade

Description

@cgranade

Improvements to representations of numeric-valued quantum registers

Abstract and conceptual overview

The computational basis states for registers of qubits are each labelled by strings of classical bit; for example, a five-qubit register may be in the computational basis state |01100⟩.
Just as with classical registers, these bit strings may be a representation of some more structured data.
In arithmetic or cryptographic applications, for instance, we may wish to interpret the classical bitstring "01100" as an integer "6," such that a register of qubits in the |01100⟩ state could be interpreted as the integer-valued state |6⟩ instead.

In Q#, we can use user-defined types (UDTs) to couple a register of qubits to any classical metadata needed to interpret computational basis states as structured data.
For example, ths current newtype LittleEndian = Qubit[] UDT documents that a register of qubits is to be interpreted in precisely the manner described above, namely as a representation of integer-valued data.

By marking quantum registers to be interpreted as representing integer-valued data with UDTs, it is difficult to then accidentally use a register in a manner inconsistent with that interpretation.
While the underlying "raw" register can always be accessed using the unwrap operator (!), a value of type LittleEndian can only be used as-is with functions and operations that are designed to work with integer-valued quantum registers.

From that, we can derive the general principle that functions and operations which require a register of qubits to be interpreted as integers should accept an appropriate UDT to communicate this requirement.
This proposal makes usage of UDTs to mark integer interpretations of quantum registers more consistent and easier to use, to encapsulate implementation details about that representation, and to allow for documenting integer representations in a more discoverable fashion.

This proposal also modifies the Microsoft.Quantum.Arithmetic namespace to make more consistent use of these UDTs.
Currently, the names of arithmetic operations depends on the type on which those operations act in an unstructured manner (e.g.: adding a classical and quantum fixed-point number is performed by AddConstantFxP, while adding a classical and quantum integer is performed by IncrementByInteger).
Finally, this proposal adds new functions and operations to provide uniform coverage across UDTs that mark representation of numeric data where possible.

In addition to the general Q# API Design Principles, the changes detailed in this proposal follow a few principles specific to arithmetic representation to help ensure a consistent and discoverable user experience for developers working with the Quantum Development Kit:

  • Names of operations and functions for acting on different numeric data should parallel each other as close as possible, using general conventions such as type suffixes (e.g.: AddConstantQI vs AddConstantQU) to indicate which specific type each operation acts on.
  • Whenever reasonable, operations and functions supported by one numeric UDT should also be supported by other numeric UDTs, so that support for each type is uniform and predictable. There will of course be some exceptions, such as that it does not make sense to take the arithmetic inverse of an unsigned integer, but to the fullest extent reasonable this principle should be followed to help organize numerics support.

Together, these two design principles can be roughly encapsulated as the idea of a set of type classes (see below discussion of related language proposal microsoft/qsharp-language#149), also called concepts or traits. In particular, preparation, measurement, and assertion of different numeric UDTs falls under the general concept QuantizationOf<'T>:

Similar, we can capture principles such as that different numeric UDTs support the same arithmetic operations using concepts to organize public APIs. For example:

  • AddConstant takes an input of type 'Classical and an input of type 'Quantum, where 'Quantum is a quantization of type 'Classical, and where 'Classical supports the semigroup concept over + (NB: a semigroup is a set that is closed with respect to a given operation).
  • Invert takes an input of type 'Quantum, where 'Quantum is a quantization of another type 'Classical, and where 'Classical supports the group concept over + (NB: a group is a semigroup with a "zero" element, and where every element is invertible).
  • Add takes two inputs of type 'Quantum, where 'Quantum is a quantization of type 'Classical, and where 'Classical supports the group concept over + (NB: a group is required to allow a reversible implementation; an implementation only using semigroup properties would require three inputs and a concept representing the availability of an XOR implementation).

Though we do not do so in this proposal, one could consider extending the use of concepts further to expose the underlying algebraic structure of classical numeric data types through to quantizations of those types:

  • PrepareZero takes an input of type 'Quantum, where 'Quantum is a quantization of another type 'Classical, and where 'Classical supports the monoid concept over + (NB: a monoid is a semigroup with a "zero" element).
  • PrepareOne takes an input of type 'Quantum, where 'Quantum is a quantization of another type 'Classical, and where 'Classical supports the monoid concept over *.

Current status

Numeric data is currently represented by the LittleEndian, BigEndian, SignedLittleEndian, and FixedPoint UDTs, all of which are located in the Microsoft.Quantum.Arithmetic namespace.
While LittleEndian and BigEndian are provided in the Microsoft.Quantum.Standard package, SignedLittleEndian and FixedPoint are provided by the Microsoft.Quantum.Numerics package and thus are not provided to Q# applications by default.

These representations in turn are used by operations and functions in the Microsoft.Quantum.Arithmetic namespace and provided by the Microsoft.Quantum.Standard and Microsoft.Quantum.Numerics packages.
The package required for each type, function, and operation will be documented in API documentation starting in December 2020.

Relevant user feedback

  • As pointed out in Optimization change false positive leads to infinite loop qsharp-compiler#243, current functions such as ControlledOnInt take raw registers (i.e.: Qubit[]) when UDTs marking the interpretations of such registers (i.e.: LittleEndian) are expected, leading to confusion. The QuantizationOf<'T> principle above is intended to resolve this and similar feedback moving forward.
  • As pointed out in Infinite loop in optimization passes qsharp-compiler#244, we currently are not consistent between LittleEndian and BigEndian. This reduces predictability and discoverability of our APIs, but we have also gotten separate feedback (personal communications) that this requires users to need to be aware of internal implementation details such as which qubit internal to a UDT represents the most significant qubit.
  • As pointed out in Add Extensions.json and readme guidance for VSCode qsharp-compiler#374, we are currently inconsistent between what operations are defined for working with Int values and what operations are defined for working with BigInt values.

Child issues

Proposal

New and modified UDTs

The following UDT would replace the existing SignedLittleEndian UDT:

/// # Summary
/// A register of qubits that represents signed integer-valued data.
///
/// # Named Items
/// ## Register
/// The raw register of qubits used to represent integer-valued data.
///
/// # Remarks
/// Internally, integer data is represented using a twos-complement
/// little-endian encoding.
///
/// Functions and operations that act on this type are denoted by the suffix
/// `QI`.
///
/// # Example
/// TODO
newtype QInt = (
    Register: Qubit[]
);

The following UDT would replace the existing LittleEndian UDT:

/// # Summary
/// A register of qubits that represents unsigned integer-valued data.
///
/// # Named Items
/// ## Register
/// The raw register of qubits used to represent integer-valued data.
///
/// # Remarks
/// Internally, integer data is represented using a little-endian encoding.
///
/// Functions and operations that act on this type are denoted by the suffix
/// `QU`.
///
/// # Example
/// TODO
newtype QUnsignedInt = (
    Register: Qubit[]
);

The existing FixedPoint type would be modified as:

/// TODO: write new API docs.
newtype QFixedPoint = (
    Exponent: Int,
    Register: Qubit[]
);

Other changes:

  • Deprecate Microsoft.Quantum.Arithmetic.BigEndian.

New and modified functions and operations

Note that the list of replacements and modifications here is not intended to be fully exhaustive, but rather to provide examples of the higher-level action items to be taken in implementing this proposal.

  • Microsoft.Quantum.Canon namespace:

    • ApplyControlledOnInt, ControlledOnInt: Modify to accept QInt inputs, add type suffixes, and add variants for QU and QFx.
      • operation ApplyControlledOnInt<'T>(numberState : Int, oracle : ('T => Unit is Adj + Ctl), control : Qubit[], target : 'T) : Unit is Adj + Ctl
      • operation ApplyControlledOnQI<'T>(numberState : Int, oracle : ('T => Unit is Adj + Ctl), control : QInt, target : 'T) : Unit is Adj + Ctl
      • operation ApplyControlledOnQU<'T>(numberState : Int, oracle : ('T => Unit is Adj + Ctl), control : QUnsignedInt, target : 'T) : Unit is Adj + Ctl // NB: This can fail when numberState < 0.
      • operation ApplyControlledOnQFx<'T>(numberState : Double, oracle : ('T => Unit is Adj + Ctl), control : QFixedPoint, target : 'T) : Unit is Adj + Ctl
      • function ControlledOnInt<'T> (numberState : Int, oracle : ('T => Unit is Adj + Ctl)) : ((Qubit[], 'T) => Unit is Adj + Ctl)
      • function ControlledOnQI<'T> (numberState : Int, oracle : ('T => Unit is Adj + Ctl)) : ((QInt, 'T) => Unit is Adj + Ctl)
      • function ControlledOnQU<'T> (numberState : Int, oracle : ('T => Unit is Adj + Ctl)) : ((QUnsignedInt, 'T) => Unit is Adj + Ctl)
      • function ControlledOnQFx<'T> (numberState : Double, oracle : ('T => Unit is Adj + Ctl)) : ((QFixedPoint, 'T) => Unit is Adj + Ctl)
    • Deprecate QFT and QFTLE, add new ApplyQuantumFourierTransform that takes QUnsignedInt.
      • operation Microsoft.Quantum.Canon.QFT(qs : BigEndian) : Unit is Adj + Ctl
      • operation Microsoft.Quantum.Canon.QFTLE(qs : LittleEndian) : Unit is Adj + Ctl
      • operation Microsoft.Quantum.Canon.ApplyQuantumFourierTransform(qs : LittleEndian) : Unit is Adj + Ctl
      • operation Microsoft.Quantum.Arithmetic.ApplyQuantumFourierTransform(qs : QUnsignedInt) : Unit is Adj + Ctl
      • operation Microsoft.Quantum.Arithmetic.QFT(qs : QUnsignedInt) : Unit is Adj + Ctl // Shorthand for ApplyQuantumFourierTransform. Moved to Microsoft.Quantum.Arithmetic namespace to avoid conflicting with previous signature.
  • Microsoft.Quantum.Characterization namespace:

    • QuantumPhaseEstimation: Replace BigEndian with new quantum integer type.
  • Microsoft.Quantum.Convert namespace:

    • IntAsBoolArray, BigIntAsBoolArray: Extend to allow zero or negative inputs via twos-complement.
  • Microsoft.Quantum.Arithmetic namespace:

    • Deprecate functions and operations that require deprecated UDTs.
      • Deprecate all operations ending with BE, as the BigEndian UDT is deprecated by this proposal.
        • E.g.: operation ApplyQuantumFourierTransform (qs : Microsoft.Quantum.Arithmetic.LittleEndian) : Unit is Adj + Ctl
    • Deprecate functions and operations that are redundant with other functions and operations.
      • Deprecate GreaterThan (currently duplicated with CompareGTI).
        • operation GreaterThan(xs : LittleEndian, ys : LittleEndian, result : Qubit) : Unit is Adj + Ctl
    • Rename functions and operations to use consistent type suffixes.
      • Rename *I operations to *QI (e.g.: AddIAddQI).
        • operation AddI(xs : LittleEndian, ys : LittleEndian) : Unit is Adj + Ctl
        • operation AddQI(xs : QInt, ys : QInt) : Unit is Adj + Ctl
      • Rename *FxP operations to *QFx (e.g. AddFxPAddQFx).
        • operation AddFxP(fp1 : FixedPoint, fp2 : FixedPoint) : Unit is Adj + Ctl
        • operation AddQFx(xs : QFixedPoint, ys : QFixedPoint) : Unit is Adj + Ctl
      • ReflectAboutIntegerReflectAboutQU
        // NB: See function ReflectAbout<'TQuantum, 'TClassical> where 'TQuantum is QuantizationOf<'TClassical> below for a formalization of this naming convention as a concept.
        • operation ReflectAboutInteger(index : Int, reg : LittleEndian) : Unit
        • operation ReflectAboutQI(index : Int, reg : QInt) : Unit
        • operation ReflectAboutQU(index : Int, reg : QUnsignedInt) : Unit
        • operation ReflectAboutQFx(index : Double, reg : QFixedPoint) : Unit
    • Rename functions and operations to use names that are consistent across types.
      • Rename IncrementByInteger operation to AddConstantQI to match existing AddConstantFxP.
        • operation IncrementByInteger(increment : Int, target : LittleEndian) : Unit is Adj + Ctl
        • operation AddConstantFxP (constant : Double, fp : FixedPoint) : Unit is Adj + Ctl
        • operation AddConstantQI(constant : Int, fp : QInt) : Unit is Adj + Ctl
        • operation AddConstantQFx(constant : Double, fp : QFixedPoint) : Unit is Adj + Ctl
    • Add new functions and operations to reach parity in support for different numeric UDTs.
      • Add new AddQU and AddConstantQU operations, matching existing AddFxP and AddConstantFxP.
        • operation AddQU(xs : QUnsignedInt, ys : QUnsignedInt) : Unit is Adj + Ctl
        • operation AddConstantQU(constant : Int, fp : QUnsignedInt) : Unit is Adj + Ctl
      • AssertAllZeroFxPAssertIsZeroQFx, add new AssertIsZeroQI and AssertIsZeroQU to match.
        // NB: See AssertIsZero below as a formalization of this naming convention using concepts.
        • operation AssertAllZeroFxP(fp : FixedPoint) : Unit is Adj + Ctl
        • operation AssertIsZeroQFx(fp : QFixedPoint) : Unit is Adj + Ctl
      • Rename Invert2sSIInvertQI, add new InvertQFx operation to match. (NB: InvertQU does not make sense here, so should not be added.)
      • MeasureFxPMeasureQFx, MeasureIntegerMeasureQI, add new MeasureQU to match.
      • Add new PrepareQI and PrepareQU operations to match PrepareFxP.
    • Add new functions and operations to make it easier to work with numeric UDTs:
      • New ApplyTo{Most,Least}SignificantQubitQ{I,U,Fx}{,C,A,CA} operations that apply a single-qubit operation to the most or least significant bit of a register.
        // NB: Characteristic suffixes are some what ugly when combined with type suffixes, but they should hopefully be removed before Q# 1.0.
        • e.g.: operation ApplyToMostSignificantQubitQICA(op : (Qubit => Unit is Adj + Ctl), register : QInt) : Unit is Adj + Ctl

Modifications to style guide

  • UDTs representing classical data stored in a quantum register should start with a capital letter Q; e.g.: QInt, QFixedPoint, etc.

Impact of breaking changes

While the @Deprecated attribute allows for temporarily preserving an old function or operation name when modifying APIs, this functionality does not extend to allowing for modifying the signature of a function or operation without also changing its name, nor does @Deprecated allow for modifying user-defined types.

As a result, the changes listed in this proposal will require a hard breaking change.
In particular, user code written against current Q# library APIs will not only raise warnings against a version implementing this proposal, but will fail to compile.
For example, if the LittleEndian type is removed, then user code that constructs values of type LittleEndian will fail to compile without modifications.

This can be partially mitigated by providing an explicit migration guide with release notes.

Example

Current status

open Microsoft.Quantum.Arithmetic;
open Microsoft.Quantum.Diagnostics;

@Test("QuantumSimulator")
operation CheckThatThreeIsPreparedCorrectly() : Unit {
    using ((qs, flag) = (Qubit[4], Qubit()) {
        let register = LittleEndian(qs);

        // Prepare |3⟩.
        ApplyXorInPlace(3, register);

        // If |3⟩ was prepared correctly, then controlling
        // X on 3 should flip our flag.
        ApplyControlledOnInt(3, X, register!, flag);
        AssertMeasurement([PauliZ], [flag], One, "Didn't actually flip.");
        Reset(flag);

        // Measuring should give the right answer as well.
        let actual = MeasureInteger(register);
        EqualityFactI(actual, 3, "Didn't get right result measuring.");
    }
}

Using proposed changes

open Microsoft.Quantum.Arithmetic;
open Microsoft.Quantum.Diagnostics;

@Test("QuantumSimulator")
operation CheckThatThreeIsPreparedCorrectly() : Unit {
    using ((qs, flag) = (Qubit[4], Qubit()) {
        let register = QInt(qs);

        // Prepare |3⟩.
        PrepareQI(3, register);

        // If |3⟩ was prepared correctly, then controlling
        // X on 3 should flip our flag.
        ApplyControlledOnQI(3, X, register, flag);
        AssertMeasurement([PauliZ], [flag], One, "Didn't actually flip.");
        Reset(flag);

        // Measuring should give the right answer as well.
        let actual = MeasureQI(register);
        EqualityFactI(actual, 3, "Didn't get right result measuring.");
    }
}

If type classes / bounded polymorphism are utilized, the above could be simplified further to remove type suffixes:

open Microsoft.Quantum.Arithmetic;
open Microsoft.Quantum.Diagnostics;

@Test("QuantumSimulator")
operation CheckThatThreeIsPreparedCorrectly() : Unit {
    using ((qs, flag) = (Qubit[4], Qubit()) {
        let register = QInt(qs);

        // Prepare |3⟩.
        Prepare(3, register);

        // If |3⟩ was prepared correctly, then controlling
        // X on 3 should flip our flag.
        ApplyControlledOn(3, X, register, flag);
        AssertMeasurement([PauliZ], [flag], One, "Didn't actually flip.");
        Reset(flag);

        // Measuring should give the right answer as well.
        let actual = Measure(register);
        EqualityFactI(actual, 3, "Didn't get right result measuring.");
    }
}

Relationship to Q# language feature proposals

Bounded polymorphism (microsoft/qsharp-language#149)

Type suffixes could be eliminated by type classes / concepts. E.g.:

concept 'TInput is Measureable<'TResult> when {
    operation M(input : 'TInput) : 'TResult;
}

example Qubit is Measurable<Result> {
    operation M(input : Qubit) : Result {
        return Measure([PauliZ], [input]);
    }
}

example Qubit[] is Measurable<Result[]> { ... }
example QInt is Measurable<Int> { ... }
example QUnsignedInt is Measurable<Int> { ... }
example QFixedPoint is Measurable<Double> { ... }

Functions and operations in this proposal could be further consolidated by type classes / concepts:

concept 'TRegister is ControllableBy<'TValue> when {
    function ControlledOn<'TInput>(value : 'TValue, op : ('TInput => Unit is Ctl)) : (('TRegister, 'TInput) => Unit is Ctl);
}

example Qubit is ControllableBy<Result> {
    function ControlledOn<'TInput>(value : Result, op : ('TInput => Unixt is Ctl)) : ((Qubit, 'TInput) => Unit is Ctl) {
        return ApplyControlledOn(value, op, _, _);
    }
}

internal operation ApplyControlledOn<'TInput>(value : Result, op : ('TInput => Unit is Ctl), control : Qubit, target : 'TInput) : Unit {
    within {
        if (value == Zero) { X(control); }
    } apply {
        Controlled op([control], target);
    }
}

example Qubit[] of ControllableBy<Result> { ... }
example Qubit[] of ControllableBy<Result[]> { ... }
example QInt of ControllableBy<Int> { ... }
example QFixedPoint of ControllableBy<Double> { ... }

Perhaps even more extreme, these two concepts could be combined into a single concept, QuantizationOf<'TClassical>.

concept 'TQuantum is QuantizationOf<'TClassical> when {
    operation M(input : 'TQuantum) : 'TClassical;
    operation Prepare(value : 'TClassical, target : 'TQuantum) : Unit is Adj;
    function ControlledOn<'TInput>(value : 'TClassical, op : ('TInput => Unit is Ctl)) : (('TQuantum, 'TInput) => Unit is Ctl);
    operation Assert(expected : 'TClassical, actual : 'TQuantum) : Unit is Adj;
    function AsBareRegister(register : 'TQuantum) : Qubit[];
}

example Qubit is QuantizationOf<Bool> { ... }
example QInt is QuantizationOf<Bool> { ... }

function ReflectAbout<'TQuantum, 'TClassical> where 'TQuantum is QuantizationOf<'TClassical>(value : 'TClassical, register : 'TQuantum) : Unit is Adj + Ctl {
    let bare = AsBareRegister(register);
    within {
        Adjoint Prepare(value, register);
        ApplyToEach(X, bare);
    } apply {
        Controlled Z(Most(bare), Tail(bare));
    }
}

operation AssertIsZero<'TQuantum, 'TClassical> where 'TQuantum is QuantizationOf<'TClassical>, 'TClassical is Monoid(register : 'TQuantum) {
    let zero = MZero<'TClassical>();
    within {
        // For many representations, this will be a no-op, but writing it this
        // way allows us to consider representations where |0⟩ ≠ |000…0⟩.
        Adjoint Prepare(zero, register);
    } apply {
        // Adjoint Prepare guarantees that |value⟩ is mapped to something whose
        // bare register is |00…0⟩
        AssertAllZero(AsBareRegister(register));
    }
}

// alternatively, break into four concepts and unify with `where`:
concept 'TQuantum is QuantizationOf<'TClassical> where 'TQuantum is Measurable<'TClassical> + Preparable<'TClassical> + Controllable<'TClassical> + Assertable<'TClassical> {}

Non-breaking deprecation

The @Deprecated attribute can be used to rename operations without breaking existing code, but there is no current Q# feature that allows for modifying the signature of an operation or function without renaming it (e.g.: modifying the output of ControlledOnInt to take a QInt as its first input as opposed to Qubit[]).

To avoid breaking changes, we could consider proposing new functionality for modifying signatures while preserving old signatures as deprecation shims.

Alternatives considered

Do nothing

Doing nothing risks continuing to create user confusion due to inconsistent use of LittleEndian to denote interpretations, lack of parity between operations and functions acting on different types of numeric-valued registers, and the lack of uniform support for quantum numeric types.

Defer

The use of type suffixes in this proposal, while consistent with the style guide and API design principles, can be confusing for new Q# users.
As Q# does not yet provide an alternative to overloading that is consistent with type parameterization, first-class functions and operations, and with tuple-in tuple-out behavior (see above consideration of type classes / bounded polymorphism), type suffixes are currently required to disambiguate similar functions and operations that vary in the types that they act upon.
Thus, as an alternative to introducing further type suffixes, we could consider deferring action on this proposal until additional Q# language features are available.

Deferring risks continuing to create user confusion due to inconsistent use of LittleEndian to denote interpretations, lack of parity between operations and functions acting on different types of numeric-valued registers, and the lack of uniform support for quantum numeric types.

Develop parallel Microsoft.Quantum.Numerics namespace

As an alternative, we could deprecate the entire Microsoft.Quantum.Arithmetic namespace, and develop a new Microsoft.Quantum.Numerics namespace as a replacement, following the nomenclature used in our packaging (there is a Microsoft.Quantum.Numerics package but no Microsoft.Quantum.Arithmetic package). This would introduce significantly more changes to the API surface, but would allow for more of them to be made in a non-breaking fashion (some, such as changes to the Microsoft.Quantum.Canon namespace, would remain hard breaks).

Defer and replace with enums / DUs

As an alternative design for QInt and QUnsignedInt, we could consider deferring until microsoft/qsharp-compiler#406, and adding a named item to each for the encoding used to represent integer data:

newtype IntegerRepresentation =
    | LittleEndian()
    | BigEndian();

newtype QInt = (
    Register: Qubit[],
    Encoding: IntegerRepresentation
);

operation ApplyToMostSignificantQubitCA(op : Qubit => Unit is Adj + Ctl, target : QInt) : Unit is Adj + Ctl {
    op(
        target::Encoding match {
            LittleEndian() -> Tail(target),
            BigEndian() -> Head(target)
        }
    );
}

Open design questions and considerations

  • Should we propose a new Q# UnsignedInt type?
  • Should RippleCarry* be renamed to avoid confusion with type suffixes or characteristic suffixes (e.g.: A, C, CA)?
  • What to do with PhaseLittleEndian?
    • Related: what should be done with IncrementPhase*?
  • How to indicate Qubit[] with type suffixes?
  • Reset vs don't-reset for Microsoft.Quantum.Arithmetic.Measure*?
  • Do BlockEncoding* UDTs and functions need modified to use new QInt, etc.?

Metadata

Metadata

Assignees

No one assigned

    Labels

    Area-APIIssue concerns the API design of a library, such as style guide or design principles adherence.Kind-EnhancementNew feature or requestPkg-NumericsIssue relates to the Microsoft.Quantum.Numerics package.Pkg-StandardIssue relates to the Microsoft.Quantum.Standard package.Status-NeedsApiReviewThis PR requires an API review before merging in.

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions