中央研究院 資訊科學研究所

活動訊息

友善列印

列印可使用瀏覽器提供的(Ctrl+P)功能

學術研討會

:::

2022 Theory Seminar on Quantum Computing

  • 時間2022-06-23 (Thu.) 14:00 ~ 2022-06-23 (Thu.) 17:30
  • 地點本所新館106演講廳 ;提供視訊 線上會議
線上串流
Virtual Conference @ Webex

Link: 【webex
Number:2555 023 2101
Password: hxVr7jFwP57(49877539 用於從電話和視訊系統加入)
摘要
Time
Topics
14:00 - 15:00

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.

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)

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.

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!