Table lookup

[adrianleh]

Proposal title

Conceptual overview

We propose to add a function for a table lookup routine, as the current idiomatic implementation requires deep knowledge of the API or will be challenging to implement.

Current status

Right now, table lookups require finding MultiplexOperations and ApplyPauliFromBitString within the API.

User feedback

N/A

Child issues

N/A

Proposal

New and modified functions, operations, and UDTs

namespace Microsoft.Quantum.Canon

/// # Summary
/// Performs a table lookup operation
/// 
/// # Description
/// A table lookup uses an address to return classical data from quantum registers
/// See more details on table lookup in Craig Gidney's paper https://arxiv.org/abs/1905.07682
///
/// # Input
/// ## data
/// The classical bit data that represents the table
/// ## address
/// The address used to lookup from the table
/// ## target
/// Qubits in which the result of the lookup will be stored
operation TableLookup(data : Bool[][], address : LittleEndian, target : Qubit[]) : Unit is Adj + Ctl

Modifications to style guide

N/A

Impact of breaking changes

N/A

Examples

Current status

Currently the best implementation we came up with is to implement a table lookup is as follows:

let ApplyXFromBitString = ApplyPauliFromBitString(PauliX, true, _, _); // Applies X conditionally based on bitstring
let unitaries = Mapped(bitstring -> ApplyXFromBitString(bitstring, _), data); // Create unitaries based on data
MultiplexOperations(unitaries, address, target); // Multiplex over address onto target

Using proposed changes

As this is a wrapper function it would involve a call to the wrapper

Relationship to Q# language feature proposals

N/A

Alternatives considered

We considered not including it since table lookups are a niche usecase, however we suggest they are used enough to provide the convenience function.

Open design questions and considerations

N/A

[cgranade]

As a heads-up, you may be interested in the qRAM library from @glassnotes, @sckaiser, et al. https://github.com/qsharp-community/qram Some neat ideas there for how to offer APIs for different qRAM techniques.

[tcNickolas]

I would make the API a bit more formal, pulling into it the constraints on the inputs dictated by the operations it is using, and providing a small example of how it is used for a specific input and what results it yields.

• The number of elements in data has to be between 0 and 2^(number of qubits in address)-1, inclusive; if it is smaller, data is padded with zero elements (from MultiplexOperations).
• The length of each element of data has to match the length of target (from ApplyPauliFromBitString).
• It is probably good to specify the number of auxiliary qubits it uses (from MultiplexOperations).
• Let's add periods at the end of the summary, the sentences in descriptions, and the input descriptions to match the rest of the APIs.
• The link to Craig Gidney's paper might belong to the references section, similarly to MultiplexOperations API.

[msoeken]

I would call the operation ApplyTableLookup or ApplyXorFromAddress. If we choose the latter, the name table lookup should appear in the docs for discoverability. The data is not padded with zero elements (possibly I need to update MultiplexOperations)

[adrianleh]

I'd vote for the name ApplyTableLookup as it will make the function more discoverable and its effects clearer. I'll update the PR