NDLI: A property of quantum relative entropy with an application to privacy in quantum communication

Content Provider	ACM Digital Library
Author	Jain, Rahul Radhakrishnan, Jaikumar Sen, Pranab
Copyright Year	2009
Abstract	We prove the following information-theoretic property about quantum states. Substate theorem: Let ρ and σ be quantum states in the same Hilbert space with relative entropy $\textit{S}(ρ$ ∥ σ) ≔ Tr ρ (log ρ™ log σ) = $\textit{c}.$ Then for all ε > 0, there is a state ρ′ such that the trace distance ∥ρ′ ™ $ρ∥_{tr}$ ≔ Tr &sqrt;(ρ′ ™ $ρ)^{2}$ ≤ ε, and $ρ′/2^{O(c/ε^{2})}$ ≤ σ. It states that if the relative entropy of ρ and σ is small, then there is a state ρ′ close to ρ, i.e. with small trace distance ∥ρ′ ™ $ρ∥_{tr},$ that when scaled down by a factor $2^{O(c)}$ ‘sits inside’, or becomes a ‘substate’ of, σ. This result has several applications in quantum communication complexity and cryptography. Using the substate theorem, we derive a privacy trade-off for the set membership problem in the two-party quantum communication model. Here Alice is given a subset $\textit{A}$ &subse; $[\textit{n}],$ Bob an input $\textit{i}$ ∈ $[\textit{n}],$ and they need to determine if $\textit{i}$ ∈ $\textit{A}.$ Privacy trade-off for set membership: In any two-party quantum communication protocol for the set membership problem, if Bob reveals only $\textit{k}$ bits of information about his input, then Alice must reveal at least $n/2^{O(k)}$ bits of information about her input. We also discuss relationships between various information theoretic quantities that arise naturally in the context of the substate theorem.
Starting Page	1
Ending Page	32
Page Count	32
File Format	PDF
ISSN	00045411
e-ISSN	1557735X
DOI	10.1145/1568318.1568323
Journal	Journal of the ACM (JACM)
Volume Number	56
Issue Number	6
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2009-09-08
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Privacy Quantum communication complexity Quantum information theory
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Information Systems Control and Systems Engineering Artificial Intelligence Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees

New Strong Direct Product Results in Communication Complexity

A learning theory approach to noninteractive database privacy

An Overview of the Theory of Computational Complexity

Limits on the ability of quantum states to convey classical messages

Dense quantum coding and quantum finite automata

An Automatic Sequencing Procedure with Application to Parallel Programming

Communication Lower Bounds Using Directional Derivatives

An Observation on Relative Parsing Time

A property of quantum relative entropy with an application to privacy in quantum communication

Similar Documents

The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees

New Strong Direct Product Results in Communication Complexity

A learning theory approach to noninteractive database privacy

An Overview of the Theory of Computational Complexity

Limits on the ability of quantum states to convey classical messages

Dense quantum coding and quantum finite automata

An Automatic Sequencing Procedure with Application to Parallel Programming

Communication Lower Bounds Using Directional Derivatives

An Observation on Relative Parsing Time

A property of quantum relative entropy with an application to privacy in quantum communication