Here is your task, along with the files, and tips. You must implement every problem sequentially step by step and explain everything you are doing in detail:


There are two particular registers with n = 1 that we use repeatedly:
traditional our vector
name name
|0⟩ k0
( 1
0
)
|1⟩ k1
( 0
1
)
To define quantum circuit expressions, we need two different ways of combining matrices: ordi-
nary matrix multiplication, and another operation called Kronecker product which is probably new
to you. We discuss these in turn.
Ordinarily, multiplying two matrices A and B is only defined if the number of columns of A
equals the number of rows of B. In this assignment, we introduce a new error matrix whose sole
role is to indicate that an error has been made, at some stage in a calculation, due to trying to
multiply incompatible matrices. It has no rows, columns or entries, and we regard it as having
n = −1. Once an error matrix appears in a calculation, you cannot get rid of it: the result of any
subsequent calculation with it will again be the error matrix. With this little “hack”, we can allow
any two matrices to be multiplied together; we just have to keep in mind the possibility of producing
the error matrix and having it “swamp” the remainder of our current calculation.
We now define the Kronecker product.
Let A = (aij )r×c be an r×c matrix, with r rows and c columns, whose i, j-entry is aij . Similarly,
let B = (bkl)s×d be an s ×d matrix, with s rows and d columns, whose k, l-entry is bkl. Then
the Kronecker product A ⊗B is the rs ×cd matrix, with rs rows and cd columns, formed by
multiplying each entry of A by a copy of B:
A ⊗B =


a11B a12B ··· a1cB
a21B a22B ··· a2cB
... ... . . . ...
ar1B ar2B ··· arcB


It can be shown that the entry in row (i −1)s + k and column (j −1)d + l of A ⊗B is aij bkl (where
1 ≤i ≤r, 1 ≤j ≤c, 1 ≤k ≤s, 1 ≤l ≤d). For example, if both A and B are 2 ×2 matrices, with
A =
( a11 a12
a21 a22
)
, B =
( b11 b12
b21 b22
)
,
then
A ⊗B =


a11b11 a11b12 a12b11 a12b12
a11b21 a11b22 a12b21 a12b22
a21b11 a21b12 a22b11 a22b12
a21b21 a21b22 a22b21 a22b22

.
Some concrete examples:
Let I be the usual 2 ×2 identity matrix,
I =
( 1 0
0 1
)
. (1)
Define H by
H =


1√2
1√2
1√2 − 1√2

. (2)
13
Then
I ⊗I =


1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1

, H ⊗H =


1
2
1
2
1
2
1
2
1
2 −1
2
1
2 −1
2
1
2
1
2 −1
2 −1
2
1
2 −1
2 −1
2
1
2


,
I ⊗H =


1√2
1√2 0 0
1√2 − 1√2 0 0
0 0 1√2
1√2
0 0 1√2 − 1√2


, H ⊗I =


1√2 0 1√2 0
0 1√2 0 1√2
1√2 0 − 1√2 0
0 1√2 0 − 1√2


. (3)
The Kronecker product can also be applied to our vectors, which are, after all, just matrices with
only one column:
k0 ⊗k1 =


0
1
0
0

, k1 ⊗k0 =


0
0
1
0

.
We see from these examples that Kronecker product is not commutative in general.
Note that the Kronecker product is always defined, regardless of the dimensions of the matrices.
Quantum gates
We use a small set of fundamental matrices, called quantum gates, to help build our expressions.
The quantum gates we use are:
I =
( 1 0
0 1
)
, H =


1√2
1√2
1√2 − 1√2

, X =
( 0 1
1 0
)
, Y =
( 0 −i
i 0
)
, Z =
( 1 0
0 −1
)
,
CNOT =


1 0 0 0
0 1 0 0
0 0 0 1
0 0 1 0

, TOF =


1 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 0


.
This set of gates is sufficient to build a quantum circuit to approximate any quantum computation
arbitrarily closely. In fact, even the two-gate set {H, TOF} is sufficient for that.
H is known as the Hadamard gate, and X, Y and Z are the Pauli-X, Pauli-Y and Pauli-Z
gates. CNOT is the controlled-not gate and TOF is the Toffoli gate. The matrix Y includes the
complex numbers ±i, where i = √−1. The other matrices are all real matrices (although combining
them with Y in any way will usually produce some complex numbers of the form a + bi where a and
b are real).
14
Languages for quantum expressions
Quantum circuit expressions are defined inductively as follows.
• Each of I, H, X, Y, Z, CNOT and TOF is a quantum circuit expression.
• If Q is a quantum circuit expression, then so is (Q).
• If P and Q are quantum circuit expressions, then so is P ∗Q. (This represents ordinary matrix
multiplication.)
• If P and Q are quantum circuit expressions, then so is P ⊗Q. (This represents Kronecker
product.)
This inductive definition can be used as the starting point for writing a Context-Free Grammar for
these expressions.
Quantum register expressions are defined inductively as follows.
• Each of k0 and k1 is a quantum register expression.
• If R is a quantum register expression, then so is (R).
• If R and S are quantum register expressions, then so is R ⊗S.
• If Q is a quantum circuit expression and R is a quantum register expression, then Q ∗R is a
quantum register expression.
This inductive definition can also be used as the starting point for writing a Context-Free Grammar.
The languages QCIRC, QREG and QUANT
We define three languages to describe the types of quantum expressions we are working with.
• QCIRC is the language, over the eleven-symbol alphabet {I, H, X, Y, Z, CNOT, TOF, *, ⊗, (, ) },
of valid quantum circuit expressions.
• QREG is the language, over the thirteen-symbol alphabet {I, H, X, Y, Z, CNOT, TOF, k0, k1, *,
⊗, (, ) }, of valid quantum register expressions.
• QUANT is their union: QUANT = QCIRC ∪ QREG.
When representing members of these languages in text, we replace ⊗ by the three-letter string (x),
which is intended to be as close as we can get, with keyboard characters, to a cross in a circle! (Note
that it uses lower-case x.) Always remember that it is our text representation of the Kronecker
product symbol ⊗; it is not an expression x enclosed in parentheses, and it is not an argument x
being supplied to some function! In this assignment, we only use the lower-case letter x in this way,
enclosed in one pair of parentheses in order to represent ⊗.
In lexical analysis, we treat (x) as the sole lexeme associated with the token KRONECKERPROD.
We also treat k0 and k1 as the sole lexemes associated with tokens KET0 and KET1, respectively.
This follows a widespread convention that token names are upper-case.
I, H, X, Y, Z, CNOT, TOF are tokens representing the names of the matrices we use as quantum
gates. Each is also the sole lexeme for its token.
The following table gives some members of QUANT. For each, we indicate in the right column
whether it belongs to QCIRC or QREG.
15
quantum string evaluates comments
expression representation to
I I see (1) QCIRC: ✓QREG: ✗
This is a 2 ×2 identity matrix and is a
valid quantum circuit expression. But
it’s not a vector, so is not a quantum
register expression.
H ⊗I H (x) I see (3) QCIRC: ✓QREG: ✗
This is also a valid quantum circuit ex-
pression, but is not a vector.
k0 ⊗k1 k0 (x) k1


