50 citations · 56 across the 9 of their papers we have counts for
Showing 2022 · quant-phShow all
3 papers · 2 filters
quant-ph2022★ 50 cited
Quantum Cryptography in Algorithmica
William Kretschmer, Luowen Qian, Makrand Sinha +1
We construct a classical oracle relative to which yet single-copy secure pseudorandom quantum states exist. In the language of Impagliazzo's five worlds,…
quant-ph2022★ 4 cited
The NISQ Complexity of Collision Finding
Yassine Hamoudi, Qipeng Liu, Makrand Sinha
Collision-resistant hashing, a fundamental primitive in modern cryptography, ensures that there is no efficient way to find distinct inputs that produce the same hash value. This p…
quant-ph2022
Influence in Completely Bounded Block-multilinear Forms and Classical Simulation of Quantum Algorithms
Nikhil Bansal, Makrand Sinha, Ronald de Wolf
The Aaronson-Ambainis conjecture (Theory of Computing '14) says that every low-degree bounded polynomial on the Boolean hypercube has an influential variable. This conjecture, if t…