Monash University

Faculty of Information Technology

2

nd

Semester 2024

FIT2014

Assignment 2

Regular Languages, Context-Free Languages, Lexical analysis, Parsing,

Turing machines and Quantum Computation

DUE: 11:55pm, Friday 4 October 2024

In these exercises, you will

•implement a lexical analyser usinglex(Problem 3);

•implement parsers usinglexandyacc(Problems 1–6);

•program a Turing machine (Problem 7);

•learn about some aspects of quantum circuits and quantum registers, by applying our methods

to calculations with them (Problems 2–6);

•practise your skills relating to the Pumping Lemmas and Context-Free Languages (Problem 8).

Solutions to Problem 7 must be implemented in the simulator Tuatara. We are providing version

2.1 on Moodle under week 8; the file name istuatara-monash-2.1.jar.You must use exactly

this version, not some other version downloaded from the internet.Do not unpack this

file. It must be run directly using the Java runtime.

How to manage this assignment

•You should start working on this assignment now and spread the work over the time until it

is due. Do as much as possiblebeforeweek 10.

•Don’t be deterred by the length of this document! Much of it is an extended tutorial to get

you started withlexandyacc(pp. 7–11) and documentation for functions, written in C, that

are provided for you to use (pp. 12–17); some matrices and sample outputs also take up a fair

bit of space. There is an optional three-page introduction tosomeof the basics of quantum

computing (pp. 17–19), which is there for those who are interested in knowing more but is

not required for this assignment. Althoughlexandyaccare new to you, the questions about

them only require you to modify some existing input files for them rather than write your own

input files from scratch.

•The tasks required for the assignment are on pp. 3–6.

For Problems 1–5, read the background material on pp. 7–11.

For Problems 2–6, also read the background material on pp. 12–17.

For Problem 7, read the background material on p. 21.

For Problem 8, read the background material on p. 22.

Instructions

Instructions are mostly as for Assignment 1, except that some of the filenames have changed, and now

each Problem has its own directory. To begin working on the assignment, download the workbench

asgn2.zipfrom Moodle. Create a new Ed Workspace and upload this file, letting Ed automatically

extract it.Edit thestudent-idfile to contain your name and student ID.Refer to Lab 0

for a reminder on how to do these tasks.

Open a terminal and change into the directoryasgn2. You will find four other files already in

the directory:plus-times-power.l,plus-times-power.y,quant.handprob6.awk. You will not

modify these files directly; you will make copies of the first two and modify the copies, whilequant.h

andprob6.awkmust remain unaltered (although it’s ok to have copies of them in other directories).

1

You need to construct newlexfiles, usingplus-times-power.las a starting point, for Problems

1, 3, 4 & 5, and you’ll need to construct a newyaccfile fromplus-times-power.yfor Problems 4

& 5. Your submission must include:

•the filestudent-id, edited to contain your name and student ID

•alexfileprob1.lwhich should be obtained by modifying a copy ofplus-times-power.l

•a PDF fileprob2.pdfwhich should contain your solution to Problem 2 (with your name and

student ID at the start)

•alexfileprob3.lwhich should also be obtained by modifying a copy ofplus-times-power.l

•alexfileprob4.lwhich should be obtained by modifying a copy ofprob3.l

•ayaccfileprob4.ywhich should be obtained by modifying a copy ofplus-times-power.y

•alexfileprob5.lwhich should be obtained by modifying a copy ofprob4.l

•ayaccfileprob5.ywhich should be obtained by modifying a copy ofprob4.y

•atextfileprob6.txtwhich should contain ten lines, being your solution to Problem 6

•a Tuatara Turing machine fileprob7.tm

•a PDF fileprob8.pdfwhich should contain your solution to Problem 8 (with your name and

student ID at the start).

The original directory structure and file locations must be preserved. For each problem, the files

you are submitting must be in the corresponding subdirectory, i.e.problemxfor Problemx.

Each of these problem subdirectories contains empty files with the required filenames. These must

each be replaced by the files you write, as described above. Before submission,checkthat each of

these empty files is, indeed, replaced by your own file.

To submit your work, download the Ed workspace as a zip file by clicking on “Download All” in

the file manager panel. The “Download All” option preserves the directory structure of the zip file,

which is required to aid the marking process.You must submit this zip file to Moodle by the

deadline given above.

2

Assignment tasks

First, read about “Lex, Yacc and thePLUS-TIMES-POWERlanguage” on pp. 7–11.

