Efficient sets of gates and shallow quantum circuits

In quantum computers information is encoded into quantum states and transformations between different states are realised by the quantum evolution. A basic task of a quantum computer is to evolve an initial quantum state |Ψiy to a target state |Ψf y. A priori the target state can be arbitrary (it depends on a problem we want solve using our quantum computer). A quantum computer that allows reaching any final state |Ψfy is called universal. In typical quantum architectures the evolution Ψiy Ñ |Ψf y jest is realised by a quantum circuit that is build of quantum gates. Quantum gates can act on a single qubit (1-qubit or 1-local gates) or on several qubits (k-qubit or k-local gates). Given a transformation U which realises evolution |Ψiy Ñ |Ψf y and a universal set of gates S “ tg1, . . . , gku, there will be many quantum circuits with a different arrangement and number of quantum gates that realise U. Moreover, the number of gates can also depend on a choice of a universal set, i.e. some universal sets of gates (we will call them efficient) can result with much shorter circuits than other ones.Practical realisations of quantum computers are constricted by noise and decoherence that affect large-scale quantum systems. Taking into account these destructive effects it is crucial that we find circuits with the lowest number of gates, aka circuits with the lowest depth. The main idea of this proposal is to connect recent advanced techniques from representation theory, and theory of random walks in compact groups with concrete problems concerning efficiency of quantum gates and shallow quantum circuits. In particular we would like to learn as much as possible about the efficiency of a universal gate set S from the averaging/mixing operator that corresponds to a random walk generated by S. The main objectives of the project are: Objective 1 To develop quantitive methods that allow fast identification of gate sets that give short quantum circuits. Objective 2 To study efficiency of random gate sets and of quantum circuits with architecture that allows random gates. The results of this project can be used to design efficient quantum compilers.