2001-seminars in Tokyo office

• January --- 2001: 2001.Jan.16, 2001.Jan.26
• February --- 2001: 2001.Feb.02, 2001.Feb.09, 2001.Feb.13, 2001.Feb.16, 2001.Feb.23, 2001.Feb.27
• March --- 2001: 2001.Mar.01, 2001.Mar.16, 2001.Mar.23, 2001.Mar.30
• April --- 2001: 2001.Apr.06, 2001.Apr.13, 2001.Apr.20, 2001.Apr.27
• May --- 2001: 2001.May.11, 2001.May.18, 2001.May.25, 2001.May.29
• June --- 2001: 2001.Jun.01, 2001.Jun.04, 2001.Jun.08, 2001.Jun.11, 2001.Jun.15, 2001.Jun.19, 2001.Jun.22, 2001.Jun.29
• July --- 2001: 2001.Jul.06, 2001.Jul.13, 2001.Jul.17, 2001.Jul.27,
• August --- 2001: 2001.Aug.03, 2001.Aug.03, 2001.Aug.30, 2001.Aug.31
• September --- 2001: 2001.Sep.10, 2001.Sep.11, 2001.Sep.12, 2001.Sep.14, 2001.Sep.21, 2001.Sep.28
• October --- 2001: 2001.Oct.1, 2001.Oct.5, 2001.Oct.12, 2001.Oct.19, 2001.Oct.26
• November --- 2001: 2001.Nov.2, 2001.Nov.9, 2001.Nov.14, 2001.Nov.16, 2001.Nov.22, 2001.Nov.30
• December --- 2001: 2001.Dec.7, 2001.Dec.10, 2001.Dec.21,
• 2000-seminars

• Date: 2001.Jan.16
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: Y. Tokunaga
• Abstract:

• Date: 2001.Jan.26
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: S. Natori
• Abstract: Steganography is the art and science of hiding data into innocent-looking cover data so that no one can detect the very existence of the hidden data. In this seminar we introduce both classical and quantum steganography systems, and compare their capabilities. First, we generalize the notion of \epsilon-security which Christian Cachin introduced for the measurement of the safety of classical steganography systems and make it suitable for quantum steganography systems. Based on the measure, we evaluate the quantum steganography systems Marcos Curty et al. introduced, and show that there is no essential difference between the power of their quantum steganography systems and classical steganography systems. Finally, we show that quantum steganography systems are strictly more powerful than classical ones, by constructing a perfectly secure steganography system using entangled qubits as its shared secret key.

• Date: 2001.Feb.02
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: Hamada
• Abstract: Problems and results on quantum channel coding will be surveyed. Especially, the talk will be on extensions of Shannon's classical noisy channel coding theorem for one-sender and one-receiver communication. There are roughly two kinds of problems: (1) that of sending classical information though quantum channels, and (2) that of sending quantum states. (1) was solved, though not completely, by Holevo and others in 90's. In particular, Fujiwara and Nagaoka (1998) greatly contributed to this problem, which is not often cited in the literature in spite of their importance. I will also review their work briefly in the talk. (2) is far from being settled. There seems to be no decisive result yet on this problem, but I will mention some.

• Date: 2001.Feb.09
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: Wang
• Abstract: Properties of quantum entanglement in two level space is reviewed. We first introduce Bell state, Bell inequality and quantum teleportation. We then turn to 2 specific topics in the subject: 1. Definitition of entanglement, i.e., given a state, how to mathematically judge whether it is entangled or not. 2. Purfication scheme. Given many copies of entangled pairs with partially corruption, how do we increase the entanglement on part of the pairs with the price of sacrificing other pairs. The same subject on continuous variable state will be reported latter.

• Date: 2001.Feb.13
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: Nanbu
• Abstract: Mayers and Lo gave a proof of no bit commitment theorem about four years ago. However, their proof is nonconstructive and underlying assumptions are not clear. We argue that the standard bit commitment protocol can be expressed as known orthogonal mixed states. Then, we show that no standard bit commitment protocol is unconditionally secure from an information theoretic point of view. It is shown that there is a trade-off relation between information acquired by Bob during commitment phase and ability of tampering a commit bit by Alice during opening phase. As a result, a protocol that is unbiased to both Alice and Bob cannot be at the same time secure against both parties. A connection to the no zero knowledge convincing protocol by Horodecki et al. is briefly given. Possible loophole on no bit commitment theorem recently pointed out by Yuen is also discussed.

