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.

Simple and consistent arithmetic API #423

@msoeken

Description

@msoeken

Simple and consistent arithmetic API

Abstract and conceptual overview

The proposal introduces

  • simple names for common arithmetic operations
  • additional operations where currently only one is available (e.g., additional comparison operations)
  • optimized implementations for T-count (all operations make use of ApplyAnd when possible)
  • optimizations based on measurement-based uncomputation

Proposal

All operations are in the Microsoft.Quantum.Arithmetic namespace.

New functions and operations

  • Addition

    • operation Add(x : LittleEndian, y : LittleEndian) : Unit is Adj+Ctl

    • operation AddWithCarryIn(x : LittleEndian, y : LittleEndian, carryIn : Qubit) : Unit is Adj+Ctl

      Both operations cover without carry-out (Length(x!) == Length(y!)) as well as with carry-out (Length(x!) + 1 == Length(y!))

    • operation AddConstant(c : BigInt, y : LittleEndian) : Unit is Adj+Ctl

  • Subtraction

    • operation Subtract(x : LittleEndian, y : LittleEndian) : Unit is Ctl+Adj

      The operation covers without carry-out (Length(x!) == Length(y!)) as well as with carry-out (Length(x!) + 1 == Length(y!))

  • Comparison

    • operation GreaterThanOrEqual(x : LittleEndian, y : LittleEndian, target : Qubit) : Unit is Adj+Ctl

    • operation GreaterThan(x : LittleEndian, y : LittleEndian, target : Qubit) : Unit is Adj+Ctl

      This API already exists, but would be replaced by new implementation.

    • operation LessThanOrEqual(x : LittleEndian, y : LittleEndian, target : Qubit) : Unit is Adj+Ctl

    • operation LessThan(x : LittleEndian, y : LittleEndian, target : Qubit) : Unit is Adj+Ctl

    • operation GreaterThanOrEqualConstant(c : BigInt, y : LittleEndian, target : Qubit) : Unit is Adj+Ctl

    • operation GreaterThanConstant(c : BigInt, y : LittleEndian, target : Qubit) : Unit is Adj+Ctl

    • operation LessThanOrEqualConstant(c : BigInt, y : LittleEndian, target : Qubit) : Unit is Adj+Ctl

    • operation LessThanConstant(c : BigInt, y : LittleEndian, target : Qubit) : Unit is Adj+Ctl

    • There are special variants for when it's guaranteed that the target qubit
      is released in state Zero, making use of measurement-based uncomputation.
      (all these variants can be emulated with the general variants above when
      applied in ToffoliSimulator):

      • operation GreaterThanOrEqualWithZeroOutput(x : LittleEndian, y : LittleEndian, target : Qubit) : Unit is Adj+Ctl
      • operation GreaterThanWithZeroOutput(x : LittleEndian, y : LittleEndian, target : Qubit) : Unit is Adj+Ctl
      • operation LessThanOrEqualWithZeroOutput(x : LittleEndian, y : LittleEndian, target : Qubit) : Unit is Adj+Ctl
      • operation LessThanWithZeroOutput(x : LittleEndian, y : LittleEndian, target : Qubit) : Unit is Adj+Ctl
      • operation GreaterThanOrEqualConstantWithZeroOutput(c : BigInt, y : LittleEndian, target : Qubit) : Unit is Adj+Ctl
      • operation GreaterThanConstantWithZeroOutput(c : BigInt, y : LittleEndian, target : Qubit) : Unit is Adj+Ctl
      • operation LessThanOrEqualConstantWithZeroOutput(c : BigInt, y : LittleEndian, target : Qubit) : Unit is Adj+Ctl
      • operation LessThanConstantWithZeroOutput(c : BigInt, y : LittleEndian, target : Qubit) : Unit is Adj+Ctl
  • Modular arithmetic

    • operation ModularAdd(modulus : BigInt, x : LittleEndian, y : LittleEndian) : Unit is Adj
    • operation ModularAddConstant(modulus : BigInt, c : BigInt, y : LittleEndian) : Unit is Adj

Deprecations

  • CompareUsingRippleCarry in favor of GreaterThan
  • GreaterThan in favor of GreaterThan (same name, new implementation)
  • CompareGTI in favor of GreaterThan
  • delete Carry (should have been internal)
  • delete Sum (should have been internal)
  • RippleCarryAdderD in favor of Add
  • AddI in favor of Add
  • rename RippleCarryAdderCDKM to LowWidthAdd
  • rename RippleCarryAdderTTK to NoWidthAdd (distinguish by register length)
  • rename RippleCarryAdderNoCarryTTK to NoWidthAdd (distinguish by register length)

Considerations regarding Q# runtime

  • If we were tracking whether qubits are in state Zero (e.g., after each call to AssertAllZero or AssertQubit until the qubit is used again),
    one could automatically use the *WithZeroOutput variants and only use the general variants in the user source code.

Relationship to Q# language feature proposals

Open design questions and considerations

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