Institute of Information Science, Academia Sinica

Talk 1:
Undecidability on Quantum Finite Automata
Kazuo Iwama (Kyoto University)

Abstract:
The end of the last century was a peak time for the quantum research from an algorithmic/mathematical point of view. We had Show's factoring algorithm, Grover's searching algorithm and much more. In this talk, we study quantum finite automata, probably the simplest computation model but more imaginable as a "computer" than quantum circuits, which also emerged dramatically around this time. Because of the model's simplicity, it is easier and more direct to understand the essential power (and restriction) of quantum mechanism rather than quantum Turing machines for which most other results are based on.
For instance, we can describe the condition for unitary transformation as a simple rule for state transitions. It turns out that quantum finite automata are much more powerful than they seem and we see where that power comes from.

Discussion & Break

Talk 2:
On relating one-way classical and quantum communication complexities
Han-Hsuan Lin (NTHU)

Abstract:
Communication complexity is the amount of communication needed to compute a function when the function inputs are distributed over multiple parties. In its simplest form, one-way communication complexity, Alice and Bob compute a function $f(x,y)$, where $x$ is given to Alice and $y$ is given to Bob, and only one message from Alice to Bob is allowed. A fundamental question in quantum information is the relationship between one-way quantum and classical communication complexities, i.e., how much shorter the message can be if Alice is sending a quantum state instead of bit strings? We make some progress towards this question by showing that there is no separation under certain conditions.