• Date: 2001.Feb.16
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: Tomita
• Abstract: I will review the implementation issues of quantum gates. The talk will cosider a quantum circuit without two-qubit quantum gates, and quantum gates on continuous variables. Ongoing and future experiments in the Imai-Pj will be discussed.

• Date: 2001.Feb.23
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: Matsumoto
• Abstract:

• Date: 2001.Feb.27
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: Koashi
• Abstract: Quantum mechanics pose fundamental restrictions when one reads out information from a quantum system. The most basic rule is well known-if one reads out information from a quantum system in an `unknown' initial state, the quantum state of the system will change. Recent development of quantum information theory revealed various schemes of handling information through quantum systems, and understanding of more detailed rules seems to become an important issue. One example is the case when the initial state is partially known. What kind of information can be extracted, and what cannot be, without changing the state? We show that the fundamental properties of classical and quantum signals lead to a principle that gives a definite distinction between the operations that preserve the states of the system and those that do not. Many types of no-cloning and no-imprinting conditions can easily be derived from this principle. The principle also gives a unified view on how various schemes of quantum cryptography work.

• Date: 2001.Mar.01
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: Yanagisawa
• Abstract: Feedback is a method by which the dynamics of a system is altered and the performance and robustness of the system is improved considerably even if the system includes some uncertainty in its environment and components for which the system is highly structured. Of our particular interest is the quantum system interacting with an optical field through which the output of the system is fed back. For this process, the interaction Hamiltonian over the quantum systems and the optical field is derived. This establishes a link between quantum optics and control theory, and the concept and tools of control theory contribute not only to understanding of quantum network, but are available for some of the most important problems in quantum systems.

• Date: 2001.Mar.16
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: H. Kobayashi
• Abstract: We introduce a quantum analogue of multi-prover interactive proof systems by naturally extending the model of single-prover quantum interactive proof systems defined by Watrous. It is proved that the class of languages having quantum multi-prover interactive proof systems is equal to NEXP, which follows that the quantum analogue has no gain to the classical counterpart in the setting of multi-prover interactive proof systems. It is also proved that, in case the prover does not have his private qubits, the class of languages that have single-prover quantum interactive proof systems is equal to NEXP.

• Date: 2001.Mar.23
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: M. Hachimori
• Abstract: The first half of this talk is a suggestion what quantum-algorithmic theories should be, possibly with a few examples from classical algorithmic theories, and a proposal of a research plan toward them. (This part is rather a philosophical presentation.) The latter half is an exposition of what are hopefully done around matroids and topological quantum field theories.

• Date: 2001.Mar.30
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: T. Yamasaki
• Abstract: Quantum pushdown automata (QPA) was first introduced by C. Moore and J. P. Crutchfield. In the paper I review, M. Golovkins introduced another model of QPA by using the definition of quantum finite automata, and proved that every regular language can be recognized by QPA.

• Date: 2001.April.06
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: S. Natori
• Abstract: Pati discovered a way how a secret qubit can be hidden into certain $n$-partite entangled states, in such a way that these $n$ parties cannot salvage the hidden qubit by local and joint unitary operations, no matter how they cooperate. He named this type of multipartite entangled state `quantum cobweb,' and quantified the amount of resource required to create it.

• Date: 2001.April.13
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: Shi Baosen
• Abstract: About two years ago, a lab. of quantum communication and quantum computa tion was setup in USTC. It is the first Lab. about quantum information i n China. In this seminar, I will show what have been done, what are been doing now in this Lab. of USTC, including theory and experiment.

• Date: 2001.April.20
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: F. Yura
• Title: Soliton Cellular Automaton (SCA) and Ultradiscrete Limit
• Abstract: Box and ball system (BBS) is reviewed. A remarkable feature of this SCA is that any state consists only of solitons, interacting in the same manner as KdV solitons. The talk will be as follows:
  1. Derivation of BBS from the KdV equation
  2. The conserved quantities of the system
  3. Relations between classical algorithms and soliton equations
  4. Solvable lattice model and combinatorial R matrix
  

