All reports by Author Tomoyuki Yamakami:

__
TR06-020
| 10th February 2006
__

Akinori Kawachi, Tomoyuki Yamakami#### Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding

Revisions: 1

__
TR04-110
| 24th November 2004
__

Tomoyuki Yamakami, Harumichi Nishimura#### An Application of Quantum Finite Automata to Interactive Proof Systems

__
TR04-066
| 6th July 2004
__

Tomoyuki Yamakami, Toshio Suzuki#### Resource Bounded Immunity and Simplicity

__
TR03-059
| 18th May 2003
__

Harumichi Nishimura, Tomoyuki Yamakami#### Polynomial time quantum computation with advice

Revisions: 2

__
TR98-073
| 14th December 1998
__

Tomoyuki Yamakami, Andrew Chi-Chih Yao#### NQP = co-C_{=}P

Revisions: 2

__
TR95-039
| 11th July 1995
__

Tomoyuki Yamakami#### Polynomial Time Samplable Distributions

Revisions: 2

Akinori Kawachi, Tomoyuki Yamakami

We present three new quantum hardcore functions for any quantum one-way function. We also give a "quantum" solution to Damgard's question (CRYPTO'88) on his pseudorandom generator by proving the quantum hardcore property of his generator, which has been unknown to have the classical hardcore property.

Our technical tool is ...
more >>>

Tomoyuki Yamakami, Harumichi Nishimura

Quantum finite automata have been studied intensively since

their introduction in late 1990s as a natural model of a

quantum computer with finite-dimensional quantum memory space.

This paper seeks their direct application

to interactive proof systems in which a mighty quantum prover

communicates with a ...
more >>>

Tomoyuki Yamakami, Toshio Suzuki

Revisiting the thirty years-old notions of resource-bounded immunity and simplicity, we investigate the structural characteristics of various immunity notions: strong immunity, almost immunity, and hyperimmunity as well as their corresponding simplicity notions. We also study limited immunity and simplicity, called k-immunity and feasible k-immunity, and their simplicity notions. Finally, we ... more >>>

Harumichi Nishimura, Tomoyuki Yamakami

Advice is supplementary information that enhances the computational

power of an underlying computation. This paper focuses on advice that

is given in the form of a pure quantum state. The notion of advised

quantum computation has a direct connection to non-uniform quantum

circuits and tally languages. The paper examines the ...
more >>>

Tomoyuki Yamakami, Andrew Chi-Chih Yao

Adleman, DeMarrais, and Huang introduced the

nondeterministic quantum polynomial-time complexity class NQP as an

analogue of NP. It is known that, with restricted amplitudes, NQP is

characterized in terms of the classical counting complexity class

C_{=}P. In this paper we prove that, with unrestricted amplitudes,

NQP indeed coincides with the ...
more >>>

Tomoyuki Yamakami

This paper studies distributions which

can be ``approximated'' by sampling algorithms in time polynomial in

the length of their outputs. First, it is known that if

polynomial-time samplable distributions are polynomial-time

computable, then NP collapses to P. This paper shows by a simple

...
more >>>