T2: 1. Classical Computing

Question 1

Define algorithm

Answer 1

A procedure for performing a calculation; that is, a means for evaluating f(x).

Question 2

What are the two primary resources in computing and how are they quantised in the circuit model?

Answer 2

Time - number of gates

Space - number of bits

Question 3

Define complexity class

Answer 3

A set of problems which take similar computational resources (typically time as a function of input size) to solve.

Question 4

How are algorithms classified into complexity classes

Answer 4

An upper bound is placed on computation time (as function of input bits) to give a worst case scenario

Question 5

Define the class of NP problems

Answer 5

Problems which have a verified solution in polynomial time, despite the solution being difficult to find.

Question 6

Define NP-complete problems

Answer 6

NP Problems for which, if an answer was found, could be modified to solve all NP problems, implying P=NP.

Question 7

Define computation

Answer 7

Some procedure for evaluating a given function f(x)

Question 8

What are the four functions f:{0,1} → {0,1}

Answer 8

1. Identity f(x)=x
2. NOT f(x)=not(x)
3. f(x)=0
4. f(x)=1

Question 9

What function does the NOT gate represent?

Answer 9

f(x) = x+1 modulo 2

Question 10

Why does the fanout gate not have a direct quantum analogue?

Answer 10

No cloning theorem prevents cloning of an arbitrary qubit.

Question 11

Why are there 16 gates which map two bits to one?

Answer 11

There are four possible inputs: 00, 01, 10, 11

There are 2^input ways we can uniquely assign ones and zeroes to each input.

Question 12

What properties do NOT and CNOT share, that AND, NAND and OR do not?

Answer 12

They are reversible; they map from and to the same number of bits.

Question 13

How do we label bits/qubits on a circuit diagram (numerically or alphabetically)

Answer 13

Increasing numbers as we go up/x bottom, y top etc.

Question 14

What function does the CNOT gate represent?

Answer 14

x⊕y ≔ x+y mod2

The outcome is on the top line.

Question 15

How can we use a CNOT to copy a number?

Answer 15

Initialise an ancillary bit to zero and use this as the target for a not. It will copy the control.

Question 16

What function does the CCNOT/Toffoli gate represent?

Answer 16

(x_1 and x_2) ⊕ y mod2

Question 17

Define the Universal Gate Set (UGS)

Answer 17

A finite set of gates which suffices to construct arbitrary functions f : {0, 1}^n →{0, 1}^m.

Question 18

Briefly describe how we can create an arbitrary function f : {0, 1}^n →{0, 1}^m

Answer 18

Consider a series of m functions mapping {0,1}^n→{0, 1}. Once we show each f_m can be built using a UGS, we can compose it into f. We copy the input m times using CNOTS and ancillary qubits (=0) and have each f_m act on a set of the copies.