{
"cells": [
{
"cell_type": "markdown",
"id": "bdb06cf5-4f71-4b0f-88c1-f88efe94a673",
"metadata": {},
"source": [
"# Classical bits in Deutcsh Jozsa algorithm\n",
"\n",
"***"
]
},
{
"cell_type": "markdown",
"id": "ca1e35f6-39d2-4a99-ad3f-bb93b7b575d7",
"metadata": {},
"source": [
"
\n",
"\n",
"## Preliminarys\n",
"\n",
"***"
]
},
{
"cell_type": "code",
"execution_count": 1,
"id": "a2c83b31-a152-4ee9-a144-b38c962effb2",
"metadata": {},
"outputs": [],
"source": [
"# Returning functions.\n",
"def power(e):\n",
" \"\"\"Returns a single argument function that raises the argument to e.\"\"\"\n",
" # Define the function f. It is local to the function power.\n",
" def f(x):\n",
" # This is f's return value. Note it uses power's e variable.\n",
" return x**e\n",
" # This is power's return value. It's the function f.\n",
" # Note that in some sense f will live longer than power even though it's \"local\".\n",
" return f"
]
},
{
"cell_type": "code",
"execution_count": 2,
"id": "c36134cd-0e84-4556-aa94-e6117c23a08c",
"metadata": {},
"outputs": [],
"source": [
"# Call the power function, square is a function.\n",
"square = power(2)"
]
},
{
"cell_type": "code",
"execution_count": 3,
"id": "a62439ca-a3cb-4a59-a0af-f0afe45a1a59",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"25"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Call square.\n",
"square(5)"
]
},
{
"cell_type": "markdown",
"id": "d5dcdab1-237c-4819-95db-18f2e77053b5",
"metadata": {},
"source": [
"
\n",
"\n",
"## Constant Boolean functions\n",
"\n",
"***"
]
},
{
"cell_type": "code",
"execution_count": 4,
"id": "9cfbaa08-8ead-4ee8-94a0-52e2d828d6e2",
"metadata": {},
"outputs": [],
"source": [
"# A constant function.\n",
"def bitstobit(x0, x1, x2):\n",
" return 1"
]
},
{
"cell_type": "code",
"execution_count": 5,
"id": "64dc8211-9714-4c82-89a3-e8aa03a8177d",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Always returns 1.\n",
"bitstobit(1, 0, 1)"
]
},
{
"cell_type": "code",
"execution_count": 6,
"id": "4aa209e5-55e6-48b4-b9f0-e0080cee0531",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Always returns 1.\n",
"bitstobit(0, 0, 0)"
]
},
{
"cell_type": "code",
"execution_count": 7,
"id": "ca4776a6-e40f-4623-a7ba-5e1e001d38cf",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" x0 x1 x2 f\n",
" 0 0 0 1\n",
" 0 0 1 1\n",
" 0 1 0 1\n",
" 0 1 1 1\n",
" 1 0 0 1\n",
" 1 0 1 1\n",
" 1 1 0 1\n",
" 1 1 1 1\n"
]
}
],
"source": [
"# Print all possible inputs/outputs.\n",
"print(\" x0 x1 x2 f\")\n",
"for x0 in [0, 1]:\n",
" for x1 in [0, 1]:\n",
" for x2 in [0, 1]:\n",
" print(f\"{x0:4d} {x1:4d} {x2:4d} {bitstobit(x0, x1, x2):4d}\")"
]
},
{
"cell_type": "markdown",
"id": "4e438a74-727c-4544-8378-50baf1f5cda7",
"metadata": {},
"source": [
"
\n",
"\n",
"## Balanced Boolean functions\n",
"\n",
"***"
]
},
{
"cell_type": "markdown",
"id": "92977464-0f66-4646-a5c9-99af1891c3ce",
"metadata": {},
"source": [
"$\n",
"000 \\rightarrow (0 \\times 2^0) + (0 \\times 2^1) + (0 \\times 2^2) = 0 \\\\\n",
"001 \\rightarrow (0 \\times 2^0) + (0 \\times 2^1) + (1 \\times 2^2) = 1 \\\\\n",
"010 \\rightarrow (0 \\times 2^0) + (1 \\times 2^1) + (0 \\times 2^2) = 2 \\\\\n",
"011 \\rightarrow (0 \\times 2^0) + (1 \\times 2^1) + (1 \\times 2^2) = 3 \\\\\n",
"100 \\rightarrow (1 \\times 2^0) + (0 \\times 2^1) + (0 \\times 2^2) = 4 \\\\\n",
"101 \\rightarrow (1 \\times 2^0) + (0 \\times 2^1) + (1 \\times 2^2) = 5 \\\\\n",
"110 \\rightarrow (1 \\times 2^0) + (1 \\times 2^1) + (0 \\times 2^2) = 6 \\\\\n",
"111 \\rightarrow (1 \\times 2^0) + (1 \\times 2^1) + (1 \\times 2^2) = 7 \\\\\n",
"$"
]
},