9 papers
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…
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 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 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…