26 citations · 44 across the 4 of their papers we have counts for
4 papers · 1 filter
Prior Entanglement Exponentially Improves One-Server Quantum Private Information Retrieval for Quantum Messages
Seunghoan Song, Francois Le Gall, Masahito Hayashi
Quantum private information retrieval (QPIR) for quantum messages is a quantum communication task, in which a user retrieves one of the multiple quantum states from the server with…
Privacy in Quantum Communication Complexity
Iordanis Kerenidis, Mathieu Laurière, François Le Gall +1
In two-party quantum communication complexity, Alice and Bob receive some classical inputs and wish to compute some function that depends on both these inputs, while minimizing the…
The quantum query complexity of certification
Andris Ambainis, Andrew M. Childs, François Le Gall +1
We study the quantum query complexity of finding a certificate for a d-regular, k-level balanced NAND formula. Up to logarithmic factors, we show that the query complexity is Theta…
Exponential Separation of Quantum and Classical Online Space Complexity
Francois Le Gall
Although quantum algorithms realizing an exponential time speed-up over the best known classical algorithms exist, no quantum algorithm is known performing computation using less s…