From Low-Distortion Norm Embeddings to Explicit Uncertainty Relations and Efficient Information Locking
Open accessThe DOI matches its Crossref record; 7 of the 7 references it cites were found in a registry or an index.
Abstract
The existence of quantum uncertainty relations is the essential reason that some classically unrealizable cryptographic primitives become realizable when quantum communication is allowed. One operational manifestation of these uncertainty relations is a purely quantum effect referred to as information locking [DiVincenzo et al. 2004]. A locking scheme can be viewed as a cryptographic protocol in which a uniformly random n -bit message is encoded in a quantum system using a classical key of size much smaller than n . Without the key, no measurement of this quantum state can extract more than a negligible amount of information about the message, in which case the message is said to be “locked”. Furthermore, knowing the key, it is possible to recover, that is “unlock”, the message. In this article, we make the following contributions by exploiting a connection between uncertainty relations and low-distortion embeddings of Euclidean spaces into slightly larger spaces endowed with the ℓ 1 norm. We introduce the notion of a metric uncertainty relation and connect it to low-distortion embeddings of ℓ 2 into ℓ 1 . A metric uncertainty relation also implies an entropic uncertainty relation. We prove that random bases satisfy uncertainty relations with a stronger definition and better parameters than previously known. Our proof is also considerably simpler than earlier proofs. We then apply this result to show the existence of locking schemes with key size independent of the message length. Moreover, we give efficient constructions of bases satisfying metric uncertainty relations. The bases defining these metric uncertainty relations are computable by quantum circuits of almost linear size. This leads to the first explicit construction of a strong information locking scheme. These constructions are obtained by adapting an explicit norm embedding due to Indyk [2007] and an extractor construction of Guruswami et al. [2009]. We apply our metric uncertainty relations to exhibit communication protocols that perform equality testing of n -qubit states. We prove that this task can be performed by a single message protocol using O (log 2 n ) qubits and n bits of communication, where the computation of the sender is efficient.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
�ber den anschaulichen Inhalt der quantentheoretischen Kinematik und Mechanik
Heisenberg, W. (1927) · Zeitschrift f�r Physik · doi:10.1007/bf01397280 · Cited by 4,278
Simple Proof of Security of the BB84 Quantum Key Distribution Protocol
Shor, P. W., & Preskill, J. (2000) · Physical Review Letters · doi:10.1103/physrevlett.85.441 · Cited by 3,047
Robertson, H. P. (1929) · Physical Review · doi:10.1103/physrev.34.163 · Cited by 1,877
Buhrman, H., Cleve, R., Watrous, J., & de Wolf, R. (2001) · Physical Review Letters · doi:10.1103/physrevlett.87.167902 · Cited by 1,190
Monogamy of quantum entanglement and other correlations
Koashi, M., & Winter, A. (2004) · Physical Review A · doi:10.1103/physreva.69.022309 · Cited by 609
Randomizing Quantum States: Constructions and Applications
Hayden, P., Leung, D., Shor, P. W., & Winter, A. (2004) · Communications in Mathematical Physics · doi:10.1007/s00220-004-1087-6 · Cited by 345
Self-citationThe decoupling approach to quantum information theory
Dupuis, F. (2010) · arXiv · doi:10.48550/arxiv.1004.1641 · Cited by 90
Cited by
Advances in quantum cryptography
Pirandola, S., Andersen, U. L., Banchi, L., Berta, M., Bunandar, D., Colbeck, R., Englund, D., Gehring, T., Lupo, C., Ottaviani, C., et al. (2020) · Advances in Optics and Photonics · doi:10.1364/aop.361502 · Cited by 2,033
Secure quantum key distribution with realistic devices
Xu, F., Ma, X., Zhang, Q., Lo, H.-K., & Pan, J.-W. (2020) · Reviews of Modern Physics · doi:10.1103/revmodphys.92.025002 · Cited by 1,543
(2009) · Information Theory · doi:10.1109/9780470544907.ch24 · Cited by 533
Learning the Alpha-bits of black holes
Hayden, P., & Penington, G. (2019) · Journal of High Energy Physics · doi:10.1007/jhep12(2019)007 · Cited by 125
Self-citationApproximate Quantum Error Correction Revisited: Introducing the Alpha-Bit
Hayden, P., & Penington, G. (2020) · Communications in Mathematical Physics · doi:10.1007/s00220-020-03689-1 · Cited by 40
Self-citation
Metadata
- Authors
- Fawzi, O., Hayden, P., & Sen, P.
- Venue
- Journal of the ACM
- Published
- 2013-11
- Volume
- 60
- Issue
- 6
- Pages
- 1-61
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W2568356985
- Cited by
- 42
- References
- 7
- FWCI
- 7.73
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: From Low-Distortion Norm Embeddings to Explicit Uncertainty Relations and Efficient Information Locking. https://app.cochat.ai/papers/10.1145/2518131
- The paper
- Fawzi, O., Hayden, P., & Sen, P. (2013). From Low-Distortion Norm Embeddings to Explicit Uncertainty Relations and Efficient Information Locking. Journal of the ACM. https://doi.org/10.1145/2518131
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.