Problem 1. [2 marks]

Constructprob1.l, as described on pp. 9–11, so that it can be used withplus-times-power.y

to build a parser forPLUS-TIMES-POWER.

Now refer to the document “Quantum circuits, registers and the languageQUANT”, pages 12–17.

In fact, for Problem 2, you can focus just on pages 15–17 and the languageQCIRC.

Problem 2. [3 marks]

Write a Context-Free Grammar for the languageQCIRCover the eleven-symbol alphabet

{I,H,X,Y,Z,CNOT,TOF,*,⊗,(,)}. It can be typed or hand-written, but must be in PDF

format and saved as a fileprob2.pdf.pdf.

Now we use some very basic regular expressions (in thelexfile,prob3.l) and a CFG (in the

yaccfile,prob4.y) to construct a lexical analyser (Problem 3) and a parser (Problem 4) forQCIRC.

Problem 3. [3 marks]

Using the file provided forPLUS-TIMES-POWERas a starting point, construct alexfile,

prob3.l, and use it to build a lexical analyser forQCIRC.

You’ll need to introduce simple regexps for the various tokens, among other things.

Sample output:

$./a.out

CNOT* ( H (x)I)

Token: CNOT; Lexeme: CNOT

Token and Lexeme: *

Token and Lexeme: (

Token: H; Lexeme: H

Token: KRONECKERPROD; Lexeme: (x)

Token: I; Lexeme: I

Token and Lexeme: )

Token and Lexeme:

Control-D

3

Problem 4. [6 marks]

Make a copy ofprob3.l, call itprob4.l, then modify it so that it can be used withyacc.

Then construct ayaccfileprob4.yfromplus-times-power.y. Then use theselexandyacc

files to build a parser forQCIRCthat can correctly evaluate any expression in that language.

Note that you do not have to program any of the quantum expression functions yourself.

They have already been written: see the Programs section of theyaccfile. Theactionsin your

yaccfile will need to call these functions, and you can do that by using the function call for

pow(. . .)inplus-times-power.yas a template.

The core of your task is to write the grammar rules in the Rules section, inyaccformat,

with associated actions, using the examples inplus-times-power.yas a guide. You also need

to do some modifications in the Declarations section; see page 10 and further details below.

When entering your grammar into the Rules section ofprob4.y, it is best to leave the existing

rules for the nonterminalstartunchanged, as this has some extra stuff designed to allow you to

enter a series of separate expressions on separate lines. So, take the Start symbol from your grammar

in Problem 2 and represent it by the nonterminallineinstead of bystart.

The specific modifications you need to do in the Declarations section should be:

•You need a new%tokendeclaration for the tokensI,H,X,Y,Z,CNOT,TOF, andKRONECKERPROD.

These have the same structure as the line for theNUMBERtoken, except that “num” is replaced

by “str” (since each of the above tokens represents a string, being names of matrices, registers

or operations, whereasNUMBERrepresents a number).

•You should include each of our two matrix operations,*(multiplication) andKRONECKERPROD

(the Kronecker product,⊗), in a%leftor%rightstatement. Such a statement specifies when

an operation is left- or right-associative, i.e., whether you do multiple consecutive operations

left-to-right or right-to-left. Mathematically, for*and⊗, it doesn’t matter. So, for these, you

can use either%leftor%right. But you should do one of them, because it helps the parser

determine an order in which to do the operations and removes some ambiguity. For operations

whose%leftor%rightstatements are on different lines, the operations with higher precedence

are those with higher line numbers (i.e.,laterin the file). Ordinary matrix multiplication

should have higher precedence than Kronecker product.

•For nonterminal symbols, you can include a%typeline that declares its type, i.e., the type of

value that is returned when an expression generated from this nonterminal is evaluated. E.g.,

%type start here

Here, “qmx” is the type name we are using for quantum matrices. The various type names can

be seen in the%unionstatement a little earlier in the file. But you do not need to know how

that works in order to do this task.

•You should still usestartas your Start symbol. If you use another name instead, you will

need to modify the%startline too.

Sample output:

$./a.out

CNOT* ( H (x)I)

4x4 matrix:

0.7071 0.0000 0.7071 0.0000

0.0000 0.7071 0.0000 0.7071

0.0000 0.7071 0.0000 -0.7071

0.7071 0.0000 -0.7071 0.0000

Control-D

4

Problem 5. [5 marks]

Make a copy ofprob4.l, call itprob5.l. Also, make a copy ofprob4.y, call itprob5.y. Then

