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

Comparison operations #593

Open
msoeken opened this issue Jun 8, 2022 · 3 comments
Open

Comparison operations #593

msoeken opened this issue Jun 8, 2022 · 3 comments
Assignees
Labels
Area-API Issue concerns the API design of a library, such as style guide or design principles adherence. Kind-Enhancement New feature or request Pkg-Numerics Issue relates to the Microsoft.Quantum.Numerics package. Pkg-Standard Issue relates to the Microsoft.Quantum.Standard package. tracking This label will trigger gh-sync to create or update a mirror internal ADO issue.

Comments

@msoeken
Copy link
Member

msoeken commented Jun 8, 2022

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)

@msoeken msoeken added Kind-Enhancement New feature or request Pkg-Standard Issue relates to the Microsoft.Quantum.Standard package. Pkg-Numerics Issue relates to the Microsoft.Quantum.Numerics package. Status-NeedsApiReview This PR requires an API review before merging in. Area-API Issue concerns the API design of a library, such as style guide or design principles adherence. labels Jun 8, 2022
@msoeken msoeken self-assigned this Jun 8, 2022
@msoeken msoeken added the tracking This label will trigger gh-sync to create or update a mirror internal ADO issue. label Jun 8, 2022
@msoeken msoeken added this to Ready to be reviewed in API Review Scheduling Jun 8, 2022
@tcNickolas
Copy link
Member

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
Copy link
Member Author

msoeken commented Jul 6, 2022

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

@msoeken msoeken moved this from Ready to be reviewed to Reviewed: approved in API Review Scheduling Jul 6, 2022
@msoeken
Copy link
Member Author

msoeken commented Jul 7, 2022

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 (#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 #337. That issue suggests a lot of changes, both new operations and new data types. Similarly, #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 #337 for UDTs when all the operations are in place.

@msoeken msoeken removed the Status-NeedsApiReview This PR requires an API review before merging in. label Jul 7, 2022
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
Area-API Issue concerns the API design of a library, such as style guide or design principles adherence. Kind-Enhancement New feature or request Pkg-Numerics Issue relates to the Microsoft.Quantum.Numerics package. Pkg-Standard Issue relates to the Microsoft.Quantum.Standard package. tracking This label will trigger gh-sync to create or update a mirror internal ADO issue.
Projects
API Review Scheduling
Reviewed: approved
Development

No branches or pull requests

2 participants