4 papers · 1 filter
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…
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 {\…
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…
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…