Quantum information complexity
From MaRDI portal
Abstract: We define a new notion of information cost for quantum protocols, and a corresponding notion of quantum information complexity for bipartite quantum channels, and then investigate the properties of such quantities. These are the fully quantum generalizations of the analogous quantities for bipartite classical functions that have found many applications recently, in particular for proving communication complexity lower bounds. Our definition is strongly tied to the quantum state redistribution task. Previous attempts have been made to define such a quantity for quantum protocols, with particular applications in mind; our notion differs from these in many respects. First, it directly provides a lower bound on the quantum communication cost, independent of the number of rounds of the underlying protocol. Secondly, we provide an operational interpretation for quantum information complexity: we show that it is exactly equal to the amortized quantum communication complexity of a bipartite channel on a given state. This generalizes a result of Braverman and Rao to quantum protocols, and even strengthens the classical result in a bounded round scenario. Also, this provides an analogue of the Schumacher source compression theorem for interactive quantum protocols, and answers a question raised by Braverman. We also discuss some potential applications to quantum communication complexity lower bounds by specializing our definition for classical functions and inputs. Building on work of Jain, Radhakrishnan and Sen, we provide new evidence suggesting that the bounded round quantum communication complexity of the disjointness function is Omega (n/M + M), for M-message protocols. This would match the best known upper bound.
Recommendations
Cites work
- Approximate distance oracles
- Approximate distance oracles with constant query time
- Automata, Languages and Programming
- Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- Fast C-K-R partitions of sparse graphs
- Near-Linear Time Construction of Sparse Neighborhood Covers
- On approximate distance labels and routing schemes with affine stretch
- On sparse spanners of weighted graphs
- Ramsey partitions and proximity data structures
- Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
- Shortest-path queries in static networks
Cited in
(18)- Attacking quantum hashing. Protocols and their cryptanalysis
- Trading information complexity for error. II: The case of a large error and the external information complexity
- Quantum Hamiltonian Complexity
- Interactive Information Complexity
- Near-optimal bounds on the bounded-round quantum communication complexity of disjointness
- Interactive information complexity
- Quantum hardness of learning shallow classical circuits
- Nonlocal Games with Noisy Maximally Entangled States are Decidable
- Augmented index and quantum streaming algorithms for \textsc{Dyck}(2)
- Noisy interactive quantum communication
- Quantum Kolmogorov complexity
- Bounds on oblivious multiparty quantum communication complexity
- Communication and information complexity
- A hierarchy of constant communication complexity
- Quantum distributed complexity of set disjointness on a line
- Decidability of fully quantum nonlocal games with noisy maximally entangled states
- The complexity of learning (pseudo)random dynamics of black holes and other chaotic systems
- Quantum information and the PCP theorem
This page was built for publication: Quantum information complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2941521)
