Insights from Chapter 1 of Introduction to Classical and Quantum Computing​
​by Roman Parker​
​Intern, Wolfram Research
Introduction to Classical and Quantum Computing ( http://www.thomaswong.net/introduction-to-classical-and-quantum-computing-1e.pdf ) is an introductory textbook designed to teach the mechanics of computing, especially quantum programming and computation, without requiring the calculus foundation that most courses and books on this subject require. Its first chapter covers basic logic and computation, starting with a probabilistic understanding of states, moving to logic gates, and finishing with error correction, complexity, and Turing Machines. These concepts provide an important basis for the rest of the subjects in the book, which dive deeper into the quantum side of things.

Section 1.1: Bits

The first major theme of the chapter is states and probability, focusing on how many states there are and how to encode something using them. To begin with, the chapter focuses on basic counting of states.

Encoding Size

Question 1.3

This question asks us how many 20-sided die are required to encode a value with 7 states. This can easily be solved by noticing that a 20-sided die could have 1-7 represent those seven states, while the rest of the sides aren’t necessary, but it is possible to make this into a formula. By finding the logarithm of the number of states to be encoded in the base of the number of sides, then taking the ceiling (since we can’t have fractional die), we can find how many die are needed to represent those states.
In[]:=
Log[20,7]//Ceiling
Out[]=
1

Converting Encodings

Question 1.7

Next, the chapter switches topics to focus on converting between bases and other representation forms. This is related to the problems involving states as, in reality, representing a number with some amount of N-sided dice is the same as converting that number to base N. The first part of this problem concerns converting 3B7C from hexadecimal to decimal. To do this, we use Interpreter[“HexInteger”]. I do not know whether this differs at all from FromDigits[“3B7C”,16], but Interpreter is usually better at returning valid results from edge cases. Either way, both functions take a string representing a base-16 number as input and convert it into a base-10 number.
In[]:=
Interpreter["HexInteger"]@"3B7C"
Out[]=
15228
The second part involves converting FF from hexadecimal to binary. This can most easily be done by converting it into a decimal number, getting the list of digits in base 2, and using FromDigits to combine these together (for display purposes).
In[]:=
FromDigits@IntegerDigits[Interpreter["HexInteger"]@"FF",2]
Out[]=
11111111
The final section of this problem involves converting a hex code into the color values. Here, we first use Interpreter[“Color”], which returns a RGBColor object of the form RGBColor[r,g,b], where r, g, and b are values from 0 to 1. Replacing the head of RGBColor with List gives us a list of the RGB values, which, when multiplied by 255, gives us the values in the form we want.
In[]:=
Interpreter["Color"]["#FA10E4"]
Out[]=
In[]:=
List@@Interpreter["Color"]["#FA10E4"]*255
Out[]=
{250,16,228}

Question 1.8

Two’s Complement is another form of encoding, which allows for representing negative numbers in binary with only one extra bit (although it does need a fixed-length representation). The function implemented here to convert from binary to two’s complement takes an input in the form of a string (same as FromDigits) and returns a decimal integer. First, we convert the string into a list of digits by using FromDigits to turn “111” into 111, then using IntegerDigits to split it into a list of digits. Then, we take all but the first element of this list and convert it to base 2 as normal. Finally, we subtract from this the first value of the list multiplied by its positional value, which is 2^(length - 1).
​
This code here has a few quirks in an attempt to make it shorter, like using prefix and infix notation whenever possible and using 2^Length@x/2 instead of 2^(Length@x-1) to avoid parentheses. These same techniques can also be seen in the input generation code, plus a few extras. Array is used instead of Table since, even though it requires the addition of an &, the specification of a variable can be skipped, removing four characters. Additionally, the Array counts from 1 to 8 instead of from 0 to 7 since that would require removing the infix notation (adding a character) and adding two characters to specify the starting index, which, when put together, is longer than subtracting 1.
In[]:=
v=StringJoin[ToString/@IntegerDigits[#-1,2]~PadLeft~3]&~Array~8
Out[]=
{000,001,010,011,100,101,110,111}
In[]:=
Block[{x=FromDigits/@Characters@#},Rest@x~FromDigits~2-2^Length@x/2*x[[1]]]&/@v
Out[]=
{0,1,2,3,-4,-3,-2,-1}

Question 1.10

The final topic of the chapter is converting to and from character codes. Wolfram Language has a builtin function to perform this, but it takes the input as a base-10 number instead of a base-2 string. For that reason, we have to convert from binary into decimal first, which can all be handed by FromDigits. Interestingly, there’s a typo in the book here. The second character should be 1110101, but it is instead 1010001.
In[]:=
FromCharacterCode[#~FromDigits~2&/@{"1010001","1010001","1100001","1101110","1110100","1110101","1101101"}]
Out[]=
QQantum

Section 1.2: Logic Gates

Then, the book changes gears and focuses on logic gates. The first part of this is focused on combining these gates and creating truth tables.

Basic Logic

Question 1.11

These first few problems simply concern implementing the shown functions, so the main portion of the code is simply used to create a truth table. Since our only task is to invert the inputs of an Or gate, we use Or[Not[a],Not[b]]. First, we use Tuples[{False,True},2] to create the left hand side of the table, then we negate these values and replace the List head with Or, so that {False, False} becomes Or[True,True]. Then, we put these values in a grid (after transposing them) and display.
In[]:=
Grid[Transpose@{Tuples[{False,True},2],Or@@#&/@(Not/@#&/@Tuples[{False,True},2])},Frame->All]
Out[]=
{False,False}
True
{False,True}
True
{True,False}
True
{True,True}
False
This truth table is identical to that of NAND, which verifies DeMorgan’s Laws in that Or[!a,!b] is the same as !And[a,b] (AKA NAND).

Question 1.19

Skipping forward to a more complex example, here, we have to implement a circuit diagram. Simply put, it’s Not[And[Or[a,b],Nand[c,c]]], which can be simplified to !And[Or[a,b],!c]. This is true whenever c is true or both a and b are false, which our truth table backs up. A few changes have been made to the display functions here, including using a Dataset with an Association to get headers and using {False,True}[[a]] inside of a Table[___,{a,2}] to output all possible value combinations in a simpler and more flexible way.
In[]:=
Table[<|"a"->{False,True}[[a]],"b"->{False,True}[[b]],"c"->{False,True}[[c]],"Output"->Not[And[Or[{False,True}[[a]],{False,True}[[b]]],Nand[{False,True}[[c]]]]]|>,{a,2},{b,2},{c,2}]//Dataset
Out[]=
a
b
c
Output
False
False
False
True
False
False
True
True
False
True
False
False
False
True
True
True
True
False
False
False
True
False
True
True
True
True
False
False
True
True
True
True

Question 1.20

This problem asks us how many possible logic gates there are with n input bits. Each output value can have two possible values, and if there are n input bits, there’s 2^n outputs (one for each combination of inputs), so for n bits, there are 2^2^n logic gates.
In[]:=
Length[{False,True}]^(Length[{False,True}]^#)&/@Range[5]
Out[]=
{4,16,256,65536,4294967296}
Then, we move to determining which logic gates are universal and the various sets of gates which define each other.

Gate Universality

Question 1.21

For the next few questions, we focus on converting from one set of gates to another, and trying to prove that it is possible to create all circuits with various different combinations of gates.
This first problem is to represent Xor using only Not, And, and Or. Since Xor is the same as Or except when a and b are both true, we can use And[Or[a,b],Not[And[a,b]]]. Additionally, we use Column@Flatten here to display the truth table values vertically without needing the more complicated Grid/Dataset method.
In[]:=
Column@Flatten@Table[Xor[{False,True}[[a]],{False,True}[[b]]],{a,2},{b,2}]
Out[]=
False
True
True
False
In[]:=
Column@Flatten@Table[And[Or[{False,True}[[a]],{False,True}[[b]]],Not[And[{False,True}[[a]],{False,True}[[b]]]]],{a,2},{b,2}]
Out[]=
False
True
True
False

Question 1.25

The goal of this problem was to obtain the truth table below with only Nand gates. I noticed that it was the same as !Xor[a,b], so I realized that if I could find a way to implement the “insides” of the definition of Xor, Nand instead of And would result in this gate. After that, it was mostly trial and error until I found that Nand[Nand[a,b],Nand[Nand[a],Nand[b]]] reduces to !And[!And[a,b],!And[!a,!b]], which is And[!And[a,b],Or[a,b]]. We can also improve on the truth table display function here by making it work with grid display without the difficult programming that came with the Tuple method.
In[]:=
Grid[Flatten[Table[Module[{a={False,True}[[x]],b={False,True}[[y]]},{{a,b},Nand[Nand[a,b],Nand[Nand[a],Nand[b]]]}],{x,2},{y,2}],1],FrameAll]
Out[]=
{False,False}
True
{False,True}
False
{True,False}
False
{True,True}
True

Section 1.3: Adders (and Verilog):

Here, we focus on defining adders (half and full) and examining their properties. Normally, these functions would be programmed in Verilog, but for the sake of this essay, they have been implemented in Mathematica instead.

Basic Implementation

Question 1.29

This first circuit is an always-true gate. It contains Or[___,Or[b,!b]], which is the same as Or[___,True], so there is no possible way for it to be false. This problem was initially in this section just to give an example for coding in Verilog, but I thought it was an interesting enough example to show.
In[]:=
Grid[Flatten[Table[Module[{a={False,True}[[x]],b={False,True}[[y]]},{{a,b},Or[a,Or[b,!b]]}],{x,2},{y,2}],1],Frame->All]
Out[]=
{False,False}
True
{False,True}
True
{True,False}
True
{True,True}
True

Full Adders

Question 1.30
This problem is our first to show the full adder, which has three inputs and two outputs. The first output is simply Xor[Xor[a,b],c], while the second output is Or[And[Xor[a,b],c],And[a,b]]. This means that the first output is true either when exactly one or three of the inputs is true, while the second input is true if at least two inputs are true. This can be thought of as a function which sums A and B and adds a “carry” of C. The first output is the first output it, while the second is either the “carry” or the second bit, as the full adder combines three 1-bit numbers into one 2-bit number. By combining these together and feeding the outputs in as inputs into more adders, it is possible to sum multi-bit numbers.
​
Specifically, this problem asks us to prove that replacing the Or in the second output with an Xor makes no difference. Creating the truth tables allows us to verify this, but it also makes sense. For the second input into Or[And[Xor[a,b],c],And[a,b]] to be true, a and b must both be true, while for the first input to be true, exactly one of the two inputs must be true, but NOT both. Therefore, the full adder encounters no situations where Xor would behave different than Or.
In[]:=
xorTable=Grid[Flatten[Table[Module[{a={False,True}[[x]],b={False,True}[[y]],c={False,True}[[z]]},{{a,b,c},Xor[Xor[a,b],c],Or[And[Xor[a,b],c],And[a,b]]}],{x,2},{y,2},{z,2}],2],FrameAll]
Out[]=
{False,False,False}
False
False
{False,False,True}
True
False
{False,True,False}
True
False
{False,True,True}
False
True
{True,False,False}
True
False
{True,False,True}
False
True
{True,True,False}
False
True
{True,True,True}
True
True
The book also contained several problems about combining together multiple full adders to sum larger numbers, but they didn’t seem to add much.

Section 1.4: Circuit Simplification and Boolean Algebra

Now, we work on simplifying and combining logic gates, which can easily be done through BooleanMinimize. There are various rules of logic which can allow us to do this by hand, including commutativity, associativity, and distributivity of And/Or and various two-variable identities. However, BooleanMinimize often allows for an automated solution which is significantly simpler.

Simplification and BooleanMinimize

Question 1.34

Here, our goal is to simplify !And[!a,Or[a,!b]]. And[!a,Or[a,!b]] can only be true if a and b are both false, so we can replace that with Nor[a,b]. !Nor[a,b] is the same as Or (by definition), so !And[!a,Or[a,!b]] is the same as Or[a,b], which we can see is also the result BooleanMinimize gives us.
Occasionally, BooleanMinimize will not simplify to exactly the same expression as a human might, as we will see in the next problem. It seems to prefer more readable/understandable expressions over the shortest possible, but it’s almost always easy to fix

Question 1.36

For this problem, we are given a very large circuit and have to simplify it. Starting at the end, we have an Or gate with three inputs. The first input is And[a,b,c], the second is And[!a,b,c], while the final one is And[a,b,!c], so our initial structure is Or[And[a,b,c],And[!a,b,c],And[a,b,!c]]. However, if we think about it, Or[And[a,b,c],And[!a,b,c]] is just the same as And[b,c], while Or[And[a,b,c],And[a,b,!c]] is identical to And[a,b]. This lets us simplify to Or[And[a,b],And[a,c]]. This is what BooleanMinimize outputs.
​
However, it is possible to simplify slightly further. Since And is distributive, we can move the Or inside the Ands to remove a gate. Therefore, the simplest form is instead And[a,Or[b,c]].

Section 1.5: Reversible Logic Gates

Switching gears again, the book covers what makes gates reversible/irreversible and how to modify a gate to make it reversible. Reversible gates are gates such that it is possible to reproduce the inputs of the gate from the outputs, like Not, while irreversible gates have multiple inputs which correspond to the same output, like Or.

Determining Reversibility

Question 1.39

For this problem, we have to see which of the following two-output gates are reversible. Our first gate is a half-adder (Xor[a,b], And[a,b]). We can see that on a half-adder, it’s too “symmetric” and {True,False} can’t be distinguished from {False,True}, so therefore, it is not reversible.
However, Xor[a,b], b has 4 distinct output values, so by definition, it’s reversible. There is a 1-to-1 correspondence between input pairs and output pairs.
If #distinct outputs< #distinct inputs, it has to be irreversible, since we can see that by the Pigeonhole Principle, at least two inputs will have to share an output.

Question 1.40

Here, we are told a simple definition of the Fredkin gate (if A is true, swap B and C, otherwise change nothing) and have to find if it is reversible. This shows one of the powers of this truth table function, in that we don’t have to use only logic gates in our definitions. By using a simple If[a,c,b] statement instead of Or[And[!a,b],And[a,c]], we can make things significantly simpler and more intuitive.
​
For the reversibility question, we have two options. If we go through the truth table, we can see we have eight distinct output combinations, so it is reversible. On the other hand, we can also intuit this through the definition. We can always determine what a was, since a is returned as the first element in the output. Then, from there, we know that the second element is either b or c (depending on a) and the third element is the other one. Since we know a, it is trivial to determine whether the second element is identical to b or c, and then the third element must be the other. Therefore, the Fredkin gate is reversible.

Question 1.41

Now, we look at the Toffoli gate, a logic gate with three inputs and three outputs which is similar to And, but is reversible. The first two outputs are identical to the first two outputs, while the final output provides our And gate. However, if c is true, we instead have a Nand gate, as we take the Xor of And[a,b] with c. This means that we can reconstruct the inputs with ease and control whether the And gate is “on” or not.
This problem set primarily concerns implementing the anti-Toffoli gate, which instead of using And[a,b], uses And[!a,!b].The anti-Toffoli gate is relatively easy to program, as simply negating the two values inside the And functions well.
By DeMorgan’s Laws, we can replace And[!a,!b] with !Or[a,b] (AKA Nor), so the anti-Toffoli gate is a controlled Nor gate. When c is False, the third output is only true if a and b are both false, while if c is True, the third output is true in all cases where both a and b are not false.
To convert the Toffoli gate into an anti-Toffoli gate without modifying the third output, there are a few tricks we can use. By replacing a and b with !a and !b, the third output of a Toffoli gate will be identical to that of a “regular” anti-Toffoli gate. However, this flips the first two outputs, so we have to negate them. Therefore, adding a ! before the first two outputs and the first two INPUTS (in the first input of Module) switches to an anti-Toffoli.

Adding Reversibility

Question 1.45

The final question we will cover in this section concerns making the full-adder reversible. We can see that although only one input combination returns False, False and only one returns True, True, there are three each that return False, True and True, False. It is impossible to distinguish between three different inputs with only one Boolean output value to tell them apart, so we will have to add at least two additional outputs. The original full-adder returned True, False for all cases with one true input and False, True for all cases with two, so we need to be able to distinguish between a, b, or c being the one value that differs from the other two. The simplest way to do this is to output a and c as our third and fourth output, as if one of them is True (in the case with only one true input), we know the exact input, and if both are False, b must be True. The same logic applies to the two true inputs case, simply replacing True with False.

Section 1.6: Error Correction

Section 1.6 focuses on errors, how to correct them, and the techniques used in their prevention. It starts with simple techniques like parity bits for detection, then moves to techniques for error correction. I was surprised the book didn’t cover Hamming codes, as those are one of the most prevalent and effective methods of error correction for their size, but they are slightly more complex.

Correcting Errors

Question 1.48

Here, we look at using repeated bits to catch errors. By repeating each bit three times, it is possible to catch errors as long as a single-bit error doesn’t occur twice on the same set of three bytes (ignoring swap errors and other more complicated forms of errors). First, we have to find where an error is located if we have odd parity on both the left and right.
If the parity between the leftmost two is odd, that means the two are different, meaning that one of them has an error. Since we also know that the rightmost two differ, the error must be in the middle. We can apply this same technique when we see an odd parity on the left but not on the right.
This shows us that the error must be on the left, since on the right, the two elements are identical.
Then, we can calculate the chance of two 1-bit errors happening to a 3-bit string for any given error rate. This can be done by finding the chance of exactly two errors happening and adding the chance of three errors.
Interestingly, if 70% of bits have errors, the error correction is detrimental, as it is more likely to get two errors out of three bits than to get one error on one bit.

Question 1.49

Finally, we move on to a 5-bit case, which can correct two errors instead of just one. If the parity of two sets of adjacent bits are wrong and no others are (like bit 4 and 3, and bits 3 and 2), the middle bit must have the error. On the other hand, if there is a single pair with incorrect parity, it must be whichever endpoint is contained within that string. Finally, in cases with three or four parities wrong, “fix” one error, then apply the same technique again.
Now, we can solve to see what error rates cause the 5-bit system to be better than random chance using a generalized version of the function we used before.
Obviously, the negative chance and the chance above 1 do not correspond to real probabilities, but we can see that as long as the error rate is less than 50%, it is more likely that the 5-bit expression will remain intact. Using these formulae, we can check to see if the 3-bit or 5-bit method performs better when the error rate is 10%.
It seems that the 5-bit method is better in this case. It turns out that as long as the error rate is below 50% (where either method is helpful), the 5-bit method always performs better.

Section 1.7: Computational Complexity

This section moves away from logic to focus on computational complexity and varying definitions of it. These last few sections had very few computationally applicable questions, so I picked the ones that I thought gave a basic summary of the topics.

Basic Complexity

Question 1.50

Here, our first goal is to find out at what point 5247*x^2 becomes smaller than 11*x^3. This can quite easily be done using Solve, but it demonstrates how eventually, the higher exponent will outpace the lower one, no matter the constants.
Finally, we have to determine which complexity classes of 11*x^3 we can put 5247*x^2 into. 5247*x^2 falls into o(11*x^3) quite obviously, as it scales slower, and by definition, that means it is also in O(11*x^3). However, it is not in Θ(11*x^3), Ω(11*x^3), or ω(11*x^3), as it scales slower and all three of those require at least equal speed of scaling.

Section 1.8: Turing Machines

The final section with problems focuses on Turing machines and their creation. Thankfully, WL has a series of built-ins to help with this.

Creating Turing Machines

Question 1.58

This question asks us to implement a Turing machine where when the head is in state 1 and encounters a False, the head will switch to state 2, and otherwise keep moving to the right until it encounters an empty cell, where it outputs False/True based on its state, respectively.
​
TuringMachine is a bit of a confusing function, and I don’t know if my implementation of the machine is the most clear or simplest. TuringMachine uses a list of rules of the form {state of head, value of cell}->{new state of head, new value of cell, how much to move by}, which can be adapted either from the list given in the book or from the verbal description I gave above. Then, the second input is of the form {starting state, starting values on tape}, and the third determines how many iterations to run.
​
I instructed the program to run for 10 iterations (since there was no way it would take longer than that with this short of a starting tape), and gave it an input of all 2-bit Boolean value combinations. After running the machine, it appears that it returns the same values as a Nand gate, which makes sense, as it makes no modifications to the early sections of the tape, but as soon as it encounters a False, its output (once it reaches the end) becomes True.
Additionally, even with an extra input, it still behaves the same way as a 3+ input Nand gate would be expected to.

Question 1.59

The final (codeable) question in the book concerns implementing a parity function (an Xor gate). We can implement this similarly to the Nand gate, but instead of switching from state 1 to 2 upon encountering False, this one flips state whenever it encounters a True. Just like the Nand gate, however, the head behaved identically in states 1 and 2, always moving rightwards and changing no values, except for the fact that when it reaches a blank cell, state 1 enters False and state 2 writes True. Then, we can have the head swap into state 3 (which does nothing).