Arrow Research search

Author name cluster

Makrand Sinha

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

10 papers
1 author row

Possible papers

10

FOCS Conference 2024 Conference Paper

Simple Constructions of Linear-Depth t-Designs and Pseudorandom Unitaries

  • Tony Metger
  • Alexander Poremba
  • Makrand Sinha
  • Henry Yuen

Uniformly random unitaries, i. e. unitaries drawn from the Haar measure, have many useful properties, but cannot be implemented efficiently. This has motivated a long line of research into random unitaries that “look” sufficiently Haar random while also being efficient to implement. Two different notions of derandomisation have emerged: $t$ -designs are random unitaries that information-theoretically reproduce the first $t$ moments of the Haar measure, and pseudorandom unitaries (PRUs) are random unitaries that are computationally indistinguishable from Haar random. In this work, we take a unified approach to constructing $t$ -designs and PRUs. For this, we introduce and analyse the “ $PFC$ ensemble”, the product of a random computational basis permutation $P$, a random binary phase operator $F$, and a random Clifford unitary $C$. We show that this ensemble reproduces exponentially high moments of the Haar measure. We can then derandomise the $PFC$ ensemble to show the following: •Linear-depth $t$ -designs. We give the first construction of a (diamond-error) approximate $t$ -design with circuit depth linear in $t$. This follows from the $PFC$ ensemble by replacing the random phase and permutation operators with their $2t$ -wise independent counterparts. •Non-adaptive PRUs. We give the first construction of PRUs with non-adaptive security, i. e. we construct unitaries that are indistinguishable from Haar random to polynomial-time distinguishers that query the unitary in parallel on an arbitary state. This follows from the $PFC$ ensemble by replacing the random phase and permutation operators with their pseudorandom counterparts. •Adaptive pseudorandom isometries. We show that if one considers isometries (rather than unitaries) from $n$ to $n+\omega(\log n)$ qubits, a small modification of our PRU construction achieves adaptive security, i. e. even a distinguisher that can query the isometry adaptively in sequence cannot distinguish it from Haar random isometries. This gives the first construction of adaptive pseudorandom isometries. Under an additional conjecture, this proof also extends to adaptive PRUs.

Details

STOC Conference 2024 Conference Paper

The Power of Adaptivity in Quantum Query Algorithms

  • Uma Girish
  • Makrand Sinha
  • Avishay Tal
  • Kewen Wu 0001

Motivated by limitations on the depth of near-term quantum devices, we study the depth-computation trade-off in the query model, where depth corresponds to the number of adaptive query rounds and the computation per layer corresponds to the number of parallel queries per round. We achieve the strongest known separation between quantum algorithms with r versus r −1 rounds of adaptivity. We do so by using the k -fold Forrelation problem introduced by Aaronson and Ambainis (SICOMP’18). For k =2 r , this problem can be solved using an r round quantum algorithm with only one query per round, yet we show that any r −1 round quantum algorithm needs an exponential (in the number of qubits) number of parallel queries per round. Our results are proven following the Fourier analytic machinery developed in recent works on quantum-classical separations. The key new component in our result are bounds on the Fourier weights of quantum query algorithms with bounded number of rounds of adaptivity. These may be of independent interest as they distinguish the polynomials that arise from such algorithms from arbitrary bounded polynomials of the same degree.

Details

FOCS Conference 2023 Conference Paper

Fourier Growth of Communication Protocols for XOR Functions

  • Uma Girish
  • Makrand Sinha
  • Avishay Tal
  • Kewen Wu 0001