• Date: 2001.April.27 10:00am --
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: M. Hamada
• Title: On binary quantum channels and additivity of capacity with possibly entangled input states
• Abstract: The additivity problem for classical capacities of quantum channels will be discussed. Especially, reviewed is a recent result of King (March 28, quant-pt/0103156), which proves that the Holevo-Schumacher-Westmoreland-Fujiwara-Nagaoka coding theorem is valid even if the input states are allowed to be entangled in the case of a certain class of binary quantum (or qubit) channels, which includes the depolarizing channel.

• Date: 2001.May.11 10:00am --
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: TADAKI Kohtaro
• Title: Kolmogorov complexity and its quantum extension
• Abstract: The Kolmogorov complexity of a classical finite binary string x is the length of the shortest input for a classical universal Turing machine to output x. In this talk, after giving a brief account of (classical) Kolmogorov complexity, I will review the following three approaches defining the quantum Kolmogorov complexity of a qubit string.
  [1] "Quantum Kolmogorov Complexity Based on Classical Descriptions", Paul M.B. Vitanyi (quant-ph/0102108)
  [2] "Quantum Kolmogorov Complexity", Andre Berthiaume, Wim van Dam, and Sophie Laplante (quant-ph/0005018)
  [3] "Quantum Algorithmic Entropy", Peter Gacs (quant-ph/0011046)
  

• Date: 2001.May.18 10:00am --
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: Wang
• Title: Time evolution property of Josephson junction in the computational subspace
• Abstract: We studied the time evoultion property of the SQUID state in computational subspace.The optimizing parameters for single qubit and two qubits quantum gate are given.

• Date: 2001.May.25 10:00am --
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: A. Tomita
• Title:Path-integral method on quantum processes
• Abstract: Let's go back to the basics of quantum mechanics. I will introduce Feynman's path integral formulation of quantum mechanics. This formulation gives us intuitive descriptions of quantum processes under measurements or perturbations. The talk may include the following topics: discrete formulation of a quantum process, introduction to Feynman's path-integral method, interpretation of measurements, and (if possible) example(s) taken from quantum process(es) related to quantum computing (quantum walk, quantum automaton,....).

• Date: 2001.May.29 15:30pm --
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: MORIKOSHI Fumiaki
• Title: Deterministic Entanglement Concentration
• Abstract: Quantum teleportation requires that a sender (Alice) and a receiver (Bob) share a maximally entangled state (Bell pair) in advance. If Alice and Bob share only partially entangled pairs, they can prepare Bell pairs from the partially entangled pairs by local operations and classical communication (LOCC). In this talk we will discuss an entanglement concentration scheme in which Alice and Bob extract Bell pairs from partially entangled pairs in a deterministic manner. We derive the maximum number of Bell pairs that can be obtained with probability one by LOCC. It is proved that the optimal deterministic concentration needs only two-pair collective manipulation in each step and collective manipulation of all entangled pairs is not necessary. Finally, this scheme reveals an entanglement measure for the deterministic concentration.

• Date: 2001.Jun.01 10:00am --
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: Heng Fan
• Title: Universal Quantum Cloning Machine
• Abstract: For one arbitrary unknow quantum input state, using the UQCM, we can have two output state with fidelity 5/6. If we just deal with a restricted set of input state, for example, the equatorial qubit, one of its Bloch vector is zero, we can achieve higher fidelity. The transformation for N input state and M output state will be discussed. The concatenation of the UQCM will be presented.

• Date: 2001.Jun.04 3:30pm -- 5:30pm
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: Tomoyuki Yamakami
• Title:
• Abstract:

• Date: 2001.Jun.08 10:00am --
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: Hwang WonYoung
• Title: Shor-Preskill type security-proofs for concatenated six-state quantum key distribution scheme
• Abstract: We give the Shor-Preskill type security -proofs to the six-state concatenated scheme. The (secure) modified Lo-Chau concatenated scheme is reduced to the Calderbank-Shor-Steane six-state concatenated scheme, which is then reduced to the (BB84-like) six-state concatenated scheme.

