291 citations · 664 across the 28 of their papers we have counts for
4 papers · 1 filter
Breaking the cubic barrier for the inverse-free Solovay-Kitaev algorithm
Adam Bouland, Victor Shyaka, Chenyi Zhang
The Solovay-Kitaev algorithm states that it is possible to efficiently compile unitaries to accuracy in time using any universal gate set. While Solovay a…
Exponential quantum space advantage in random data streams
Adam Bouland, Matthew Ding, Siddhartha Jain
We show two unconditional quantum space advantages in the random-order streaming model. First, we show the Yamakawa--Zhandry Code Intersection problem admits exponential quantum ad…
A Separation Between Types of Quantum Oracle Separations
Scott Aaronson, Adam Bouland, Jordan Docter +1
Recent works have demonstrated that quantum oracles have subtle behavior, as access to inverse, conjugate or controlled queries can exponentially change the query complexity of cer…
Does Not Relativize
Adam Bouland, Andrew Huang, Anand Natarajan +2
We construct an oracle relative to which , resolving a long-standing open question in quantum complexity theory. Together with recent work d…