14 citations · 21 across the 10 of their papers we have counts for
4 papers · 2 filters
Simultaneous Communication Protocols with Quantum and Classical Messages
Dmitry Gavinsky, Oded Regev, Ronald de Wolf
We study the simultaneous message passing (SMP) model of communication complexity, for the case where one party is quantum and the other is classical. We show that in an SMP protoc…
Locally Decodable Quantum Codes
Jop Briët, Ronald de Wolf
We study a quantum analogue of locally decodable error-correcting codes. A q-query locally decodable quantum code encodes n classical bits in an m-qubit state, in such a way that e…
A note on quantum algorithms and the minimal degree of epsilon-error polynomials for symmetric functions
Ronald de Wolf
The degrees of polynomials representing or approximating Boolean functions are a prominent tool in various branches of complexity theory. Sherstov recently characterized the minima…
Upper Bounds on the Noise Threshold for Fault-tolerant Quantum Computing
Julia Kempe, Oded Regev, Falk Unger +1
We prove new upper bounds on the tolerable level of noise in a quantum circuit. We consider circuits consisting of unitary k-qubit gates each of whose input wires is subject to dep…