List of research outcomes
This list is not complete and representing at the moment only items from zbMATH Open and arXiv. We are working on additional sources - please check back here soon!
| Publication | Date of Publication | Type |
|---|---|---|
| Efficient tomography of non-interacting-fermion states | 2024-11-20 | Paper |
| The acrobatics of BQP | 2024-07-05 | Paper |
| Quantum approximate counting, simplified | 2024-05-14 | Paper |
| Certified randomness from quantum supremacy | 2024-05-08 | Paper |
| scientific article; zbMATH DE number 7799579 (Why is no real title available?) | 2024-02-05 | Paper |
| Degree vs. approximate degree and Quantum implications of Huang’s sensitivity theorem Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
| An automated approach to the Collatz conjecture Journal of Automated Reasoning | 2023-06-27 | Paper |
| Discrete bulk reconstruction Journal of High Energy Physics | 2023-06-09 | Paper |
| scientific article; zbMATH DE number 7561499 (Why is no real title available?) (available as arXiv preprint) | 2022-07-21 | Paper |
| scientific article; zbMATH DE number 7561744 (Why is no real title available?) (available as arXiv preprint) | 2022-07-21 | Paper |
| Quantum lower bounds for approximate counting via Laurent polynomials (available as arXiv preprint) | 2022-07-21 | Paper |
| New approaches for quantum copy-protection (available as arXiv preprint) | 2022-03-31 | Paper |
| An automated approach to the Collatz conjecture (available as arXiv preprint) | 2021-12-01 | Paper |
| Online learning of quantum states Journal of Statistical Mechanics: Theory and Experiment | 2021-03-16 | Paper |
| On the classical hardness of spoofing linear cross-entropy benchmarking Theory of Computing | 2020-12-17 | Paper |
| Shadow tomography of quantum states SIAM Journal on Computing | 2020-10-29 | Paper |
| A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory Complex Systems | 2020-10-20 | Paper |
| Complexity-theoretic foundations of quantum supremacy experiments (available as arXiv preprint) | 2020-05-26 | Paper |
| Gentle measurement of quantum states and differential privacy Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
| Shadow tomography of quantum states Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
| The fewest clues problem Theoretical Computer Science | 2018-11-23 | Paper |
| Forrelation: a problem that optimally separates quantum from classical computing SIAM Journal on Computing | 2018-07-04 | Paper |
| The classification of reversible bit operations (available as arXiv preprint) | 2018-05-03 | Paper |
| Polynomials, quantum query complexity, and Grothendieck's inequality (available as arXiv preprint) | 2017-10-10 | Paper |
| scientific article; zbMATH DE number 6789291 (Why is no real title available?) (available as arXiv preprint) | 2017-10-10 | Paper |
| Separations in query complexity using cheat sheets Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | Paper |
| The computational complexity of ball permutations Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
| The fewest clues problem | 2017-07-17 | Paper |
| \(\mathrm P \overset {?} {=} \mathrm{NP}\) Open Problems in Mathematics | 2016-10-18 | Paper |
| The space ``just above BQP Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science | 2016-04-15 | Paper |
| Algebrization: a new barrier in complexity theory ACM Transactions on Computation Theory | 2015-09-24 | Paper |
| Forrelation: a problem that optimally separates quantum from classical computing Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | 2015-08-21 | Paper |
| The equivalence of sampling and searching Theory of Computing Systems | 2015-02-05 | Paper |
| The computational complexity of linear optics Theory of Computing | 2014-10-06 | Paper |
| The need for structure in quantum speedups Theory of Computing | 2014-10-06 | Paper |
| Quantum money from hidden subspaces Theory of Computing | 2014-10-06 | Paper |
| A full characterization of quantum advice SIAM Journal on Computing | 2014-09-18 | Paper |
| BQP and the polynomial hierarchy Proceedings of the forty-second ACM symposium on Theory of computing | 2014-08-13 | Paper |
| A full characterization of quantum advice Proceedings of the forty-second ACM symposium on Theory of computing | 2014-08-13 | Paper |
| Weak parity Automata, Languages, and Programming | 2014-07-01 | Paper |
| Weak parity Automata, Languages, and Programming | 2014-07-01 | Paper |
| The computational complexity of linear optics Proceedings of the forty-third annual ACM symposium on Theory of computing | 2014-06-05 | Paper |
| Quantum money from hidden subspaces Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | Paper |
| The one-way communication complexity of subgroup membership Chicago Journal of Theoretical Computer Science | 2014-05-06 | Paper |
| Sophistication as randomness deficiency Descriptional Complexity of Formal Systems | 2013-08-09 | Paper |
| Skepticism of quantum computing Quantum Computing since Democritus | 2012-12-27 | Paper |
| Impossibility of succinct quantum proofs for collision-freeness | 2012-10-21 | Paper |
| On circuit lower bounds from derandomization Theory of Computing | 2012-09-27 | Paper |
| A linear-optical proof that the permanent is \(\#\mathrm{P}\)-hard Proceedings of the Royal Society of London. Series A. Mathematical, Physical and Engineering Sciences | 2012-07-31 | Paper |
| Quantum computing and hidden variables Physical Review A | 2011-12-04 | Paper |
| Advice coins for classical and quantum computation Automata, Languages and Programming | 2011-07-06 | Paper |
| The equivalence of sampling and searching Computer Science – Theory and Applications | 2011-06-17 | Paper |
| Quantum search of spatial regions Theory of Computing | 2011-05-24 | Paper |
| Quantum versus classical proofs and advice Theory of Computing | 2011-05-24 | Paper |
| The power of unentanglement Theory of Computing | 2011-05-24 | Paper |
| Limitations of Quantum Advice and One-Way Communication Theory of Computing | 2011-05-24 | Paper |
| The complexity of agreement Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
| Lower bounds for local search by quantum arguments Proceedings of the thirty-sixth annual ACM symposium on Theory of computing | 2010-08-15 | Paper |
| Multilinear formulas and skepticism of quantum computing Proceedings of the thirty-sixth annual ACM symposium on Theory of computing | 2010-08-15 | Paper |
| Quantum lower bound for the collision problem Proceedings of the thiry-fourth annual ACM symposium on Theory of computing | 2010-08-05 | Paper |
| Closed timelike curves make quantum and classical computing equivalent Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences | 2010-05-19 | Paper |
| scientific article; zbMATH DE number 5604094 (Why is no real title available?) | 2009-09-15 | Paper |
| On perfect completeness for QMA (available as arXiv preprint) | 2009-02-24 | Paper |
| scientific article; zbMATH DE number 5485587 (Why is no real title available?) | 2009-01-05 | Paper |
| Quantum lower bound for recursive Fourier sampling | 2008-09-03 | Paper |
| The learnability of quantum states Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences | 2008-06-27 | Paper |
| The Limits of Quantum Computers Computer Science – Theory and Applications | 2008-06-03 | Paper |
| Quantum lower bounds for the collision and the element distinctness problems Journal of the ACM | 2008-05-17 | Paper |
| Quantum certificate complexity Journal of Computer and System Sciences | 2008-03-11 | Paper |
| Quantum computing, postselection, and probabilistic polynomial-time Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences | 2007-11-21 | Paper |
| Lower Bounds for Local Search by Quantum Arguments SIAM Journal on Computing | 2006-06-01 | Paper |
| Algorithms for Boolean Function Query Properties SIAM Journal on Computing | 2003-09-28 | Paper |
Research outcomes over time
This page was built for person: Scott Aaronson
