2.7k citations
- University of AmsterdamNL294 papers
- Eindhoven University of TechnologyNL163 papers
- QuSoftNL123 papers
- Leiden UniversityNL91 papers
- Delft University of TechnologyNL82 papers
- Vrije Universiteit AmsterdamNL61 papers
- Centre National de la Recherche ScientifiqueFR52 papers
- Radboud University NijmegenNL37 papers
- Utrecht UniversityNL37 papers
- University of WaterlooCA34 papers
- University of OxfordGB28 papers
- University College LondonGB26 papers
5 papers · 2 filters
Comparing EQP and MOD_{p^k}P using Polynomial Degree Lower Bounds
M. de Graaf, P. Valiant
We show that an oracle A that contains either 1/4 or 3/4 of all strings of length n can be used to separate EQP from the counting classes MOD_{p^k}P. Our proof makes use of the deg…
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…
Exponential Lower Bound for 2-Query Locally Decodable Codes via a Quantum Argument
Iordanis Kerenidis, Ronald de Wolf
A locally decodable code encodes n-bit strings x in m-bit codewords C(x), in such a way that one can recover any bit x_i from a corrupted codeword by querying only a few bits of th…
Quantum Circuits with Unbounded Fan-out
Peter Hoyer, Robert Spalek
We demonstrate that the unbounded fan-out gate is very powerful. Constant-depth polynomial-size quantum circuits with bounded fan-in and unbounded fan-out over a fixed basis (denot…