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
Abstract
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.