4 citations · 8 across the 9 of their papers we have counts for
10 papers
New lower bounds for CDS and -routing
Atsuya Hasegawa, Ranitha Mataraarachchi
Understanding the entanglement cost of non-local quantum computation (NLQC) is relevant to complexity theory, cryptography, quantum gravity, and related areas. A central special ca…
Constant-round quantum advantage in communication complexity for total functions
Atsuya Hasegawa, François Le Gall
We show that there exists a total function for which there is a polynomial gap between the randomized and the constant-round quantum communication complexity. Previously, such a se…
Multi-Prover Interactive Proof Systems with Leakage
Vahid R. Asadi, Atsuya Hasegawa, François Le Gall
It is known that there exist multi-prover interactive protocols ( protocols) for the complexity class , succinct protocols for $\mathsf{…
Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions
Nai-Hui Chia, Atsuya Hasegawa, François Le Gall +1
The local Hamiltonian (LH) problem is the canonical -complete problem introduced by Kitaev. In this paper, we show its hardness in a very strong sense: we show that t…
Dequantization and Hardness of Spectral Sum Estimation
Roman Edenhofer, Atsuya Hasegawa, François Le Gall
We give new dequantization and hardness results for estimating spectral sums of matrices, such as the log-determinant. Recent quantum algorithms have demonstrated that the logarith…
Maximum Separation of Quantum Communication Complexity With and Without Shared Entanglement
Atsuya Hasegawa, François Le Gall, Augusto Modanese
We present relation problems whose input size is such that they can be solved with no communication for entanglement-assisted quantum communication models, but require q…