7COM1078 Computational Algorithms and Paradigms - University of Hertfordshire

Problem 1

The Quantum Programming Paradigm has been in existence now for more than twenty years with quantum based languages based on the imperative, functional and concurrent approaches to solving problems

a) Compare and contrast the concept of information processing employing bits, cbits, qubits and logic gates for Turing and quantum Turing based machines.

b) The quantum teleportation protocol using EPR and classical channels is now an essential ingredient in the successful development of quantum based networks. Draw, with explanation, the circuit used in the teleportation protocol. The following code is taken from the quantum based LanQ program for the teleportation protocol. Explain what is meant by the given code indicating which part of the circuit the code relates to.

#library "library.libq"
..........
void bert(channelEnd[int] c1, qbit stateToTeleportOn) { int i;
i = recv(c1); if (i == 1) {
Sigma_z(stateToTeleportOn);
} else if (i == 2) { Sigma_x(stateToTeleportOn);
} else if (i == 3) { Sigma_x(stateToTeleportOn); Sigma_z(stateToTeleportOn);
}
dump_q(stateToTeleportOn);
}

c) What Qiskit code, if any, corresponds to the above LanQ code?

Problem 2

The functional paradigm has been described as one response to the challenge of developing alternative models to the imperative paradigm for dealing with different types of problem. Examples of such problems may be found in natural language processing, rule based systems, theorem proving and symbolic computation.

a) In your own words, explain the difference between a functional paradigm and an imperative paradigm. Include in your discussion, the concept of state, assignment, referential transparency, source, domain, target, codomain and range.
(7 Marks)

The foundation of the functional paradigm is the λ - calculus developed by Alonzo Church in 1941.

b) Give an example of a lambda expression for a function that gives the cube of a real number. Is your function total or partial? Justify your answer. Hence define a pure (or uninterpreted) λ - calculus in terms of identifier, application and abstraction. Include examples for each and a set of BNF grammar rules for the syntax of the pure λ - calculus.
(6 Marks)

c) Using an example of your own describe how either Lisp or Haskell could be used to accomplish a task incorporating conditionals and recursion.

d) What is the difference between static and dynamic type checking and what are the relative advantages and disadvantages

e) Let f(n) = 3n² - 43n + 16. Show that f(n) = O(n⁴).