Optimality of approximate randomization of quantum states: key rates for private quantum channels, the 1:2 quantum data-hiding ratio, and the entropy statistics of random bases

A perfectly secure private quantum channel (quantum one-time pad) on a d-dimensional system requires 2 log d shared secret key bits. Hayden, Leung, Shor and Winter (2004) showed that for near-perfect (epsilon-) security roughly d log d unitaries suffice, i.e. a key of log d + o(log d) bits, and used the same concentration phenomenon to hide roughly l qubits in 2l physical qubits by LOCC data hiding and to lock classical correlations. The paper left open whether these resource scalings are information-theoretically optimal. The open core that survives later work is: (i) whether the ~log d bit key rate for approximate encryption is optimal once arbitrary completely positive trace-preserving (CPTP) encryption maps with unbounded output dimension are allowed (the rank-based lower bound covers only bounded output dimension, and no better lower bound is known even for unitary maps in the epsilon-dependence); (ii) whether the 1:2 ratio of hidden to physical qubits in bipartite LOCC data hiding is optimal, or can be improved; and (iii) finer questions of sharpening constants and characterizing the full distribution of the entropic uncertainty functional min_phi sum_j H(p_j) for collections of random measurement bases. Efficient (polynomial-time) constructions were subsequently supplied by Ambainis and Smith and successors, and constants were improved by Aubrun, so the surviving problem is the optimality (lower-bound) side of the program.

Background

A private quantum channel, also called a quantum one-time pad, is a symmetric-key encryption scheme for quantum states: a sender applies one of several completely positive trace-preserving (CPTP) maps - typically unitaries - selected by a shared classical key, so that an eavesdropper who sees the average output learns (almost) nothing, while the receiver, knowing the key, can invert the map. A channel is called epsilon-randomizing (Hayden-Leung-Shor-Winter) if for every input state the averaged output is within epsilon, in trace norm (the Schatten 1-norm, i.e. the sum of the singular values of the difference), of the maximally mixed state I/d_out of the channel's output (ciphertext) space, where d_out is its dimension; other Schatten p-norms, obtained by replacing the sum of singular values by the p-th root of the sum of their p-th powers, are sometimes used instead, and the source states the corresponding condition in the operator norm as the requirement that every eigenvalue of the averaged output lie in the interval [(1-epsilon)/d_out, (1+epsilon)/d_out]. When the output space is allowed to be unbounded (the regime of question (1) below), d_out may differ from the dimension d of the input system, and the reference state is then the maximally mixed state I/d_out of the output space rather than I/d; trace norm is the convention adopted for question (1). A map that sends every input state to I/d_out itself meets this bound but is not an admissible encryption map, as it is excluded by the correctness/decoding requirement. Perfect (epsilon = 0) randomization of a d-dimensional system is known to require d^2 unitaries, i.e. 2 log d key bits, a bound proved by a rank argument together with entropy counting (Ambainis-Mosca-de Wolf; Boykin-Roychowdhury). Hayden, Leung, Shor and Winter (2004) showed by a concentration-of-measure argument - the phenomenon that any sufficiently smooth function of a Haar-random unitary (one drawn from the uniform invariant measure on the unitary group) is, with high probability, close to its median - that roughly d log d Haar-random unitaries form an epsilon-randomizing family with high probability, giving an approximate private quantum channel with a key of $\log d + o(\log d)$ bits - asymptotically half the perfect-encryption requirement - and they proved optimality of this 1:1 ratio of key bits to encrypted qubits by a rank argument, but only under the restriction to unitary encryption maps (with bounded output dimension; polynomial output blowup was noted to be tractable by combining earlier hiding arguments with Fannes-type continuity inequalities, which bound the change of entropy under small perturbations of a state). They applied the same randomizing maps to quantum data hiding - schemes that encode bits or qubits into bipartite states that are almost indistinguishable under measurements restricted to local operations and classical communication (LOCC), i.e. instruments in which each party acts only on their own subsystem and the parties may exchange classical messages, yet are decodable by unrestricted joint measurements - hiding roughly $l$ qubits in $2l$ physical qubits (a 1:2 hidden-to-physical ratio, far better than earlier constructions based on Werner states, i.e. bipartite states invariant under $U \otimes U$ rotations, which needed on the order of tens of qubits per hidden bit at comparable security); to information locking - bipartite states whose accessible information (the mutual information with a reference system, optimized over measurements) is much smaller than their classical correlation, yet jumps to nearly maximal after transmission of a negligibly short classical key; and to remote state preparation - conveying to an entangled receiver a pure state known to the sender, using fewer classical bits than teleportation would need. The locking analysis rests on a random-matrix calculation showing that for $n$ random orthonormal measurement bases and a random state $\varphi$, the sum of Shannon entropies $\sum_{j=1}^n H(p_j)$ of the measurement outcome distributions $p_j$ concentrates near $n\log d$ - an entropic uncertainty relation for typical collections of observables, analogous to the Maassen-Uffink relation for a pair of conjugate measurements - but the tail estimates were crude. In their discussion the authors posed the optimality questions above, plus the demand for computationally efficient (polynomial-time, explicit rather than existential) constructions with the same asymptotic scalings; their Appendix A showed that products of Pauli operators (the n-qubit generalization of the single-qubit matrices I, X, Y, Z, which form an orthogonal operator basis) can replace Haar-random unitaries, but the number of required selections was exponential in the number of encrypted qubits. Subsequent work - Ambainis-Smith derandomization via small-bias sets (families of sign-vectors whose pairwise correlations are bounded by a small parameter, so-called epsilon-biased sets), Dickinson-Nayak Pauli constructions, Aubrun's random-Kraus-operator analysis, Nagaj-Kerenidis single-qubit optimality, Lai-Chung quantum Shannon impossibility results - has mapped which parts of this program are settled and which remain open.

