5 papers
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{…
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 …
Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions
Nai-Hui Chia, Atsuya Hasegawa, François Le Gall +2
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 +1
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…
Does there exist a quantum fingerprinting protocol without coherent measurements?
Atsuya Hasegawa, Srijita Kundu, François Le Gall +2
Buhrman, Cleve, Watrous, and de Wolf (PRL 2001) discovered the quantum fingerprinting protocol, which is the quantum SMP protocol with qubits communication for the equa…