4 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…
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…
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…