0
1
0
0

 QCIRC: ✗QREG: ✓
H ∗k0 H * k0


1√2
1√2

 QCIRC: ✗QREG: ✓
(H ∗k0) ⊗(H ∗k1) (H * k0) (x) (H * k1)


1
2
−1
2
1
2
−1
2


QCIRC: ✗QREG: ✓
(H ⊗H) ∗(k0 ⊗k1) (H (x) H) * (k0 (x) k1)


1
2
−1
2
1
2
−1
2


QCIRC: ✗QREG: ✓
CNOT ∗k1 CNOT * k1 error QCIRC: ✗QREG: ✓
The attempt to multiply 4 ×4 matrix
CNOT by 2-element column vector k1
results in error. But the string still be-
longs to QREG.
(I ⊗I) ∗H ∗k1 (I (x) I) * H * k1 error QCIRC: ✗QREG: ✓
Again, an attempt at an illegal matrix
multiplication results in error. But the
string still belongs to QREG.
Some examples of invalid quantum expressions (i.e., not members of QUANT):
16
expression text repr’n comment
H ⊗k0 H (x) k0 The inductive definition of a QUANT does not allow for the Kronecker
product of a quantum circuit expression and a quantum register expres-
sion. (Mathematically, such a Kronecker product gives a valid matrix,
but not one that represents either a quantum circuit expression or a
quantum register expression.)
k0 ∗H k0 * H This product is the wrong way round. As it is, it’s a 2 ×4 matrix, so is
neither a quantum circuit expression nor a quantum register expression.
For the other way round, H * k0, see previous table.
H + I H + I + is not a valid operation in QUANT.
Power(H, 2) Power(H,2) Power is not valid in QUANT; we only use it in PLUS-TIMES-POWER.
Also, commas are not used in QUANT.
Quantum computation
The previous sections give as much detail as you need to know, at a minimum, to do the assignment.
In this section, we give a very brief introduction to some of the concepts of quantum computing. It
won’t be enough to enable you to go away and write quantum algorithms. But, if you do want to
learn how to do that, what you have learned from reading this section and doing this assignment
will make it a bit easier to get started.
Let’s consider quantum registers again. A quantum register has 2n entries, for some nonnegative
integer n. We could index them by the numbers 0, 1, . . . , 2n −1. We could also index them by
strings of n bits, with these strings being the n-bit binary representations of those index numbers
(with leading zeros allowed, this time). The following table shows a register with n = 2 and four
entries −1√2 , 0, −1
2 , 1
2 . The register is shown as a four-element vector on the right. You can verify that
its length is (|−1√2 |2 + 02 + |−1
2 |2 + |1
2 |2)1/2 = (1
2 + 1
4 + 1
4
)1/2 = 11/2 = 1, as required. On the left,
we give it in tabular form. The register’s entries are in the third column (amplitude), with the first
and second columns showing its indices as numbers and bit-strings respectively.
outcome amplitude probability
0 00 − 1√2
1
2
1 01 0 0
2 10 −1
2
1
4
3 11 1
2
1
4
register as vector

1√2
0
1
2
1
2


