50 citations · 56 across the 9 of their papers we have counts for
6 papers · 1 filter
The Power of Adaptivity in Quantum Query Algorithms
Uma Girish, Makrand Sinha, Avishay Tal +1
Motivated by limitations on the depth of near-term quantum devices, we study the depth-computation trade-off in the query model, where the depth corresponds to the number of adapti…
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,…
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…
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…
-Forrelation Optimally Separates Quantum and Classical Query Complexity
Nikhil Bansal, Makrand Sinha
Aaronson and Ambainis (SICOMP `18) showed that any partial function on bits that can be computed with an advantage over a random guess by making quantum queries, can al…
Exponential Separation between Quantum Communication and Logarithm of Approximate Rank
Makrand Sinha, Ronald de Wolf
Chattopadhyay, Mande and Sherif (ECCC 2018) recently exhibited a total Boolean function, the sink function, that has polynomial approximate rank and polynomial randomized communica…