Problem Statement

Determine the information-theoretically optimal resource rates of the approximate-randomization program initiated by Hayden, Leung, Shor and Winter, and the fine probabilistic structure of the underlying random-unitary entropy statistics. Concretely, in the setting of epsilon-randomizing maps (CPTP maps whose key-averaged output is within epsilon of the maximally mixed state for every input, together with a correctness/decoding requirement), the problem consists of the following linked questions posed in the source paper's discussion: (1) Is the asymptotic key rate $\log d + o(\log d)$ shared secret bits for an approximate private quantum channel on a $d$-dimensional system optimal among arbitrary CPTP encryption maps, in particular when the output dimension is allowed to be unbounded (the rank argument covers only bounded output dimension)? A matching lower bound - or a construction with an asymptotically smaller key - is sought; in particular, closing the gap between the rank-based lower bound and the upper bound $n + 2\log(1/\epsilon) + O(1)$ for $n$ qubits, including the dependence on the security parameter $\epsilon$, would resolve the optimality conjecture of Dickinson and Nayak. (2) Is the ratio of roughly 1 hidden qubit per 2 physical qubits in bipartite quantum data hiding against LOCC measurements optimal - i.e. can no encoding-and-decoding scheme with LOCC security hide asymptotically more than $l$ qubits in $(2+o(1))l$ physical qubits - or can the factor of two be reduced, as it can when superselection rules (dynamical restrictions forbidding coherent superpositions of states in different sectors, such as different total charge) are imposed? (3) Sharpen the constants and finite-size estimates of the randomization, data-hiding and locking constructions (several of which remain a polylogarithmic factor off). (4) Provide computationally efficient, explicit (polynomial-time) constructions realizing the same asymptotic guarantees - largely achieved by later derandomization work, with the fine questions of polylogarithmic factors and norm-specific security remaining. (5) Characterize, beyond tail bounds, the distribution of the entropic uncertainty functional $\min_\varphi \sum_{j=1}^n H(p_j)$ for collections of random orthonormal bases (equivalently, the constraints entropic uncertainty relations impose on typical collections of observables), which controls the locking behavior of classical correlations. These five questions are independent: none of them presupposes any other, and each of the three named in the title - the key rate (1), the 1:2 data-hiding ratio (2) and the entropy statistics (5) - can be settled without the others. Of the other two, (3) is a fine refinement of the constants entering (1), (2) and (5), and (4), the demand for computationally efficient constructions, has been largely achieved by subsequent derandomization work, so that only its residual polylogarithmic-factor and norm-specific points remain open. The common objective is to establish, by lower-bound/impossibility results or improved constructions, the true asymptotic costs - key bits per encrypted qubit, physical qubits per hidden qubit, and entropy constants - of approximate-randomization-based quantum cryptography.

References

