8 citations · 23 across the 8 of their papers we have counts for
8 papers
Computational Complexity of Space-Bounded Real Numbers
Masaki Nakanishi, Marcos Villagra
In this work we study the space complexity of computable real numbers represented by fast convergent Cauchy sequences. We show the existence of families of trascendental numbers wh…
Exact Affine Counter Automata
Masaki Nakanishi, Kamil Khadiev, Krišjānis Prūsis +2
We introduce an affine generalization of counter automata, and analyze their ability as well as affine finite automata. Our contributions are as follows. We show that there is a la…
New results on classical and quantum counter automata
Masaki Nakanishi, Abuzer Yakaryılmaz, Aida Gainutdinova
We show that one-way quantum one-counter automaton with zero-error is more powerful than its probabilistic counterpart on promise problems. Then, we obtain a similar separation res…
Quantum Pushdown Automata with a Garbage Tape
Masaki Nakanishi
Several kinds of quantum pushdown automaton models have been proposed, and their computational power is investigated intensively. However, for some quantum pushdown automaton model…
Tensor Rank and Strong Quantum Nondeterminism in Multiparty Communication
Marcos Villagra, Masaki Nakanishi, Shigeru Yamashita +1
In this paper we study quantum nondeterminism in multiparty communication. There are three (possibly) different types of nondeterminism in quantum computation: i) strong, ii) weak…
Quantum Walks on the Line with Phase Parameters
Marcos Villagra, Masaki Nakanishi, Shigeru Yamashita +1
In this paper, a study on discrete-time coined quantum walks on the line is presented. Clear mathematical foundations are still lacking for this quantum walk model. As a step towar…
Average/Worst-Case Gap of Quantum Query Complexities by On-Set Size
Andris Ambainis, Kazuo Iwama, Masaki Nakanishi +4
This paper considers the query complexity of the functions in the family F_{N,M} of N-variable Boolean functions with onset size M, i.e., the number of inputs for which the functio…
Robust Quantum Algorithms with $\eps$-Biased Oracles
Tomoya Suzuki, Shigeru Yamashita, Masaki Nakanishi +1
This paper considers the quantum query complexity of {\it $\eps$-biased oracles} that return the correct value with probability only $1/2 + \eps$. In particular, we show a quantum…