
{
"cell_type": "code",
"execution_count": 8,
"id": "2ddb867c-9f18-4970-b9b7-55460e7b1392",
"metadata": {},
"outputs": [],
"source": [
"# A balanced function.\n",
"def bitstobit(x0, x1, x2):\n",
" # Return values.\n",
" vals = [0, 1, 0, 1, 0, 1, 0, 1]\n",
" # Get the retun value's index in vals.\n",
" # e.g. 010 -> (0 x 2^0) + (1 x 2^1) + (0 x 2^2)\n",
" i = x0 * 2**0 + x1 * 2**1 + x2 * 2**2\n",
" # Return the correct value.\n",
" return vals[i]"
]
},
{
"cell_type": "code",
"execution_count": 9,
"id": "89aa74cb-f75a-4bfe-84b4-970cf5d4d520",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"bitstobit(1, 0, 0)"
]
},
{
"cell_type": "code",
"execution_count": 10,
"id": "d6fba48f-8c63-467d-97f6-f68c24d2f151",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"bitstobit(1, 1, 1)"
]
},
{
"cell_type": "code",
"execution_count": 11,
"id": "472fe341-3a95-431a-adcf-6a131c57b75d",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" x0 x1 x2 f\n",
" 0 0 0 0\n",
" 0 0 1 0\n",
" 0 1 0 0\n",
" 0 1 1 0\n",
" 1 0 0 1\n",
" 1 0 1 1\n",
" 1 1 0 1\n",
" 1 1 1 1\n"
]
}
],
"source": [
"# Print all possible inputs/outputs.\n",
"print(\" x0 x1 x2 f\")\n",
"for x0 in [0, 1]:\n",
" for x1 in [0, 1]:\n",
" for x2 in [0, 1]:\n",
" print(f\"{x0:4d} {x1:4d} {x2:4d} {bitstobit(x0, x1, x2):4d}\")"
]
},
{
"cell_type": "markdown",
"id": "a6a93657-60f9-4c34-b1bd-acaddb8aebe2",
"metadata": {},
"source": [
"
\n",
"\n",
"## All the functions\n",
"\n",
"***"
]
},
{
"cell_type": "code",
"execution_count": 12,
"id": "14f7fa11-dc5f-4129-8fb1-2b5a0e79ae37",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" x0 x1 f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15\n",
" 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1\n",
" 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1\n",
" 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1\n",
" 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1\n"
]
}
],
"source": [
"import itertools as it\n",
"\n",
"# No of bits in input.\n",
"nobits = 2\n",
"\n",
"# Generate all length four binary tuples, then transpose.\n",
"funcs = list(zip(*it.product([0,1], repeat=2**nobits)))\n",
"\n",
"# Generate all possible values of two bits.\n",
"bits = list(it.product([0,1], repeat=nobits))\n",
"\n",
"# Print a header.\n",
"th = [f\"x{i}\" for i in range(nobits)] + [f\"f{i}\" for i in range(2**2**nobits)]\n",
"print(\" \".join([(\" \" + h)[-5:] for h in th] ))\n",
"\n",
"# Print the functions.\n",
"for i in range(len(bits)):\n",
" print(\" \".join([f\"{j:5d}\" for j in bits[i]] + [f\"{j:>5d}\" for j in funcs[i]]))"
]
},
{
"cell_type": "markdown",
"id": "0f204604-8e87-4849-862c-940b7aabb59c",
"metadata": {},
"source": [
"
\n",
"\n",
"## Random function\n",
"\n",
"***"
]
},