1. P. Hayden, D. Leung, P. W. Shor, A. Winter, "Randomizing quantum states: Constructions and applications", Commun. Math. Phys. 250(2), 371-391 (2004). DOI: 10.1007/s00220-004-1087-6, arXiv: quant-ph/0307104, https://arxiv.org/abs/quant-ph/0307104
2. A. Ambainis, A. Smith, "Small Pseudo-Random Families of Matrices: Derandomizing Approximate Quantum Encryption", in Approximation, Randomization, and Combinatorial Optimization (RANDOM 2004), Lecture Notes in Computer Science, 249-260 (2004). DOI: 10.1007/978-3-540-27821-4_23, arXiv: quant-ph/0404075, https://arxiv.org/abs/quant-ph/0404075
3. P. A. Dickinson, A. Nayak, "Approximate Randomization of Quantum States With Fewer Bits of Key", AIP Conference Proceedings 864, 18-36 (2006). DOI: 10.1063/1.2400876, arXiv: quant-ph/0611033, https://arxiv.org/abs/quant-ph/0611033
4. D. Nagaj, I. Kerenidis, "On the optimality of quantum encryption schemes", Journal of Mathematical Physics 47(9), 092102 (2006). DOI: 10.1063/1.2339014, arXiv: quant-ph/0509169, https://arxiv.org/abs/quant-ph/0509169
5. G. Aubrun, "A remark on the paper 'Randomizing quantum states: Constructions and applications'" (2008). arXiv: 0802.4193, https://arxiv.org/abs/0802.4193
6. G. Aubrun, "On Almost Randomizing Channels with a Short Kraus Decomposition", Commun. Math. Phys. 288, 1103-1116 (2009). DOI: 10.1007/s00220-008-0695-y, arXiv: 0805.2900, https://arxiv.org/abs/0805.2900
7. S. P. Desrosiers, F. Dupuis, "Quantum Entropic Security and Approximate Quantum Encryption", IEEE Transactions on Information Theory 56(7), 3455-3464 (2010). DOI: 10.1109/TIT.2010.2048488, https://doi.org/10.1109/TIT.2010.2048488
8. C.-Y. Lai, K.-M. Chung, "Quantum encryption and generalized Shannon impossibility", Designs, Codes and Cryptography 87, 1961-1972 (2019). DOI: 10.1007/s10623-018-00597-3, arXiv: 1801.03656, https://arxiv.org/abs/1801.03656
9. R. Adamczak, R. Latala, Z. Puchala, K. Zyczkowski, "Asymptotic entropic uncertainty relations", Journal of Mathematical Physics 57(3), 032204 (2016). DOI: 10.1063/1.4944425, arXiv: 1412.7065, https://arxiv.org/abs/1412.7065
10. R. Adamczak, "Metric and classical fidelity uncertainty relations for random unitary matrices", Journal of Physics A: Mathematical and Theoretical 50, 105302 (2017). DOI: 10.1088/1751-8121/aa5662, arXiv: 1608.06658, https://arxiv.org/abs/1608.06658
11. L. Lami, C. Palazuelos, A. Winter, "Ultimate Data Hiding in Quantum Mechanics and Beyond", Commun. Math. Phys. 361, 661-708 (2018). DOI: 10.1007/s00220-018-3154-4, arXiv: 1703.03392, https://arxiv.org/abs/1703.03392
12. C. Lupo, M. M. Wilde, S. Lloyd, "Quantum Data Hiding in the Presence of Noise", IEEE Transactions on Information Theory 62(6), 3745-3756 (2016). DOI: 10.1109/TIT.2016.2552547, arXiv: 1507.06038, https://arxiv.org/abs/1507.06038
13. F. Verstraete, J. I. Cirac, "Quantum Nonlocality in the Presence of Superselection Rules and Data Hiding Protocols", Phys. Rev. Lett. 91, 010404 (2003). DOI: 10.1103/PhysRevLett.91.010404, https://doi.org/10.1103/PhysRevLett.91.010404
14. F. A. Mele, L. Lami, "Optimising quantum data hiding" (2025). arXiv: 2510.03538, https://arxiv.org/abs/2510.03538
15. O. Akresh, J. Beckey, F. Leditzky, "Tight Universal Bounds on Quantum Data Hiding with Multipartite Werner States" (2026). arXiv: 2609.40332, https://arxiv.org/abs/2609.40332