2 citations · 2 across the 3 of their papers we have counts for
6 papers
Additive-error fine-grained quantum supremacy
Tomoyuki Morimae, Suguru Tamaki
It is known that several sub-universal quantum computing models, such as the IQP model, the Boson sampling model, the one-clean qubit model, and the random circuit model, cannot be…
On Computing a Center Persistence Diagram
Yuya Higashikawa, Naoki Katoh, Guohui Lin +4
Throughout this paper, a persistence diagram is composed of a set of planar points (each corresponding to a topological feature) above the line , as well as the…
An FPT Algorithm for Max-Cut Parameterized by Crossing Number
Yasuaki Kobayashi, Yusuke Kobayashi, Shuichi Miyazaki +1
The Max-Cut problem is known to be NP-hard on general graphs, while it can be solved in polynomial time on planar graphs. In this paper, we present a fixed-parameter tractable algo…
Fine-grained quantum supremacy based on Orthogonal Vectors, 3-SUM and All-Pairs Shortest Paths
Ryu Hayakawa, Tomoyuki Morimae, Suguru Tamaki
Fine-grained quantum supremacy is a study of proving (nearly) tight time lower bounds for classical simulations of quantum computing under "fine-grained complexity" assumptions. We…
Fine-grained quantum computational supremacy
Tomoyuki Morimae, Suguru Tamaki
Output probability distributions of several sub-universal quantum computing models cannot be classically efficiently sampled unless some unlikely consequences occur in classical co…
Derandomizing HSSW Algorithm for 3-SAT
Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto
We present a (full) derandomization of HSSW algorithm for 3-SAT, proposed by Hofmeister, Schöning, Schuler, and Watanabe in [STACS'02]. Thereby, we obtain an O(1.3303^n)-time deter…