modify theselexandyaccfiles further to build a parser forQUANTthat can correctly evaluate

any expression in that language.

Again, the core of your task is to write the grammar rules in the Rules section, inyacc

format with associated actions, in prob5.y. You will also need new tokensKET0andKET1,

which representk0andk1respectively. These tokens need appropriate rules inprob5.land

declarations inprob5.y, and you will use them in the grammar.

Problem 6. [5 marks]

In theproblem6directory you will find a file,prob6.awk. This is anawkprogram for converting

your student ID number to a particular quantum register expression.

Do this conversion by running thisawkprogram usingawk -f prob6.awk, then (when it

waits for your input) entering your student ID number. You will see the quantum register

expression appear as output.

(a)Copy this quantum register expression (which will be a member ofQUANT) and enter it

as the first line in the text fileprob6.txt.

(b)Run your parser on your expression from (a), and report the result of evaluating it by

appending the output to the fileprob6.txt.

The answer to (a) should be the first line of your fileprob6.txt. Your answer to (b) should

occupy the remaining nine lines. The file should therefore have ten lines altogether. You can

use wc prob6.txt to verify this.

For example, if your ID is 12345678, then your ten-line fileprob6.txtshould look like this:

(X (x) Y (x) Z) * (Y (x) CNOT) * (X (x) Y (x) Z) * (k0 (x) k0 (x) k0)

3-qubit register, 8-element vector:

0.0000

0.0000

0.0000

0.0000

0.0000

0.0000+1.0000i

0.0000

0.0000

5

Turing machines

Now refer to the description of thenumber choice functionon page 21.

Problem 7. [7 marks]

Build, in Tuatara v2.1, a Turing machine that computes the number choice function, and save

the Turing machine as a fileprob7.tm.

Context-Free Languages

Now refer to the description ofUniversal Modelson page 22.

Problem 8. [9 marks]

(a) Prove, using the Pumping lemma for Regular Languages, that there is no Universal Regular

Expression.

(b) Prove, using the Pumping lemma for Context-Free Languages, that there is no Universal

Context-Free Grammar.

Your submission can be typed or hand-written, but it must be in PDF format and saved as

a single fileprob8.pdf.

6

Lex, Yacc and thePLUS-TIMES-POWERlanguage

In this part of the Assignment, you will use the lexical analyser generatorlex, initially by itself,

and then with the parser generatoryacc

1

.

Some useful references on Lex and Yacc:

•T. Niemann,Lex & Yacc Tutorial,http://epaperpress.com/lexandyacc/

•Doug Brown, John Levine, and Tony Mason,lex and yacc (2nd edn.), O’Reilly, 2012.

•thelexandyaccmanpages.

We will illustrate the use of these programs with a languagePLUS-TIMES-POWERbased on

simple arithmetic expressions involving nonnegative integers, using just addition, multiplication and

powers. Then you will uselexandyaccon some languages related to quantum computing.

PLUS-TIMES-POWER

The languagePLUS-TIMES-POWERconsists of expressions involving addition, multiplication and

powers of nonnegative integers, without any parentheses (except for those required by the function

Power). Example expressions include:

5 + 8,8 + 5,3 + 5∗2,13 + 8∗4 + Power(2,Power(3,2)),Power(1,3) + Power(5,3) + Power(3,3),

Power(999,0),0 + 99∗0 + 1,2014,10∗14 + 74 + 10∗13∗73,2∗3∗5∗7∗11∗13∗17∗19.

In these expressions, integers are written in unsigned decimal, with no leading zeros or decimal point

(so 2014, 86, 10, 7, and 0 are ok, but +2014,−2014, 86.0, A, 007, and 00 are not).

For lexical analysis, we treat every nonnegative integer as a lexeme for the token NUMBER.

Lex

An input file tolexis, by convention, given a name ending in.l. Such a file has three parts:

•definitions,

•rules,

•C code.

These are separated by double-percent,%%. Comments begin with/*and end with*/. Any

comments are ignored whenlexis run on the file.

You will find an input file,plus-times-power.l, among the files for this Assignment. Study

its structure now, identifying the three sections and noticing that various pieces of code have been

commented out. Those pieces of code are not neededyet, but some will be needed later.

We focus mainly on the Rules section, in the middle of the file. It consists of a series of statements

of the form

pattern{action}

where thepatternis a regular expression and theactionconsists of instructions, written in C,

specifying what to do with text that matches thepattern.

