msoeken commented 2 years ago

Comparison operations

Conceptual overview

Provides operations for <, <=, =>, > for

in Standard:

two LittleEndian registers with X on target
two LittleEndian registers with arbitrary action on target
a LittleEndian register and a constant with X on target
a LittleEndian register and a constant with arbitrary action on target

in Numerics:

two FixedPoint registers with X on target
two FixedPoint registers with arbitrary action on target
a FixedPoint register and a constant (with X on target)

Current status

Comparison operations are not readily available for all 4 cases and no specializations with constants exists. The constant variants are optimized and do not lead to additional qubit overhead.

User feedback

Useful for resource estimation.

Proposal

We describe all operations for the case LessThan (<), but analogously operations are introduced for LessThanOrEqual (<=), GreaterThanOrEqual (>=), and GreaterThan (>)

New and modified functions, operations, and UDTs

namespace Microsoft.Quantum.Arithmetic {

/// # Summary
/// Performs less-than comparison of two quantum registers.
///
/// # Description
/// Inverts classical state of output qubit `output` if and only if input register `x`
/// is less than input register `y`.
///
/// # Input
/// ## x
/// Quantum register.
/// ## y
/// Quantum register.
/// ## target
/// Target qubit for comparison result.
operation CompareLessThan(x : LittleEndian, y : LittleEndian, target : Qubit) : Unit is Adj+Ctl { ... }

/// # Summary
/// Conditional action based on less-than comparison of two quantum registers.
///
/// # Description
/// Applies `action` to `output` if and only if input register `x` is less than input register `y`.
///
/// # Input
/// ## action
/// Action to be applied to `target`
/// ## x
/// Quantum register.
/// ## y
/// Quantum register.
/// ## target
/// Target input for `action`.
operation ApplyControlledOnLessThan<'T>(action : 'T => Unit is Adj + Ctl, x : LittleEndian, y : LittleEndian, target : 'T) : Unit is Adj + Ctl { ... }

/// # Summary
/// Performs less-than comparison of a quantum register with a constant.
///
/// # Description
/// Inverts classical state of output qubit `output` if and only if input register `x`
/// is less than constant `c`.
///
/// # Input
/// ## c
/// Constant value.
/// ## x
/// Quantum register.
/// ## target
/// Target qubit for comparison result.
operation CompareLessThanConstant(c : BigInt, x : LittleEndian, target : Qubit) : Unit is Adj + Ctl { ... }

/// # Summary
/// Conditional action based on less-than comparison of two quantum registers.
///
/// # Description
/// Applies `action` to `output` if and only if input register `x` is less than constant `c`.
///
/// # Input
/// ## action
/// Action to be applied to `target`
/// ## c
/// Constant value.
/// ## x
/// Quantum register.
/// ## target
/// Target input for `action`.
operation ApplyControlledOnLessThanConstant<'T>(action : 'T => Unit is Adj + Ctl, c : BigInt, x : LittleEndian, target: 'T) { ... }

/// # Summary
/// Performs less-than comparison of two quantum registers in fixed-point representation.
///
/// # Description
/// Inverts classical state of output qubit `output` if and only if input register `x`
/// is less than to input register `y`.
///
/// # Input
/// ## x
/// Quantum register.
/// ## y
/// Quantum register.
/// ## target
/// Target qubit for comparison result.
operation CompareLessThanFxP(fp1 : FixedPoint, fp2 : FixedPoint, target : Qubit) : Unit is Adj + Ctl { ... }

/// # Summary
/// Conditional action based on less-than comparison of two quantum registers in fixed-point representation.
///
/// # Description
/// Applies `action` to `output` if and only if input register `x` is less than input register `y`.
///
/// # Input
/// ## action
/// Action to be applied to `target`
/// ## x
/// Quantum register.
/// ## y
/// Quantum register.
/// ## target
/// Target input for `action`.
operation ApplyControlledOnLessThanFxP<'T>(action : 'T => Unit is Adj + Ctl, fp1 : FixedPoint, fp2 : FixedPoint, target : 'T) : Unit is Adj + Ctl { ... }

/// # Summary
/// Performs less-than comparison of a quantum fixed-point register with a constant.
///
/// # Description
/// Inverts classical state of output qubit `output` if and only if input register `x`
/// is less than to constant `c`.
///
/// # Input
/// ## c
/// Constant value.
/// ## x
/// Quantum register.
/// ## target
/// Target qubit for comparison result.
operation CompareLessThanConstantFxP(c : Double, x : FixedPoint, target : Qubit) : Unit is Adj + Ctl { ... }

}

Relationship to other proposals

(see comments below)

tcNickolas commented 2 years ago

The fixed point and LittleEndian sets of comparisons differ - there is no "a FixedPoint register and a constant with arbitrary action on target". Do we need to add that one as well?

msoeken commented 2 years ago

Yes, we can add them. They might not be as optimized as the ones for LittleEndian though.

msoeken commented 2 years ago

Comment from @cgranade during June 2022 API review

Does the action input to ApplyControlledOnLessThanFxP need to be adjointable? Should there be a separate Adj variant? We may also want to describe quickly how this proposal works with the outstanding proposal for numerics refactoring all-up (https://github.com/microsoft/QuantumLibraries/issues/337).

The operation action must at least have Ctl as a requirement to the implementation of ApplyControlledOnLessThanFxP. It is possible to have action not be adjointable, however, I think that this is a very uncommon case. Adding variants for the two different cases (adjointable vs. non-adjointable) would make the more common case a special case in the operation name (A suffix vs. no suffix). I think this is different to more general building blocks such as ApplyToEach or SinglyControlled that are used equally likely with different variants.

I added a reference to https://github.com/microsoft/QuantumLibraries/issues/337. That issue suggests a lot of changes, both new operations and new data types. Similarly, https://github.com/microsoft/QuantumLibraries/issues/423 is a superset of this issue, with more arithmetic operations. It's difficult to address such large issues, so that's why I started with this one aiming to first improve consistency in the arithmetic APIs, and then tackle https://github.com/microsoft/QuantumLibraries/issues/337 for UDTs when all the operations are in place.

microsoft / QuantumLibraries