9 citations · 29 across the 24 of their papers we have counts for
4 papers · 1 filter
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…
Sampling of globally depolarized random quantum circuit
Tomoyuki Morimae, Yuki Takeuchi, Seiichiro Tani
The recent paper [F. Arute et al. Nature {\bf 574}, 505 (2019)] considered exact classical sampling of the output probability distribution of the globally depolarized random quantu…
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…