The bit-strings that index the entries of the quantum register are its outcomes. The entries
themselves are called the amplitudes of the outcomes.7 So, in the above register, the outcome 00
has amplitude −1√2 , while outcome 11 has amplitude 1
2 .
A classical register, in a classical computer, stores just one bit-string. But quantum registers are
very different. All the 2n outcomes, of n bits each, exist simultaneously in some sense, each with
its own amplitude. Outcomes of zero amplitude (like 01 in the above example) are impossible, but
all outcomes with nonzero amplitude are present to some extent. We say that the register is in a
superposition of all its possible outcomes.
7We follow Lipton and Regan [5] in moving freely between (i) the index of an entry in a vector representing a
register and (ii) a vector that has 1 at that index and 0 elsewhere.
17
In general, the amplitudes may be arbitrary complex numbers of length ≤ 1, subject to the
constraint that the sum of the squares of their absolute values is 1 (so that, as a vector of 2n entries,
its length is 1).
A classical register has n positions (for some n). Each position holds one bit, either 0 or 1 (but
not both!).
A quantum register also has n positions (for some n), but because of superposition, the informa-
tion at that position is not just one single bit. Rather, it is a superposition of bits, this superposition
being induced by the register’s superposition of outcomes. This superposition of bits, in a particular
position, is called a qubit, and we say that the register has n qubits.
Mathematically, classical registers may be regarded as a special case of quantum registers. A
classical register containing a given bit-string is just a quantum register in which that bit-string,
as an outcome, has amplitude 1 and all other outcomes have amplitude 0. For example, a two-bit
classical register containing 01 is equivalent to the quantum register k0⊗k1. Such a register is called
a basis register.
We mentioned measurement on page 12 in our summary of the heart of a quantum computer.
We don’t use it in this assignment, but it’s the only way we get output from a quantum computer,
so let’s consider it now.
In classical computing, reading a register will recover whatever bit-string is stored in it at the time,
and nothing else. Given that a quantum register contains 2n outcomes at once (in a superposition),
we might hope to get much more out of it! But it’s a bit trickier than that. When we read a
quantum register, we are sampling from a probability distribution over its outcomes. Each outcome
has a probability of being chosen, with that probability being the square of the absolute value of its
amplitude. These probabilities do indeed sum to 1, because the length of the register (as a vector)
is 1.
The probabilities for each of the outcomes in our example register above are given in the fourth
column of the table. If we read this register, we have a probability of 1
2 of getting 00. Outcomes 10
and 11 each have a probability of 1
4 , while outcome 01 is impossible.
For reasons related to the underlying physics, the act of reading a register is called measure-
ment.
We have so far envisaged measuring (i.e., reading) an entire quantum register. But it is also
possible to measure individual qubits, i.e., to read what is at a given position. Suppose we wanted
to measure the second qubit in the two-qubit quantum register given above. The probability of it
being 0 is the sum of the squares of the absolute values of the amplitudes of those outcomes with
second bit 0:
Pr(measurement of 2nd bit gives 0) = |amplitude of 00|2 + |amplitude of 10|2
= |−1√2 |2 + |−1
2 |2
= 3
4 .
Similarly,
Pr(measurement of 2nd bit gives 1) = |amplitude of 01|2 + |amplitude of 11|2
= |0|2 + |1
2 |2
= 1
4 .
A quantum computation proceeds by
• starting with a register with a single outcome having amplitude 1 and all other outcomes
having amplitude 0 (such a register can be formed from a Kronecker product of copies of k0
and k1);
• applying a quantum circuit — which we model as a quantum circuit expression — to the
register, thereby producing a new register;
• measuring one or more qubits of this new register. This becomes the output of the computation.
18
The initial register is not the means of providing input to the quantum computer; it is more analo-
gous to the Start State of an automaton. Input is provided to the quantum computer by using the
input in the construction of the quantum circuit. So, that circuit is determined in some computable
way by the input. Specification of how the circuit is computed from the input is part of the specifi-
cation of a quantum algorithm.
Let’s look at a couple of very simple quantum computations.
Suppose we have n = 1 (one qubit) and start with k0. Let’s use a quantum circuit consisting
solely of H. Then the computation produces
H ∗k0 =


1√2
1√2
1√2 − 1√2



 1
0

 =


1√2
1√2

.
Then, if we measure the register, we obtain
outcome =


0, with probability
( 1√2
)2
= 1
2 ;
1, with probability
( 1√2
)2
= 1
2 .
So this is like tossing a fair coin.
Now suppose we use a one-qubit circuit consisting of two consecutive applications of H. So the
quantum circuit expression is now H ∗H. Starting again with k0, we obtain
H∗H∗k0 =


1√2
1√2
1√2 − 1√2




1√2
1√2
1√2 − 1√2



 1
0

 =


1√2
1√2
1√2 − 1√2




1√2
1√2

 =

 1
0

.
So, this time, we just end up with k0 again which has only one possible outcome. Mathematically,
this is no surprise because the matrix H is its own inverse: H ∗H = I. Let’s consider what happens
in more physical terms:
1. one application of H takes us from k0, which has only one possible outcome, to a superposition
of two outcomes (so H seems to “spread out” the available amplitude across more outcomes);
2. then another application of H — which we might intuitively expect to “spread things out”
even further — actually creates “cancellation” so that only one outcome is left standing. This
phenomenon is known as interference.
Now let’s graduate to two qubits and use the quantum circuit CNOT∗(H ⊗I) with initial register
k0 ⊗k0. The final register is
CNOT∗(H⊗I)∗(k0⊗k0) =


1 0 0 0
0 1 0 0
0 0 0 1
0 0 1 0




1√2 0 1√2 0
0 1√2 0 1√2
1√2 0 − 1√2 0
0 1√2 0 − 1√2




1
0
0
0


=


1√2
0
0
1√2


