Zobrazeno 1 - 10
of 36
pro vyhledávání: '"Sinha, Makrand"'
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 al
Externí odkaz:
http://arxiv.org/abs/2404.12647
Pseudorandom unitaries (PRUs) are ensembles of efficiently implementable unitary operators that cannot be distinguished from Haar random unitaries by any quantum polynomial-time algorithm with query access to the unitary. We present a simple PRU cons
Externí odkaz:
http://arxiv.org/abs/2402.14803
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 adaptive query rounds and the computation per layer corresponds to the numbe
Externí odkaz:
http://arxiv.org/abs/2311.16057
Standard mixed-integer programming formulations for the stable set problem on $n$-node graphs require $n$ integer variables. We prove that this is almost optimal: We give a family of $n$-node graphs for which every polynomial-size MIP formulation req
Externí odkaz:
http://arxiv.org/abs/2308.16711
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 com
Externí odkaz:
http://arxiv.org/abs/2307.13926
We construct a classical oracle relative to which $\mathsf{P} = \mathsf{NP}$ yet single-copy secure pseudorandom quantum states exist. In the language of Impagliazzo's five worlds, this is a construction of pseudorandom states in "Algorithmica," and
Externí odkaz:
http://arxiv.org/abs/2212.00879
Publikováno v:
Proceedings of the 43rd International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2024)
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 property underpins the security of various cryptographic applications,
Externí odkaz:
http://arxiv.org/abs/2211.12954
The well-known Koml\'os conjecture states that given $n$ vectors in $\mathbb{R}^d$ with Euclidean norm at most one, there always exists a $\pm 1$ coloring such that the $\ell_{\infty}$ norm of the signed-sum vector is a constant independent of $n$ an
Externí odkaz:
http://arxiv.org/abs/2204.11427
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 true, would imply that the acceptance probability of every $d$-query qu
Externí odkaz:
http://arxiv.org/abs/2203.00212
A well-known result of Banaszczyk in discrepancy theory concerns the prefix discrepancy problem (also known as the signed series problem): given a sequence of $T$ unit vectors in $\mathbb{R}^d$, find $\pm$ signs for each of them such that the signed
Externí odkaz:
http://arxiv.org/abs/2111.07049