Lost in translation

The emergence of quantum computation has changed our perspective on many fundamental aspects of computing. The most widely used quantum computing model is the quantum circuit model (QCM). Recently, distinctly different models have emerged, collectively called measurement-based quantum computing (MBQC). They have received a wide attention as they suggest different architectures, new fault tolerant schemes, specific approaches to new applications and algorithms, and novel means to compare classical and quantum computation. These fundamentally different models for quantum computing, inspired by the Teleportation protocol, are known to be computationally equivalent to the quantum circuit model. However, only lately, other measures such as depth complexity highlighted the differences between QCM and MBQC models challenging our understanding of their structural relationship. In this talk the question of forward and backward translation between measurement- based patterns, and quantum circuit is addressed. It is known that the class of patterns with particular properties, having flow, is in one-to-one correspondence with quantum circuits. However we show that a more general class of patterns, those having generalised flow, will sometime translate to imaginary circuits, cyclic circuits that are not runnable. On the other hand since a pattern with generalised flow implements a well-defined and executable quantum operator one might be able to rewrite the obtained imaginary circuit into an equivalent acyclic circuit. Such topological rewriting rules that transform a particular class of imaginary circuits coming from well-defined MBQC patterns into a runnable equivalent circuit will be presented.