Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

On Compressing Linearly Shared Correlations

Geoffroy Couteau, Alexander Koch, Nikolas Melissaris, Peter Schöll, Sacha Servan-Schreiber, Xiangtao Ye

Published Nov 5, 2026• 0 citations
Publisher
DOI
10.1007/978-3-032-43588-0_6

Related papers

Compressing Unit-Vector Correlations via Sparse Pseudorandom Generators

Amit Agarwal, Elette Boyle, Niv Gilboa +3 more

Lecture notes in computer science•Jan 1, 2024•7 citations

Quantum Entanglement-Driven Distributed Compression

Jincheng Zhang

This paper proposes a novel approach to distributed compression leveraging the unique properties of quantum entanglement. Traditional distributed compression techniques rely heavily on classical communication and shared local information, often limited by the Shannon limit. We introduce a framework where data is encoded into entangled states between multiple quantum systems. By performing measurements and implementing correction protocols on these entangled states, we can extract shared information while maintaining the entanglement correlation. This process effectively reduces data redundancy, leading to compression. The key innovation lies in utilizing the inherent non-locality of entanglement for direct data compression without the constraints of classical communication channels. We outline the theoretical foundations, explore the potential compression rates, and discuss the challenges and future directions of this entanglement-driven approach. The core claim is that this method can achieve compression rates exceeding those possible with classical methods, offering a fundamentally new paradigm for data compression. ---

•Sep 1, 2026•0 citations

Explaining Correlations by Partitions

Chrysovalantis Stergiou

Foundations of Physics•Aug 11, 2015•4 citations

Compressing Vector OLE

Elette Boyle, Geoffroy Couteau, Niv Gilboa +1 more

Oblivious linear-function evaluation (OLE) is a secure two-party protocol allowing a receiver to learn any linear combination of a pair of field elements held by a sender. OLE serves as a common building block for secure computation of arithmetic circuits, analogously to the role of oblivious transfer (OT) for boolean circuits. A useful extension of OLE is vector OLE (VOLE), allowing the receiver to learn any linear combination of two vectors held by the sender. In several applications of OLE, one can replace a large number of instances of OLE by a smaller number of instances of VOLE. This motivates the goal of amortizing the cost of generating long instances of VOLE. We suggest a new approach for fast generation of pseudo-random instances of VOLE via a deterministic local expansion of a pair of short correlated seeds and no interaction. This provides the first example of compressing a non-trivial and cryptographically useful correlation with good concrete efficiency. Our VOLE generators can be used to enhance the efficiency of a host of cryptographic applications. These include secure arithmetic computation and non-interactive zero-knowledge proofs with reusable preprocessing. Our VOLE generators are based on a novel combination of function secret sharing (FSS) for multi-point functions and linear codes in which decoding is intractable. Their security can be based on variants of the learning parity with noise (LPN) assumption over large fields that resist known attacks. We provide several constructions that offer tradeoffs between different efficiency measures and the underlying intractability assumptions.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Oct 15, 2018•222 citations

Error Bounds for Smooth Correlations

Emil V. Prodan

SpringerBriefs in mathematical physics•Jan 1, 2017•1 citation

Convex-Split and Hypothesis Testing Approach to One-Shot Quantum Measurement Compression and Randomness Extraction

Anurag Anshu, Rahul Jain, Naqueeb Ahmad Warsi

This paper concerns the problem of quantum measurement compression with side information in the one-shot setting with shared-randomness. In this problem, Alice shares a pure quantum state with Bob and the reference system. She performs a measurement on her registers and wishes to communicate the outcome to Bob using shared-randomness and classical communication. The outcome that Bob receives must be correctly correlated with the reference system and his own registers. Our goal is to concurrently minimize the classical communication and shared-randomness cost. The suggested protocol presented in this paper is based on convex-split and position based decoding. The communication is upper bounded in terms of smooth max and hypothesis testing relative entropies. A second protocol addresses the task of strong randomness extraction in the presence of quantum side information. The protocol provides an error guarantee in terms of relative entropy (as opposed to trace distance) and extracts close to the optimal number of uniform bits. As an application, we provide a new achievability result for the task of quantum measurement compression without feedback, in which Alice does not need to know the outcome of the measurement. The result achieves the optimal number of bits communicated and the required number of bits of shared-randomness, for the same task in the asymptotic and i.i.d. setting.

arXiv:1703.02342•IEEE Transactions on Information Theory•May 8, 2019•27 citations
This paper proposes a novel approach to distributed compression leveraging the unique properties of quantum entanglement. Traditional distributed compression techniques rely heavily on classical communication and shared local information, often limited by the Shannon limit. We introduce a framework where data is encoded into entangled states between multiple quantum systems. By performing measurements and implementing correction protocols on these entangled states, we can extract shared information while maintaining the entanglement correlation. This process effectively reduces data redundancy, leading to compression. The key innovation lies in utilizing the inherent non-locality of entanglement for direct data compression without the constraints of classical communication channels. We outline the theoretical foundations, explore the potential compression rates, and discuss the challenges and future directions of this entanglement-driven approach. The core claim is that this method can achieve compression rates exceeding those possible with classical methods, offering a fundamentally new paradigm for data compression. ---
Oblivious linear-function evaluation (OLE) is a secure two-party protocol allowing a receiver to learn any linear combination of a pair of field elements held by a sender. OLE serves as a common building block for secure computation of arithmetic circuits, analogously to the role of oblivious transfer (OT) for boolean circuits. A useful extension of OLE is vector OLE (VOLE), allowing the receiver to learn any linear combination of two vectors held by the sender. In several applications of OLE, one can replace a large number of instances of OLE by a smaller number of instances of VOLE. This motivates the goal of amortizing the cost of generating long instances of VOLE. We suggest a new approach for fast generation of pseudo-random instances of VOLE via a deterministic local expansion of a pair of short correlated seeds and no interaction. This provides the first example of compressing a non-trivial and cryptographically useful correlation with good concrete efficiency. Our VOLE generators can be used to enhance the efficiency of a host of cryptographic applications. These include secure arithmetic computation and non-interactive zero-knowledge proofs with reusable preprocessing. Our VOLE generators are based on a novel combination of function secret sharing (FSS) for multi-point functions and linear codes in which decoding is intractable. Their security can be based on variants of the learning parity with noise (LPN) assumption over large fields that resist known attacks. We provide several constructions that offer tradeoffs between different efficiency measures and the underlying intractability assumptions.
This paper concerns the problem of quantum measurement compression with side information in the one-shot setting with shared-randomness. In this problem, Alice shares a pure quantum state with Bob and the reference system. She performs a measurement on her registers and wishes to communicate the outcome to Bob using shared-randomness and classical communication. The outcome that Bob receives must be correctly correlated with the reference system and his own registers. Our goal is to concurrently minimize the classical communication and shared-randomness cost. The suggested protocol presented in this paper is based on convex-split and position based decoding. The communication is upper bounded in terms of smooth max and hypothesis testing relative entropies. A second protocol addresses the task of strong randomness extraction in the presence of quantum side information. The protocol provides an error guarantee in terms of relative entropy (as opposed to trace distance) and extracts close to the optimal number of uniform bits. As an application, we provide a new achievability result for the task of quantum measurement compression without feedback, in which Alice does not need to know the outcome of the measurement. The result achieves the optimal number of bits communicated and the required number of bits of shared-randomness, for the same task in the asymptotic and i.i.d. setting.