• Date: 2001.Jun.11 3:30pm -- 5:30pm
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: Saitoh Keiji
• Title: Quantum Spin Dynamics and Quantum Computation
• Abstract: We describe a simulation method for a quantum spin model of a generic, general purpose quantum computer. The use of this quantum computer simulator is illustrated through several implementations of Grover's database search algorithm. Some preliminary results on the stability of quantum algorithms are presented. We also discuss some method to stabilize the system.

• Date: 2001.Jun.15 10:00am --
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: K. Matsumoto
• Title: Quantum Universal Source Coding
• Abstract: The reseach of data compression of quantum (i.i.d.) state source, defined as
  

  \begin{eqnarray*} \rho_i \sim p_i, \end{eqnarray*}

  is started by Schumacher\cite{Schumacher}, in relation with consise realization of quantum computer. In his paper, it is proved that von Neumann entropy $S({\cal S})$ of the source ${\cal S}$, where $\bar{\rho}=\sum_i p_i\rho_i$, give the lower bound of the rate, and that data compression scheme which achive the bound is constructed. One drawback of his scheme is that, one needs to know the exact form of the source, for the coding is dependent on the source to be compressed.
  
  In 1997, Josza and Hokideckis proposed a new scheme such that whatever the quantum state source is, if its von Neumann entropy is smaller than $R$, the source is successfully compressed up to the rate $R$. Their scheme is a quantum version of fixed length universal codeing, and their scheme share the same drawback which classical fixed length universal coding has. That is, in their scheme, if the von Neumann etropy of the source is larger than $R$, the source is distorted by the compression. In addition, the source whoes von Neumann entropy is smaller than $R$ cannot be compressed to the optimal rate.
  
  So the question is that : is there any quantum version of variable length universal coding, or a coding which is constructed independent of source, and can be compressed up to the rate of von Neumann entropy?
  
  It seems that variable length universal quantum source coding is impossible. In this talk, however, quasi-universal quantum variable length codings (a), (b) are proposed, which have following property respectively. Both of them make use of large deviation theory of representation of a general linear group.

  \begin{itemize}
  \item[(a)] Let $\{{\cal S}\}_{\xi\in \Xi}$ be a possible candidate of the quantum state source. If $I$ consists of finite number of elements, the quantum source is compressed up to von Neuman entropy of the true source.
  \item[(b)] Let $\{{\cal S}\}_{\xi\in \Xi}$ be a possible candidate of the quantum state source (this time, $X$ can contain continuously infinite number of elements), and assume that the source ${\cal S}_{\xi}$ be selected with the probability $p_{\xi}$. We consider all the coding for which the expectation of error of decoding goes to zero asymptotically. Then, optimal compression rate is von Neuman entropy of the true source.
  \end{itemize}
  

  
  Reference.
  [1] Schumacher
  ``Quantum coding,'' Phys. Rev. A 51, 2738-2747 (1995)
  [2] Richard Jozsa, Michal Horodecki, Pawel Horodecki, Ryszard Horodecki,
  ``Universal Quantum Information Compression,'' quant-ph/9805017 (1998)

• Date: 2001.Jun.19 3:30pm -- 5:30pm
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: Patel Apoorva Dayaram,
  (the Indian Institute of Science, Bangalore, India)
• Title: Why genetic information processing could have a quantum basis
• Abstract: Living organisms are not just random collections of organic molecules. There is continuous information processing going on in the apparent bouncing around of molecules of life. Optimisation criteria in this information processing can be searched for using the laws of physics. Quantum dynamics can explain why living organisms have 4 nucleotide bases and 20 amino acids, as optimal solutions of the molecular assembly process. Experiments should be able to tell whether evolution indeed took advantage of quantum dynamics or not.

• Date: 2001.Jun.22 10:00am --
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: T. Yamasaki
• Title: Quantum walks
• Abstract: Random walks on graphs have found many applications, and are studied by many researchers in order to deverop similar techniques for quantum algorithms. In this paper, we mention some results of numerical analysis and conjectures we obtained from these results.

• Date: 2001.Jun.29 10:00am --
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: H. Kobayashi
• Title:
• Abstract:

• Date: 2001.Jul.06 10:00am --
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: NIWA Junpei
• Title:The simulator for quantum computing on the parallel computers
• Abstract: In current technology, it is very difficult to implement quantum computers with many qubits. It is therefore of importance to simulate quantum computing on the existing computers. We have developed the simulation methods of reducing memory consumptions. However, for a large-size problem, the simulation often requires more computational power than is available from sequential processing. Therefore, the simulation methods using parallel processing are required. We have developed the simulator for quantum computing on the parallel computers (Sun, Enterprise4500). We have experimented Shor's factorization and Grover's database search and analyzed robustness of these quantum circuits in the presence of decoherence.

• Date: 2001.Jul.13 10:00am -- 12:00
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: M. Hachimori
• Title: Approximate counting
• Abstract: A brief review of approximate counting:
  * by Jerrum & Sinclair from classical computation,
  * by Mosca from quantum computation.
  (Before this topic is a remark on the edge labeling of graphs.)

• Date: 2001.Jul.17 3:00pm -- 5:00pm
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: Dr. Gregor Weihs (University of Wien)
• Title: Photonic Entanglement for Quantum Communication

• Date: 2001.Jul.27 10:00am -- 12:00
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: TSUDA Yoshiyuki
• Title: Quantum estimation for the concurrence
• Abstract: We consider an estimation problem for the concurrence, or the strength of the entanglement, of the two photon polarization state. When the state is not known at all, we estimate the concurrence by estimating the all components of the density matrix by the linear tomography and its maximum likelihood version. When the state is parameterized by some parameters including the concurrence, we consider how to preserve the SLD Fisher information by classical, semi classical and quantum measurement.

• Date: 2001.Aug.3 10:00am -- 12:00
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: NATORI Shin
• Title: Why quantum steganography can be stronger than classical steganography
• Abstract: Steganography is the art and science of hiding the existence of a message by embedding it into another message. In this talk we first define a quantum steganography model by extending classical one. Next we show that quantum steganography can be stronger than classical steganography, by introducing a quantum steganography system that cannot be imitated by classical one.

• Date: 2001.Aug.3 2:00pm -- 4:00pm
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: Dominic Mayers (NECI)
• Title: Quantum Error Correction in Quantum Cryptography.

• Date: 2001.Aug.30
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: Dr. Andreas Winter
• Title: Scalable programmable quantum gates and a new aspect of the additivity problem for the classical capacity of quantum channels

• Date: 2001.Aug.31 10:00am --
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: HAMADA Mitsuru
• Title: On quantum channel capacities
• Abstract: Quantum channel coding problems are discussed. The main topic of the talk is on quantum channel capacities. This is closely related to fault-tolerant quantum computation, especially to quantum error-correcting codes. The quantum channel capacity of a channel is the asymptotically achievable highest information rate of quantum error-correcting schemes. The problem of determining quantum channel capacities is far from being settled. I present a derivation of a lower bound on quantum capacities, which I suppose would be a refinement of the recent result of R. Matsumoto and T. Uyematsu, Tokyo Institute of Technology (quant-ph/0105151). Their proof is based on the Witt theorem (a geometric or algebraic one), which makes available random coding arguments similar to Shannon's to prove the lower bound.

• Date: 2001.Sep.10 15:00am --
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: Dr. L. Fortnow (NECI)
• Title: Comparing Notions of Full Derandomization
• Abstract: Most of the hypotheses of full derandomization fall into two sets of equivalent statements: Those equivalent to the existence of efficient pseudorandom generators and those equivalent to approximating the accepting probability of a circuit. We give the first relativized world where these sets of equivalent statements are not equivalent to each other.

• Date: 2001.Sep.11 13:30am --
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: Professor Richard Cleve (Univ. Calgary)
• Title: Fast parallel algorithms for the quantum Fourier transform
• Abstract: We give new bounds on the circuit complexity of the quantum Fourier transform (QFT). We give an upper bound of O(log n + log log (1/epsilon)) on the circuit depth for computing an approximation of the QFT with respect to the modulus 2^n with error bounded by epsilon. Thus, even for exponentially small error, our circuits have depth O(log n). The best previous depth bound was O(n), even for approximations with constant error. Moreover, our circuits have size O(n log (n/epsilon)).
  As an application of the above depth bound, we show that Shor's factoring algorithm may be based on quantum circuits with depth only O(log n) and polynomial size, in combination with classical polynomial-time pre- and post-processing.
  Next, we prove an Omega(log n) lower bound on the depth complexity of approximations of the QFT with constant error. This implies that the above upper bound is asymptotically tight (for a reasonable range of values of epsilon).
  We also give an upper bound of O(n (log n)^2 log log n) on the circuit size of the exact QFT modulo 2^n, for which the best previous bound was O(n^2).
  This is joint work with John Watrous.