.
If we measure the final register, it will give outcome 00 with probability 1
2 and outcome 11 with
probability 1
2 . Note that, in both these possible outcomes, the left and right bits are identical. So,
in the register, the left and right qubits are not independent; in fact, they are entangled.
References
[1] Michael Brooks, Quantum computers: what are they good for?, Nature 617 (S1-S3) (24 May
2023), https://doi.org/10.1038/d41586-023-01692-9. Part of Nature Spotlight: Quantum
Computing.
19
[2] David Deutsch, Quantum theory, the Church-Turing thesis, and the universal quantum computer,
Proceedings of the Royal Society of London, Series A 400 (no. 1818) (1985) 97–117.
[3] Richard P. Feynman, Simulating physics with computers, International Journal of Theoretical
Physics 21 (1982) 467–488.
[4] Richard P. Feynman, Quantum mechanical computers, Optics News 11 (February 1985) 11–20.
[5] Richard J. Lipton and Kenneth W. Regan, An Introduction to Quantum Algorithms via Linear
Algebra (2nd edn.), MIT Press, Cambridge, Ma., USA, 2021.
[6] Michael A. Nielsen and Isaac L. Chuang, Quantum Computation and Quantum Information,
Cambridge Univ. Press, 2016.
20
The number choice function
The number choice function is defined as follows.
Input: a sequence k, x1, x2, . . . , xn where
• k is a positive integer.
• For each i, xi is a nonnegative integer.
• All these numbers are encoded in unary using repetition of the letter a , with the letter
b used as a separator (in effect, playing the role of the commas). So the input sequence
k, x1, x2, . . . , xn is encoded as the string
akbax1bax2b ···axn
Output: xk, i.e., the k-th of the x-numbers.
• This also is encoded in unary in the same way, but without any b at the end. So the
output xk is encoded as the string axk.
• Recall the definition of the output of a Turing machine from Lecture 18 slide 28 (or Course
Notes §18.8 p. 223). Once the machine enters the Accept state, it does not matter what
comes after the leftmost blank cell; those later cells are not considered to be part of the
output string.
Some example inputs and outputs:
input sequence input encoded as string output number output encoded as string
3,1,5,2 aaababaaaaabaa 2 aa
2,4,7,0,3 aabaaaabaaaaaaabbaaa 7 aaaaaaa
1,0,1 abba 0 ε [first tape cell must be empty]
1,3,2,0 abaaabaab 3 aaa
3,3,2,0 aaabaaabaab 0 ε [first tape cell must be empty]
0,1,5,2 babaaaaabaa undefined crash: invalid input, k = 0
4,1,5,2 aaaababaaaaabaa undefined crash: invalid input, k > n
Notes:
• Any input string that is not of the specified form should be rejected, by crashing. Examples
of situations that must lead to a crash include: k = 0; k > n.
• You can, and should, have extra letters in your tape alphabet that are not in the input alphabet
{a,b}.
21
Universal models
We know that Universal Turing Machines exist. Motivated by this, we can ask if universality also
arises with the other abstract models for formal languages that we have been considering.
Universal regular expressions
A universal regular expression (URE) is a regular expression U over the nine-symbol alphabet
{a, b, ∪, ∗, (, ), ε, ∅, $} such that, for every regular expression R over {a,b} and every string x ∈
{a, b}∗,
R matches x ⇐⇒ U matches R$x.
The only role of $here is to serve as a separator between the regular expression R and the string x.
This is analogous to our use of $as a separator between an encoded Turing machine and its input,
when these two are combined and given as input to a Universal Turing Machine.
For example, if R is the regular expression (a ∪b)b∗a and x is the string abba then R matches x
and R$x is the string (a∪b)b∗a$abba. So any URE U would have to match the string (a∪b)b∗a$abba.
But if y is the string baa then R does not match y, so any URE U must not match R$y, which is
(a ∪b)b∗a$baa.
Universal context-free grammars
A universal context-free grammar (UCFG) is a context-free grammar U over the 18-symbol
alphabet {a, b, S, T, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, →, ε, ;, $} such that, for every context-free grammar G
over {a,b} and every string x ∈{a, b}∗,
G generates x ⇐⇒ U generates G$x.
Again, the only role of $is as a separator. We assume throughout that, apart from S, nonterminals
have names consisting of the symbol T followed by a decimal positive integer, and that the semicolon
is used as a separator between production rules in order to encode a grammar as a string. (We are
not using the vertical bar when encoding grammars here.)
For example, suppose G is the CFG
S → aT
T → aTb
T → ε
This grammar can be encoded as
S→aT1;T1→aT1b;T1→ε
We have two nonterminals, S and T1, and three production rules. Suppose x is the string aaabb.
Then G$x is the string
S→aT1;T1→aT1b;T1→ε$aaabb
Any UCFG U would have to match this string, since G generates x, but it could not match U$y
where y = bb, since G cannot generate y.


read this pdf, understand all instructions perfectly and help me go through each problem 1 by 1. Here is some extra information to help you:

n response to queries about Assignment 2, and to help track down forum posts on some issues that keep coming up, here are some answers to FAQs and reminders:

General:

You can move copies of  quant.h  into whatever directory you like.  You'll need it in Problem 1 and Problems 3-6 (unless you execute code from another directory using appropriate paths: see  #620 ).   #625   

Problem 1:

This is a straightforward editing task, requiring only some commenting and uncommenting.  But it must be done carefully and meticulously; it's not hard to miss something.  See pages 9-11.

Problem 2:

The inductive definition on p15 is the best starting point.  The process of turning this into a grammar is similar to turning an inductive definition of arithmetic expressions into a CFG for them:  see Lecture 12, Slides 3-4.

Some general tips:  see if your grammar can generate various quantum circuit expressions, including examples given in the assignment document and various simple expressions including solitary quantum gates, and also that it doesn't generate some invalid expressions like the non-QCIRC examples on pages 16-17.  It's also worth thinking about whether there's any unnecessary duplication, which may introduce ambiguity or make it harder to detect and remove any errors.

Your grammar doesn't have to be minimal, in either number of rules or number of nonterminals.  The main thing is to be correct, and of course it must be clear and verifiable.

You can use the vertical bar (correctly) if you wish, but it's not required.   #568

See also comments about grammar in Problem 4 below.

Problem 3:

This is a standalone lexical analyser that outputs to the screen; it isn't coupled with a parser.  So it's analogous to the lexical analyser given by the original provided file  plus-times-power.l.  So, be clear on what needs to be commented and uncommented in  prob3.l.  #628   #635   

Problem 4:

Take your grammar from Problem 2 and encode it in your Yacc file, but replace the start symbol  S  from your Problem 2 grammar by the Yacc nonterminal "line" instead of by "start".

The following three lines early in the Rules section of your Yacc file should be unchanged, and these should be the only lines in the Rules section where the nonterminal "start" appears:

start : line '\n' { } 

      | start line '\n' { } 

      ; 
For more detailed explanations of the above two points about "start" and "line", see  #630.

If you don't do this modification, you may find your parser can only handle one line of input: if you try and give it another line of input, then it may complain about a syntax error.  See the paragraph after Problem 4 on p4.

