-
Notifications
You must be signed in to change notification settings - Fork 175
Enhancements to UDTs for representing numeric data in quantum registers #337
Description
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
vsAddConstantQU
) 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>
:
Qubit
is a quantization ofBool
.'T[]
is a quantization of'U[]
, where'T
is a quantization of'U
.QInt
is a quantization ofInt
(alternatively,BigInt
as per Add Extensions.json and readme guidance for VSCode qsharp-compiler#374).QFixedPoint
is a quantization ofDouble
.
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. TheQuantizationOf<'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
andBigEndian
. 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 withBigInt
values.
Child issues
ControlledOnInt
return should use LittleEndian argument #243- QuantumPhaseEstimation takes BigEndian argument #244
- Add BigInt variants of all Int methods #374
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 acceptQInt
inputs, add type suffixes, and add variants forQU
andQFx
.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 whennumberState < 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
andQFTLE
, add newApplyQuantumFourierTransform
that takesQUnsignedInt
.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 forApplyQuantumFourierTransform
. Moved toMicrosoft.Quantum.Arithmetic
namespace to avoid conflicting with previous signature.
-
Microsoft.Quantum.Characterization
namespace:QuantumPhaseEstimation
: ReplaceBigEndian
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 theBigEndian
UDT is deprecated by this proposal.- E.g.:
operation ApplyQuantumFourierTransform (qs : Microsoft.Quantum.Arithmetic.LittleEndian) : Unit is Adj + Ctl
- E.g.:
- Deprecate all operations ending with
- Deprecate functions and operations that are redundant with other functions and operations.
- Deprecate
GreaterThan
(currently duplicated withCompareGTI
).operation GreaterThan(xs : LittleEndian, ys : LittleEndian, result : Qubit) : Unit is Adj + Ctl
- Deprecate
- Rename functions and operations to use consistent type suffixes.
- Rename
*I
operations to*QI
(e.g.:AddI
→AddQI
).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.AddFxP
→AddQFx
).operation AddFxP(fp1 : FixedPoint, fp2 : FixedPoint) : Unit is Adj + Ctl
operation AddQFx(xs : QFixedPoint, ys : QFixedPoint) : Unit is Adj + Ctl
ReflectAboutInteger
→ReflectAboutQU
// NB: Seefunction ReflectAbout<'TQuantum, 'TClassical> where 'TQuantum is QuantizationOf<'TClassical>
below for a formalization of this naming convention as aconcept
.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
- Rename functions and operations to use names that are consistent across types.
- Rename
IncrementByInteger
operation toAddConstantQI
to match existingAddConstantFxP
.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
- Rename
- Add new functions and operations to reach parity in support for different numeric UDTs.
- Add new
AddQU
andAddConstantQU
operations, matching existingAddFxP
andAddConstantFxP
.operation AddQU(xs : QUnsignedInt, ys : QUnsignedInt) : Unit is Adj + Ctl
operation AddConstantQU(constant : Int, fp : QUnsignedInt) : Unit is Adj + Ctl
AssertAllZeroFxP
→AssertIsZeroQFx
, add newAssertIsZeroQI
andAssertIsZeroQU
to match.
// NB: SeeAssertIsZero
below as a formalization of this naming convention usingconcept
s.operation AssertAllZeroFxP(fp : FixedPoint) : Unit is Adj + Ctl
operation AssertIsZeroQFx(fp : QFixedPoint) : Unit is Adj + Ctl
- Rename
Invert2sSI
→InvertQI
, add newInvertQFx
operation to match. (NB:InvertQU
does not make sense here, so should not be added.) MeasureFxP
→MeasureQFx
,MeasureInteger
→MeasureQI
, add newMeasureQU
to match.- Add new
PrepareQI
andPrepareQU
operations to matchPrepareFxP
.
- Add new
- 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
- e.g.:
- New
- Deprecate functions and operations that require deprecated UDTs.
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*
?
- Related: what should be done with
- 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.?