194 citations · 1.9k across the 115 of their papers we have counts for
Showing 2014 · quant-phShow all
2 papers · 2 filters
quant-ph2014
Forrelation: A Problem that Optimally Separates Quantum from Classical Computing
Scott Aaronson, Andris Ambainis
We achieve essentially the largest possible separation between quantum and classical query complexities. We do so using a property-testing problem called Forrelation, where one nee…
quant-ph2014★ 4 cited
Quantum Attacks on Classical Proof Systems - The Hardness of Quantum Rewinding
Andris Ambainis, Ansis Rosmanis, Dominique Unruh
Quantum zero-knowledge proofs and quantum proofs of knowledge are inherently difficult to analyze because their security analysis uses rewinding. Certain cases of quantum rewinding…