You need a new  %token  declaration for  
Y
Y  as well as for the others  (
I
I, 
H
H, ...).  It was inadvertently omitted from a list of these in the first version of the Assignment document, but corrected a few days after release.

If your program only outputs integers instead of matrices, or outputs some extra random-looking integers as well as matrices, then you may still be calling  printf(...) somewhere.  Make sure you use the provided C function,  printMatrix(...),  to output matrices, instead of  printf(...).

If you multiply quantum gates of different sizes, such as  H * CNOT,  then this is still a member of QCIRC because it satisfies the definition, so it must be able to be generated by your grammar.  Evaluating it should give an error message about undefined matrix product, but should not give a syntax error.  #564   #605   

Your parser may output partial results before correctly reporting an error.  That may be ok.   #631   

Make sure that quant.h is in whatever directory you're working in, and that it's included using a statement  #include "quant.h"  in the Lex and Yacc files.

Most of the above points also apply to Problem 5.

Problem 6:

Be careful and meticulous in following the instructions exactly.  Marks in this question depend on it.

Keep your student ID number to yourself.  This is confidential identity-related information, and any Computer Scientist or CS student should know the importance of keeping such information secure.

Problem 7:

Many points about what your Tuatara TMs are allowed to do or not do are covered in  #565.

Be sure to ensure that your Turing machine never stands still.

Ensure that it never attempts to move left from the leftmost tape cell.   #621   

 Both these behaviours are permitted in Tuatara but not in FIT2014 Turing machines.

You can use the Otherwise character "?" in Tuatara, provided you don't introduce nondeterminism.  You should really only do this if you're sure you understand it fully and know exactly what you're doing.

You can use ε as Tuatara shorthand for writing the same letter that you read (i.e., not changing the current letter).

You can use multiple Accept states, because they're just a cosmetic change from our FIT2014 model, enabling tidier diagrams without changing the computational model. 

But you can't use multiple Start states.

You can use any characters you like in your tape alphabet, but your input string and output string must be in the specified format using the specified letters.

You can't leave comments in Tuatara, except in state names (but keep them brief).  #573

The Turing machine tape is only infinite to the right.  #554 

In the encoding of input strings, there is no  
b
b  after the last unary number.  If the input string ends in  
b
b,  that means that the last number encoded is 0 (which, in unary, is represented by the input string).  So, the input sequence  3,3,2,0,1  is encoded as  
aaabaaabaabba
aaabaaabaabba,  while the input sequence  3,3,2,0  is  encoded as  
aaabaaabaab
aaabaaabaab.  This last example was given incorrectly in the first version of the Assignment document but was corrected on the day it was released.  #557

You can't use your own output format.  E.g., you can't introduce some "start of output string" marker at the start of the tape (or anywhere else).  Output must follow the standard definition:  Lecture 18, slide 28.    #603  #621  #666   #680   

Focus on correctness.  Your TM does not have to be as small and elegant as possible.   #563

Problem 8:

The name  
U
U  is used for the (hypothetical) Universal Regular Expression in (a) and the (hypothetical) Universal Context-Free Grammar in (b).  So it's not a name for a language.

****

here are the files you need:

plus-times-power.l:

/*  flex  file for lexical analyser for PLUS-TIMES-POWER expressions,
    which involve simple arithmetic for nonnegative integers
    with addition, multiplication and powers.
    Graham Farr, Monash University
    Initially, copied from the Wikipedia page for  lex, then modified over time.
    Last updated:   5 September 2024
*/
    
/*** Definition section ***/

%{
/* C code to be copied verbatim */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <complex.h>
#undef  I
void yyerror(char *);
#include "quant.h"
/*
#include "y.tab.h"
*/
%}


%%
    /*** Rules section ***/

            /* yytext is a string containing the matched text. */

    /* Nonnegative integers ...  */

(0|[1-9][0-9]*)   {
            printf("Token: NUMBER;  Lexeme: %s\n", yytext);
/*
            yylval.num = atof(yytext);
            return  NUMBER;
*/
        }



Power  {
            printf("Token: POWER;  Lexeme: %s\n", yytext);
/*
            yylval.str = strdup(yytext);
            return  POWER;
*/
         }



[+*(),]   {
            printf("Token and Lexeme: %s\n", yytext);
/*
            return  *yytext;
*/
        }

\n      {
            printf("Token and Lexeme: <newline>\n");
/*
            return  *yytext;
*/
        }


[ \t]   {    }     /*  skip whitespace  */


.       {
           printf("Invalid character.\n");
/*
           yyerror("invalid character");
*/
        }
     /*  will match any single character that does not match
         any of the above patterns
     */


%%
    /*** C Code section ***/

void yyerror(char *s) {
      fprintf(stderr, "line %d: yytext = %s.  Error msg: %s.\n", yylineno, yytext, s);
}


int yywrap(void) {
   return 1;
}


/*  comment out the function  main()  if using  lex  with  yacc   */
int main(void) {
    yylex();
    return 0;
}


plus-times-power.y:

/*  yacc  file for PLUS-TIMES-POWER expressions, for copying and then
    modification (of the copy) to make a calculator for quantum
    expressions.
    It already contains C functions for use by that calculator.
    Graham Farr, Monash University
    Last updated:  5 September 2024
*/

        /*   declarations   */


%{
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <complex.h>
#undef  I
#include <limits.h>
#include "quant.h"
int yylex(void);
void yyerror(char *);
int yydebug=0;   /*  set to 1 if using with yacc's debug/verbose flags   */
int  printMatrix(Matrix x);
Matrix  identity();
Matrix  had();
Matrix  pauliX();
Matrix  pauliY();
Matrix  pauliZ();
Matrix  cNot();
Matrix  toffoli();
Matrix  productMxMx(Matrix a, Matrix b);
Matrix  kroneckerProductMx(Matrix a, Matrix b);
int  printRegister(Register x);
Register  ket0();
Register  ket1();
Register  productMxReg(Matrix a, Register v);
Register  kroneckerProductReg(Register v, Register w);
%}

