49 citations · 281 across the 55 of their papers we have counts for
23 papers · 1 filter
How Does Adiabatic Quantum Computation Fit into Quantum Automata Theory?
Tomoyuki Yamakami
Quantum computation has emerged as a powerful computational medium of our time, having demonstrated the remarkable efficiency in factoring a positive integer and searching database…
Interactive Proofs with Quantum Finite Automata
Harumichi Nishimura, Tomoyuki Yamakami
Following an early work of Dwork and Stockmeyer on interactive proof systems whose verifiers are two-way probabilistic finite automata, the authors initiated in 2004 a study on the…
A Non-Interactive Quantum Bit Commitment Scheme that Exploits the Computational Hardness of Quantum State Distinction
Tomoyuki Yamakami
We propose an efficient quantum protocol performing quantum bit commitment, which is a simple cryptographic primitive involved with two parties, called a committer and a verifier.…
Constant-Space Quantum Interactive Proofs Against Multiple Provers
Tomoyuki Yamakami
We present upper and lower bounds of the computational complexity of the two-way communication model of multiple-prover quantum interactive proof systems whose verifiers are limite…
One-Way Reversible and Quantum Finite Automata with Advice
Tomoyuki Yamakami
We examine the characteristic features of reversible and quantum computations in the presence of supplementary external information, known as advice. In particular, we present a si…
The Efficiency of Quantum Identity Testing of Multiple States
Masaru Kada, Harumichi Nishimura, Tomoyuki Yamakami
We examine two quantum operations, the Permutation Test and the Circle Test, which test the identity of n quantum states. These operations naturally extend the well-studied Swap Te…
Quantum List Decoding of Classical Block Codes of Polynomially Small Rate from Quantumly Corrupted Codewords
Tomoyuki Yamakami
Given a classical error-correcting block code, the task of quantum list decoding is to produce from any quantumly corrupted codeword a short list containing all messages whose code…
Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding
Akinori Kawachi, Tomoyuki Yamakami
Hardcore functions have been used as a technical tool to construct secure cryptographic systems; however, little is known on their quantum counterpart, called quantum hardcore func…
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…
An Application of Quantum Finite Automata to Interactive Proof Systems
Harumichi Nishimura, Tomoyuki Yamakami
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.…
Computational Indistinguishability between Quantum States and Its Cryptographic Application
Akinori Kawachi, Takeshi Koshiba, Harumichi Nishimura +1
We introduce a computational problem of distinguishing between two specific quantum states as a new cryptographic problem to design a quantum cryptographic scheme that is "secure"…
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…
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…
Quantum Optimization Problems
Tomoyuki Yamakami
Krentel [J. Comput. System. Sci., 36, pp.490--509] presented a framework for an NP optimization problem that searches an optimal value among exponentially-many outcomes of polynomi…
Quantum DNF Learnability Revisited
Jeffrey C. Jackson, Christino Tamon, Tomoyuki Yamakami
We describe a quantum PAC learning algorithm for DNF formulae under the uniform distribution with a query complexity of , where is the size of…
Quantum Certificate Verification: Single versus Multiple Quantum Certificates
Hirotada Kobayashi, Keiji Matsumoto, Tomoyuki Yamakami
The class MA consists of languages that can be efficiently verified by classical probabilistic verifiers using a single classical certificate, and the class QMA consists of languag…
Quantum Computation Relative to Oracles
Christino Tamon, Tomoyuki Yamakami
This paper has been withdrawn by Christino Tamon and Tomoyuki Yamakami because of errors of the main theorems. An erratum appeared in the Proceedings of the UMC 2000 Conference pub…
Analysis of Quantum Functions
Tomoyuki Yamakami
This paper initiates a systematic study of quantum functions, which are (partial) functions defined in terms of quantum mechanical computations. Of all quantum functions, we focus…
A Foundation of Programming a Multi-Tape Quantum Turing machine
Tomoyuki Yamakami
The notion of quantum Turing machines is a basis of quantum complexity theory. We discuss a general model of multi-tape, multi-head Quantum Turing machines with multi final states…
NQP_{C} = co-C_{=}P
Tomoyuki Yamakami, Andrew C. Yao
Adleman, DeMarrais, and Huang introduced the nondeterministic quantum polynomial-time complexity class NQP as an analogue of NP. Fortnow and Rogers implicitly showed that, when the…