2

In our file, eachpatternrepresents a set

of possible lexemes which we wish to identify. These are:

1

actually, Linux includes more modern implementations of these programs calledflexandbison.

2

This may seem reminiscent ofawk, but note that: the pattern is not delimited by slashes,/. . ./, as inawk; the

actioncode is in C, whereas inawkthe actions are specified inawk’s own language, which has similarities with C but

is not the same; and theactionpertains only to the text that matches the pattern, whereas inawkthe action pertains

to the entire line in which the matching text is found.

7

•a decimal representation of a nonnegative integer, represented as described above;

– This is taken to be an instance of the token NUMBER (i.e., a lexeme for that token).

•the specific stringPower, which is taken to be an instance of the token POWER.

•certain specific characters:+,*,(,), and comma;

•the newline character;

•white space, being any sequence of spaces and tabs.

Note that all matching inlexis case-sensitive.

Ouractionis, in most cases, to print a message saying what token and lexeme have been found.

For white space, we take no action at all. A character that cannot be matched by any pattern yields

an error message.

If you runlexon the fileplus-times-power.l, thenlexgenerates the C programlex.yy.c.

3

This is the source code for the lexical analyser. You compile it using a C compiler such ascc.

For this assignment we useflex, a more modern variant oflex. We generate the lexical analyser

as follows.

$flex plus-times-power.l

$cc lex.yy.c

By default,ccputs the executable program in a file calleda.out

4

. This can be executed in

the usual way, by just entering./a.outat the command line. If you prefer to give the executable

program another name, such asplus-times-power-lex, then you can tell this to the compiler using

the-ooption:cc lex.yy.c -o plus-times-power-lex.

When you run the program, it will initially wait for you to input a line of text to analyse. Do

so, pressing Return at the end of the line. Then the lexical analyser will print, to standard output,

messages showing how it has analysed your input. The printing of these messages is done by the

printfstatements from the fileplus-times-power.l. Note how it skips over white space, and only

reports on the lexemes and tokens.

$./a.out

13+8 * 4 + Power(2,Power (3,2 ))

Token: NUMBER; Lexeme: 13

Token and Lexeme: +

Token: NUMBER; Lexeme: 8

Token and Lexeme: *

Token: NUMBER; Lexeme: 4

Token and Lexeme: +

Token: POWER; Lexeme: Power

Token and Lexeme: (

Token: NUMBER; Lexeme: 2

Token and Lexeme: ,

Token: POWER; Lexeme: Power

Token and Lexeme: (

Token: NUMBER; Lexeme: 3

Token and Lexeme: ,

Token: NUMBER; Lexeme: 2

Token and Lexeme: )

Token and Lexeme: )

Token and Lexeme:

Try running this program with some input expressions of your own. You can keep entering new

expressions on new lines, and enter Control-D to stop when you are finished.

3

The C program will have this same name,lex.yy.c, regardless of the name you gave to thelexinput file.

4

a.outis short forassembleroutput. In some other environments, it may be calleda.exe.

8

Yacc

We now turn to parsing, usingyacc.

Consider the following grammar forPLUS-TIMES-POWER.

S−→E

E−→I

E−→POWER(E, E)

E−→E∗E

E−→E+E

I−→NUMBER

In this grammar, the non-terminals areS,EandI. TreatNUMBERandPOWERas just single

tokens, and hence single terminal symbols in this grammar.

We now generate a parser for this grammar, which will also evaluate the expressions, with +,∗

interpreted as the usual integer arithmetic operations andPower(. . . ,. . .)interpreted as raising its

first argument to the power of its second argument.

To generate this parser, you need two files,prob1.l(forlex) andplus-times-power.y(for

yacc):

•Change into yourproblem1subdirectory and do the following steps in that directory.

•Copyplus-times-power.lto a new fileprob1.l, and then modifyprob1.las follows:

–in theDefinitionssection,uncomment the statement#include "y.tab.h";

–in theRulessection, in eachaction:

∗uncomment the statements of the form

·yylval.str = ...;

·yylval.num = ...;

·returnTOKENNAME;

·return *yytext;

·yyerror ...

∗Comment out theprintfstatements. These may still be handy if debugging is

needed, so don’t delete them altogether, but the lexical analyser’s main role now is

to report the tokens and lexemes to the parser, not to the user.

–in theC codesection, comment out the functionmain(), which in this case occupies

four lines at the end of the file.