%union {
    int  iValue;
    char *str;
    Matrix  qmx;
    Register  qreg;
    double num;
};

%token  <num>  NUMBER
%token  <str>  POWER

%left '+'
%left '*'

%type  <iValue>  start
%type  <iValue>  line
%type  <iValue>  expr
%type  <iValue>  int

%start  start



%%       /*   rules section   */



start    :    line  '\n'       {  }
         |    start  line  '\n'          {  }
         ;

line     :    expr   {  printf("%d\n", $1);   }
         |        /*  allow "empty" expression  */           {     }
         ;
         

expr     :    int    {  $$ = $1;  }
         |    POWER '(' expr ',' expr ')'    {  $$ = pow($3,$5);  }
         |    expr '*' expr    {  $$ = $1 * $3;  }
         |    expr '+' expr    {  $$ = $1 + $3;  }
         ;

int      :    NUMBER             {  $$ = $1;   }
         ;


%%      /*   programs   */


int  printMatrix(Matrix a)
/*  print the matrix  a  */
{
  int  printfReturnValue;
  int  sumPrintfReturnValue = 0;
  int  minPrintfReturnValue = INT_MAX;
  int  n = 1<<a.dim;
  double complex  aij;
  double  aijRe;
  double  aijIm;

  if  (a.dim == -1)
  {
    return  printf("Undefined matrix product used.\n");
  }

  printfReturnValue = printf("%dx%d matrix:\n", n, n);
  sumPrintfReturnValue += printfReturnValue;
  minPrintfReturnValue = (printfReturnValue < minPrintfReturnValue ?
                          printfReturnValue : minPrintfReturnValue);
  for  (int i=0; i<n; i++)
  {
    for  (int j=0; j<n; j++)
    {
      aij = a.mx[i][j];
      aijRe = creal(aij);
      aijIm = cimag(aij);
      if  (aijRe == 0)
      {
        if  (aijIm == 0)
        {
          printfReturnValue = printf("   0.0000        ");
        }
        else if  (aijIm > 0)
        {
          printfReturnValue = printf("   0.0000+%6.4lfi", aijIm);
        }
        else   /*  aijIm < 0  */
        {
          printfReturnValue = printf("   0.0000%7.4lfi", aijIm);
        }
      }
      else   /*  aijRe != 0  */
      {
        if  (aijIm == 0)
        {
          printfReturnValue = printf("  %7.4lf        ", aijRe);
        }
        else if  (aijIm > 0)
        {
          printfReturnValue = printf("  %7.4lf+%6.4lfi", aijRe, aijIm);
        }
        else   /*  aijIm < 0  */
        {
          printfReturnValue = printf("  %7.4lf%7.4lfi", aijRe, aijIm);
        }
      }
      sumPrintfReturnValue += printfReturnValue;
      minPrintfReturnValue = (printfReturnValue < minPrintfReturnValue ?
                              printfReturnValue : minPrintfReturnValue);
    }
    printfReturnValue = printf("\n");
    sumPrintfReturnValue += printfReturnValue;
    minPrintfReturnValue = (printfReturnValue < minPrintfReturnValue ?
                            printfReturnValue : minPrintfReturnValue);
  }
  if  (minPrintfReturnValue < 0)
  {
    return  minPrintfReturnValue;
  }
  else
  {
    return  sumPrintfReturnValue;
  }
}


Matrix  identity()
/*  returns the 2x2 identity matrix ((1 0) (0 1))
*/
{
  Matrix  id;
  double complex  idmx[2][2] = {
                        { 1.0,  0.0 },
                        { 0.0,  1.0 }
                      };

  id.dim = 1;
  id.mx = malloc(2*sizeof(double complex*));
  id.mx[0] = malloc(2*sizeof(double complex));
  id.mx[1] = malloc(2*sizeof(double complex));
  id.mx[0][0] = idmx[0][0];
  id.mx[0][1] = idmx[0][1];
  id.mx[1][0] = idmx[1][0];
  id.mx[1][1] = idmx[1][1];

  return  id;
}


Matrix  had()
/*  returns the 2x2 Hadamard matrix (1/sqrt(2)) * ((1 1) (1 -1))
*/
{
  Matrix  h;
  double complex  hmx[2][2] = {
                        { 1./sqrt(2),  1./sqrt(2) },
                        { 1./sqrt(2), -1./sqrt(2) }
                      };

  h.dim = 1;
  h.mx = malloc(2*sizeof(double complex*));
  h.mx[0] = malloc(2*sizeof(double complex));
  h.mx[1] = malloc(2*sizeof(double complex));
  h.mx[0][0] = hmx[0][0];
  h.mx[0][1] = hmx[0][1];
  h.mx[1][0] = hmx[1][0];
  h.mx[1][1] = hmx[1][1];

  return  h;
}


Matrix  pauliX()
/*  returns the 2x2 Pauli X matrix ((0 1) (1 0))
*/
{
  Matrix  x;
  double complex  xmx[2][2] = {
                        { 0.0,  1.0 },
                        { 1.0,  0.0 }
                      };

  x.dim = 1;
  x.mx = malloc(2*sizeof(double complex*));
  x.mx[0] = malloc(2*sizeof(double complex));
  x.mx[1] = malloc(2*sizeof(double complex));
  x.mx[0][0] = xmx[0][0];
  x.mx[0][1] = xmx[0][1];
  x.mx[1][0] = xmx[1][0];
  x.mx[1][1] = xmx[1][1];

  return  x;
}


