419 citations
- Massachusetts Institute of TechnologyUS181 papers
- Vilnius UniversityLT180 papers
- Boğaziçi UniversityTR178 papers
- Deutsches Elektronen-Synchrotron DESYDE178 papers
- University of Nebraska–LincolnUS178 papers
- Bulgarian Academy of SciencesBG176 papers
- Sofia University "St. Kliment Ohridski"BG175 papers
- University of BristolGB175 papers
- University of HelsinkiFI175 papers
- University of AntwerpBE174 papers
- University of BelgradeRS174 papers
- University of Notre DameUS174 papers
6 papers · 2 filters
A Quantum Lovasz Local Lemma
Andris Ambainis, Julia Kempe, Or Sattath
The Lovasz Local Lemma (LLL) is a powerful tool in probability theory to show the existence of combinatorial objects meeting a prescribed collection of "weakly dependent" criteria.…
The Need for Structure in Quantum Speedups
Scott Aaronson, Andris Ambainis
Is there a general theorem that tells us when we can hope for exponential speedups from quantum algorithms, and when we cannot? In this paper, we make two advances toward such a th…
Random tensor theory: extending random matrix theory to random product states
Andris Ambainis, Aram W. Harrow, Matthew B. Hastings
We consider a problem in random matrix theory that is inspired by quantum information theory: determining the largest eigenvalue of a sum of p random product states in (C^d)^{otime…
Limits on entropic uncertainty relations for 3 and more MUBs
Andris Ambainis
We consider entropic uncertainty relations for outcomes of the measurements of a quantum state in 3 or more mutually unbiased bases (MUBs), chosen from the standard construction of…
Average/Worst-Case Gap of Quantum Query Complexities by On-Set Size
Andris Ambainis, Kazuo Iwama, Masaki Nakanishi +4
This paper considers the query complexity of the functions in the family F_{N,M} of N-variable Boolean functions with onset size M, i.e., the number of inputs for which the functio…
The quantum query complexity of certification
Andris Ambainis, Andrew M. Childs, François Le Gall +1
We study the quantum query complexity of finding a certificate for a d-regular, k-level balanced NAND formula. Up to logarithmic factors, we show that the query complexity is Theta…