Adam Bouland

According to our database, Adam Bouland authored at least 29 papers between 2012 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

The state hidden subgroup problem and an efficient algorithm for locating unentanglement.

Adam Bouland, Tudor Giurgica-Tiron, John Wright

CoRR, 2024

Efficient unitary designs and pseudorandom unitaries from permutations.

Chi-Fang Chen, Adam Bouland, Fernando G. S. L. Brandão, Jordan Docter, Patrick Hayden, Michelle Xu

CoRR, 2024

Efficient Unitary T-designs from Random Sums.

Chi-Fang Chen, Jordan Docter, Michelle Xu, Adam Bouland, Patrick Hayden

CoRR, 2024

Quantum Pseudoentanglement.

Scott Aaronson, Adam Bouland, Bill Fefferman, Soumik Ghosh, Umesh V. Vazirani, Chenyi Zhang, Zixin Zhou

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

Efficient Unitary Designs from Random Sums and Permutations.

Chi-Fang Chen, Jordan Docter, Michelle Xu, Adam Bouland, Fernando G. S. L. Brandão, Patrick Hayden

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

Public-Key Pseudoentanglement and the Hardness of Learning Ground State Entanglement Structure.

Adam Bouland, Bill Fefferman, Soumik Ghosh, Tony Metger, Umesh V. Vazirani, Chenyi Zhang, Zixin Zhou

Proceedings of the 39th Computational Complexity Conference, 2024

2023

Pseudorandomness from Subset States.

Tudor Giurgica-Tiron, Adam Bouland

CoRR, 2023

Complexity-theoretic foundations of BosonSampling with a linear number of modes.

Adam Bouland, Daniel Jost Brod, Ishaun Datta, Bill Fefferman, Daniel Grier, Felipe Hernandez, Michal Oszmaniec

CoRR, 2023

Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling.

Adam Bouland, Yosheb M. Getachew, Yujia Jin, Aaron Sidford, Kevin Tian

Proceedings of the International Conference on Machine Learning, 2023

2022

Quantum Pseudoentanglement.

Adam Bouland, Bill Fefferman, Soumik Ghosh, Umesh V. Vazirani, Zixin Zhou

CoRR, 2022

2021

Efficient Universal Quantum Compilation: An Inverse-free Solovay-Kitaev Algorithm.

Adam Bouland, Tudor Giurgica-Tiron

CoRR, 2021

Noise and the Frontier of Quantum Supremacy.

Adam Bouland, Bill Fefferman, Zeph Landau, Yunchao Liu

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

On the Power of Statistical Zero Knowledge.

Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan

SIAM J. Comput., 2020

Computational Pseudorandomness, the Wormhole Growth Paradox, and Constraints on the AdS/CFT Duality (Abstract).

Adam Bouland, Bill Fefferman, Umesh V. Vazirani

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

2019

Computational pseudorandomness, the wormhole growth paradox, and constraints on the AdS/CFT duality.

Adam Bouland, Bill Fefferman, Umesh V. Vazirani

CoRR, 2019

"Quantum Supremacy" and the Complexity of Random Circuit Sampling.

Adam Bouland, Bill Fefferman, Chinmay Nirkhe, Umesh V. Vazirani

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

2018

Trading Inverses for an Irrep in the Solovay-Kitaev Theorem.

Adam Bouland, Maris Ozols

Proceedings of the 13th Conference on the Theory of Quantum Computation, 2018

Classical Lower Bounds from Quantum Upper Bounds.

Shalev Ben-David, Adam Bouland, Ankit Garg, Robin Kothari

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

Complexity Classification of Conjugated Clifford Circuits.

Adam Bouland, Joseph F. Fitzsimons, Dax Enshan Koh

Proceedings of the 33rd Computational Complexity Conference, 2018

2017

Space around bounded-error quantum polynomial time.

Adam Bouland

PhD thesis, 2017

Quantum Advantage from Conjugated Clifford Circuits.

Adam Bouland, Joseph F. Fitzsimons, Dax Enshan Koh

CoRR, 2017

The computational complexity of ball permutations.

Scott Aaronson, Adam Bouland, Greg Kuperberg, Saeed Mehraban

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

2016

Complexity Classification of Two-Qubit Commuting Hamiltonians.

Adam Bouland, Laura Mancinska, Xue Zhang

Electron. Colloquium Comput. Complex., 2016

On SZK and PP.

Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan

Electron. Colloquium Comput. Complex., 2016

Establishing quantum advantage.

Adam Bouland

XRDS, 2016

On the Complexity of Probabilistic Trials for Hidden Satisfiability Problems.

Itai Arad, Adam Bouland, Daniel Grier, Miklos Santha, Aarthi Sundaram, Shengyu Zhang

Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

2014

The space "just above" BQP.

Scott Aaronson, Adam Bouland, Joseph F. Fitzsimons, Mitchell Lee

Electron. Colloquium Comput. Complex., 2014

2013

Any Beamsplitter Generates Universal Quantum Linear Optics.

Adam Bouland, Scott Aaronson

Electron. Colloquium Comput. Complex., 2013

2012

On Tractable Parameterizations of Graph Isomorphism.

Adam Bouland, Anuj Dawar, Eryk Kopczynski

Proceedings of the Parameterized and Exact Computation - 7th International Symposium, 2012