
{
"cell_type": "code",
"execution_count": 13,
"id": "47c4f93a-b2a7-4e67-b800-be8699db3997",
"metadata": {},
"outputs": [],
"source": [
"import random\n",
"\n",
"def f_bitstobit():\n",
" \"\"\"Creates a function mapping three bits to 1.\n",
" The function is randomly either constant or balanced.\"\"\"\n",
" \n",
" # Randomly decide if we're balanced or constant.\n",
" if random.random() < 0.5:\n",
" # List of eight bits, four 0's and four 1's.\n",
" vals = [0, 1] * 4\n",
" else:\n",
" # Pick 0 half the time, 1 half the time.\n",
" if random.random() < 0.5:\n",
" # Eight 1 bits.\n",
" vals = [1] * 8\n",
" else:\n",
" # Eight 0 bits.\n",
" vals = [0] * 8\n",
" \n",
" # Randiomly shuffle the values.\n",
" random.shuffle(vals)\n",
" \n",
" # Construct the function. Note this is a function within a function.\n",
" def f(x0, x1, x2):\n",
" # Get the retun value's index in vals.\n",
" i = x0 * 2**0 + x1 * 2**1 + x2 * 2**2\n",
" # Return the correct value.\n",
" return vals[i]\n",
" \n",
" # Return the function f. Note it will live on beyond this function.\n",
" return f"
]
},
{
"cell_type": "code",
"execution_count": 14,
"id": "3fdf519b-4b69-4eaa-86c1-6d4d5aab1473",
"metadata": {},
"outputs": [],
"source": [
"# Create the function. We don't know if its constant of balanced.\n",
"bitstobit = f_bitstobit()"
]
},
{
"cell_type": "code",
"execution_count": 15,
"id": "b1f3803d-fbea-47b9-ab16-cc47136793c0",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"0"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Do a test run of the function.\n",
"bitstobit(1, 0, 1)"
]
},
{
"cell_type": "markdown",
"id": "e286c42b-1c6f-46a5-940b-76f7e83434a1",
"metadata": {},
"source": [
"
\n",
"\n",
"#### Questions\n",
"\n",
"1. In the best case scenario, what is the minimum number of times we need to call `bitstobit` to determine if it is constant or balanced?\n",
"2. In the worst case scenario, what is the minimum number of times we need to call `bitstobit` to determine if it is constant or balanced?\n",
"3. If we get the same return value from four different calls to `bitsttobit`, what is the probability it is balanced?\n",
"\n",
"#### Exercise 1\n",
"\n",
"Write a function called `isbalanced` that takes a `bitstobit` function as an input and returns True if it is definitely balanced and False otherwise."
]
},
{
"cell_type": "code",
"execution_count": 16,
"id": "48c03500-3511-44e1-bcdc-4fd1fc3e313c",
"metadata": {},
"outputs": [],
"source": [
"def isbalanced(bitstobit):\n",
" \"\"\"Returns True if bitstobit is balanced, False otherwise.\"\"\"\n",
" # Make this function work here.\n",
" return True"
]
},
{
"cell_type": "code",
"execution_count": 17,
"id": "1b518b14-beb6-4b13-89a8-7c7c5a532e8b",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# This is how the above function will be called.\n",
"# Create a new random bitstobit function.\n",
"bitstobit = f_bitstobit()\n",
"# Check if it's balanced.\n",
"isbalanced(bitstobit)"
]
},
{
"cell_type": "code",
"execution_count": 18,
"id": "926f0849-03b0-4111-9e42-1ac1e822e063",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" x0 x1 x2 f\n",
" 0 0 0 0\n",
" 0 0 1 0\n",
" 0 1 0 0\n",
" 0 1 1 0\n",
" 1 0 0 0\n",
" 1 0 1 0\n",
" 1 1 0 0\n",
" 1 1 1 0\n"
]
}
],
"source": [
"# This should check that it works.\n",
"# Print all possible inputs/outputs.\n",
"print(\" x0 x1 x2 f\")\n",
"for x0 in [0, 1]:\n",
" for x1 in [0, 1]:\n",
" for x2 in [0, 1]:\n",
" print(f\"{x0:4d} {x1:4d} {x2:4d} {bitstobit(x0, x1, x2):4d}\")"
]
},
{
"cell_type": "markdown",
"id": "36dd848f-7729-486d-981c-315a89467b56",
"metadata": {},
"source": [
"
\n",
"\n",
"## General number of bits\n",
"\n",
"***"
]
},