Current Research

Computational Aspects of Quantum Information Processing

Quantum information science is a research field on information processing which uses the quantum mechanics. I am studying what is possible or impossible by quantum information processing beyond the current information processing, which is based on classical physics, and how much the fundamental principles of the quantum mechanics (such as the superposition principle and the entanglement) work as the merit of information processing from a viewpoint of the theory of computation.

[Topics]

Quantum computing models

To clarify the power of quantum computers, we need modeling them in a theoretical framework. As the theory of classical computation, many quantum computing models have been introduced so far according to their complexity measures or purposes. In the case of quantum computing models, there are some difficulties that the classical computing models do not have, such as the unitary restriction of computation and the continuity of the parameters defining quantum operations. I am studying a reasonable modeling of quantum computing for these specific difficulties, which provides the foundation of quantum algorithms and quantum computational complexity.

I am also studying the model of quantum network coding, which includes the structure of computation. Network coding is a new paradigm of communication systems on networks, which allows to process information at every node on the network for efficient communication. The idea of network coding is rather important for quantum network since quantum communication is much more expensive than classical communication. One of my contributions is a construction of quantum network coding over multiple unicast networks with the help of classical communication.

Quantum algorithms

Quantum information processing makes the computation more efficient than classical one such as the Shor algorithm that solves integer factoring problems in polynomial time. A natural question is: What types of computational problems can be sped up by quantum computers, and how much speed-ups are possible by quantum algorithms? I am constructing quantum algorithms for a number of quantum computing models such as quantum query complexity and quantum communication complexity. Recently, I gave a quantum algorithm for the counterfeit coin problem, a well-known combinatorial problem, which achieves a quartic speed-up over classical algorithms. This speed-up is much different from previous quantum algorithms including the Shor and the Grover.

Quantum complexity theory

Understanding what tasks are efficiently implementable by quantum information processing is very important since it may guarantee the optimality of quantum algorithms or the computational security of cryptography that resists the attacks by quantum computers. In quantum complexity theory, various quantum complexity classes have been studied for the corresponding computational tasks under the existence of quantum computers. Among them, I am studying the inclusion relations or the complexity theoretic properties for some of the classes, which include the class of problems solved in quantum polynomial time (quantum version of P) as well as the class of problems verified in quantum polynomial time (quantum NP) and the class of problems verified by quantum interactive communication systems (quantum interactive proof systems). I am also interested in applications of quantum complexity theory to cryptography such as public-key cryptosystems.