This kata provides an introduction into representing Boolean functions in terms of integers, in which each bit represents a truth value for some input assignment.
Each task is wrapped in one operation preceded by the description of the task.
Your goal is to fill in the blank (marked with // ...
comments)
with some Q# code that solves the task. To verify your answer, run the cell using Ctrl+Enter (⌘+Enter on macOS).
This tutorial teaches you how to represent Boolean functions as integers. We use the bits in the binary integer representation as truth values in the truth table of the Boolean function.
Formally, a Boolean function is a function $f(x) : \{0,1\}^n \rightarrow \{0,1\}$ that takes an $n$-bit input, called input assignment, and produces a 1-bit output, called function value or truth value.
We can think of an $n$-variable Boolean function as an integer with at least $2^n$ binary digits. Each digit represents the truth value for each of the $2^n$ input assignments. The least significant bit represents the assignment 00...00, the next one - 00...01, and so on, and the most significant bit represents 11...11.
In Q# we can use the 0b
prefix to specify integers in binary notation,
which is useful when describing the truth table of a Boolean function.
For example, the truth table of the 2-input function ($x_1 \wedge x_2$) can be
represented by the integer 0b1000 = 8
.
Here is how you would get this representation:
$x_2$ | $x_1$ | $f(x_1, x_2)$ | Bit of the truth table |
---|---|---|---|
0 | 0 | 0 | Least significant |
0 | 1 | 0 | |
1 | 0 | 0 | |
1 | 1 | 1 | Most significant |
Since the number of bits in a Q# integer is always the same, we need to specify the number of variables explicitly. Therefore, it makes sense to introduce a user defined type for truth tables. Here is its definition:
newtype TruthTable = (bits : Int, numVars : Int);
Goal: Describe the three projective functions $x_1$, $x_2$, $x_3$ represented by integers. Each of them is a 3-input function, i.e., $f(x) : \{0,1\}^{3} \rightarrow \{0,1\}$
We use the following convention:
The function $x_1$ (least significant input) is given as an example.
The function is true for assignments $001$, $011$, $101$, and $111$, since for all these assignments their least significant bit $x_1 = 1$.
$x_3$ | $x_2$ | $x_1$ | Is $x_1 = 1?$ | Bit of the integer which represents the truth table |
---|---|---|---|---|
0 | 0 | 0 | Least significant | |
0 | 0 | 1 | Yes | |
0 | 1 | 0 | ||
0 | 1 | 1 | Yes | |
1 | 0 | 0 | ||
1 | 0 | 1 | Yes | |
1 | 1 | 0 | ||
1 | 1 | 1 | Yes | Most Significant |
$x_3$ | $x_2$ | $x_1$ | Is $x_1 = 1?$ | Is $x_2 = 1?$ | Is $x_3 = 1?$ | Bit of the integer which represents the truth table |
---|---|---|---|---|---|---|
0 | 0 | 0 | Least significant | |||
0 | 0 | 1 | Yes | |||
0 | 1 | 0 | Yes | |||
0 | 1 | 1 | Yes | Yes | ||
1 | 0 | 0 | Yes | |||
1 | 0 | 1 | Yes | Yes | ||
1 | 1 | 0 | Yes | Yes | ||
1 | 1 | 1 | Yes | Yes | Yes | Most Significant |
%kata T01_ProjectiveTruthTables
open Quantum.Kata.TruthTables;
function ProjectiveTruthTables () : (TruthTable, TruthTable, TruthTable) {
let x1 = TruthTable(0b10101010, 3);
let x2 = TruthTable(0, 0); // Update the value of x2 ...
let x3 = TruthTable(0, 0); // Update the value of x3 ...
return (x1, x2, x3);
}
Can't come up with a solution? See the explained solution in the Truth Tables Workbook.
Goal: Describe a 3-input function $f(x_3,x_2,x_1)$ represented by an integer which is true if and only if exactly 1 bit out of $x_1$, $x_2$ or $x_3$ is true.
$x_3$ | $x_2$ | $x_1$ | $f(x_1,x_2,x_3)$ | Bit of the truth table |
---|---|---|---|---|
0 | 0 | 0 | Least significant | |
0 | 0 | 1 | Yes | |
0 | 1 | 0 | Yes | |
0 | 1 | 1 | ||
1 | 0 | 0 | Yes | |
1 | 0 | 1 | ||
1 | 1 | 0 | ||
1 | 1 | 1 | Most Significant |
%kata T02_ExactlyOneBitTrue
open Quantum.Kata.TruthTables;
function ExactlyOneBitTrue () : (TruthTable) {
let f = TruthTable(0, 3); // Update the value of f ...
return f;
}
Can't come up with a solution? See the explained solution in the Truth Tables Workbook.
Goal: Describe a 3-input function $f(x_3,x_2,x_1)$ represented by an integer which is true if and only if exactly 2 bits out of $x_1$, $x_2$ or $x_3$ are true.
$x_3$ | $x_2$ | $x_1$ | $f(x_1,x_2,x_3)$ | Bit of the truth table |
---|---|---|---|---|
0 | 0 | 0 | Least significant | |
0 | 0 | 1 | ||
0 | 1 | 0 | ||
0 | 1 | 1 | Yes | |
1 | 0 | 0 | ||
1 | 0 | 1 | Yes | |
1 | 1 | 0 | Yes | |
1 | 1 | 1 | Most Significant |
%kata T03_ExactlyTwoBitsTrue
open Quantum.Kata.TruthTables;
function ExactlyTwoBitsTrue () : (TruthTable) {
let f = TruthTable(0, 3); // Update the value of f ...
return f;
}
Can't come up with a solution? See the explained solution in the Truth Tables Workbook.
Goal: Compute a truth table that computes the conjunction (AND) of two truth tables. Find a way to perform the computation directly on the integer representations of the truth tables, i.e., without accessing the bits individually.
%kata T04_TTAnd
open Quantum.Kata.TruthTables;
function TTAnd (tt1 : TruthTable, tt2 : TruthTable) : TruthTable {
// ...
}
Can't come up with a solution? See the explained solution in the Truth Tables Workbook.
Goal: Compute a truth table that computes the disjunction (OR) of two truth tables.
%kata T05_TTOr
open Quantum.Kata.TruthTables;
function TTOr (tt1 : TruthTable, tt2 : TruthTable) : TruthTable {
// ...
}
Can't come up with a solution? See the explained solution in the Truth Tables Workbook.
Goal: Compute a truth table that computes the exclusive-OR (XOR) of two truth tables.
%kata T06_TTXor
open Quantum.Kata.TruthTables;
function TTXor (tt1 : TruthTable, tt2 : TruthTable) : TruthTable {
// ...
}
Can't come up with a solution? See the explained solution in the Truth Tables Workbook.
Goal: Compute a truth table that computes negation of a truth table.
%kata T07_TTNot
open Quantum.Kata.TruthTables;
function TTNot (tt : TruthTable) : TruthTable {
// ...
}
Can't come up with a solution? See the explained solution in the Truth Tables Workbook.
Goal:
Compute the truth table of the if-then-else function ttCond ? ttThen | ttElse
(if ttCond then ttThen else ttElse
) by making use of the truth table operations
defined in the previous four tasks.
%kata T08_IfThenElseTruthTable
open Quantum.Kata.TruthTables;
function TTIfThenElse (ttCond : TruthTable, ttThen : TruthTable, ttElse : TruthTable) : TruthTable {
// ...
}
Can't come up with a solution? See the explained solution in the Truth Tables Workbook.
Goal: Return an array that contains all input assignments in a truth table that have a true truth value. These input assignments are called minterms. The order of assignments in the return does not matter.
You could make use of Q# library functions to implement this operation in a
single return statement without implementing any helper operations. Useful
Q# library functions to complete this task are Mapped
, Filtered
, Compose
,
Enumerated
, IntAsBoolArray
, EqualB
, Fst
, and Snd
.
Example:
The truth table of 2-input OR is 0b1110
, i.e., its minterms are [1, 2, 3]
.
%kata T09_AllMinterms
open Quantum.Kata.TruthTables;
function AllMinterms (tt : TruthTable) : Int[] {
// ...
}
Can't come up with a solution? See the explained solution in the Truth Tables Workbook.
Goal: Apply the X operation on the target qubit, if and only if the classical state of the controls is a minterm of the truth table.
%kata T10_ApplyFunction
open Quantum.Kata.TruthTables;
operation ApplyXControlledOnFunction (tt : TruthTable, controls : Qubit[], target : Qubit) : Unit is Adj {
// ...
}
Can't come up with a solution? See the explained solution in the Truth Tables Workbook.