New operation: Apply arithmetic function via table lookup

[rajkk1]

LookupTable

Conceptual overview

LookupTable creates a select-swap circuit similar to Fig 1c. https://arxiv.org/abs/1812.00954 to implement the arithmetic function of your choice given an input domain, maximum allowed input error, maximum allowed output error and the amount of the input qubits to use for the swap section

Current status

This primitive is not implemented in Q# yet.

User feedback

We need the LookupTable for a quantum resource estimation project over at GS

Proposal

New and modified functions, operations, and UDTs

See LookupTable.qs for the Q# code. Here are signatures of operations and comments:

namespace Microsoft.Quantum.Arithmetic {

    /// # Summary
    /// The return type when making a lookup table. This contains the operation that 
    /// makes the lookup table circuit, as well as all the parameters required to make 
    /// the two FixedPoint registers that need to be used as inputs and outputs to the 
    /// operator. The reason we have this structure is so that the operator is similar 
    /// to the other typical Q# arithmetic function implementations (a larger discussion
    /// can had as to whether that can be changed)
    newtype FunctionWithLookupTable = (
        IntegerBitsIn: Int,
        FractionalBitsIn: Int,
        IntegerBitsOut: Int,
        FractionalBitsOut: Int,
        Apply: (FixedPoint, FixedPoint) => Unit is Adj
    );

    /// # Summary
    /// This function creates a select-swap lookup table operator for the function that you want to approximate, as well as
    /// the parameters required to make the two FixedPoint registers that need to be used as inputs to the operator. 
    /// This is so that it is in similar to the other typical Q# arithmetic function (a larger discussion can be had 
    /// as to whether that can be changed). The circuit for the operator can be found in Fig. 1c in arXiv:1812.00954.
    /// The operator guarantees that given an input value x and a function f(x), 
    /// it will compute f'(x') where f' is an approximation of f with a maximum error of epsOut and x' is an
    /// approximation of the input value x with a maximum error of epsIn. This is useful for most reasonably behaved 
    /// functions, but not that it computes f'(x') and not f'(x) so if the domain function is very oscillatory and/or
    /// has funky derivatives then it may have high errors.
    ///
    /// # Input
    /// ## func
    /// The Q# arithmetic function that you want to implement with the lookup table
    /// ## domain
    /// A tuple consisting of the minimum and maximum values of the input values to the function
    /// ## epsIn
    /// The maximum allowed error of the input value to the computation (i.e. |x'-x|)
    /// ## epsOut
    /// The maximum allowed error of the output without taking into account the error in input value (i.e. |f'(x')-f(x')|)
    /// ## numSwapBits
    /// The number of bits of the input register that will be used in the SWAP section of the circuits. Another way of looking
    /// at this is that in step in the SELECT section of the circuit in Fig 1c of arXiv:1812.00954, we will encode 2^numSwapBits
    /// encoded 
    function ApplyFunctionWithLookupTable(func: Double -> Double, domain: (Double, Double), epsIn: Double, epsOut: Double, numSwapBits: Int): FunctionWithLookupTable { ... }

}

Modifications to style guide

n / a

Impact of breaking changes

n / a

Examples

See LookupTabletests.qs

Relationship to Q# language feature proposals

n / a

Alternatives considered

n / a

Open design questions and considerations

The operator is similar to the other typical Q# arithmetic function implementations, it would be cool to have the operation just take in directly the domain, input error and output error (instead of having to go via taking in a fixed point register)

[msoeken]

Thanks for the proposal @rajkk1. I made some changes to the description.

[msoeken]

Closed via #611