291 citations · 664 across the 28 of their papers we have counts for
5 papers · 1 filter
The Computational Complexity of Ball Permutations
Scott Aaronson, Adam Bouland, Greg Kuperberg +1
Inspired by connections to two dimensional quantum theory, we define several models of computation based on permuting distinguishable particles (which we call balls), and character…
On the Power of Statistical Zero Knowledge
Adam Bouland, Lijie Chen, Dhiraj Holden +2
We examine the power of statistical zero knowledge proofs (captured by the complexity class SZK) and their variants. First, we give the strongest known relativized evidence that SZ…
Rescuing Complementarity With Little Drama
Ning Bao, Adam Bouland, Aidan Chatwin-Davies +2
The AMPS paradox challenges black hole complementarity by apparently constructing a way for an observer to bring information from the outside of the black hole into its interior if…
On the complexity of probabilistic trials for hidden satisfiability problems
Itai Arad, Adam Bouland, Daniel Grier +3
What is the minimum amount of information and time needed to solve 2SAT? When the instance is known, it can be solved in polynomial time, but is this also possible without knowing…
Complexity classification of two-qubit commuting hamiltonians
Adam Bouland, Laura Mančinska, Xue Zhang
We classify two-qubit commuting Hamiltonians in terms of their computational complexity. Suppose one has a two-qubit commuting Hamiltonian H which one can apply to any pair of qubi…