2015 · 42 citations · 45 references
ComputingComputer SciencePhysicsInformation TheoryQuantum ComputingQuantum MechanicsCommunication ComplexityComputational ComplexityQuantum CommunicationQuantum Complexity TheoryQuantum ComputationQuantum Information TheoryCommunication Complexity Lower BoundsCommunication Complexity Upper BoundsComplexityDirect Product TheoremsDirect Sum TheoremsInformation ComplexityQuantum Communication ComplexityQuantum Complexity
We define a new notion of information cost for quantum protocols, and a corresponding notion of quantum information complexity for bipartite quantum tasks. These are the fully quantum generalizations of the analogous quantities for bipartite classical tasks that have found many applications recently, in particular for proving communication complexity lower bounds and direct sum theorems. Finding such a quantum generalization of information complexity was one of the open problems recently raised by Braverman (STOC'12).
45
A single quantum cannot be cloned
William K. Wootters, Wojciech H. Zurek · Nature · 1982 · 5.4K citations
Dennis Dieks · Physics Letters A · 1982 · 1.5K citations · Full text