Quantum Synthesis

Quantum circuits form the basic building blocks of quantum computers and algorithms.Current quantum algorithms are created and analysed manually and in an ad-hoc manner. We want to automatically synthesize correct circuits for given specifications, which is beyond current technologies.In this project we will develop new techniques for automated synthesis of quantum circuits.We will do this by advancing game-theoretical approaches for stochastic games and apply them to quantum synthesis problems.Specifically, we will study games with probabilistic finite automata (PFAs) as both specifications and winning strategies, extending these insights to games with quantum finite automata (QFA). QFAs, the quantum counterparts of PFAs, are the most basic models of quantum computation. We will develop specification languages capable of expressing temporal, geometric, and stochastic properties in quantum computation and study the trade-offs between their expressiveness and effectiveness of related verification problems. Finally, we will develop proof-of-concept tools to implement the methods derived from this project.