Quantum Computation and Information Seminar 

05/06/2009, 15:00 — 16:00 — Room P4.35, Mathematics Building
Ana Maria Martins, GoLP, IST-TULisbon

Minimization of a quantum automaton

In order to understand computation in a quantum context, it might be useful to introduce as many concepts as possible from the classical computation theory to the quantum case. One of these basic concepts concerns the functioning of finite automata. In this talk I present a model of Quantum Automaton (QA), the quantum transducer, working with qubits and address the problem of minimizing its dimension and the cardinality of its state set. The quantum memory of the QA is formed by a finite number of two-level quantum particles where the information is encoded in the form of qubits. These quantum particles are prepared in an initial quantum sate that is transformed by a finite set of quantum gates (unitary operators), in accordance to a classical program (input string). Finally the QA is measured. The outputs of the QA are a set of probability measures. The quantum states of the QA are represented by density operators. Based on its linearity I use the partial trace operator jointly with the properties of quotient spaces to derive the necessary and sufficient conditions to reduce its dimension and to minimize the cardinality of its state set. These conditions depend uniquely in the structure of the unitary operators and are independent of the initial state of the QA. Based on these conditions I develop an iterative algorithm to find the minimal QA. It is also shown that the minimization of the number of qubits is possible whether the QA is finite or not. The states of the minimal QA are described by reduced density operators, obtained by applying the partial trace operator to the quantum states of the original QA. An immediate conclusion of the minimization procedure here developed is that it is also possible to minimize the number of qubits in a quantum circuit.