The level-k $\ell_{1}$-Fourier weight of a Boolean function refers to the sum of absolute values of its level-k Fourier coefficients. Fourier growth refers to the growth of these weights as k grows. It has been extensively studied for various computational models, and bounds on the Fourier growth, even for the first few levels, have proven useful in learning theory, circuit lower bounds, pseudorandomness, and quantum-classical separations. In this work, we investigate the Fourier growth of certain functions that naturally arise from communication protocols for XOR functions (partial functions evaluated on the bitwise XOR of the inputs x and y to Alice and Bob). If a protocol $\mathcal C$ computes an XOR function, then $\mathcal{C}(x, y)$ is a function of the parity $x \oplus y$. This motivates us to analyze the XOR-fiber of the communication protocol $\mathcal{C}$, defined as $h(z): =\mathbb{E}_{\boldsymbol{x}, \boldsymbol{y}}[\mathcal{C}(\boldsymbol{x}, \boldsymbol{y}) \mid \boldsymbol{x} \oplus \boldsymbol{y}=z]$. We present improved Fourier growth bounds for the XOR-fibers of randomized protocols that communicate d bits. For the first level, we show a tight $O(\sqrt{d})$ bound and obtain a new coin theorem, as well as an alternative proof for the tight randomized communication lower bound for the Gap-Hamming problem. For the second level, we show an $d^{3 / 2} \cdot \operatorname{polylog}(n)$ bound, which improves the previous $O\left(d^{2}\right)$ bound by Girish, Raz, and Tal (ITCS 2021) and implies a polynomial improvement on the randomized communication lower bound for the XOR-lift of the Forrelation problem, which extends the quantum-classical gap for this problem. Our analysis is based on a new way of adaptively partitioning a relatively large set in Gaussian space to control its moments in all directions. We achieve this via martingale arguments and allowing protocols to transmit real values. We also show a connection between Fourier growth and lifting theorems with constant-sized gadgets as a potential approach to prove optimal bounds for the second level and beyond.

Details

SODA Conference 2021 Conference Paper

Online Discrepancy Minimization for Stochastic Arrivals

  • Nikhil Bansal 0001
  • Haotian Jiang
  • Raghu Meka
  • Sahil Singla 0001
  • Makrand Sinha

In the stochastic online vector balancing problem, vectors v 1, v 2, …, v T chosen independently from an arbitrary distribution in ℝ n arrive one-by-one and must be immediately given a ± sign. The goal is to keep the norm of the discrepancy vector, i. e. , the signed prefix-sum, as small as possible for a given target norm. We consider some of the most well-known problems in discrepancy theory in the above online stochastic setting, and give algorithms that match the known offline bounds up to polylog( nT ) factors. This substantially generalizes and improves upon the previous results of Bansal, Jiang, Singla, and Sinha (STOC' 20). In particular, for the Komlós problem where ‖v t ‖ 2 ≤ 1 for each t, our algorithm achieves Õ (1) discrepancy with high probability, improving upon the previous Õ ( n 3/2 ) bound. For Tusnády's problem of minimizing the discrepancy of axis-aligned boxes, we obtain an O (log d +4 T ) bound for arbitrary distribution over points. Previous techniques only worked for product distributions and gave a weaker O (log 2 d +1 T ) bound. We also consider the Banaszczyk setting, where given a symmetric convex body K with Gaussian measure at least 1/2, our algorithm achieves Õ (1) discrepancy with respect to the norm given by K for input distributions with sub-exponential tails. Our results are based on a new potential function approach. Previous techniques consider a potential that penalizes large discrepancy, and greedily chooses the next color to minimize the increase in potential. Our key idea is to introduce a potential that also enforces constraints on how the discrepancy vector evolves, allowing us to maintain certain anti-concentration properties. We believe that our techniques to control the evolution of states could find other applications in stochastic processes and online algorithms. For the Banaszczyk setting, we further enhance this potential by combining it with ideas from generic chaining. Finally, we also extend these results to the setting of online multicolor discrepancy.

Details

FOCS Conference 2019 Conference Paper

Exponential Separation between Quantum Communication and Logarithm of Approximate Rank

  • Makrand Sinha
  • Ronald de Wolf

Chattopadhyay, Mande and Sherif (CMS19) recently exhibited a total Boolean function, the sink function, that has polynomial approximate rank and polynomial randomized communication complexity. This gives an exponential separation between randomized communication complexity and logarithm of the approximate rank, refuting the log-approximate-rank conjecture. We show that even the quantum communication complexity of the sink function is polynomial, thus also refuting the quantum log-approximate-rank conjecture. Our lower bound is based on the fooling distribution method introduced by Rao and Sinha (Theory Comput. , 2018) for the classical case and extended by Anshu, Touchette, Yao and Yu (STOC, 2017) for the quantum case. We also give a new proof of the classical lower bound using the fooling distribution method.

Details

FOCS Conference 2012 Conference Paper

Constructing a Pseudorandom Generator Requires an Almost Linear Number of Calls

  • Thomas Holenstein
  • Makrand Sinha

We show that a black-box construction of a pseudorandom generator from a one-way function needs to make Ω(n/log(n)) calls to the underlying one-way function. The bound even holds if the one-way function is guaranteed to be regular. In this case it matches the best known construction due to Gold Reich, Krawczyk, and Luby (SIAM J. Comp. 22, 1993), which uses O(n/log(n)) calls.

Details