
{
"cell_type": "code",
"execution_count": 19,
"id": "c6bdf616-43e8-4582-a52c-f56c347ba044",
"metadata": {},
"outputs": [],
"source": [
"def f_bitstobit(k=3):\n",
" \"\"\"Creates a function mapping k bits to 1.\n",
" The function is randomly either constant or balanced.\"\"\"\n",
" \n",
" # Randomly decide if we're constant or balanced.\n",
" if random.random() < 0.5:\n",
" # List of 2^k bits, 2^(k-1) 0's and 2^(k-1) 1's.\n",
" vals = [0, 1] * (2**(k-1))\n",
" else:\n",
" # Pick 0 half the time, 1 half the time.\n",
" if random.random() < 0.5:\n",
" # 2^k 1's.\n",
" vals = [1] * (2**k)\n",
" else:\n",
" # 2^k 0's.\n",
" vals = [0] * (2**k)\n",
" \n",
" # Shuffle the values.\n",
" random.shuffle(vals)\n",
" \n",
" # Construct the function.\n",
" def f(xs):\n",
" # Get the retun value's index in vals.\n",
" i = sum([(xs[i] * 2**i) for i in range(len(xs))])\n",
" # Return the correct value.\n",
" return vals[i]\n",
" \n",
" # Return f.\n",
" return f"
]
},
{
"cell_type": "code",
"execution_count": 20,
"id": "75732870-9ede-4515-b47b-b7f321338ebb",
"metadata": {},
"outputs": [],
"source": [
"# Number of inputs bits.\n",
"k = 4"
]
},
{
"cell_type": "code",
"execution_count": 21,
"id": "4ec3ead2-7d0e-4053-866e-24da1fb4e33a",
"metadata": {},
"outputs": [],
"source": [
"bitstobit = f_bitstobit(k)"
]
},
{
"cell_type": "code",
"execution_count": 22,
"id": "13df7eb5-0fb4-4430-bafd-1daa70bb9c84",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[0, 0, 0, 1]"
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Make sure the bits are in a list or tuple.\n",
"t = [random.choice([0,1]) for i in range(k)]\n",
"t"
]
},
{
"cell_type": "code",
"execution_count": 23,
"id": "8b528c67-2611-42a0-bfa9-094a1e798046",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"0"
]
},
"execution_count": 23,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Example of calling bitstobit.\n",
"bitstobit(t)"
]
},
{
"cell_type": "code",
"execution_count": 24,
"id": "fce988a6-bbcb-425a-810b-ff790c6e9b94",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" x0 x1 x2 x3 f\n",
" 0 0 0 0 0\n",
" 0 0 0 1 0\n",
" 0 0 1 0 0\n",
" 0 0 1 1 0\n",
" 0 1 0 0 0\n",
" 0 1 0 1 0\n",
" 0 1 1 0 0\n",
" 0 1 1 1 0\n",
" 1 0 0 0 0\n",
" 1 0 0 1 0\n",
" 1 0 1 0 0\n",
" 1 0 1 1 0\n",
" 1 1 0 0 0\n",
" 1 1 0 1 0\n",
" 1 1 1 0 0\n",
" 1 1 1 1 0\n"
]
}
],
"source": [
"import itertools\n",
"\n",
"print(\"\".join([f\" x{i}\" for i in range(k)]) + \" f\")\n",
"for x in itertools.product([0,1], repeat=k):\n",
" print(\"\".join([f\"{i:4d}\" for i in x]) + f\" {bitstobit(x)}\")"
]
},
{
"cell_type": "markdown",
"id": "8cca67d4-11d1-4531-b4af-3490c8dcb307",
"metadata": {},
"source": [
"
\n",
"\n",
"#### Questions\n",
"\n",
"1. In the worst case, if there are 100 input bits, how many times does bitstobit have to be called to determine if the function if balanced?\n",
"2. How long will that take on the machine you're running this on?\n",
"3. How many input bits will make the number of calls required greater than the number of known atoms in the universe?\n",
"\n",
"***"
]
},
{
"cell_type": "code",
"execution_count": 25,
"id": "8b71aae5-7e62-4f86-bb70-1377f28482af",
"metadata": {},
"outputs": [],
"source": [
"import timeit"
]
},
{
"cell_type": "code",
"execution_count": 26,
"id": "133b1d80-7fce-45fd-ade9-04a9e2aa062e",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"4.3679002"
]
},
"execution_count": 26,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"timeit.timeit(lambda: bitstobit([random.choice([0,1]) for i in range(k)]))"
]
},
{
"cell_type": "markdown",
"id": "5dcbf073-157c-47f4-ad6d-e00534c9f1ae",
"metadata": {},
"source": [
"***\n",
"\n",
"## End"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.9.5"
}
},
"nbformat": 4,
"nbformat_minor": 5
}