4 citations · 4 across the 7 of their papers we have counts for
9 papers
Near-Optimal Gap Amplification for Nonnegative Unentangled Quantum Proofs
Masayuki Miyamoto
We study gap amplification of the class characterized by unentangled quantum proofs whose amplitudes are nonnegative in the computational basis. This class wa…
Distributed Statistical Zero-Knowledge Proofs via Sumcheck
Benjamin Jauregui, Masayuki Miyamoto
We study distributed zero-knowledge proofs, introduced by Bick, Kol, and Oshman (SODA 2022). While distributed interactive proofs have advanced rapidly, general-purpose techniques…
Classical simulability of quantum circuits followed by sparse classical post-processing
Yasuhiro Takahashi, Masayuki Miyamoto, Noboru Kunihiro
We study the classical simulability of a polynomial-size quantum circuit on qubits followed by sparse classical post-processing (SCP) on bits, where $m \leq n \leq {\…
Distributed Complexity of -freeness: Decision and Certification
Masayuki Miyamoto
The class of graphs that do not contain a path on nodes as an induced subgraph (-free graphs) has rich applications in the theory of graph algorithms. This paper explores…
Quantum Merlin-Arthur proof systems for synthesizing quantum states
Hugo Delavenne, François Le Gall, Yupan Liu +1
Complexity theory typically focuses on the difficulty of solving computational problems using classical inputs and outputs, even with a quantum computer. In the quantum world, it i…
Distributed Quantum Interactive Proofs
François Le Gall, Masayuki Miyamoto, Harumichi Nishimura
The study of distributed interactive proofs was initiated by Kol, Oshman, and Saxena [PODC 2018] as a generalization of distributed decision mechanisms (proof-labeling schemes, etc…
Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications
François Le Gall, Masayuki Miyamoto, Harumichi Nishimura
The generation and verification of quantum states are fundamental tasks for quantum information processing that have recently been investigated by Irani, Natarajan, Nirkhe, Rao and…
Lower Bounds for Induced Cycle Detection in Distributed Computing
François Le Gall, Masayuki Miyamoto
The distributed subgraph detection asks, for a fixed graph , whether the -node input graph contains as a subgraph or not. In the standard CONGEST model of distributed com…
Quantum Speedup for the Minimum Steiner Tree Problem
Masayuki Miyamoto, Masakazu Iwamura, Koichi Kise +1
A recent breakthrough by Ambainis, Balodis, Iraids, Kokainis, Prūsis and Vihrovs (SODA'19) showed how to construct faster quantum algorithms for the Traveling Salesman Problem and…