search

microsoft / QuantumLibraries

Q# libraries for the Quantum Development Kit
https://docs.microsoft.com/quantum
MIT License
544 stars 178 forks source link

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

Open cgranade opened 3 years ago

cgranade commented 3 years ago

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:

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 https://github.com/microsoft/qsharp-language/issues/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:

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:

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

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:

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.

Modifications to style guide

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 (https://github.com/microsoft/qsharp-language/issues/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 https://github.com/microsoft/qsharp-compiler/issues/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

cgranade commented 3 years ago

Following on the discussion at the Oct/Nov API review meeting (#368), I will edit the above proposal to incorporate the following action items:

cgranade commented 3 years ago

With all action items resolved, this should now be good for re-reviewing in the next cycle; moving to the appropriate column in preparation for next review.