1.2k citations · 3.7k across the 62 of their papers we have counts for
46 papers · 1 filter
State preparation by shallow circuits using feed forward
Harry Buhrman, Marten Folkertsma, Bruno Loff +1
In order to achieve fault-tolerant quantum computation, we need to repeat the following sequence of four steps: First, perform 1 or 2 qubit quantum gates (in parallel if possible).…
Relating non-local quantum computation to information theoretic cryptography
Rene Allerstorfer, Harry Buhrman, Alex May +2
Non-local quantum computation (NLQC) is a cheating strategy for position-verification schemes, and has appeared in the context of the AdS/CFT correspondence. Here, we connect NLQC…
A Qubit, a Coin, and an Advice String Walk Into a Relational Problem
Scott Aaronson, Harry Buhrman, William Kretschmer
Relational problems (those with many possible valid outputs) are different from decision problems, but it is easy to forget just how different. This paper initiates the study of FB…
Quantum majority vote
Harry Buhrman, Noah Linden, Laura Mančinska +2
Majority vote is a basic method for amplifying correct outcomes that is widely used in computer science and beyond. While it can amplify the correctness of a quantum device with cl…
On the Role of Quantum Communication and Loss in Attacks on Quantum Position Verification
Rene Allerstorfer, Harry Buhrman, Florian Speelman +1
We study the role of quantum communication in attacks on quantum position verification. In this work, we construct the first known example of a QPV protocol that is provably secure…
Memory Compression with Quantum Random-Access Gates
Harry Buhrman, Bruno Loff, Subhasree Patro +1
In the classical RAM, we have the following useful property. If we have an algorithm that uses memory cells throughout its execution, and in addition is sparse, in the sense th…
Limits of quantum speed-ups for computational geometry and other problems: Fine-grained complexity via quantum walks
Harry Buhrman, Bruno Loff, Subhasree Patro +1
Many computational problems are subject to a quantum speed-up: one might find that a problem having an O(n^3)-time or O(n^2)-time classic algorithm can be solved by a known O(n^1.5…
Towards practical and error-robust quantum position verification
Rene Allerstorfer, Harry Buhrman, Florian Speelman +1
Loss of inputs can be detrimental to the security of quantum position verification (QPV) protocols, as it may allow attackers to not answer on all played rounds, but only on those…
The Quantum Strong Exponential-Time Hypothesis
Harry Buhrman, Subhasree Patro, Florian Speelman
The strong exponential-time hypothesis (SETH) is a commonly used conjecture in the field of complexity theory. It states that CNF formulas cannot be analyzed for satisfiability wit…
Round elimination in exact communication complexity
Jop Briët, Harry Buhrman, Debbie Leung +2
We study two basic graph parameters, the chromatic number and the orthogonal rank, in the context of classical and quantum exact communication complexity. In particular, we conside…
Bounding quantum-classical separations for classes of nonlocal games
Tom Bannink, Jop Briët, Harry Buhrman +2
We bound separations between the entangled and classical values for several classes of nonlocal -player games. Our motivating question is whether there is a family of -player…
The European Quantum Technologies Roadmap
Antonio Acín, Immanuel Bloch, Harry Buhrman +15
Within the last two decades, Quantum Technologies (QT) have made tremendous progress, moving from Noble Prize award-winning experiments on quantum physics into a cross-disciplinary…
Quantum Pascal's Triangle and Sierpinski's carpet
Tom Bannink, Harry Buhrman
In this paper we consider a quantum version of Pascal's triangle. Pascal's triangle is a well-known triangular array of numbers and when these numbers are plotted modulo 2, a fract…
Nondeterministic quantum communication complexity: the cyclic equality game and iterated matrix multiplication
Harry Buhrman, Matthias Christandl, Jeroen Zuiddam
We study nondeterministic multiparty quantum communication with a quantum generalization of broadcasts. We show that, with number-in-hand classical inputs, the communication comple…
Quantum communication complexity advantage implies violation of a Bell inequality
Harry Buhrman, Lukasz Czekaj, Andrzej Grudka +5
We obtain a general connection between a quantum advantage in communication complexity and non-locality. We show that given any protocol offering a (sufficiently large) quantum adv…
On the Parallel Repetition of Multi-Player Games: The No-Signaling Case
Harry Buhrman, Serge Fehr, Christian Schaffner
We consider the natural extension of two-player nonlocal games to an arbitrary number of players. An important question for such nonlocal games is their behavior under parallel rep…
Entanglement-assisted zero-error source-channel coding
Jop Briët, Harry Buhrman, Monique Laurent +2
We study the use of quantum entanglement in the zero-error source-channel coding problem. Here, Alice and Bob are connected by a noisy classical one-way channel, and are given corr…
Violating the Shannon capacity of metric graphs with entanglement
Jop Briet, Harry Buhrman, Dion Gijswijt
The Shannon capacity of a graph G is the maximum asymptotic rate at which messages can be sent with zero probability of error through a noisy channel with confusability graph G. Th…
Classical simulation of entanglement swapping with bounded communication
Cyril Branciard, Nicolas Brunner, Harry Buhrman +5
Entanglement appears under two different forms in quantum theory, namely as a property of states of joint systems and as a property of measurement eigenstates in joint measurements…
Complete Insecurity of Quantum Protocols for Classical Two-Party Computation
Harry Buhrman, Matthias Christandl, Christian Schaffner
A fundamental task in modern cryptography is the joint computation of a function which has two inputs, one from Alice and one from Bob, such that neither of the two can learn more…
The Garden-Hose Model
Harry Buhrman, Serge Fehr, Christian Schaffner +1
We define a new model of communication complexity, called the garden-hose model. Informally, the garden-hose complexity of a function f:{0,1}^n x {0,1}^n to {0,1} is given by the m…
Near-Optimal and Explicit Bell Inequality Violations
Harry Buhrman, Oded Regev, Giannicola Scarpa +1
Entangled quantum systems can exhibit correlations that cannot be simulated classically. For historical reasons such correlations are called "Bell inequality violations." We give t…
Position-Based Quantum Cryptography: Impossibility and Constructions
Harry Buhrman, Nishanth Chandran, Serge Fehr +4
In this work, we study position-based cryptography in the quantum setting. The aim is to use the geographical position of a party as its only credential. On the negative side, we s…
Better Non-Local Games from Hidden Matching
Harry Buhrman, Giannicola Scarpa, Ronald de Wolf
We construct a non-locality game that can be won with certainty by a quantum strategy using log n shared EPR-pairs, while any classical strategy has winning probability at most 1/2…