142 citations · 803 across the 51 of their papers we have counts for
54 papers
Group Order is in QCMA
François Le Gall, Harumichi Nishimura, Dhara Thakkar
In this work, we show that verifying the order of a finite group given as a black-box is in the complexity class QCMA. This solves an open problem asked by Watrous in 2000 in his s…
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…
Quantum Simultaneous Protocols without Public Coins using Modified Equality Queries
François Le Gall, Oran Nadler, Harumichi Nishimura +1
In this paper we study a quantum version of the multiparty simultaneous message-passing (SMP) model, and we show that in some cases, quantum communication can replace public random…
Space-bounded quantum interactive proof systems
François Le Gall, Yupan Liu, Harumichi Nishimura +1
We introduce two models of space-bounded quantum interactive proof systems, and . The model, a space-bounded variant of quantu…
On the Power of Quantum Distributed Proofs
Atsuya Hasegawa, Srijita Kundu, Harumichi Nishimura
Quantum nondeterministic distributed computing was recently introduced as dQMA (distributed quantum Merlin-Arthur) protocols by Fraigniaud, Le Gall, Nishimura and Paz (ITCS 2021).…
Distributed Quantum Interactive Proofs
François Le Gall, Masayuki Miyamoto, Harumichi Nishimura
The study of distributed interactive proofs was initiated by Kol, Oshman, and Saxena [PODC 2018] as a generalization of distributed decision mechanisms (proof-labeling schemes, etc…