{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Truth Tables Tutorial Workbook\n", "\n", "**What is this workbook?**\n", "A workbook is a collection of problems, accompanied by solutions to them. \n", "The explanations focus on the logical steps required to solve a problem; they illustrate the concepts that need to be applied to come up with a solution to the problem, explaining the mathematical steps required. \n", "\n", "Note that a workbook should not be the primary source of knowledge on the subject matter; it assumes that you've already read a tutorial or a textbook and that you are now seeking to improve your problem-solving skills. You should attempt solving the tasks of the respective kata first, and turn to the workbook only if stuck. While a textbook emphasizes knowledge acquisition, a workbook emphasizes skill acquisition.\n", "\n", "This workbook describes the solutions to the problems offered in the [Truth Tables tutorial](./TruthTables.ipynb). \n", "Since the tasks are offered as programming problems, the explanations also cover some elements of Python that might be non-obvious for a first-time user.\n", "\n", "**What you should know for this workbook**\n", "\n", "1. Truth tables.\n", "2. Basic Python knowledge is helpful but not necessary." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Task 1. Projective functions (elementary variables)\n", "\n", "**Goal:** \n", "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\\}$\n", "\n", "We use the following convention:\n", "- $x_1$ is the least significant input.\n", "- $x_3$ is the most significant input.\n", "\n", "> The function $x_1$ (least significant input) is given as an example. \n", "The function is true for assignments $001$, $011$, $101$, and $111$, since for all these assignments their least significant bit $x_1 = 1$.\n", "\n", "If $x_1 = 0b10101010$, what are the values of $x_2$ and $x_3$?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Solution\n", "\n", "Let's take another look at the truth table for the functions $x_1$, $x_2$, and $x_3$ \n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
$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
000Least significant
001Yes
010Yes
011YesYes
100Yes
101YesYes
110YesYes
111YesYesYesMost Significant
\n", "\n", "To convert this form of a truth table into a single integer format, we need to write out all the bits of its values, from the most significant to the least significant. \n", "\n", "The truth table for $x_2$ is `0b11001100` (the bits in the $x_2$ column, from the bottom row to the top row) and the truth table for $x_3$ is `0b11110000`." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "%kata T01_ProjectiveTruthTables \n", "\n", "open Quantum.Kata.TruthTables;\n", "\n", "function ProjectiveTruthTables () : (TruthTable, TruthTable, TruthTable) {\n", " let x1 = TruthTable(0b10101010, 3);\n", " let x2 = TruthTable(0b11001100, 3);\n", " let x3 = TruthTable(0b11110000, 3);\n", "\n", " return (x1, x2, x3);\n", "}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "[Return to task 1 of the Truth Tables kata.](./TruthTables.ipynb#Task-1.-Projective-functions-(elementary-variables))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Task 2. \"Exactly 1 bit is true\" function\n", "\n", "**Goal:** \n", "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." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Solution\n", "The function is true for assignments $100$, $010$, and $001$, since for these assignments exactly one bit is true. The function is false for assignments $000$, $011$, $101$, $110$, and $111$, since for all these assignments either all bits are false or more than one bit is true.\n", "\n", "To spell out the binary notation of the resulting integer, we list the bits (1 if the function is true and 0 if it is false), starting with the input $111$ and ending with $000$: `0b00010110`." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "%kata T02_ExactlyOneBitTrue\n", "\n", "open Quantum.Kata.TruthTables;\n", "\n", "function ExactlyOneBitTrue () : (TruthTable) {\n", " let f = TruthTable(0b00010110, 3);\n", " return f;\n", "}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "[Return to task 2 of the Truth Tables kata.](./TruthTables.ipynb#Task-2.-\"Exactly-1-bit-is-true\"-function)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Task 3. \"Exactly 2 bits are true\" function\n", "\n", "**Goal:** \n", "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.\n", "\n", "If $f = 0$, what are the values of $x_1$, $x_2$, and $x_3$?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Solution\n", "The function is true for assignments $011$, $101$, and $110$, since for these assignments exactly 2 bits are true. The function is false for assignments $000$, $001$, $010$, $100$, $111$, since all these assignments do not have exactly 2 bits as true.\n", "\n", "The binary notation of the resuling integer is `0b01101000`." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "%kata T03_ExactlyTwoBitsTrue\n", "\n", "open Quantum.Kata.TruthTables;\n", "\n", "function ExactlyTwoBitsTrue () : (TruthTable) {\n", " let f = TruthTable(0b01101000, 3); // Update the value of f ...\n", " return f;\n", "}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "[Return to task 3 of the Truth Tables kata.](./TruthTables.ipynb#Task-3.-\"Exactly-2-bits-are-true\"-function)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Task 4. Compute AND of two truth tables\n", "**Goal:** \n", "Compute a truth table that computes the conjunction (AND)\n", "of two truth tables. Find a way to perform the computation\n", "directly on the integer representations of the truth tables,\n", "i.e., without accessing the bits individually." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Solution\n", "For each input, the value of the goal function is an AND of the values of the two given functions for the same input. \n", "We can use &&& operator to compute the bitwise conjunction (AND) of two integers representing truth tables to get the integer representing the goal function directly.\n", "\n", "Remember that `TruthTable` is a user-defined type with fields `bits` and `numVars`. You can access these fields as `tt1::bits` and `tt1::numVars`, respectively, and construct the return value from the fields using a constructor `TruthTable(newBits, newNumVars)`." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "%kata T04_TTAnd \n", "\n", "open Quantum.Kata.TruthTables;\n", "\n", "function TTAnd (tt1 : TruthTable, tt2 : TruthTable) : TruthTable {\n", " return TruthTable(tt1::bits &&& tt2::bits, tt1::numVars);\n", "}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "[Return to task 4 of the Truth Tables kata.](./TruthTables.ipynb#Task-4.-Compute-AND-of-two-truth-tables)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Task 5. Compute OR of two truth tables\n", "**Goal:** \n", "Compute a truth table that computes the disjunction (OR)\n", "of two truth tables." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Solution\n", "Similarly to the previous task, we can use the bitwise OR ||| operator to compute the disjunction (OR) of two truth tables." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "%kata T05_TTOr \n", "\n", "open Quantum.Kata.TruthTables;\n", "\n", "function TTOr (tt1 : TruthTable, tt2 : TruthTable) : TruthTable {\n", " return TruthTable(tt1::bits ||| tt2::bits, tt1::numVars);\n", "}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "[Return to task 5 of the Truth Tables kata.](./TruthTables.ipynb#Task-5.-Compute-OR-of-two-truth-tables)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Task 6. Compute XOR of two truth tables\n", "**Goal:** \n", "Compute a truth table that computes the exclusive-OR (XOR)\n", "of two truth tables." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Solution\n", "We can use the bitwise XOR ^^^ operator to compute the exclusive-OR (XOR) of two truth tables such as: tt1 ^^^ tt2." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "%kata T06_TTXor \n", "\n", "open Quantum.Kata.TruthTables;\n", "\n", "function TTXor (tt1 : TruthTable, tt2 : TruthTable) : TruthTable {\n", " return TruthTable(tt1::bits ^^^ tt2::bits, tt1::numVars);\n", "}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "[Return to task 6 of the Truth Tables kata.](./TruthTables.ipynb#Task-6.-Compute-XOR-of-two-truth-tables)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Task 7. Compute NOT of a truth table\n", "**Goal:** \n", "Compute a truth table that computes negation of a truth\n", "table." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Solution\n", "We can use the bitwise negation `~~~` operator to compute the negation (NOT) a truth table. \n", "Note, though, that this operator will flip all bits of the integer, and we need to flip only $2^{numVars}$ least significant bits, since the rest of the bits should remain set to 0.\n", "To do this, we can do the following steps:\n", "\n", "1. Construct a bitmask `0b0..01..1`, in which the $2^{numVars}$ least significant bits are set to 1, representing all possible inputs to the function. This mask can be constructed as $2^{2^{numVars}} - 1$.\n", "2. Subtract the integer representation of the truth table from this mask. This will have the effect of negating each of the least significant $2^{numVars}$ bits, while leaving the most significant bits set to 0." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "%kata T07_TTNot \n", "\n", "open Quantum.Kata.TruthTables;\n", "\n", "function TTNot (tt : TruthTable) : TruthTable {\n", " return TruthTable((1 <<< (1 <<< tt::numVars)) - 1 - tt::bits, tt::numVars);\n", "}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "[Return to task 7 of the Truth Tables kata.](./TruthTables.ipynb#Task-7.-Compute-NOT-of-a-truth-table)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Task 8. Build if-then-else truth table\n", "**Goal:** \n", "Compute the truth table of the if-then-else function `ttCond ? ttThen | ttElse`\n", "(`if ttCond then ttThen else ttElse`) by making use of the truth table operations\n", "defined in the previous four tasks." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Solution\n", "We can use the following formula to satisfy If/Else conditional function: `((NOT ttCond) AND ttThen) OR (ttCond AND ttElse)`. We've implemented all the building blocks of this formula in the previous tasks, so we can use them here." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "%kata T08_IfThenElseTruthTable \n", "\n", "open Quantum.Kata.TruthTables;\n", "\n", "function TTIfThenElse (ttCond : TruthTable, ttThen : TruthTable, ttElse : TruthTable) : TruthTable {\n", " return TTXor(TTAnd(ttCond, ttThen), TTAnd(TTNot(ttCond), ttElse));\n", "}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "[Return to task 8 of the Truth Tables kata.](./TruthTables.ipynb#Task-8.-Build-if-then-else-truth-table)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Task 9. Find all true input assignments in a truth table\n", "**Goal:** \n", "Return an array that contains all input assignments in a truth table\n", "that have a true truth value. These input assignments are called minterms.\n", "The order of assignments in the return does not matter.\n", "\n", "> **Example:**\n", "The truth table of 2-input OR is `0b1110`, i.e., its minterms are `[1, 2, 3]`." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Solution 1\n", "\n", "Let's iterate over all assignments, checking whether each of them is true, and aggregating the indices of those that are into an array to be returned." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "%kata T09_AllMinterms \n", "\n", "open Quantum.Kata.TruthTables;\n", "\n", "function AllMinterms (tt : TruthTable) : Int[] {\n", " mutable minterms = [];\n", " mutable bits = tt::bits;\n", " for i in 0 .. 2 ^ tt::numVars - 1 {\n", " if bits % 2 == 1 {\n", " set minterms += [i];\n", " }\n", " set bits /= 2;\n", " }\n", " return minterms;\n", "}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Solution 2\n", "\n", "Alternatively, we can use Q# library functions for handling arrays to express the same logic:\n", "\n", "* [IntAsBoolArray](https://learn.microsoft.com/qsharp/api/qsharp/microsoft.quantum.convert.intasboolarray) function will convert the truth table stored as an integer into an array of individual bits; the bit at index `ind` will be the value of the function for the input assignment `ind`.\n", "* [Enumerated](https://learn.microsoft.com/qsharp/api/qsharp/microsoft.quantum.arrays.enumerated) function will convert the array of values into an array of tuples, attaching the index `ind` to each bit.\n", "* [Filtered](https://learn.microsoft.com/qsharp/api/qsharp/microsoft.quantum.arrays.filtered) function will filter out the tuples based on the value of the bit, keeping only the ones for which it is true.\n", "* Finally, [Mapped](https://learn.microsoft.com/qsharp/api/qsharp/microsoft.quantum.arrays.mapped) function will keep only the indices of the remaining tuples.\n", "* [Fst](https://learn.microsoft.com/qsharp/api/qsharp/microsoft.quantum.canon.fst) and [Snd](https://learn.microsoft.com/qsharp/api/qsharp/microsoft.quantum.canon.snd) functions return the first and the second elements of the input tuple, respectively." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "%kata T09_AllMinterms\n", "\n", "open Microsoft.Quantum.Arrays;\n", "open Microsoft.Quantum.Convert;\n", "open Quantum.Kata.TruthTables;\n", "\n", "function AllMinterms (tt : TruthTable) : Int[] {\n", " let bits = IntAsBoolArray(tt::bits, 2^tt::numVars);\n", " let indexedBits = Enumerated(bits);\n", " let filteredTuples = Filtered(Snd, indexedBits);\n", " return Mapped(Fst, filteredTuples);\n", "}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "[Return to task 9 of the Truth Tables kata.](./TruthTables.ipynb#Task-9.-Find-all-true-input-assignments-in-a-truth-table)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Task 10. Apply the truth table as a quantum operation\n", "**Goal:** \n", "Apply the X operation on the target qubit, if and only if\n", "the classical state of the controls is a minterm of the truth table." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Solution\n", "\n", "A typical controlled gate (implemented by the [ControlledOnInt](https://learn.microsoft.com/qsharp/api/qsharp/microsoft.quantum.canon.controlledonint) function) applies the gate if the classical state of the control qubits matches the given integer. \n", "In our case, we need to apply the X gate if the classical state matches any one of the minterms; we can implement this by applying a series of controlled X gates, one per minterm. Since all minterms are different, the X gate will never end up being applied two or more times.\n", "\n", "> This operation is very similar to the operation [ApplyXControlledOnTruthTable](https://learn.microsoft.com/qsharp/api/qsharp/microsoft.quantum.synthesis.applyxcontrolledontruthtable) from the Q# libraries." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "%kata T10_ApplyFunction \n", "\n", "open Quantum.Kata.TruthTables;\n", "\n", "operation ApplyXControlledOnFunction (tt : TruthTable, controls : Qubit[], target : Qubit) : Unit is Adj {\n", " for term in AllMinterms(tt) {\n", " ControlledOnInt(term, X)(controls, target);\n", " }\n", "}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "[Return to task 10 of the Truth Tables kata.](./TruthTables.ipynb#Task-10.-Apply-the-truth-table-as-a-quantum-operation)" ] } ], "metadata": { "kernelspec": { "display_name": "Q#", "language": "qsharp", "name": "iqsharp" }, "language_info": { "file_extension": ".qs", "mimetype": "text/x-qsharp", "name": "qsharp", "version": "0.24" } }, "nbformat": 4, "nbformat_minor": 2 }