Matrix  pauliY()
/*  returns the 2x2 Pauli Y matrix ((0 -i) (i 0))
*/
{
  Matrix  y;
  double complex  ymx[2][2] = {
                        { 0.0,        -_Complex_I },
                        { _Complex_I,  0.0 }
                      };

  y.dim = 1;
  y.mx = malloc(2*sizeof(double complex*));
  y.mx[0] = malloc(2*sizeof(double complex));
  y.mx[1] = malloc(2*sizeof(double complex));
  y.mx[0][0] = ymx[0][0];
  y.mx[0][1] = ymx[0][1];
  y.mx[1][0] = ymx[1][0];
  y.mx[1][1] = ymx[1][1];

  return  y;
}


Matrix  pauliZ()
/*  returns the 2x2 Pauli Z matrix ((1 0) (0 -1))
*/
{
  Matrix  z;
  double complex  zmx[2][2] = {
                        { 1.0,  0.0 },
                        { 0.0, -1.0 }
                      };

  z.dim = 1;
  z.mx = malloc(2*sizeof(double complex*));
  z.mx[0] = malloc(2*sizeof(double complex));
  z.mx[1] = malloc(2*sizeof(double complex));
  z.mx[0][0] = zmx[0][0];
  z.mx[0][1] = zmx[0][1];
  z.mx[1][0] = zmx[1][0];
  z.mx[1][1] = zmx[1][1];

  return  z;
}


Matrix  cNot()
/*  returns the 4x4 matrix of the CNOT gate
*/
{
  Matrix  c;
  double complex  cmx[4][4] =
      { {1.0, 0.0, 0.0, 0.0},
        {0.0, 1.0, 0.0, 0.0},
        {0.0, 0.0, 0.0, 1.0},
        {0.0, 0.0, 1.0, 0.0},
      };

  c.dim = 2;
  c.mx = malloc(4*sizeof(double complex*));
  for  (int i=0; i<4; i++)
  {
    c.mx[i] = malloc(4*sizeof(double complex));
    for  (int j=0; j<4; j++)
    {
      c.mx[i][j] = cmx[i][j];
    }
  }

  return  c;
}



Matrix  toffoli()
/*  returns the 8x8 matrix of the Toffoli gate
*/
{
  Matrix  t;
  double complex  tmx[8][8] =
      { {1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0},
        {0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0},
        {0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0},
        {0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0},
        {0.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0},
        {0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0},
        {0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0},
        {0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0}
      };

  t.dim = 3;
  t.mx = malloc(8*sizeof(double complex*));
  for  (int i=0; i<8; i++)
  {
    t.mx[i] = malloc(8*sizeof(double complex));
    for  (int j=0; j<8; j++)
    {
      t.mx[i][j] = tmx[i][j];
    }
  }

  return  t;
}


Matrix  productMxMx(Matrix a, Matrix b)
/*  multiply two square matrices representing quantum circuits  */
{
  Matrix c;
  int  n = 1<<a.dim;
  double complex  sum;

  if  (a.dim == b.dim && a.dim >= 0)
  {
    c.dim = a.dim;
    c.mx = malloc(n*sizeof(double complex*));
    for  (int i=0; i<n; i++)
    {
      c.mx[i] = malloc(n*sizeof(double complex));
      for  (int j=0; j<n; j++)
      {
        sum = 0.0;
        for  (int k=0; k<n; k++)
        {
          sum += a.mx[i][k] * b.mx[k][j];
        }
        c.mx[i][j] = sum;
      }
    }
  }
  else   /*  matrix product undefined   */
  {
    c.dim = -1;
    c.mx = malloc(sizeof(double complex*));
  }

  return  c;
}


Matrix  kroneckerProductMx(Matrix a, Matrix b)
/*  compute the Kronecker product of two square matrices representing
    quantum circuits
*/
{
  Matrix c;
  int  na;
  int  nb;
  int  n;

  if  (a.dim >= 0 && b.dim >= 0)
  {
    na = 1<<a.dim;
    nb = 1<<b.dim;
    c.dim = a.dim+b.dim;
    n = 1<<c.dim;
    c.mx = malloc(n*sizeof(double complex*));
    for  (int ia=0; ia<na; ia++)
    {
      for  (int ib=0; ib<nb; ib++)
      {
        c.mx[ia*nb+ib] = malloc(n*sizeof(double complex));
        for  (int ja=0; ja<na; ja++)
        {
          for  (int jb=0; jb<nb; jb++)
          {
            c.mx[ia*nb+ib][ja*nb+jb] = a.mx[ia][ja] * b.mx[ib][jb];
          }
        }
      }
    }
  }
  else   /*  at least one of  a, b  is undefined   */
  {
    c.dim = -1;
    c.mx = malloc(sizeof(double complex*));
  }

  return  c;
}


int  printRegister(Register v)
/*  print the register  v  */
{
  int  printfReturnValue;
  int  sumPrintfReturnValue = 0;
  int  minPrintfReturnValue = INT_MAX;
  int  n = 1<<v.dim;
  double complex  vi;
  double  viRe;
  double  viIm;

  if  (v.dim == -1)
  {
    return  printf("Undefined product used.\n");
  }

  printfReturnValue = printf("%d-qubit register, %d-element vector:\n", v.dim, n);
  sumPrintfReturnValue += printfReturnValue;
  minPrintfReturnValue = (printfReturnValue < minPrintfReturnValue ?
                          printfReturnValue : minPrintfReturnValue);
  for  (int i=0; i<n; i++)
  {
      vi = v.reg[i];
      viRe = creal(vi);
      viIm = cimag(vi);
      if  (viRe == 0)
      {
        if  (viIm == 0)
        {
          printfReturnValue = printf("   0.0000        \n");
        }
        else if  (viIm > 0)
        {
          printfReturnValue = printf("   0.0000+%6.4lfi\n", viIm);
        }
        else   /*  viIm < 0  */
        {
          printfReturnValue = printf("   0.0000%7.4lfi\n", viIm);
        }
      }
      else   /*  viRe != 0  */
      {
        if  (viIm == 0)
        {
          printfReturnValue = printf("  %7.4lf        \n", viRe);
        }
        else if  (viIm > 0)
        {
          printfReturnValue = printf("  %7.4lf+%6.4lfi\n", viRe, viIm);
        }
        else   /*  viIm < 0  */
        {
          printfReturnValue = printf("  %7.4lf%7.4lfi\n", viRe, viIm);
        }
      }
      sumPrintfReturnValue += printfReturnValue;
      minPrintfReturnValue = (printfReturnValue < minPrintfReturnValue ?
                              printfReturnValue : minPrintfReturnValue);
  }
  if  (minPrintfReturnValue < 0)
  {
    return  minPrintfReturnValue;
  }
  else
  {
    return  sumPrintfReturnValue;
  }
}


