63 citations · 63 across the 2 of their papers we have counts for
3 papers · 1 filter
Symmetries, graph properties, and quantum speedups
Shalev Ben-David, Andrew M. Childs, András Gilyén +3
Aaronson and Ambainis (2009) and Chailloux (2018) showed that fully symmetric (partial) functions do not admit exponential quantum query speedups. This raises a natural question: h…
Quantum Lower Bounds for Approximate Counting via Laurent Polynomials
Scott Aaronson, Robin Kothari, William Kretschmer +1
We study quantum algorithms that are given access to trusted and untrusted quantum witnesses. We establish strong limitations of such algorithms, via new techniques based on Lauren…
Simulation of Qubit Quantum Circuits via Pauli Propagation
Patrick Rall, Daniel Liang, Jeremy Cook +1
We present novel algorithms to estimate outcomes for qubit quantum circuits. Notably, these methods can simulate a Clifford circuit in linear time without ever writing down stabili…