•plus-times-power.y, the input file foryacc, is provided for you. You don’t need to modify

thisyet.

An input file foryaccis, by convention, given a name ending in.y, and has three parts, very loosely

analogous to the three parts of alexfile but very different in their details and functionality:

•Declarations,

•Rules,

•Programs.

These are separated by double-percent,%%. Comments begin with/*and end with*/.

Peruse the provided fileplus-times-power.y, identify its main components, and pay particular

attention to the following, since you will need to modify some of them later.

9

•in the Declarations section:

–lines like

int printMatrix(Matrix x);

Matrix identity();

.

.

.

Register kroneckerProductReg(Register v, Register w);

which aredeclarationsof functions (but they aredefinedlater, in the Programs section);

5

–declarations of the tokens to be used:

%token NUMBER

%token POWER

–some specifications that certain operations are left-associative (which helps determine the

order in which operations are applied and can help resolve conflicts and ambiguities):

%left ’+’

%left ’*’

–declarations of the nonterminal symbols to be used (which don’t need to start with an

upper-case letter):

%type start

%type line

%type expr

%type int

–nomination of which nonterminal is the Start symbol:

%start start

•in the Rules section, a list of grammar rules in Backus-Naur Form (BNF), except that the

colon “:” is used instead of→, and there must be a semicolon at the end of each rule. Rules

with a common left-hand-side may be written in the usual compact form, by listing their

right-hand-sides separated by vertical bars, and one semicolon at the very end. The terminals

may be token names, in which case they must be declared in the Declarations section and also

used in thelexfile, or single characters enclosed in forward-quote symbols. Each rule has

anaction, enclosed in braces{. . .}. A rule for a Start symbol may print output, but most

other rules will have an action of the form$$=. . . . The special variable$$represents the

value to be returned for that rule, and in effect specifies how that rule is to be interpreted for

evaluating the expression. The variables$1,$2, . . . refer to the values of the first, second, . . .

symbols in the right-hand side of the rule.

•in the Programs section, various functions, written in C, that your parsers will be able to use.

You do not need to modify these functions, and indeed should not try to do so unless you are

an experienced C programmer and know exactly what you are doing! Most of these functions

are not used yet; some will only be used later, in Problem 4.

After constructing the newlexfileprob1.las above, the parser can be generated by:

$yacc -d plus-times-power.y

$flex prob1.l

$cc lex.yy.c y.tab.c -lm

The executable program, which is now a parser forPLUS-TIMES-POWER, is again nameda.out

by default, and will replace any other program of that name that is sitting in the same directory.

5

These functions for computing with quantum expressions are not needed byplus-times-power.y, but you will

need them later, when you make a modified version ofplus-times-power.yto parse quantum expressions.

10

$./a.out

13+8 * 4 + Power(2,Power (3,2 ))

557

13+8*4+Power(2,Power(3,2))

557

Power(1,3)+Power(5,3)+Power(3,3)

153

1+2+3+4+5+6+7+8+9+10

55

10*9*8*7*6*5*4*3*2*1

3628800

Power(999,0)

1

Control-D

Run it with some input expressions of your own. You can keep entering new expressions on new

lines, as above, and enter Control-D to stop when you are finished.

11

Quantum circuits, registers and the languageQUANT

Introduction

Roughly speaking, aquantum computeris a computer that is able to use certain capabilities

based on quantum physics in addition to the usual (“classical”) capabilities that computers have.

The idea to use quantum physics for computation arose in the 1980s with work by the physicists

Richard Feynman and David Deutsch. Interest increased considerably in the 1990s when Peter Shor

gave an efficient quantum algorithm for integer factorisation. It had been assumed that integer

factorisation was difficult; a fast factorisation algorithm could be used to break the RSA public-key

cryptosystem. RSA was the first public-key cryptosystem to be published and is still the most

widely used, underpinning the security of a large proportion of modern electronic communications.

6

.

Since then, many quantum algorithms have appeared, some improving considerably on the best

classical algorithms. But, to have any impact in practice, they will have to be implemented on

actual quantum computers and applied to large inputs.

Several dozen quantum computers have been built. Many of these are experimental, while some

have been used for highly specialised applications. But they are nowhere near powerful enough or

robust enough to be useful on a large scale. Practical quantum computing still faces huge technical

challenges including adequately protecting the delicate computations from being perturbed by the

surrounding environment. In spite of this, there is considerable optimism about their future, and

a widespread belief that, in time, their effect will be revolutionary (as well as some scepticism

about this). Although they cannot yet be used to break RSA, the threat they pose has been

