List of Arithmetic Bloqs which need decompositions

[fdmalone]

Square integers

• code https://github.com/quantumlib/Qualtran/blob/main/qualtran/bloqs/arithmetic/multiplication.py#L93
• ref: https://arxiv.org/abs/2105.12767. pg 76 for Toffoli complexity (text not circuit)
• adjoint: No

Sum of Squares (integers)

• code: https://github.com/quantumlib/Qualtran/blob/main/qualtran/bloqs/arithmetic/multiplication.py#L135
• ref: https://arxiv.org/abs/2105.12767 pg 80 (text no circuit)
• adjoint: No

Product (integers)

• code: https://github.com/quantumlib/Qualtran/blob/main/qualtran/bloqs/arithmetic/multiplication.py#L192
• ref: https://arxiv.org/abs/2105.12767 pg 81 (text no circuit)
• adjoint: No

Scale integer by real number

• code: https://github.com/quantumlib/Qualtran/blob/main/qualtran/bloqs/arithmetic/multiplication.py#L242
• ref: https://arxiv.org/pdf/2007.07391.pdf pg 70 (text)
• adjoint: No

Multiply two real numbers

• code: https://github.com/quantumlib/Qualtran/blob/main/qualtran/bloqs/arithmetic/multiplication.py#L298
• ref: https://arxiv.org/pdf/2007.07391.pdf pg 71 (text)
• adjoint: No

Square real number

• code: https://github.com/quantumlib/Qualtran/blob/main/qualtran/bloqs/arithmetic/multiplication.py#L349
• ref: https://arxiv.org/pdf/2007.07391.pdf) pg 74 (text)
• adjoint: No

AddConstantMod

• code: https://github.com/quantumlib/Qualtran/blob/main/qualtran/bloqs/arithmetic/addition.py#L423
• ref ?
• adjoint: ArithmeticGate

Greater Than

• code: https://github.com/quantumlib/Qualtran/blob/main/qualtran/bloqs/arithmetic/comparison.py#L465
• ref: ? (modification of <=)
• adjoint: No

Greater Than Constant

• code: https://github.com/quantumlib/Qualtran/blob/main/qualtran/bloqs/arithmetic/comparison.py#L515
• ref: ? (modification of <= c)
• adjoint: No

Equals A constant

• code: https://github.com/quantumlib/Qualtran/blob/main/qualtran/bloqs/arithmetic/comparison.py#L562
• ref: ? (modification of <= c)
• adjoint: No

ToContiguousIndex

• code: https://github.com/quantumlib/Qualtran/blob/main/qualtran/bloqs/arithmetic/conversions.py#L33
• ref: https://arxiv.org/pdf/2011.03494.pdf Eq. 29 (it's just multiplication and addition of integers really)
• adjoint: No

SignedIntegerToTwosComplement

• code: https://github.com/quantumlib/Qualtran/blob/main/qualtran/bloqs/arithmetic/conversions.py#L97
• ref: https://arxiv.org/abs/2105.12767 page 24
• adjoint: No

[fdmalone]

Other relevant things:
#390 #235 (inequality tests can be inverted with zero Toffoli cost using out of place adders)

[tanujkhattar]

SimpleAddConstant can be replaced with Figure 18 of https://arxiv.org/pdf/2007.07391.pdf

[mpharrigan]

@NoureldinYosri can you review this issue. How many of these have been implemented?

[NoureldinYosri]

bloqs for real number arithmetics and bloqs in arithmetic/multiply.py need work ... the others are either done or need a couple of lines

[christopherkang]

In this vein --- is there a list of unimplemented operations?

I may be misunderstanding, but I believe AddIntoPhaseGrad is also unimplemented, meaning that dependent functions (e.g., Approximate QFT) are also not implemented.