• Date: 2001.Sep.12 14:00am --
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: Dr. Lance Fortnow (NECI)
• Title: One Complexity Theorist's View of Quantum Computing
• Abstract: The complexity of quantum computation remains poorly understood. While physicists attempt to find ways to create quantum computers, we still do not have much evidence one way or the other as to how useful these machines will be. The tools of computational complexity theory should come to bear on these important questions.
  Quantum computing often scares away many potential researchers from computer science because of the apparent background need in quantum mechanics and the alien looking notation used in papers on the topic.
  This paper will give an overview of quantum computation from the point of view of a complexity theorist. We will see that one can think of BQP as yet another complexity class and study its power without focusing on the physical aspects behind it.

• Date: 2001.Sep.14 10:00am --
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: Andreas Winter
• Title: On the statistics of quantum state tomography
• Abstract: In recent years the state reconstruction method of "quantum tomography" from observations data has gained great interest. I propose a study of the mean square error of this method (and maybe other quality measures such as large deviation exponents) by means of a theory of operator valued random variables.
  After reviewing the basic theory, we can give expressions for very natural estimates on the variance, and speculate on optimal tomographic schemes.
  The ultimate goal of the investigation (which still is at an early stage) is a comparison of tomography to optimal state estimation, insofar known.

• Date: 2001.Sep.21 10:00am --
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: SASAKI Yuuya
• Title: (unspecified)
• Abstract: (unspecified)

• Date: 2001.Sep.28 10:00am --
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: F.Yura
• Title: On braid relations
• Abstract: "Quantum Computation and the Jones Polynomial" (math.QA/0105255; L. H. Kauffman) is reviewed. The author discusses the structure of the Jones polynomial in relation to representations of the Temperley-Lieb algebra, and gives an example of an unitary representation of the braid group.

• Date: 2001.Oct.1 15:00am --
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: Andreas Winter
• Title: Quantum data compression and related topics

• Date: 2001.Oct.5 10:00am --
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: Bao-Sen Shi
• Title: Quantum key distribution based on disentanglement eraser
• Abstract: In this paper, we present a novel quantum key distribution way, based on disentanglement eraser. Besides, we give a practical scheme, using two-photon polarization entangled state. The main advantage of this scheme is that we can realize the decoherence-free , bit-flip error rejection transformation and loss-rejection transmission, which can enhance the security.

• Date: 2001.Oct.12 10:00am --
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: Wang Xiangbin
• Title: A fully efficient secure quantum cryptography protocol
• Abstract: Since Bennett and Brassard\cite{bennett1} suggested their quantum key distribution protocol(BB84 protocol) in 1984, the subject has been extensively studied both theoretically and experimentally. The protocol allows two remote parties Alice and Bob to create and share a secret key using a quantum channel and public authenticated communications. The quantum key created in this way is in principle secure because eavesdroppers have no way to tap the quantum channel without disturb it. In the protocol, two level quantum bits are measured in two basis, $X$ and $Z$ randomly by Bob. So at least half of the measurement results will be discarded because Bob has a half probability taking the measurement in a wrong basis. On the other hand, the security is not the maximum in BB84 protocol. To increase the security, one may straightforwardly increase the number of basis used in the protocol. For example, six state protocol was proposed recently\cite{brub} for two level system.
  However, in this way, it seems to be the case that the higher the security is, the more measurement results will be finally discarded. So it should be interesting to find a protocol by which both the economy and security are maximized. It looks impossible at a first sight to the strategy. Here we give a new protocol to maximize both economy and security simultaneously.
  In the new protocol Bob can always measures the qubits in correct basis so that no measurement results will be discarded( except the ones used to check eavesdropping) in principle. Besides this, we give the condition to maximize the security of the protocol under the symmetric channel.