taken very seriously by cryptographers, whose work has led to the development of new quantum-

resistant cryptosystems:https://www.nist.gov/news-events/news/2022/07/nist-announces-

first-four-quantum-resistant-cryptographic-algorithms.

For a recent review of the field’s current progress and prospects, see [1].

Mathematically, the heart of a quantum computer has three parts:

•aregisterthat stores information, and in fact can store multiple data items simultaneously, in

asuperposition, although these data items cannot be accessed in standard classical ways;

•aquantum circuit expression, in which certain basic components (calledgates) are combined in

order to produce a transformation that is applied to the register to produce another register;

•measurement, in which some part of a register is measured (i.e., read), but the result is de-

termined probabilistically by the entire contents of the register, and the act of measurement

reduces the amount of information held in the register.

In this assignment, we just consider registers and quantum circuit expressions, and in fact we only

consider restricted types of these. Nonetheless, our registers and expressions are sufficient, in prin-

ciple, to represent the pre-measurement parts of quantum computations arbitrarily accurately. We

define these concepts now.

Aregisteris a 2

n

-dimensional vector of unit length. It may contain complex numbers (e.g.,

i=

√

−1). Examples of registers include:

n= 0 :

1

n= 0 :

−i

n= 1 :



0.6i

−0.8



n= 2 :









1/2

−1/2

−1/2

1/2









n= 3 :

























0.6

0.2

−0.2

−0.4

0.2

−0.2

0.4

−0.4

























6

Shor also gave an efficient quantum algorithm for another number-theoretic problem called discrete log. A fast

discrete log algorithm would break the Diffie-Hellman key-exchange scheme, another important cryptographic tool.

12

There are two particular registers withn= 1 that we use repeatedly:

traditionalourvector

namename

|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 calledKronecker productwhich is probably new

to you. We discuss these in turn.

Ordinarily, multiplying two matricesAandBis only defined if the number of columns ofA

equals the number of rows ofB. In this assignment, we introduce a newerror matrixwhose 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

anytwo 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.

LetA= (a

ij

)

r×c

be anr×cmatrix, withrrows andccolumns, whosei, j-entry isa

ij

. Similarly,

letB= (b

kl

)

s×d

be ans×dmatrix, withsrows anddcolumns, whosek, l-entry isb

kl

. Then

theKronecker productA⊗Bis thers×cdmatrix, withrsrows andcdcolumns, formed by

multiplying each entry ofAby a copy ofB:

A⊗B=











a

11

B a

12

B···a

1c

B

a

21

B a

22

B···a

2c

B

.

.

.

.

.

.

.

.

.

.

.

.

a

r1

B a

r2

B···a

rc

B











It can be shown that the entry in row (i−1)s+kand column (j−1)d+lofA⊗Bisa

ij

b

kl

(where

1≤i≤r, 1≤j≤c, 1≤k≤s, 1≤l≤d). For example, if bothAandBare 2×2 matrices, with

A=



a

11

a

12

a

21

a

22



,B=



b

11

b

12

b

21

b

22



,

then

A⊗B=









a

11

b

11

a

11

b

12

a

12

b

11

a

12

b

12

a

11

b

21

a

11

b

22

a

12

b

21

a

12

b

22

a

21

b

11

a

21

b

12

a

22

b

11

a

22

b

12

a

21

b

21

a

21

b

22

a

22

b

21

a

22

b

22









.

Some concrete examples:

LetIbe the usual 2×2 identity matrix,

I=



1 0

0 1



.(1)

DefineHby

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

00

1

√

2

−

1

√

2

00

00

1

√

2

1

√

2

00

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 isalwaysdefined, regardless of the dimensions of the matrices.

Quantum gates

We use a small set of fundamental matrices, calledquantum 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

i0



, Z=



10

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.

His known as theHadamard gate, andX,YandZare thePauli-X,Pauli-YandPauli-Z

gates. CNOT is thecontrolled-not gateand TOF is theToffoli gate. The matrixYincludes the

complex numbers±i, wherei=

√

−1. The other matrices are all real matrices (although combining

them withYin any way will usually produce some complex numbers of the forma+biwhereaand

bare real).

14

Languages for quantum expressions

Quantum circuit expressionsare defined inductively as follows.

•Each ofI,H,X,Y,Z,CNOTandTOFis a quantum circuit expression.

•IfQis a quantum circuit expression, then so is (Q).

