49 citations · 281 across the 55 of their papers we have counts for
6 papers · 1 filter
An Algorithmic Argument for Nonadaptive Query Complexity Lower Bounds on Advised Quantum Computation
Harumichi Nishimura, Tomoyuki Yamakami
This paper employs a powerful argument, called an algorithmic argument, to prove lower bounds of the quantum query complexity of a multiple-block ordered search problem in which, g…
Theory of One Tape Linear Time Turing Machines
Kohtaro Tadaki, Tomoyuki Yamakami, Jack C. H. Lin
A theory of one-tape (one-head) linear-time Turing machines is essentially different from its polynomial-time counterpart since these machines are closely related to finite state a…
Quantum NP and a Quantum Hierarchy
Tomoyuki Yamakami
The complexity class NP is quintessential and ubiquitous in theoretical computer science. Two different approaches have been made to define "Quantum NP," the quantum analogue of NP…
Computational Complexity Measures of Multipartite Quantum Entanglement
Tomoyuki Yamakami
We shed new light on entanglement measures in multipartite quantum systems by taking a computational-complexity approach toward quantifying quantum entanglement with two familiar n…
Quantum Merlin-Arthur Proof Systems: Are Multiple Merlins More Helpful to Arthur?
Hirotada Kobayashi, Keiji Matsumoto, Tomoyuki Yamakami
This paper introduces quantum ``multiple-Merlin''-Arthur proof systems in which Arthur receives multiple quantum proofs that are unentangled with each other. Although classical mul…
Polynomial time quantum computation with advice
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 sta…