• Date: 2001.Oct.19 10:00am --
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: K. Tadaki
• Title: A theory of matrix formally identical to algorithmic information theory
• Abstract: There are two equivalent ways to define the Kolmogorov complexity K(s) of a given finite binary string s. In the standard way, K(s) is defined as the length of the shortest input for a universal Turing machine to output s. In another way, we first construct what is called the ``universal probability'' P(s), and define K(s) as -log_2 P(s) without using the concept of program-size. We generalize the universal probability to a matrix-valued function, and define a matrix-valued Kolmogorov complexity. In the same context as algorithmic information theory, i.e., a theory of program-size complexity which has precisely the formal properties of classical information theory, we define a matrix-valued conditional entropy and a mutual information. Then we prove several relations which appear in classical information theory except for subadditivity. We discuss a prospects for thinking of the matrix-valued universal probability as a POVM.

• Date: 2001.Oct.26 10:00am --
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: FAN Heng
• Title: Cloning of symmetric d-level photonic states in physical systems
• Abstract: Optimal procedures play an important role in quantum information. It turns out that some natural processes in nature like emission of light from an atom can realize optimal transformations. Here we study how arbitrary symmetric states of a number of d-level systems can be cloned using a multilevel atomic system. It is shown that optimality is always ensured even though the output number of systems is probabilistic.

• Date: 2001.Nov.2 10:00am --
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: Hwang
• Title:
• Abstract:

• Date: 2001.Nov.9 10:00am --
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: TOMITA Akihisa
• Title: Quantum computation over continuous variables
• Abstract: I would like to discuss implementation of quantum gate working with continuous variables or qubits defined by encoding continuous variable states. But I may talk about a completely different subject.

• Date: 2001.Nov.14
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: M. Sohma (Matsushita Co.)
• Title: Capacity and reliability function for quantum Gaussian channels
• Abstract: The purpose of my talk is to obtain basic formulas for quantum Gaussian channels. For example, I would like to obtain a quantum analog of the Shannon formula C=(1/2)log(1+S/N). To this purpose, the discrete quantum channel is extended to continuous one, and formulas for quantum Gaussian states are derived.
  Throughout my talk, only the transmission of classical information over so-called classical-quantum channel or classical-classical channel, is discussed.
  

• Date: 2001.Nov.16
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: K. Matsumoto
• Title:
• Abstract:

• Date: 2001.Nov.22
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: H. Kobayashi
• Title: Quantum functions and complexity limitations of quantum certificate verification
• Abstract: The function classes #QP and GapQP were introduced by Yamakami as quantum analogues of #P and GapP. In this seminar we introduce one more function class OptQP, which is a quantum analogue of OptP studied by Krentel. Using the class OptQP, together with #QP and GapQP, a number of complexity theoretical properties are proved on the classes PP, NQP, and QMA.
  This is a joint work with Keiji Matsumoto and Tomoyuki Yamakami.

• Date: 2001.Nov.30
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: T.Shimono
• Title: Quantum entanglement for quantum information processing
• Abstract: Many kind of quantifications for quantum entanglement have been introduced until recently. I'd like to introduce and some of them.

• Date: 2001.Dec.7 10:00am -- 11:00am
• Place: Japan Science and Technology, Imai Quantum Computation and Information Project, Tokyo Office
• Speaker: M. Hachimori
• Title: T-G invariants
• Abstract: An overview of invaritants of knots and T-G invaritants.

• Date: December 10, 2001, 14:00-15:00
• Place: Room 214, Department of Computer Science Faculty of Science, No.7 Building, Univeristy of Tokyo
• Speaker: Dr. Julia Kempe
• Title: Quantum Random Walks
• Abstract:

• Date: December 21, 2001, 10:00am --
• Place: Room 214, Department of Computer Science Faculty of Science, No.7 Building, Univeristy of Tokyo
• Speaker: YAMASAKI Tomohiro
• Title: Analysis of quantum walks
• Abstract: I obtained experimental results that the absorbing time of quantum walks on $n$-dimensional hypercube can, in some cases, be polynomial of $n$, while that of classical random walks are always exponential. I analyze these results of "discrete-time quantum walks" theoretically and consider the relation with "continuous-time" quantum walks [1], which says that between a particular pair o nodes in particular graph, propagation is exponentially faster in the quantum case.
  [1] An example of the difference between quantum and classical random walks. A. M. Childs, E. Farhi, and S. Gutmann. quant-ph/0103020, 6 Mar 2001.