Intermediate Representations for Quantum Computing

The proliferation of qubit manipulation and generation methods (ranging from optical to topological qubits) has now been matched by an explosion in terms of user-level libraries (Q#, Qiskit, etc.) which have somehow been termed "quantum programming languages". We will develop on this theme by contrasting the classical computing programming languages and the algorithms / computational model therein (von Neumann machines) and demonstrate the gap manifest between what are essentially libraries and not programming languges. In particular we will cover the closest analogs in existing libraries to formal language, grammars, parsers and finally type safety. We will explore some programming paradigms (functional, imperative, object oriented) for typical quantum algoritms (Shor's, Grovers, Simmulated Annealing). Finally, we will posit test suites for a true quantum computing language, one which has strict correspondence to the formal theory of compilers and can express algorithms compactly (grammar) while also ensuring correctness (compilation). We note that the core of compiler development has been execution independence, the ability to run on multiple platforms, and to this end, rather than describing an entire language down to a specific qubit generation method, we will instead focus on developing a quantum intermediate representation akin to LLVM compiler project.