Weak approximate unitary designs and applications to quantum encryption

Abstract

Unitary $t$-designs are the bread and butter of quantum information theory and beyond. An important issue in practice is that of efficiently constructing good approximations of such unitary $t$-designs. Building on results by Aubrun (Comm. Math. Phys. 2009), we prove that sampling $d^t\mathrm{poly}(t,\log d,1/\epsilon )$ unitaries from an exact $t$-design provides with positive probability an $\epsilon$-approximate $t$-design, if the error is measured in one-to-one norm distance of the corresponding $t$-twirling channels. As an application, we give a partially derandomized construction of a quantum encryption scheme that has roughly the same key size and security as the quantum one-time pad, but possesses the additional property of being non-malleable against adversaries without quantum side information.

arXiv comment20 pages. Published version

References in corpus (16)

• Exact and Approximate Unitary 2-Designs: Constructions and Applications
• Randomizing quantum states: Constructions and applications
• Local random quantum circuits are approximate polynomial-designs
• Authentication of Quantum Messages
• The mother of all protocols: Restructuring quantum information's family tree
• The Quantum Reverse Shannon Theorem based on One-Shot Information Theory
• Multiqubit Clifford groups are unitary 3-designs
• A decoupling approach to the quantum capacity
• One-shot decoupling
• Pseudorandom States, Non-Cloning Theorems and Quantum Money
• Decoupling with unitary approximate two-designs
• Catalytic Decoupling of Quantum Information
• On almost randomizing channels with a short Kraus decomposition
• Non-malleable encryption of quantum information
• Noise Thresholds for the [[4, 2, 2]]-concatenated Toric Code
• Quantum non-malleability and authentication

Cited by in corpus (8)

• Deep thermalization under charge-conserving quantum dynamics
• Emergent unitary designs for encoded qubits from coherent errors and syndrome measurements
• Implementation of single-qubit measurement-based t-designs using IBM processors
• Uncloneable Encryption from Decoupling
• Concentration of quantum channels with random Kraus operators via matrix Bernstein inequality
• Optimal quantum (tensor product) expanders from unitary designs
• Investigating the effect of noise channels on the quality of unitary t-designs
• Quantum Private Broadcasting