Register  ket0()
/*  returns the column vector with entries  ( 1 0 ),  representing
    the elementary register with one qubit often denoted by  |0>,
    treated as an array of two elements indexed by 0 & 1.
*/
{
  Register  v;

  v.dim = 1;
  v.reg = malloc(2*sizeof(double complex));
  v.reg[0] = 1.0;
  v.reg[1] = 0.0;

  return  v;
}


Register  ket1()
/*  returns the column vector with entries  ( 0 1 ),  representing
    the elementary register with one qubit often denoted by  |1>,
    treated as an array of two elements indexed by 0 & 1.
*/
{
  Register  v;

  v.dim = 1;
  v.reg = malloc(2*sizeof(double complex));
  v.reg[0] = 0.0;
  v.reg[1] = 1.0;

  return  v;
}


Register  productMxReg(Matrix a, Register v)
/*  multiply the matrix  a, representing a quantum circuit, by the
    vector  v, representing a quantum register.
*/
{
  Register  u;
  int  n = 1<<a.dim;
  double complex  sum;

  if  (a.dim == v.dim && a.dim >= 0)
  {
    u.dim = a.dim;
    u.reg = malloc(n*sizeof(double complex));
    for  (int i=0; i<n; i++)
    {
        sum = 0.0;
        for  (int k=0; k<n; k++)
        {
          sum += a.mx[i][k] * v.reg[k];
        }
        u.reg[i] = sum;
    }
  }
  else   /*  matrix product undefined   */
  {
    u.dim = -1;
    /*u.reg = malloc(sizeof(double complex*));*/
  }

  return  u;
}


Register  kroneckerProductReg(Register v, Register w)
/*  compute the Kronecker product of two vectors representing
    quantum registers
*/
{
  Register  u;
  int  nv;
  int  nw;
  int  n;

  if  (v.dim >= 0 && w.dim >= 0)
  {
    nv = 1<<v.dim;
    nw = 1<<w.dim;
    u.dim = v.dim+w.dim;
    n = 1<<u.dim;
    u.reg = malloc(n*sizeof(double complex));
    for  (int iv=0; iv<nv; iv++)
    {
      for  (int iw=0; iw<nw; iw++)
      {
        u.reg[iv*nw+iw] = v.reg[iv] * w.reg[iw];
      }
    }
  }
  else   /*  at least one of  v, w  is undefined   */
  {
    u.dim = -1;
/*    u.reg = malloc(sizeof(double complex));*/
  }

  return  u;
}


/*
void yyerror(char *s) {
      fprintf(stderr, "%s\n", s);
      fprintf(stderr, "line %d: %s\n", yylineno, s);
}
*/



int main(void) {
    yyparse();
    return 0;
}


quant.h:


typedef struct
{ 
  int  dim;
  double complex**  mx;
}  Matrix;


typedef struct
{ 
  int  dim;
  double complex*  reg;
}  Register;

prob6.awk:

#  awk  program to convert a string of eight decimal digits
#  to a simple quantum register expression.
#  FIT, Monash University, Sept 2024
{
  split($0, digits, "")
  n = length($0);
  if (n != 8)
  {
    printf("ID should have eight digits.\n");
  }
  else
  {
    for (i=3; i >= 1; i--)
    {
      r = digits[i] % 4;
      if  (r == 0)
      {
        factor[i] = "H";
      }
      else  if  (r == 1)
      {
        factor[i] = "X";
      }
      else  if  (r == 2)
      {
        factor[i] = "Y";
      }
      else  #  r == 3
      {
        factor[i] = "Z";
      }
    }
    s = int(digits[4] / 2) % 4;
    if  (s == 0)
    {
      aFactor = "H";
    }
    else  if  (s == 1)
    {
      aFactor = "X";
    }
    else  if  (s == 2)
    {
      aFactor = "Y";
    }
    else  #  s == 3
    {
      aFactor = "Z";
    }
    if  (digits[4] % 2 == 1)
    {
      factor[4] = "CNOT";
      factor[5] = aFactor; 
    }
    else
    {
      factor[4] = aFactor;
      factor[5] = "CNOT"; 
    }
    for (i=7; i >= 5; i--)
    {
      r = digits[i] % 4;
      if  (r == 0)
      {
        factor[i+1] = "H";
      }
      else  if  (r == 1)
      {
        factor[i+1] = "X";
      }
      else  if  (r == 2)
      {
        factor[i+1] = "Y";
      }
      else  #  r == 3
      {
        factor[i+1] = "Z";
      }
    }
    factor[9] = "k" (int(digits[8] / 4) % 2);
    factor[10] = "k" (int(digits[8] / 2) % 2);
    factor[11] = "k" (digits[8] % 2);
    printf(" (%s (x) %s (x) %s) * (%s (x) %s) * (%s (x) %s (x) %s) * (%s (x) %s (x) %s)\n", factor[1], factor[2], factor[3], factor[4], factor[5], factor[6], factor[7], factor[8], factor[9], factor[10], factor[11]);
  }
}