Zobrazeno 1 - 10
of 30
pro vyhledávání: '"ROBIN KOTHARI"'
Publikováno v:
Physical Review X, Vol 13, Iss 4, p 041041 (2023)
We present a quantum algorithm for simulating the classical dynamics of 2^{n} coupled oscillators (e.g., 2^{n} masses coupled by springs). Our approach leverages a mapping between the Schrödinger equation and Newton’s equation for harmonic potenti
Externí odkaz:
https://doaj.org/article/f8c8665b61264185a1362bda1ff9f5df
Publikováno v:
Quantum, Vol 5, p 543 (2021)
We give new quantum algorithms for evaluating composed functions whose inputs may be shared between bottom-level gates. Let $f$ be an $m$-bit Boolean function and consider an $n$-bit function $F$ obtained by applying $f$ to conjunctions of possibly o
Externí odkaz:
https://doaj.org/article/ff61c71bd8b647f6a5a85a848aa71cc5
Publikováno v:
Forum of Mathematics, Sigma, Vol 5 (2017)
We provide a quantum algorithm for simulating the dynamics of sparse Hamiltonians with complexity sublogarithmic in the inverse error, an exponential improvement over previous methods. Specifically, we show that a $d$ -sparse Hamiltonian $H$ acting
Externí odkaz:
https://doaj.org/article/f5a175ce6770417dac0b6d9972b627e8
Autor:
Robin Kothari, Ryan O'Donnell
Publikováno v:
Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) ISBN: 9781611977554
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::4f1e46102808905bbeb0402034b4252b
https://doi.org/10.1137/1.9781611977554.ch44
https://doi.org/10.1137/1.9781611977554.ch44
Publikováno v:
Theory of Computing. 16:1-71
The approximate degree of a Boolean function f is the least degree of a real polynomial that approximates f pointwise to error at most 1/3. The approximate degree of f is known to be a lower bound on the quantum query complexity of f (Beals et al., F
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::8b660b839ed27d2e32931ce9ed106edf
https://doi.org/10.4086/toc.2020.v016a010
https://doi.org/10.4086/toc.2020.v016a010
Publikováno v:
STOC
Based on the recent breakthrough of Huang (2019), we show that for any total Boolean function f, deg(f) = O(adeg(f)^2): The degree of f is at most quadratic in the approximate degree of f. This is optimal as witnessed by the OR function. D(f) = O(Q(f
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::ce8eb4c6d3b79a216b6669e85d608c72
https://doi.org/10.1145/3406325.3451047
https://doi.org/10.1145/3406325.3451047
We exhibit an unambiguous k-DNF formula that requires CNF width $\tilde{\Omega}(k^2)$, which is optimal up to logarithmic factors. As a consequence, we get a near-optimal solution to the Alon--Saks--Seymour problem in graph theory (posed in 1991), wh
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b5fcefb461924ba283cb62ff7ac7669b
http://arxiv.org/abs/2102.08348
http://arxiv.org/abs/2102.08348
Autor:
Robin Kothari, Shalev Ben-David
Publikováno v:
Theory of Computing. 14:1-27
We study the composition question for bounded-error randomized query complexity: Is R(f o g) = Omega(R(f) R(g)) for all Boolean functions f and g? We show that inserting a simple Boolean function h, whose query complexity is only Theta(log R(g)), in
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::97dc75dac574aaf86208dac638877aa5
https://doi.org/10.4086/toc.2018.v014a005
https://doi.org/10.4086/toc.2018.v014a005
Publikováno v:
Quantum, Vol 5, p 543 (2021)
Scopus-Elsevier
Scopus-Elsevier
We give new quantum algorithms for evaluating composed functions whose inputs may be shared between bottom-level gates. Let $f$ be an $m$-bit Boolean function and consider an $n$-bit function $F$ obtained by applying $f$ to conjunctions of possibly o
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f052f5574a2c66fa8170795cc7d03f33
https://doi.org/10.22331/q-2021-09-16-543
https://doi.org/10.22331/q-2021-09-16-543
Publikováno v:
SIAM Journal on Computing. 46:1920-1950
Harrow, Hassidim, and Lloyd showed that for a suitably specified $N \times N$ matrix $A$ and $N$-dimensional vector $\vec{b}$, there is a quantum algorithm that outputs a quantum state proportional to the solution of the linear system of equations $A
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::7504e24cfb5a2662976b44b701fba65f
https://doi.org/10.1137/16m1087072
https://doi.org/10.1137/16m1087072