56 citations · 98 across the 6 of their papers we have counts for
12 papers · 1 filter
Implications of Superstrong Nonlocality for Cryptography
Harry Buhrman, Matthias Christandl, Falk Unger +2
Non-local boxes are hypothetical ``machines'' that give rise to superstrong non-local correlations, leading to a stronger violation of Bell/CHSH inequalities than is possible withi…
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))^{…
Robust Polynomials and Quantum Algorithms
Harry Buhrman, Ilan Newman, Hein Roehrig +1
We define and study the complexity of robust polynomials for Boolean functions and the related fault-tolerant quantum decision trees, where input bits are perturbed by noise. We co…
Quantum Zero-Error Algorithms Cannot be Composed
Harry Buhrman, Ronald de Wolf
We exhibit two black-box problems, both of which have an efficient quantum algorithm with zero-error, yet whose composition does not have an efficient quantum algorithm with zero-e…
Combinatorics and Quantum Nonlocality
Harry Buhrman, Peter Hoyer, Serge Massar +1
We use techniques for lower bounds on communication to derive necessary conditions (in terms of detector efficiency or amount of super-luminal communication) for being able to repr…
Quantum Property Testing
H. Buhrman, L. Fortnow, I. Newman +1
A language L has a property tester if there exists a probabilistic algorithm that given an input x only asks a small number of bits of x and distinguishes the cases as to whether x…