Startup Meeting in TOKYO March 2008: Program
TimeSpeakerTitle
9:40-10:00Kae Nemoto"Overview of the project"
10:00-10:45Takeshi Koshiba"On Quantum One-Way Permutations"
Abstract: The notion of one-way functions plays an important role both in cryptography and computational complexity theory. Even in the setting of quantum computation, the counterpart is also important. As a special case of quantum one-way functions, we take quantum one-way permutations and study them from several points of view.

First, Kashefi, Nishimura and Vedral (2003) gave a characterization of the existence of worst-case quantum one-way permutations from the computational complexity theoretic point of view. They also considered its algorithmic characterization.

Kawachi, Kobayashi, Koshiba and Raymond Putra (2005) extended the algorithmic characterization to average-case quantum one-way permutations, which are suitable for cryptography. Unfortunately, the algorithmic characterization could not answer the existence of quantum one-way permutations so much.

So, we revisit a computational complexity theoretic characterization of quantum one-way permutations. In the classical setting, Grollmann and Selman investigated it extensively and Homan and Thakur finalized it by showing that there exists a one-way permutation iff
$P \ne UP \land coUP$. We study their techniques in the quantum setting and extend the Kashefi-Nishimura-Vedral characterization.

11:00-11:45Kazuo Iwama -
12:00-12:45Simon Devitt -
13:00-14:00lunch
14:00-15:00informal discussion (seminar room on the 20th floor)
15:00-15:45Akinori Kawachi"Orthogonality versus Linear Independence"
Abstract: The orthogonality and linear independence of vectors play important roles in mathematical sciences, including the quantum information science. Trivially, the orthogonality of vectors in Hilbert space implies linear independence of the vectors, i.e., if vectors are orthogonal then they are linearly independent.

Then a natural question arises. How well does the orthogonality imply the linear independence? Our answer is "only extreme near-othogonality implies the linear independence." More precisely, we obtain the following results:

(i) Let $v_1,...,v_d$ be vectors of length $1$ in a $d$-dimensional Hilbert space. If $|\langle v_i,v_j\rangle| < 1/(d-1)$ for any distinct pair $i,j$ then $v_1,...,v_d$ are linearly independent.

(ii) There exist vectors $v_1,...,v_d$ of length $1$ such that $|\langle v_i,v_j\rangle| = 1/(d-1)$ for any distinct pair $i,j$.

We also consider "binary" vectors with $\pm 1/\sqrt{d}$ entries. This case is also important in quantum algorithms such as quantum oracle computation. We obtain the following result for the binary vectors:

(iii) There exist linear dependent vectors $v_1,...,v_d \in\{+1/\sqrt{d},-1/\sqrt{d}\}^d$ of length $1$ such that $|\langle v_i,v_j\rangle|\le 2/d$ for any distinct pair $i,j$.
Since $|\langle v_i,v_j\rangle|\ge 2/d$ for two non-orthogonal binary vectors, this result shows that near-orthogonality no longer implies the linear independence in the binary case.

This work is joint with Minato Hagiwara.

16:00-16:20Mio Murao"Authorized quantum computation"
We present authorized quantum computation, where only a user with a non-cloneable authorization key can perform a unitary operation genuinely created by a programmer.

The security of our authorized quantum computation is based on the quantum computational complexity problem of forging the key from the obfuscated quantum gate sequence. Under the assumption of the existence of a sufficiently-random gate shuffling algorithm, the problem is shown to be in QMA (Quantum Merlin-Arthur)-hard by reducing it to a known QMA-Complete problem, the non-identity check problem.

16:20-16:40Toshio Oshima"Quantum information processing along spin chains"
Practical quantum information processing using spin chains is proposed. Robustness against error and fluctuation in external control is shown for a new scheme using the adiabatic passage method in spin chains. Some variations, applications and performance in more general settings for this scheme are also discussed.

16:40-17:10Scientific and administrative discussions

Last updated 26th March 2008.