Showing quant-phShow all
3 papers · 1 filter
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…
quant-ph2020
-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…
quant-ph2018
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…