5 papers · 1 filter
Quantum Minimal One Way Information: Relative Hardness and Quantum Advantage of Combinatorial Tasks
Harumichi Nishimura, Tomoyuki Yamakami
Two-party one-way quantum communication has been extensively studied in the recent literature. We target the size of minimal information that is necessary for a feasible party to f…
A note on quantum one-way permutations
Elham Kashefi, Harumichi Nishimura, Vlatko Vedral
We discuss the question of the existence of quantum one-way permutations. First, we prove the equivalence between inverting a permutation and that of constructing a polynomial size…
Quantum subroutine problem and the robustness of quantum complexity classes
Harumichi Nishimura, Masanao Ozawa
This paper positively solves the quantum subroutine problem for fully quantum oracles. The quantum subroutine problem asks whether a quantum computer with an efficiently computable…
Computational Complexity of Uniform Quantum Circuit Families and Quantum Turing Machines
Harumichi Nishimura, Masanao Ozawa
Deutsch proposed two sorts of models of quantum computers, quantum Turing machines (QTMs) and quantum circuit families (QCFs). In this paper we explore the computational powers of…
Local Transition Functions of Quantum Turing Machines
Masanao Ozawa, Harumichi Nishimura
Foundations of the notion of quantum Turing machines are investigated. According to Deutsch's formulation, the time evolution of a quantum Turing machine is to be determined by the…