Institute of Information Science, Academia Sinica



Press Ctrl+P to print from browser

2022 Theory Seminar on Quantum Computing


2022 Theory Seminar on Quantum Computing

  • Time2022-06-23 (Thu.) 14:00 – 2022-06-23 (Thu.) 17:30
  • LocationAuditorium106 at IIS new Building ; Virtual room is available
Live Stream
Virtual Conference @ Webex

Link: 【webex
Number:2555 023 2101
Password: hxVr7jFwP57
14:00 - 15:00

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

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.

15:00 - 15:30

Discussion & Break

15:30 - 17:30

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

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.

The meeting will be held hybrid. In order to avoid affecting the progress of the event, the online meeting room will be locked 20 minutes after the start of the speech. Thank you!