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
6 papers · 2 filters
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 Symmetrically-Private Information Retrieval
Iordanis Kerenidis, Ronald de Wolf
Private information retrieval systems (PIRs) allow a user to extract an item from a database that is replicated over k>=1 servers, while satisfying various privacy constraints. We…
The statistical strength of nonlocality proofs
Wim van Dam, Peter Grunwald, Richard Gill
There exist numerous proofs of Bell's theorem, stating that quantum mechanics is incompatible with local realistic theories of nature. Here we define the strength of such nonlocali…
Quantum Search on Bounded-Error Inputs
Peter Hoyer, Michele Mosca, Ronald de Wolf
Suppose we have n algorithms, quantum or classical, each computing some bit-value with bounded error probability. We describe a quantum algorithm that uses O(sqrt{n}) repetitions o…
A geometric proof of the Kochen-Specker no-go theorem
Richard D. Gill, Michael S. Keane
We give a short geometric proof of the Kochen-Specker no-go theorem for non-contextual hidden variables models. Note added to this version: I understand from Jan-Aake Larsson that…
Multiparty Quantum Coin Flipping
Andris Ambainis, Harry Buhrman, Yevgeniy Dodis +1
We investigate coin-flipping protocols for multiple parties in a quantum broadcast setting: (1) We propose and motivate a definition for quantum broadcast. Our model of quantum bro…