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

Function to perform operation controlled on truth table #269

Open
@msoeken

Description

@msoeken

I'd like to discuss API design for a function that controls an operation based on a Boolean function represented by a truth table, similar to the functions ControlledOnInt and ControlledOnBitString. The truth table can be represented by a BigInt, the number of variables can be obtained from the number of controls. (Truth table representations are also explained in the TruthTables kata. Examples are

(ControlledOnTruthTable(0xEL, X))([a, b], c);
(ControlledOnTruthTable(0xE8L, T))([a, b, c], d);

The first example applies X if and only if a OR b is true, the second example applies T, if and only if the majority of a, b, and c is true.

An implementation in which the truth table is represented as an array of Booleans and in which the operation is X can be found in this oracle-synthesis sample. Let's call this operation ControlledXOnTruthTable, assuming that the truth table is represented as BigInt. Then one can use this implementation to implement the generic operation by conjugating it with ControlledXOnTruthTable computing the result on a helper qubit and then controlling the generic operation on that helper qubit.

However, this implementation is not favourable for the case in which the operation is X since the number of operations is doubled (a bit can saved when using measurement-based uncomputation). We cannot make a condition on the operation to choose a special implementation for the case in which the operation is X.

The following solutions are possible:

  1. Implementing ControlledOnTruthTable and ControlledXOnTruthTable. ControlledOnTruthTable using X as operator would have the same behaviour as ControlledXOnTruthTable but a most costly implementation.

  2. Implementing only ControlledXOnTruthTable and give an example in the documentation of this operation how to implement a controlled operation on an arbitrary operation.

  3. Implementing ControlledOnTruthTable as public API but ControlledXOnTruthTable as hidden API, then using AST transformation to replace occurrences of ControlledOnTruthTable with operation X by the more efficient ControlledXOnTruthTable operation.

Metadata

Metadata

Assignees

Labels

Kind-EnhancementNew feature or requestPkg-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