Zobrazeno 1 - 10
of 146
pro vyhledávání: '"Aharonov, Dorit"'
The weak value exhibits numerous intriguing characteristics, such as values outside the operator spectrum, leading to unexpected phenomena. The measurement protocol used for measuring the weak value has been the subject of an on-going controversy. In
Externí odkaz:
http://arxiv.org/abs/2401.05532
Publikováno v:
In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023)
We give a polynomial time classical algorithm for sampling from the output distribution of a noisy random quantum circuit in the regime of anti-concentration to within inverse polynomial total variation distance. This gives strong evidence that, in t
Externí odkaz:
http://arxiv.org/abs/2211.03999
Autor:
Aharonov, Dorit, Irani, Sandy
We study the complexity of classical constraint satisfaction problems on a 2D grid. Specifically, we consider the complexity of function versions of such problems, with the additional restriction that the constraints are translationally invariant, na
Externí odkaz:
http://arxiv.org/abs/2209.08731
Autor:
Aharonov, Dorit, Irani, Sandy
Despite progress in quantum Hamiltonian complexity, little is known about the computational complexity of quantum physics at the thermodynamic limit. Even defining the problem is not straight forward. We study the complexity of estimating the ground
Externí odkaz:
http://arxiv.org/abs/2107.06201
Autor:
Zhou, Leo, Aharonov, Dorit
A universal family of Hamiltonians can be used to simulate any local Hamiltonian by encoding its full spectrum as the low-energy subspace of a Hamiltonian from the family. Many spin-lattice model Hamiltonians -- such as Heisenberg or XY interaction o
Externí odkaz:
http://arxiv.org/abs/2102.02991
We initiate the systematic study of experimental quantum physics from the perspective of computational complexity. To this end, we define the framework of quantum algorithmic measurements (QUALMs), a hybrid of black box quantum algorithms and interac
Externí odkaz:
http://arxiv.org/abs/2101.04634
StoqMA characterizes the computational hardness of stoquastic local Hamiltonians, which is a family of Hamiltonians that does not suffer from the sign problem. Although error reduction is commonplace for many complexity classes, such as BPP, BQP, MA,
Externí odkaz:
http://arxiv.org/abs/2010.02835
Autor:
Aharonov, Dorit, Grilo, Alex B.
Despite the interest in the complexity class MA, the randomized analog of NP, just a few natural MA-complete problems are known. The first problem was found by (Bravyi and Terhal, SIAM Journal of Computing 2009); it was then followed by (Crosson, Bac
Externí odkaz:
http://arxiv.org/abs/2003.13065
Autor:
Atia, Yosi, Aharonov, Dorit
Towards better understanding of how to design efficient adiabatic quantum algorithms, we study how the adiabatic gap depends on the spectra of the initial and final Hamiltonians in a natural family of test-bed examples. We show that perhaps counter-i
Externí odkaz:
http://arxiv.org/abs/1906.02581
In (single-server) Private Information Retrieval (PIR), a server holds a large database $DB$ of size $n$, and a client holds an index $i \in [n]$ and wishes to retrieve $DB[i]$ without revealing $i$ to the server. It is well known that information th
Externí odkaz:
http://arxiv.org/abs/1902.09768