•IfPandQare quantum circuit expressions, then so isP∗Q. (This represents ordinary matrix

multiplication.)

•IfPandQare quantum circuit expressions, then so isP⊗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 expressionsare defined inductively as follows.

•Each ofk0andk1is a quantum register expression.

•IfRis a quantum register expression, then so is (R).

•IfRandSare quantum register expressions, then so isR⊗S.

•IfQis a quantum circuitexpression andRis a quantum register expression, thenQ∗Ris a

quantum register expression.

This inductive definition can also be used as the starting point for writing a Context-Free Grammar.

The languagesQCIRC,QREGandQUANT

We define three languages to describe the types of quantum expressions we are working with.

•QCIRCis the language, over the eleven-symbol alphabet{I,H,X,Y,Z,CNOT,TOF,*,⊗,(,)},

of valid quantum circuit expressions.

•QREGis the language, over the thirteen-symbol alphabet{I,H,X,Y,Z,CNOT,TOF,k0,k1,*,

⊗,(,)}, of valid quantum register expressions.

•QUANTis 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 useslower-casex.) Always remember that it is our text representation of the Kronecker

product symbol⊗; it isnotan expressionxenclosed in parentheses, and it isnotan argumentx

being supplied to some function! In this assignment, weonlyuse the lower-case letterxin this way,

enclosed inonepair of parentheses in order to represent⊗.

In lexical analysis, we treat(x)as the sole lexeme associated with the tokenKRONECKERPROD.

We also treatk0andk1as the sole lexemes associated with tokensKET0andKET1, respectively.

This follows a widespread convention that token names are upper-case.

I,H,X,Y,Z,CNOT,TOFare 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 ofQUANT. For each, we indicate in the right column

whether it belongs toQCIRCorQREG.

15

quantumstringevaluatescomments

expressionrepresentationto

IIsee (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

registerexpression.

H⊗IH (x) Isee (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 * k1errorQCIRC:✗QREG:✓

The attempt to multiply 4×4 matrix

CNOT by 2-element column vectork1

results in error. But the string still be-

longs toQREG.

(I⊗I)∗H∗k1 (I (x) I) * H * k1errorQCIRC:✗QREG:✓

Again, an attempt at an illegal matrix

multiplication results in error. But the

string still belongs toQREG.

Some examples ofinvalidquantum expressions (i.e., not members ofQUANT):

16

expressiontext repr’ncomment

H⊗k0 H (x) k0The 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∗Hk0 * HThis 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+IH + I+ is not a valid operation inQUANT.

Power(H,2)Power(H,2) Poweris not valid inQUANT; we only use it inPLUS-TIMES-POWER.

Also, commas are not used inQUANT.

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 tosomeof 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 considerquantum registersagain. A quantum register has 2

n

entries, for some nonnegative

integern. We could index them by the numbers 0,1, . . . ,2

n

−1. We could also index them by

strings ofnbits, with these strings being then-bit binary representations of those index numbers

(with leading zeros allowed, this time). The following table shows a register withn= 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

+ 0

2

+|

−1

2

|

2

+|

1

2

|

2

)

1/2

=

1

2

+

1

4

+

1

4

1/2

= 1

1/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.

outcomeamplitudeprobability

000−

1

√

2

1

2

10100

210−

1

2

1

4

311

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 itsoutcomes. The entries

themselves are called theamplitudesof the outcomes.

7

So, in the above register, the outcome00

has amplitude

−1

√

2

, while outcome11has amplitude

1

2

.

A classical register, in a classical computer, stores justonebit-string. But quantum registers are

very different. All the 2

n

outcomes, ofnbits each, existsimultaneouslyin some sense, each with

its own amplitude. Outcomes of zero amplitude (like01in the above example) are impossible, but

all outcomes with nonzero amplitude are present to some extent. We say that the register is in a

superpositionof all its possible outcomes.

7

We 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 2

n

entries,

its length is 1).

A classical register hasnpositions (for somen). Each position holds one bit, either0or1(but

not both!).

A quantum register also hasnpositions (for somen), 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 aqubit, and we say that the register hasnqubits.

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 containing01is equivalent to the quantum registerk0⊗k1. Such a register is called

abasis register.

We mentionedmeasurementon 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 2

n

outcomesat 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 aprobability distributionover 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 getting00. Outcomes10

and11each have a probability of

1

4

, while outcome01is impossible.

For reasons related to the underlying physics, the act of reading a register is calledmeasure-

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

