Recitations and Projects for the course of Quantum Computing and Neural Networks

Graduate course, Sapienza University of Rome, Master Degrees in Electronics Engineering and Telecommunication Engineering, 2016

On this page, you can find materials related to the recitation sessions and course projects for Quantum Computing and Neural Networks, a course offered within the Master’s Degree programmes in Electronics Engineering and Telecommunications Engineering at Sapienza University of Rome, taught by Professor Massimo Panella, PhD, with the support of the NESYA Lab.

In particular, this page provides supplementary materials covering selected topics in quantum computing, including complementary theoretical concepts, laboratory sessions, project ideas, and related resources.

Fundamental quantum algorithms: from the Deutsch-Joza problem to the Quantum Fourier Transform

As we discussed throughout the course, quantum computing has the potential to overcome certain classical computational bottlenecks using principles such as superposition, entanglement, amplitude interference and amplification. In this set of materials we will walk through a number of fundamental quantum algorithms that have been developed in the early ears of quantum computing and where the first to establish provable advantages against classical counterparts. Even if some of these algorithms require large-scale fault-tolerant quantum computers that are currently being developed and are years away from being available, analyzing them is still a good exercise to deepen the understanding about the inner workings of quantum computational devices from the software perspective, to master key techniques that have been generalized for a plethora of applications and theoretical explorations, but also to use those variants that can be used today to prove advantages in the near-term quantum computers (see, for instance, here and here).

We will start with the oracle model where parts of an algorithm are seen as given “black-boxes” that can be queried with $O(1)$ effort. In these cases, the oracle provides access to a function that is unknown to us, but, at the same time, provides a way of building a new function which can query the oracle to determine the relationship between certain input-output pairs. This is the same idea used in classical computing to “embed” an irreversible computation into a reversible one: for every irreversible Boolean gate $f:\{0,1\}^n\to \{0,1\}^m$ (e.g., $f=AND$) the extended function $G_f:\{0,1\}^{n+m}\to \{0,1\}^{n+m}$ with $m$ ancillae and the XOR gate $\oplus$ such that $G_f(x,y)=(x,y \oplus f(x))$ is bijective with inverse $G^{-1}_f=G_f$ (indeed, $(y \oplus f(x)) \oplus f(x)= y$). In the quantum setting, the oracle is precisely $O_f(\lvert x\rangle \lvert y\rangle = \lvert x\oplus f(y)\rangle$.

Now, this seems like “cheating”. Indeed, if $f$ is unknown, how can we build the quantum circuit that implements $O_f$? How can we know if this is an “efficient” circuit? A preliminary answer is that, in the oracle model, querying $O_f$ provides a lower bound on the number of steps needed for the quantum algorithm to solve a certain problem encoded by $f$. We refer to the projects below to investigate further this aspect and to see how the oracle construction helps solving classically hard problems with a quantum computer.