Introducing Control Flow in Qubit Allocation for Quantum Turing Machines

To make NISQ devices practical for quantum software engineers, novel programming tools with maximal flexibility have to be developed. Several proposed algorithms and error-correcting codes for near term devices require the ability to execute classical control statements based on quantum measurements. However, the unpredictable nature of control flow on a quantum device complicates the compilation process in the presence of variable noise. The functionality of control flow allows for expanded algorithmic power of the programming language in the form of conditional statements and loops, which a linearly-executed program is incapable of computing. In this work, we introduce a framework to reconcile the non-deterministic properties of quantum control flow when allocating virtual qubits from a given quantum circuit to physical qubits on a specific NISQ device in the pre-processing and compiling stage. We consider the respective connectivity and fidelity constraints, with the goal of reducing the expected error rate of the computation. Our protocols will allow for quantum developers and NISQ devices together to more efficiently exploit the compelling algorithmic power that the quantum Turing machine model provides.