being0is the sum of the squares of the absolute values of the amplitudes of those outcomes with

second bit 0:

Pr(measurement of 2nd bit gives0) =|amplitude of00|

2

+|amplitude of10|

2

=|

−1

√

2

|

2

+|

−1

2

|

2

=

3

4

.

Similarly,

Pr(measurement of 2nd bit gives1) =|amplitude of01|

2

+|amplitude of11|

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 ofk0

andk1);

•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 isnotthe 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 haven= 1 (one qubit) and start withk0. Let’s use a quantum circuit consisting

solely ofH. 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 ofH. So the

quantum circuit expression is nowH∗H. Starting again withk0, 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 withk0again which has only one possible outcome. Mathematically,

this is no surprise because the matrixHis its own inverse:H∗H=I. Let’s consider what happens

in more physical terms:

1. one application ofHtakes us fromk0, which has only one possible outcome, to a superposition

of two outcomes (soHseems to “spread out” the available amplitude across more outcomes);

2. then another application ofH— 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 asinterference.

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 outcome00with probability

1

2

and outcome11with

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 areentangled.

References

[1] Michael Brooks, Quantum computers: what are they good for?,Nature617(S1-S3) (24 May

2023),https://doi.org/10.1038/d41586-023-01692-9. Part ofNature 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 A400(no. 1818) (1985) 97–117.

[3] Richard P. Feynman, Simulating physics with computers,International Journal of Theoretical

Physics21(1982) 467–488.

[4] Richard P. Feynman, Quantum mechanical computers,Optics News11(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

Thenumber choice functionis defined as follows.

Input: a sequencek, x

1

, x

2

, . . . , x

n

where

•kis a positive integer.

•For eachi,x

i

is a nonnegative integer.

•All these numbers are encoded in unary using repetition of the lettera, with the letter

bused as a separator (in effect, playing the role of the commas). So the input sequence

k, x

1

, x

2

, . . . , x

n

is encoded as the string

a

k

ba

x

1

ba

x

2

b···a

x

n

Output:x

k

, i.e., thek-th of thex-numbers.

•This also is encoded in unary in the same way, but without anybat the end. So the

outputx

k

is encoded as the stringa

x

k

.

•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 sequenceinput encoded as stringoutput numberoutput encoded as string

3,1,5,2aaababaaaaabaa2aa

2,4,7,0,3aabaaaabaaaaaaabbaaa7aaaaaaa

1,0,1abba0ε[first tape cell must be empty]

1,3,2,0abaaabaab3aaa

3,3,2,0aaabaaabaab0ε[first tape cell must be empty]

0,1,5,2babaaaaabaaundefinedcrash: invalid input,k= 0

4,1,5,2aaaababaaaaabaaundefinedcrash: 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

Auniversal regular expression(URE) is a regular expressionUover the nine-symbol alphabet

{a,b,∪,∗,(,), ε,∅,$}such that, for every regular expressionRover{a,b}and every stringx∈

{a,b}

∗

,

Rmatchesx⇐⇒UmatchesR$x.

The only role of$here is to serve as a separator between the regular expressionRand the stringx.

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, ifRis the regular expression (a∪b)b

∗

aandxis the stringabbathenRmatchesx

andR$xis the string (a∪b)b

∗

a$abba. So any UREUwould have to match the string (a∪b)b

∗

a$abba.

But ifyis the stringbaathenRdoes not matchy, so any UREUmust not matchR$y, which is

(a∪b)b

∗

a$baa.

Universal context-free grammars

Auniversal context-free grammar(UCFG) is a context-free grammarUover the 18-symbol

alphabet{a,b, S, T,0,1,2,3,4,5,6,7,8,9,→, ε,;,$}such that, for every context-free grammarG

over{a,b}and every stringx∈{a,b}

∗

,

Ggeneratesx⇐⇒UgeneratesG$x.

Again, the only role of$is as a separator. We assume throughout that, apart fromS, nonterminals

have names consisting of the symbolTfollowed 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, supposeGis the CFG

S→aT

T→aTb

T→ε

This grammar can be encoded as

S→aT1;T1→aT1b;T1→ε

We have two nonterminals,SandT1, and three production rules. Supposexis the stringaaabb.

ThenG$xis the string

S→aT1;T1→aT1b;T1→ε$aaabb

Any UCFGUwould have to match this string, sinceGgeneratesx, but it could not matchG$y

wherey=bb, sinceGcannot generatey.

22