754 citations · 2.8k across the 28 of their papers we have counts for
20 papers · 1 filter
Noisy Interactive Quantum Communication
Gilles Brassard, Ashwin Nayak, Alain Tapp +2
We study the problem of simulating protocols in a quantum communication setting over noisy channels. This problem falls at the intersection of quantum information theory and quantu…
An optimal quantum algorithm to approximate the mean and its application for approximating the median of a set of points over an arbitrary distance
Gilles Brassard, Frederic Dupuis, Sebastien Gambs +1
We describe two quantum algorithms to approximate the mean value of a black-box function. The first algorithm is novel and asymptotically optimal while the second is a variation on…
Can quantum mechanics help distributed computing?
Anne Broadbent, Alain Tapp
We present a brief survey of results where quantum information processing is useful to solve distributed computation tasks. We describe problems that are impossible to solve using…
The GHZ state in secret sharing and entanglement simulation
Anne Broadbent, Paul Robert Chouha, Alain Tapp
In this note, we study some properties of the GHZ state. First, we present a quantum secret sharing scheme in which the participants require only classical channels in order to rec…
A quantum characterization of NP
Hugue Blier, Alain Tapp
In this article we introduce a new complexity class called PQMA_log(2). Informally, this is the class of languages for which membership has a logarithmic-size quantum proof with pe…
Anonymous quantum communication
Gilles Brassard, Anne Broadbent, Joseph Fitzsimons +2
We present the first protocol for the anonymous transmission of a quantum state that is information-theoretically secure against an active adversary, without any assumption on the…
A limit on nonlocality in any world in which communication complexity is not trivial
Gilles Brassard, Harry Buhrman, Noah Linden +3
Bell proved that quantum entanglement enables two space-like separated parties to exhibit classically impossible correlations. Even though these correlations are stronger than anyt…
Minimum entangled state dimension required for pseudo-telepathy
Gilles Brassard, Andre A. Methot, Alain Tapp
Pseudo-telepathy provides an intuitive way of looking at Bell's inequalities, in which it is often obvious that feats achievable by use of quantum entanglement would be classically…
Recasting Mermin's multi-player game into the framework of pseudo-telepathy
Gilles Brassard, Anne Broadbent, Alain Tapp
Entanglement is perhaps the most non-classical manifestation of quantum mechanics. Among its many interesting applications to information processing, it can be harnessed to reduce…
Quantum Pseudo-Telepathy
Gilles Brassard, Anne Broadbent, Alain Tapp
Quantum information processing is at the crossroads of physics, mathematics and computer science. It is concerned with that we can and cannot do with quantum information that goes…
Multi-Party Pseudo-Telepathy
Gilles Brassard, Anne Broadbent, Alain Tapp
Quantum entanglement, perhaps the most non-classical manifestation of quantum information theory, cannot be used to transmit information between remote parties. Yet, it can be used…
The Impossibility of Pseudo-Telepathy Without Quantum Entanglement
Viktor Galliard, Stefan Wolf, Alain Tapp
Imagine that Alice and Bob, unable to communicate, are both given a 16-bit string such that the strings are either equal, or they differ in exactly 8 positions. Both parties are th…
Authentication of Quantum Messages
Howard Barnum, Claude Crepeau, Daniel Gottesman +2
Authentication is a well-studied area of classical cryptography: a sender S and a receiver R sharing a classical private key want to exchange a classical message with the guarantee…
Private Quantum Channels and the Cost of Randomizing Quantum Information
Michele Mosca, Alain Tapp, Ronald de Wolf
We investigate how a classical private key can be used by two players, connected by an insecure one-way quantum channel, to perform private communication of quantum information. In…
The cost of exactly simulating quantum entanglement with classical communication
Gilles Brassard, Richard Cleve, Alain Tapp
We investigate the amount of communication that must augment classical local hidden variable models in order to simulate the behaviour of entangled quantum systems. We consider the…
Quantum Counting
Gilles Brassard, Peter Hoyer, Alain Tapp
We study some extensions of Grover's quantum searching algorithm. First, we generalize the Grover iteration in the light of a concept called amplitude amplification. Then, we show…
Multiparty Quantum Communication Complexity
Harry Buhrman, Wim van Dam, Peter Hoyer +1
Quantum entanglement cannot be used to achieve direct communication between remote parties, but it can reduce the communication needed for some problems. Let each of k parties hold…
Quantum Entanglement and the Communication Complexity of the Inner Product Function
Richard Cleve, Wim van Dam, Michael Nielsen +1
We consider the communication complexity of the binary inner product function in a variation of the two-party scenario where the parties have an a priori supply of particles in an…
Quantum Algorithm for the Collision Problem
Gilles Brassard, Peter Hoyer, Alain Tapp
In this note, we give a quantum algorithm that finds collisions in arbitrary r-to-one functions after only O((N/r)^(1/3)) expected evaluations of the function. Assuming the functio…
Tight bounds on quantum searching
Michel Boyer, Gilles Brassard, Peter Hoeyer +1
We provide a tight analysis of Grover's recent algorithm for quantum database searching. We give a simple closed-form formula for the probability of success after any given number…