218 citations · 643 across the 16 of their papers we have counts for
Showing 2004Show all
3 papers · 1 filter
quant-ph2004★ 6 cited
All Quantum Adversary Methods are Equivalent
Robert Spalek, Mario Szegedy
The quantum adversary method is one of the most versatile lower-bound methods for quantum algorithms. We show that all known variants of this method are equivalent: spectral advers…
quant-ph2004★ 2 cited
Quantum Verification of Matrix Products
Harry Buhrman, Robert Spalek
We present a quantum algorithm that verifies a product of two n*n matrices over any field with bounded error in worst-case time n^{5/3} and expected time n^{5/3} / min(w,sqrt(n))^{…
quant-ph2004★ 1 cited
Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs
Hartmut Klauck, Robert Spalek, Ronald de Wolf
A strong direct product theorem says that if we want to compute k independent instances of a function, using less than k times the resources needed for one instance, then our overa…