Zobrazeno 1 - 10
of 312
pro vyhledávání: '"O'Donnell, Ryan P."'
We describe a quantum algorithm for the Planted Noisy $k$XOR problem (also known as sparse Learning Parity with Noise) that achieves a nearly quartic ($4$th power) speedup over the best known classical algorithm while also only using logarithmically
Externí odkaz:
http://arxiv.org/abs/2406.19378
Autor:
He, William, O'Donnell, Ryan
We study pseudorandomness properties of permutations on $\{0,1\}^n$ computed by random circuits made from reversible $3$-bit gates (permutations on $\{0,1\}^3$). Our main result is that a random circuit of depth $n \cdot \tilde{O}(k^2)$, with each la
Externí odkaz:
http://arxiv.org/abs/2404.14648
We give a strongly explicit construction of $\varepsilon$-approximate $k$-designs for the orthogonal group $\mathrm{O}(N)$ and the unitary group $\mathrm{U}(N)$, for $N=2^n$. Our designs are of cardinality $\mathrm{poly}(N^k/\varepsilon)$ (equivalent
Externí odkaz:
http://arxiv.org/abs/2310.13597
Autor:
Flammia, Steven T., O'Donnell, Ryan
Publikováno v:
Quantum 8, 1381 (2024)
For quantum state tomography on rank-$r$ dimension-$d$ states, we show that $\widetilde{O}(r^{.5}d^{1.5}/\epsilon) \leq \widetilde{O}(d^2/\epsilon)$ copies suffice for accuracy~$\epsilon$ with respect to (Bures) $\chi^2$-divergence, and $\widetilde{O
Externí odkaz:
http://arxiv.org/abs/2305.18519
Publikováno v:
2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), Santa Cruz, CA, USA, 2023, pp. 363-390
We consider process tomography for unitary quantum channels. Given access to an unknown unitary channel acting on a $\textsf{d}$-dimensional qudit, we aim to output a classical description of a unitary that is $\varepsilon$-close to the unknown unita
Externí odkaz:
http://arxiv.org/abs/2302.14066
Autor:
Kothari, Robin, O'Donnell, Ryan
Suppose $\boldsymbol{y}$ is a real random variable, and one is given access to ``the code'' that generates it (for example, a randomized or quantum circuit whose output is $\boldsymbol{y}$). We give a quantum procedure that runs the code $O(n)$ times
Externí odkaz:
http://arxiv.org/abs/2208.07544
Autor:
O'Donnell, Ryan, Pratt, Kevin
Let $\Phi$ be an irreducible root system (other than $G_2$) of rank at least $2$, let $\mathbb{F}$ be a finite field with $p = \operatorname{char} \mathbb{F} > 3$, and let $\mathrm{G}(\Phi,\mathbb{F})$ be the corresponding Chevalley group. We describ
Externí odkaz:
http://arxiv.org/abs/2203.03705
Autor:
Jeronimo, Fernando Granha, Mittal, Tushant, O'Donnell, Ryan, Paredes, Pedro, Tulsiani, Madhur
For an abelian group $H$ acting on the set $[\ell]$, an $(H,\ell)$-lift of a graph $G_0$ is a graph obtained by replacing each vertex by $\ell$ copies, and each edge by a matching corresponding to the action of an element of $H$. In this work, we sho
Externí odkaz:
http://arxiv.org/abs/2112.01647
Autor:
Hastings, Matthew B., O'Donnell, Ryan
The fundamental problem in much of physics and quantum chemistry is to optimize a low-degree polynomial in certain anticommuting variables. Being a quantum mechanical problem, in many cases we do not know an efficient classical witness to the optimum
Externí odkaz:
http://arxiv.org/abs/2110.10701
We consider a very wide class of models for sparse random Boolean 2CSPs; equivalently, degree-2 optimization problems over~$\{\pm 1\}^n$. For each model $\mathcal{M}$, we identify the "high-probability value"~$s^*_{\mathcal{M}}$ of the natural SDP re
Externí odkaz:
http://arxiv.org/abs/2108.01038