Zobrazeno 1 - 10
of 652
pro vyhledávání: '"O'Donnell, Ryan"'
Autor:
O'Donnell, Ryan, Singer, Noah G.
Recent major results in property testing~\cite{BLM24,DDL24} and PCPs~\cite{BMV24} were unlocked by moving to high-dimensional expanders (HDXs) constructed from $\widetilde{C}_d$-type buildings, rather than the long-known $\widetilde{A}_d$-type ones.
Externí odkaz:
http://arxiv.org/abs/2411.05916
We study quantum algorithms for verifying properties of the output probability distribution of a classical or quantum circuit, given access to the source code that generates the distribution. We consider the basic task of uniformity testing, which is
Externí odkaz:
http://arxiv.org/abs/2411.04972
Autor:
Bakshi, Ainesh, Bostanci, John, Kretschmer, William, Landau, Zeph, Li, Jerry, Liu, Allen, O'Donnell, Ryan, Tang, Ewin
We study the problem of finding a product state with optimal fidelity to an unknown $n$-qubit quantum state $\rho$, given copies of $\rho$. This is a basic instance of a fundamental question in quantum learning: is it possible to efficiently learn a
Externí odkaz:
http://arxiv.org/abs/2411.04283
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