Weak approximate unitary designs and applications
to quantum encryption
Cécilia Lancien
1
and Christian Majenz
2
1
Institut de Mathématiques de Toulouse & CNRS, Université Paul Sabatier, 118 route de Narbonne, F-31062
Toulouse Cedex 9, France.
2
QuSoft and Centrum Wiskunde & Informatica, Science Park 123, 1098 XG Amsterdam, the Netherlands.
August 25 2020
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
poly(t, log d, 1/) uni-
taries from an exact t-design provides with positive probability an -approximate
t-design, if the error is measured in one-to-one norm. As an application, we give
a randomized 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 quan-
tum side information.
1 Introduction
Random unitaries, drawn from the Haar measure on the unitary group, play an important
role in many aspects of theoretical quantum information science. For instance, most results
on quantum source and channel coding are obtained with Haar-random coding strate-
gies [ADHW09; HHWY08; BCR11] using the decoupling technique [HOW07; SDTR13;
DBWR14; MBDRC17]. The columns and rows of Haar random unitaries are Haar ran-
dom unit vectors and have also found many applications in quantum information theory,
e.g. for constructing quantum money schemes [JLS18; AMR19]. However Haar random
unitaries are infeasible to even approximate, the randomness and number of gates neces-
sary to sample and implement them being exponential in the number of qubits they act
on.
In most situations, unitary t-designs, the quantum analogues of t-wise independent
functions, come to the rescue [DCEL09]. A unitary t-design is a measure on the unitary
group that reproduces the Haar measure up to the t-th moment. This means that a random
unitary sampled from a t-design can replace a Haar-random unitary in any situation where
it is only applied t times. For practical purposes, one would like this measure to be
more economical than the Haar measure (for instance to have finite, as small as possible,
support). Often even just approximate versions of unitary t-designs (in the right metrics)
are sufficient. In quantum information theory and related fields the most common metric
between measures on the unitary group is the completely bounded one-to-one norm, or
Cécilia Lancien: clancien@math.univ-toulouse.fr
Christian Majenz: christian.majenz@cwi.nl
Accepted in Quantum 2020-08-24, click title to verify. Published under CC-BY 4.0. 1
arXiv:1911.06742v2 [quant-ph] 25 Aug 2020
diamond norm, on the induced t-twirling channels. The t-twirling channel associated to a
measure is the channel that can be implemented by sampling a unitary according to the
measure, and then applying it to each sub-system of a t-partite input system.
In [HLSW04], approximate 1-designs have been studied using a metric based on the
(not completely bounded) one-to-one norm. There, it is shown that approximate 1-designs
in this weaker sense can be made of much less unitaries, and that they still have interesting
applications, such as unconditionally secure encryption of quantum data when confiden-
tiality is only desired against adversaries without quantum side information. The former
result is shown by proving that sampling a small number of independent Haar-random
unitaries provides with high probability an approximate 1-design. This construction was
subsequently partially derandomized in [Aub09], where it was shown that sampling from
a measure which is only a 1-design works as well.
Let us mention one last result which was known prior to this work. It was shown in
[LW17] that, in fact, any channel can be approximated in one-to-one norm by a channel
having few Kraus operators. However, this does not tell us whether it can be further
imposed that the Kraus operators of this approximating channel are of a specific form
(such as e.g. being unitaries sampled from a simple enough distribution, which is what we
are interested in here).
Our contribution
In this work, we generalize the approach of [Aub09] to construct small approximate t-
designs, for any given t, in one-to-one norm distance. In addition, for t = 2, we show that
the approach extends to designs where the goal is to approximate the channel twirl, i.e. the
transformation of quantum channels obtained by sampling a unitary, applying it to the
input state before the channel acts on it, and undoing this action afterwards. Here, the
appropriate distance is the one stemming from the operator norm induced by the diamond
norm, which we call diamond-to-diamond norm. To prove the approximation result on the
so-called U
⊗t
-twirl, we use basic representation theory of the unitary group, including the
Weyl dimension formula, to show that it has small one-to-operator norm. This allows us
to apply the powerful probabilistic and functional analytic tools developed in [Aub09]. For
the channel twirl, the invariant space spanned by the identity, as well as the off-diagonal
terms involving this invariant space, require a careful analysis. Along the way, we also
construct a design that approximates the so-called U ⊗
¯
U-twirl, the image of the channel
twirl under the Choi-Jamiołkowski isomorphism.
What is more, we prove that our results are optimal, in the following sense: approxi-
mating the twirling channels under consideration cannot be done with less operators than
what our sub-sampling approach gives, even without imposing any structure on them (in
our case the constraint of being a tensor product of unitaries).
An application
Subsequently, we apply our results in a cryptographic context. We show, that an ap-
proximate channel-twirl design in the diamond-to-diamond norm metric can be used to
construct a quantum encryption scheme that is as secure as the quantum one-time pad
and has (essentially) the same key length, but also is non-malleable against adversaries
without quantum side information. While the construction is not time-efficient, it pro-
vides theoretical insights, and constitutes evidence that savings in key size are possible.
In particular, the construction quantifies in a precise way the amount of secret key that a
Accepted in Quantum 2020-08-24, click title to verify. Published under CC-BY 4.0. 2
full two-design-based non-malleable quantum encryption scheme uses just to counter side
information attacks.
Beyond applications to cryptography, the Kraus rank of a quantum channel can be
considered, more generally, as a measure of its complexity. It indeed quantifies the mini-
mal amount of ancillary resources needed to implement it. Equivalently, it quantifies the
amount of degrees of freedom in it that one is ignorant of. It is thus natural to ask: given
a quantum channel, is it possible to reduce its complexity while not affecting its action too
much? Or, in other words, is it possible to find a channel with much smaller Kraus rank
which approximately simulates it? In our case, we further impose that the Kraus operators
of the approximating channel, in addition to being few, inherit the structure of those of
the original channel. Our results can therefore be seen as statements about complexity
reduction of twirling channels, under extra constraints. As explained in [LW17], results of
this type provide, amongst other, efficient schemes for the destruction of correlations and
data hiding in bipartite states.
Related work
Unitary t-designs exist for all t and all dimensions [SZ84; Kan15]
1
. For t > 3, time-efficient
constructions are, however, only known for approximate unitary t-designs [BHH16]. An
appealing approach to try and exhibit unitary t-designs would be to look for them amongst
unitary groups, equipped with their uniform measure. For t 6 3 the Clifford group is
known to be such a unitary t-group [Web16; Zhu17]. Nevertheless, it was recently proved
in [BNRT20] that there is no unitary t-group for t > 4 (except in dimension 2), so that
this strategy cannot work anymore. The sub-sampling technique that we use, following
[Aub09], i.e. the strategy of sampling a random subset of unitaries from an exact design,
was first introduced in [ABW09] to show the existence of small approximate 2-designs.
Non-malleability for quantum encryption was first introduced and characterized in
[ABW09]. In this work it was also shown that the notion of quantum non-malleability is
equivalent to the notion of approximate unitary 2-designs, under the condition that the
encryption algorithm be unitary. Subsequently, non-malleability for quantum encryption
has been further studied in [AM17; MSW19].
Notation and standard definitions
Let us gather here notation that we will be using throughout the whole paper. Given
d ∈ N, we denote by L(d) the set of linear operators on C
d
, by D(d) the set of quantum
states (i.e. positive semidefinite and trace 1 operators) on C
d
, and by U(d) the set of
unitary operators on C
d
. We additionally denote by L(d) the set of linear operators
on L(d), and by C(d) the set of quantum channels (i.e. completely positive and trace-
preserving operators) on L(d). Let us conclude with a some standard notation/definitions
from probability theory. Given a random variable X, we denote by E X its average and by
P(X ∈ E) the probability that X satisfies event E. We say that ε is a Bernoulli random
variable if P(ε = +1) = P(ε = −1) = 1/2.
1
In [Kan15], the existence of exact designs is proven in a much more general context, see [AMR19,
Corollary 2] for a straightforward application to the unitary case.
Accepted in Quantum 2020-08-24, click title to verify. Published under CC-BY 4.0. 3
2 Representation theoretic preliminaries
A good introduction to the representation-theoretic concepts used in this work can be found
in [FH13] (see also [Chr06] for a short introduction that is very accessible for quantum
information theorists). Given t ∈ N let S
t
be the permutation group of {1, . . . , t}. The
irreducible representations [λ] of S
t
are called Specht modules and are indexed by integer
partitions of t, denoted as λ ` t. Such a partition is represented as a tuple λ = (λ
1
, ..., λ
r
) ∈
N
r
, for some r ∈ N, with λ
1
> ··· > λ
r
and
P
r
i=1
λ
i
= t.
Given d ∈ N let U (d) be the unitary group of C
d
. The polynomial irreducible repre-
sentations V
λ
of U(d) are called Weyl modules and are indexed by integer partitions of any
number t ∈ N into exactly d parts (some of which might be 0), denoted as λ ` (t, d). The
dimension of the Weyl module V
λ
is given by the Weyl dimension formula
m
λ
=
Y
i,j∈{1,...,d}
i<j
λ
i
− λ
j
+ j − i
j − i
. (1)
A particular vector space that carries representations of both S
t
and U (d) is (C
d
)
⊗t
,
the corresponding actions are defined as
∀ σ ∈ S
t
, σ.|φ
1
i ⊗ ··· ⊗ |φ
t
i = |φ
σ
−1
(1)
i ⊗ ··· ⊗ |φ
σ
−1
(t)
i,
∀ U ∈ U(d), U.|φi = U
⊗t
|φi.
The two actions commute, i.e. (C
d
)
⊗t
decomposes into a direct sum of irreducible represen-
tations (irreps) of the product group S
t
×U (d). These irreps are just tensor products of an
irrep of S
t
with an irrep of U(d). What is more, the corresponding representations of the
group algebras of S
t
and U (d) are double commutants, implying that the decomposition
is multiplicity free.
Theorem 2.1 (Schur-Weyl duality). Let S
t
and U (d) act on (C
d
)
⊗t
as described above.
The direct sum decomposition into irreducible representations of S
t
× U(d) is multiplicity
free, and is given by
(C
d
)
⊗t
∼
=
M
λ`(t,d)
V
λ
⊗ [λ]. (2)
Define the quantum channel T
(t)
on (C
d
)
⊗t
as
T
(t)
: X ∈ L(d
t
) 7→
Z
U∈U(d)
U
⊗t
XU
∗⊗t
dU ∈ L(d
t
), (3)
where dU stands for the Haar measure on U(d). The channel T
(t)
is often referred to as
a twirling channel. It is obviously covariant with respect to the action of U(d). Hence,
denoting by W the isomorphism between the right and left hand sides of the equation (2)
above, Schur’s Lemma implies that
W T
(t)
(W
∗
(·)W )W
∗
=
X
λ`(t,d)
τ
V
λ
⊗ Tr
V
λ
[P
λ
(·)P
λ
] , (4)
where P
λ
is the projector onto V
λ
⊗ [λ] in
L
λ`(t,d)
V
λ
⊗ [λ] and τ
V
λ
= 1
V
λ
/m
λ
is the
maximally mixed state on V
λ
.
Let us make things slightly more explicit in the case t = 2. We have
(C
d
)
⊗2
∼
=
∧
2
(d) ⊕ ∨
2
(d),
Accepted in Quantum 2020-08-24, click title to verify. Published under CC-BY 4.0. 4
where ∧
2
(d) and ∨
2
(d) are, respectively, the symmetric and anti-symmetric subspaces of
(C
d
)
⊗2
. The corresponding projectors are P
∧
2
(d)
= (1 + F )/2 and P
∨
2
(d)
= (1 − F )/2,
where F denotes the so-called flip operator. And the action of T
(2)
can be explicitly written
as, for all X ∈ L(d
2
),
T
(2)
(X) =
2
d(d + 1)
Tr
P
∧
2
(d)
XP
∧
2
(d)
P
∧
2
(d)
+
2
d(d − 1)
Tr
P
∨
2
(d)
XP
∨
2
(d)
P
∨
2
(d)
.
Fix a basis B = {|ii}
d−1
i=0
for C
d
and let T be the transposition in this basis. It is easy
to check that, denoting by X
Γ
the partial transposition of X (i.e. X
Γ
= id ⊗ T(X)), we
have, for all X ∈ L(d
2
),
T
(2)
(X)
Γ
=
Z
U∈U(d)
U ⊗ UXU
∗
⊗ U
∗
dU
!
Γ
=
Z
U∈U(d)
U ⊗
¯
UX
Γ
U
∗
⊗
¯
U
∗
dU.
Let us define the quantum channel T
(1,1)
on (C
d
)
⊗2
as
T
(1,1)
: X ∈ L(d
2
) 7→
Z
U∈U(d)
U ⊗
¯
UXU
∗
⊗
¯
U
∗
dU. (5)
By the preceding discussion, we know that T
(1,1)
(X) can be written as a linear combination
of P
Γ
∧
2
(d)
and P
Γ
∨
2
(d)
. Now, 1
Γ
= 1 and F
Γ
= d|ψihψ|, where
|ψi =
1
√
d
d−1
X
i=0
|ii
is the standard maximally entangled state with respect to B. So equivalently, T
(1,1)
(X)
can be written as a linear combination of |ψihψ| and Q = 1 −|ψihψ|, which are orthogonal
to one another. More specifically, for all X ∈ L(d
2
),
T
(1,1)
(X) = hψ|X|ψi|ψihψ| +
1
d
2
− 1
Tr(QX)Q. (6)
3 Several channel approximation results
Before we present our various twirling channel approximation results, let us state here
the key technical lemma which is the starting point of most of our proofs. This lemma
first appeared as [Aub09, Lemma 5]. Its proof consists in estimating the average of the
supremum of an empirical process through covering numbers, thanks to Dudley’s inequality
and a duality argument for entropy numbers.
Lemma 3.1 ([Aub09, Lemma 5]). Let U
1
, . . . , U
n
∈ U (d) and let ε
1
, . . . , ε
n
be independent
Bernoulli random variables. Then,
E
sup
ρ∈D(d)
n
X
i=1
ε
i
U
i
ρU
i
∞
!
6 C(log d)
5/2
(log n)
1/2
sup
ρ∈D(d)
n
X
i=1
U
i
ρU
i
1/2
∞
,
where C > 0 is a universal constant.
Accepted in Quantum 2020-08-24, click title to verify. Published under CC-BY 4.0. 5
3.1 Approximating the twirling channel T
(t)
Let t ∈ N be such that t < d. The goal here is to show that the twirling channel T
(t)
,
as defined by equation (3), can be approximated with ‘few’ Kraus operators sampled from
a ‘simple’ probability measure. We will be able to prove such approximation in a strong
sense, namely in one-to-infinity norm.
A probability measure µ on U(d) is called a t-design if
∀ X ∈ L(d
t
),
Z
U∈U(d)
U
⊗t
XU
∗⊗t
dµ(U) = T
(t)
(X).
We will show the following result:
Theorem 3.2. Let 0 < < 1. Assume that the probability measure µ on U(d) is a
t-design, and let U
1
, . . . , U
n
be sampled independently from µ. There exists a universal
constant C > 0 such that, if n > C(td)
t
(t log d)
6
/
2
, then with probability at least 1/2, we
have
∀ ρ ∈ D(d
t
),
1
n
n
X
i=1
U
⊗t
i
ρU
∗⊗t
i
− T
(t)
(ρ)
∞
6
d
t
.
Theorem 3.2 generalizes [Aub09, Theorem 2] to t-designs for any t ∈ N rather than
only for 1-designs. We actually follow the exact same proof strategy as that of [Aub09,
Theorem 2]. The only additional technical lemma that we need in the case t > 1 is one
that tells us that T
(t)
has a small (1 → ∞)-norm (a fact which is obvious for t = 1).
Lemma 3.3. The quantum channel T
(t)
is such that
sup
ρ∈D(d
t
)
T
(t)
(ρ)
∞
6
2t
d
t
.
Proof. By equation (4), the operator norm in question is just given by the inverse of the
minimal dimension of an irrep V
λ
,
sup
ρ∈D(d
t
)
T
(t)
(ρ)
∞
=
1
min
λ`(t,d)
m
λ
.
Indeed, let us denote by λ
∗
the partition minimizing m
λ
. It is clear that if |φ
λ
∗
i ∈ V
λ
∗
and |ϕ
λ
∗
i ∈ [λ
∗
], then
T
(t)
(|φ
λ
∗
ihφ
λ
∗
| ⊗ |ϕ
λ
∗
ihϕ
λ
∗
|)
∞
= 1/m
λ
∗
. And this is obviously
maximizing
T
(t)
(ρ)
∞
as T
(t)
begins with a pinching with respect to the direct sum
decomposition (2). We go on to find a lower bound on m
λ
∗
using the formula (1). To this
end we first note that λ
∗
is a partition of t into d parts, so λ
∗
i
= 0 for all i > t. Noting that
all the factors in the product in equation (1) are lower bounded by 1, and only keeping
factors such that i ≤ t < j we get
m
λ
∗
≥
Y
i,j∈{1,...,d}
i≤t<j
λ
∗
i
+ j − i
j − i
=
t
Y
i=1
d
Y
j=t+1
λ
∗
i
+ j − i
j − i
=
t
Y
i=1
(λ
∗
i
+ d − i)!(t − i)!
(λ
∗
i
+ t − i)!(d − i)!
=
t
Y
i=1
λ
∗
i
Y
α=1
d − i + α
t − i + α
.
Accepted in Quantum 2020-08-24, click title to verify. Published under CC-BY 4.0. 6
As a final step we use that (a−x)/(b−x) ≥ a/b for all a, b, x ∈ R such that a ≥ b > x ≥ 0,
and that α ≤ t. We thus conclude that
t
Y
i=1
λ
∗
i
Y
α=1
d − i + α
t − i + α
≥
t
Y
i=1
λ
∗
i
Y
α=1
d + α
t + α
≥
t
Y
i=1
λ
∗
i
Y
α=1
d
2t
=
d
2t
t
.
We then need the technical result below, which is an immediate corollary of [Aub09,
Lemma 5], recalled earlier as Lemma 3.1.
Lemma 3.4. Let U
1
, . . . , U
n
∈ U(d). For ε
1
, . . . , ε
n
independent Bernoulli random vari-
ables, we have
E
sup
ρ∈D(d
t
)
n
X
i=1
ε
i
U
⊗t
i
ρU
∗⊗t
i
∞
!
6 C(t log d)
5/2
(log n)
1/2
sup
ρ∈D(d
t
)
n
X
i=1
U
⊗t
i
ρU
∗⊗t
i
1/2
∞
,
where C > 0 is a universal constant.
Proof. This follows directly from [Aub09, Lemma 5], applied with d
t
playing the role of d
and U
⊗t
i
playing the role of U
i
, 1 6 i 6 n.
With these two preliminary lemmas at hand, we are now in position to prove Theorem
3.2.
Proof of Theorem 3.2. Let V
1
, . . . , V
n
be independent copies of U
1
, . . . , U
n
and ε
1
, . . . , ε
n
be independent Bernoulli random variables. Setting
M = sup
ρ∈D(d
t
)
1
n
n
X
i=1
U
⊗t
i
ρU
∗⊗t
i
− T
(t)
(ρ)
∞
,
we then have
E M = E
U
sup
ρ∈D(d
t
)
1
n
n
X
i=1
U
⊗t
i
ρU
∗⊗t
i
− E
V
1
n
n
X
i=1
V
⊗t
i
ρV
∗⊗t
i
!
∞
!
6 E
U,V
sup
ρ∈D(d
t
)
1
n
n
X
i=1
U
⊗t
i
ρU
∗⊗t
i
− V
⊗t
i
ρV
∗⊗t
i
∞
!
= E
U,V,ε
sup
ρ∈D(d
t
)
1
n
n
X
i=1
ε
i
U
⊗t
i
ρU
∗⊗t
i
− V
⊗t
i
ρV
∗⊗t
i
∞
!
6 2 E
U,ε
sup
ρ∈D(d
t
)
1
n
n
X
i=1
ε
i
U
⊗t
i
ρU
∗⊗t
i
∞
!
,
where the first inequality is by Jensen’s inequality, the second equality is by symmetry,
and the third inequality is by the triangle inequality.
Accepted in Quantum 2020-08-24, click title to verify. Published under CC-BY 4.0. 7
Hence, by Lemma 3.4, we get
E M 6
2C
√
n
(t log d)
5/2
(log n)
1/2
E
sup
ρ∈D(d
t
)
1
n
n
X
i=1
U
⊗t
i
ρU
∗⊗t
i
1/2
∞
6
2C
√
n
(t log d)
5/2
(log n)
1/2
E
M +
2t
d
t
!
1/2
6
2C
√
n
(t log d)
5/2
(log n)
1/2
E
M +
2t
d
t
!!
1/2
,
where the second inequality is by Lemma 3.3 while the third inequality is by Jensen’s
inequality.
Now, it is easy to check that, given X, α, β > 0, if X 6 α
√
X + β, then X 6 α
2
+α
√
β.
Therefore, we eventually obtain
E M 6
4C
2
n
(t log d)
5
log n +
2C
√
n
(t log d)
5/2
(log n)
1/2
2t
d
t/2
.
And the latter quantity is smaller than /d
t
as soon as n is larger than C
0
(td)
t
(t log d)
6
/
2
.
To conclude, we just have to use Markov’s inequality, which guarantees that, if E M 6
/d
t
, then
P
M 6
2
d
t
> 1 −
E M
2/d
t
>
1
2
.
This is exactly what we wanted to show (after relabelling 2 in and 4C
0
in C).
Remark 3.5. Note that, up to a poly(t, log d) factor, the result of Theorem 3.2 is optimal,
in the sense that it is impossible to approximate the twirling channel T
(t)
with less than
order d
t
operators. This is true even if we only require -approximation in (1 → 1)-norm
rather than /d
t
-approximation in (1 → ∞)-norm. The argument has a similar flavor as
the one appearing in [LW17, Section 5.1], proving optimality of channel approximation in
a more general setting.
Indeed, let T,
ˆ
T be channels on L(n) which are -close in (1 → 1)-norm. Suppose that
T is such that, for all ρ ∈ D(n), kT (ρ)k
∞
6 c/n. Now, if
ˆ
T has Kraus rank k < c/n, then
a pure input state ρ is necessarily sent on an output state
ˆ
T (ρ) of rank at most k. Hence
for ρ ∈ D(n) pure, we have
T (ρ) −
ˆ
T (ρ)
1
>
n/c − k
n/c
= 1 −
ck
n
.
But since by assumption we also have
T (ρ) −
ˆ
T (ρ)
1
6 ,
this means that necessarily k > (1 − )n/c
In the case of the channel T
(t)
on L(d
t
), we know by Lemma 3.3 that, for all ρ ∈ D(d
t
),
kT
(t)
(ρ)k
∞
6 (2t/d)
t
. So if a channel is -close to T
(t)
in (1 → 1)-norm, then it has to
have Kraus rank at least (1 − )(d/2t)
t
.
Accepted in Quantum 2020-08-24, click title to verify. Published under CC-BY 4.0. 8
3.2 Approximating the twirling channel T
(1,1)
The goal here is to show that the twirling channel T
(1,1)
, as defined by equation (5), can
be approximated with ‘few’ Kraus operators sampled from a ‘simple’ probability measure.
We will only be able to prove such approximation in a weaker sense than in the case of
T
(t)
treated before, namely in one-to-one norm.
If µ is a 2-design on U(d), then, by equation (5), we have that
∀ X ∈ L(d
2
),
Z
U∈U(d)
U ⊗
¯
UXU
∗
⊗
¯
U
∗
dµ(U) = T
(1,1)
(X).
We will show the following result:
Theorem 3.6. Let 0 < < 1. Assume that the probability measure µ on U(d) is a
2-design, and let U
1
, . . . , U
n
be sampled independently from µ. There exists a universal
constant C > 0 such that, if n > Cd
2
(log d)
6
/
2
, then with probability at least 1/2, we
have
∀ ρ ∈ D(d
2
),
1
n
n
X
i=1
U
i
⊗
¯
U
i
ρU
∗
i
⊗
¯
U
∗
i
− T
(1,1)
(ρ)
1
6 .
The way we prove Theorem 3.6 is by first analysing separately the cases where the input
state is the maximally entangled state or a state orthogonal to it. This is the content of
Propositions 3.7 and 3.8 below.
Proposition 3.7. Assume that the probability measure µ on U (d) is a 2-design, and let
U
1
, . . . , U
n
be sampled independently from µ. Then,
1
n
n
X
i=1
U
i
⊗
¯
U
i
|ψihψ|U
∗
i
⊗
¯
U
∗
i
= T
(1,1)
(|ψihψ|).
Proof. We just have to notice that, for any U ∈ U(d), U ⊗
¯
U|ψi = |ψi. And thus,
1
n
n
X
i=1
U
i
⊗
¯
U
i
|ψihψ|U
∗
i
⊗
¯
U
∗
i
= |ψihψ| = T
(1,1)
(|ψihψ|),
as announced.
Proposition 3.8. Let 0 < < 1. Assume that the probability measure µ on U(d) is a
2-design, and let U
1
, . . . , U
n
be sampled independently from µ. There exists a universal
constant C > 0 such that, if n > Cd
2
(log d)
6
/
2
, then with probability at least 1/2, we
have
∀ ρ ∈ D(d
2
), ρ ⊥ ψ,
1
n
n
X
i=1
U
i
⊗
¯
U
i
ρU
∗
i
⊗
¯
U
∗
i
− T
(1,1)
(ρ)
∞
6
d
2
.
In order to prove Proposition 3.8 we follow the same route as to prove Theorem 3.2.
We thus begin by observing that T
(1,1)
has a small (1 → ∞)-norm on the orthogonal
complement of the maximally entangled state, which is the analogue of Lemma 3.3 in the
study of T
(t)
.
Lemma 3.9. The quantum channel T
(1,1)
is such that
sup
ρ∈D(d
2
), ρ⊥ψ
T
(1,1)
(ρ)
∞
=
1
d
2
− 1
.
Accepted in Quantum 2020-08-24, click title to verify. Published under CC-BY 4.0. 9
Proof. By equation (6), we see that, for any state ρ orthogonal to |ψihψ|, T
(1,1)
(ρ) =
Q/(d
2
− 1), so that kT
(1,1)
(ρ)k
∞
= 1/(d
2
− 1).
We then need the technical result below, which is the analogue of Lemma 3.4 in the
study of T
(t)
, and which is as well an immediate corollary of [Aub09, Lemma 5], recalled
earlier as Lemma 3.1.
Lemma 3.10. Let U
1
, . . . , U
n
∈ U (d). For ε
1
, . . . , ε
n
independent Bernoulli random vari-
ables, we have
E
sup
ρ∈D(d
2
), ρ⊥ψ
n
X
i=1
ε
i
U
i
⊗
¯
U
i
ρU
∗
i
⊗
¯
U
∗
i
∞
!
6 C(log d)
5/2
(log n)
1/2
sup
ρ∈D(d
2
), ρ⊥ψ
n
X
i=1
U
i
⊗
¯
U
i
ρU
∗
i
⊗
¯
U
∗
i
1/2
∞
,
where C > 0 is a universal constant.
Proof. This follows directly from [Aub09, Lemma 5], applied with d
2
− 1 playing the role
of d and U
i
⊗
¯
U
i
playing the role of U
i
, 1 6 i 6 n.
With Lemmas 3.9 and 3.10 at hand it is straightforward to prove Proposition 3.8,
starting from the same symmetrization trick than the one which allows to prove Theorem
3.2 from Lemmas 3.3 and 3.4. We therefore do not repeat the proof here.
So we can now combine Propositions 3.7 and 3.8 to get Theorem 3.6. It is interesting
to note that Propositions 3.7 and 3.8 give us approximation results for the channel T
(1,1)
in (1 → ∞)-norm, on the maximally entangled state and on states which are orthogonal to
it. However, when combining them in order to deal with the case of input states supported
on both subspaces, we are only able to get an approximation result in (1 → 1)-norm.
Indeed, as it will be clear in the proof, in order to show that the approximation error is
small also for mixed terms, we need to use the approximation result from Theorem 3.2
for the channel T
(1)
. Now, since the latter acts on L(d), and not L(d
2
) as T
(1,1)
, the
approximation error that we can guarantee for it is not small enough to give an interesting
approximation result for T
(1,1)
in the strong (1 → ∞)-norm, which is why we have to relax
to the weaker (1 → 1)-norm. A way around this limitation would probably be to try and
prove an analogue of [Aub09, Lemma 5] which encompasses the action of the channel T
(1,1)
on the whole input space, rather than analysing separately its action on two subspaces, as
we do here.
Proof of Theorem 3.6. By convexity of k · k
1
and extremality of pure states amongst all
states, it is enough to prove that the result is true for all pure input states. Given |ϕi a
unit vector, we can write it as |ϕi = α|ψi + β|ψ
0
i, where α = hψ|ϕi, |α|
2
+ |β|
2
= 1 and
|ψ
0
i is a unit vector orthogonal to |ψi. Defining
∆ : X ∈ L(d
2
) 7→
1
n
n
X
i=1
U
i
⊗
¯
U
i
XU
∗
i
⊗
¯
U
∗
i
− T
(1,1)
(X) ∈ L(d
2
), (7)
we then have
k∆(|ϕihϕ|)k
1
= k|α|
2
∆(|ψihψ|) + |β|
2
∆(|ψ
0
ihψ
0
|) + α
¯
β∆(|ψihψ
0
|) + ¯αβ∆(|ψ
0
ihψ|)k
1
6 |α|
2
k∆(|ψihψ|)k
1
+ |β|
2
k∆(|ψ
0
ihψ
0
|)k
1
+ 2|α||β|k∆(|ψihψ
0
|)k
1
.
Accepted in Quantum 2020-08-24, click title to verify. Published under CC-BY 4.0. 10
First, we know from Proposition 3.7 that k∆(|ψihψ|)k
1
= 0, while we know from
Proposition 3.8 that, with probability at least 3/4, k∆(|ψ
0
ihψ
0
|)k
1
6 d
2
k∆(|ψ
0
ihψ
0
|)k
∞
6
for any |ψ
0
i orthogonal to |ψi. Second, we know that we can write |ψ
0
i = X ⊗ 1|ψi
for some X such that Tr(X) = 0 and kXk
2
=
√
d. That way, since for any U ∈ U(d),
U ⊗
¯
U|ψi = |ψi and UX ⊗
¯
U|ψi = U XU
∗
⊗ 1|ψi, we get
k∆(|ψihψ
0
|)k
1
=
|ψihψ|
1
n
n
X
i=1
U
i
XU
∗
i
− T
(1)
(X)
!
⊗ 1
1
6
1
n
n
X
i=1
U
i
XU
∗
i
− T
(1)
(X)
!
⊗ 1
∞
=
1
n
n
X
i=1
U
i
XU
∗
i
− T
(1)
(X)
∞
.
Now, we know from Theorem 3.2 (for t = 1) that, with probability at least 3/4, for any
X such that kXk
2
=
√
d,
1
n
n
X
i=1
U
i
XU
∗
i
− T
(1)
(X)
∞
6
d
kXk
1
6
√
d
kXk
2
=
(actually as soon as n > Cd(log d)
6
/
2
, hence a fortiori for n > Cd
2
(log d)
6
/
2
).
Putting everything together we eventually obtain that, with probability at least 1/2,
for any |ϕi,
k∆(|ϕihϕ|)k
1
6
3
2
,
which, up to re-labelling 3/2 in , is exactly what we wanted to prove.
Remark 3.11. It can be shown that the result of Theorem 3.6 is optimal, up to a
poly(log d) factor, just as the one of Theorem 3.2. Indeed, using the same reasoning
as in Remark 3.5, together with Lemma 3.9, we see that, if a channel
ˆ
T
(1,1)
is -close to
T
(1,1)
in (1 → 1)-norm, then it has to satisfy r(
ˆ
T
(1,1)
) > (1 − )(d
2
− 1).
3.3 Approximating the twirling super-channel Θ
We are now interested in a slightly different kind of twirling, namely one that acts on
channels rather than states. We thus define the quantum super-channel Θ on C
d
as
Θ : M ∈ L(d) 7→
Θ(M) : X ∈ L(d) 7→
Z
U∈U(d)
UM(U
∗
XU)U
∗
dU
!
. (8)
Similarly as before, we here want to show that Θ can be approximated by sampling ‘few’
unitaries from a ‘simple’ probability measure. We will be able to prove approximation in
completely bounded one-to-one norm (also known as diamond norm) for all input channel.
More precisely, denoting by id : L(d) → L(d) the identity map on L(d), we will show
the following result:
Theorem 3.12. Let 0 < < 1. Assume that the probability measure µ on U(d) is a
2-design, and let U
1
, . . . , U
n
be sampled independently from µ. There exists a universal
constant C > 0 such that, if n > Cd
2
(log d)
6
/
2
, then with probability at least 1/2, we
have, for all N ∈ C(d),
∀ ρ ∈ D(d
2
),
1
n
n
X
i=1
1 ⊗ U
i
id ⊗ N(1 ⊗ U
∗
i
ρ 1 ⊗ U
i
) 1 ⊗ U
∗
i
− id ⊗ Θ(N)(ρ)
1
6 .
Accepted in Quantum 2020-08-24, click title to verify. Published under CC-BY 4.0. 11
Proof. By convexity of k·k
1
and extremality of pure states amongst all states, it is enough
to prove that the result is true for all pure input states (and all input channels). Let N
be a channel and |ϕi be a pure state, which we can write as |ϕi = X ⊗ 1|ψi for some X
such that kXk
2
=
√
d. Now, for any U ∈ U(d), X ⊗ U
∗
|ψi = X
¯
U ⊗ 1|ψi, so that
1 ⊗ Uid ⊗ N(1 ⊗ U
∗
|ϕihϕ|1 ⊗ U)1 ⊗ U
∗
= 1 ⊗ Uid ⊗ N(X ⊗ U
∗
|ψihψ|X
∗
⊗ U)1 ⊗ U
∗
= 1 ⊗ Uid ⊗ N(X
¯
U ⊗ 1|ψihψ|
¯
U
∗
X
∗
⊗ 1)1 ⊗ U
∗
= X
¯
U ⊗ U id ⊗ N(|ψihψ|)
¯
U
∗
X
∗
⊗ U
∗
.
Therefore, defining ∆ as in equation (7), we have
1
n
n
X
i=1
1 ⊗ U
i
id ⊗ N(1 ⊗ U
∗
i
ρ 1 ⊗ U
i
) 1 ⊗ U
∗
i
− id ⊗ Θ(N)(ρ)
1
= kX ⊗ 1 ∆(id ⊗ N(|ψihψ|)) X
∗
⊗ 1k
1
. (9)
We now proceed exactly as in the proof of Theorem 3.6. First, by Proposition 3.7,
∆(|ψihψ|) = 0, so that
kX ⊗ 1 ∆(|ψihψ|) X
∗
⊗ 1k
1
= 0.
Second, by Proposition 3.8, with probability at least 3/4, for any |ψ
0
i orthogonal to |ψi,
k∆(|ψ
0
ihψ
0
|)k
∞
6 /d
2
, so that
kX ⊗ 1 ∆(|ψ
0
ihψ
0
|) X
∗
⊗ 1k
1
6 kX ⊗ 1k
2
kX
∗
⊗ 1k
2
k∆(|ψ
0
ihψ
0
|)k
∞
= kXk
2
2
k1k
2
2
k∆(|ψ
0
ihψ
0
|)k
∞
6 ,
where the first inequality is by Hölder inequality while the last inequality is simply recalling
that kXk
2
= k1k
2
=
√
d. Third, any |ψ
0
i orthogonal to |ψi can be written as |ψ
0
i =
Y ⊗ 1|ψi for some Y such that Tr(Y ) = 0 and kY k
2
=
√
d. Since for any U ∈ U(d),
U ⊗
¯
U|ψi = |ψi and UY ⊗
¯
U|ψi = U Y U
∗
⊗ 1|ψi, we then get
kX ⊗ 1 ∆(|ψihψ
0
|) X
∗
⊗ 1k
1
=
X ⊗ 1 |ψihψ|
1
n
n
X
i=1
U
i
Y
∗
U
∗
i
− T
(1)
(Y
∗
)
!
⊗ 1 X
∗
⊗ 1
1
6 kX ⊗ 1 |ψik
X ⊗ 1
1
n
n
X
i=1
U
i
Y U
∗
i
− T
(1)
(Y )
!
⊗ 1 |ψi
=
X
1
n
n
X
i=1
U
i
Y U
∗
i
− T
(1)
(Y )
!
⊗ 1 |ψi
6
X
1
n
n
X
i=1
U
i
Y U
∗
i
− T
(1)
(Y )
!
⊗ 1
∞
=
X
1
n
n
X
i=1
U
i
Y U
∗
i
− T
(1)
(Y )
!
∞
6 kXk
∞
1
n
n
X
i=1
U
i
Y U
∗
i
− T
(1)
(Y )
∞
where the second equality is because kX ⊗ 1|ψik = k|ϕik = 1. Now on the one hand
kXk
∞
6 kXk
2
=
√
d. And on the other hand, by Theorem 3.2 for t = 1 and /
√
d instead
Accepted in Quantum 2020-08-24, click title to verify. Published under CC-BY 4.0. 12
of , we get that, for n > Cd
2
(log d)
6
/
2
, with probability at least 3/4, for all Y such that
kY k
2
=
√
d,
1
n
n
X
i=1
U
i
Y U
∗
i
− T
(1)
(Y )
∞
6
d
√
d
kY k
1
6
d
kY k
2
=
√
d
.
And thus, with probability at least 3/4, for any |ψ
0
i orthogonal to |ψi,
kX ⊗ 1 ∆(|ψihψ
0
|) X
∗
⊗ 1k
1
6
3
2
.
Putting everything together, we obtain that, with probability at least 1/2, for any state
σ (in particular for σ = id ⊗ N(|ψihψ|)),
kX ⊗ 1 ∆(σ) X
∗
⊗ 1k
1
6
3
2
.
Inserting this into equation (9), and re-labelling 3/2 in , yields exactly the claimed
result.
3.4 An alternative formulation
Given a linear map acting on a normed vector space (that of either operators or super-
operators in our case), it is natural to define its so-called induced norms. For a linear map
M : L(d) → L(d), the most relevant induced norm is the one-to-one norm, as well as its
completely bounded counterpart (also known as diamond norm). These are defined as
kMk
1→1
= sup
X∈L(d), kXk
1
61
kM(X)k
1
and kMk
= sup
k∈N
kid
k
⊗ Mk
1→1
,
where id
k
: L(k) → L(k) denotes the identity map on L(k). By extension, for a linear
map Ξ : L(d) → L(d), the most relevant induced norm is the diamond-to-diamond norm,
as well as its completely bounded counterpart (which we denote with a double diamond).
These are defined as
kΞk
→
= sup
M∈L(d), kMk
≤1
kΞ(M) k
and kΞk
= sup
k∈N
kid
k
⊗ Ξk
→
,
where id
k
: L(k) → L(k) denotes the identity map on L(k).
Using these definitions, we can reformulate Theorems 3.2 and 3.12 as follows:
Corollary 3.13. Let 0 < < 1. Assume that the probability measure µ on U(d) is a
t-design, and let U
1
, . . . , U
n
be sampled independently from µ. There exists a universal
constant C > 0 such that, if n > C(td)
t
(t log d)
6
/
2
, then with probability at least 1/2, we
have
T
(t)
− T
(t)
µ,n
1→1
6 ,
where
T
(t)
µ,n
: X ∈ L(d
t
) 7→
1
n
n
X
i=1
U
⊗t
i
XU
∗⊗t
i
.
Corollary 3.14. Let 0 < < 1. Assume that the probability measure µ on U(d) is a
2-design, and let U
1
, . . . , U
n
be sampled independently from µ. There exists a universal
constant C > 0 such that, if n > Cd
2
(log d)
6
/
2
, then with probability at least 1/2, we
have
kΘ − Θ
µ,n
k
→
≤ ,
Accepted in Quantum 2020-08-24, click title to verify. Published under CC-BY 4.0. 13
where
Θ
µ,n
: M ∈ L(d) 7→
Θ
µ,n
(M) : X ∈ L(d) 7→
1
n
n
X
i=1
U
i
M(U
∗
i
XU
i
)U
∗
i
!
.
For the applications in the next section, it is natural to define a k-bounded variant of
the completely bounded one-to-one and diamond-to-diamond norms, i.e.
kMk
,k
= kid
k
⊗ Mk
1→1
and kΞk
,k
= kid
k
⊗ Ξk
→
.
By the Schmidt decomposition it is clear that k·k
,d
= k·k
and k·k
,d
2
= k·k
. What
is more, it is well-known that, for any k 6 d, k · k
,k
6 kk · k
1→1
. We now prove a similar
upper bound for k · k
,k
in terms of k · k
→
.
Lemma 3.15. For any linear map Ξ : L(d) → L(d), we have
kΞk
,k
≤ k
2
kΞk
→
.
Proof. Let M ∈ L(kd) with kMk
= 1 be such that
kΞk
,k
= kid
k
⊗ Ξk
→
= k(id
k
⊗ Ξ) (M)k
.
By concavity of the diamond norm, we can assume that M has a Choi matrix η
M
∈
L(k
2
d
2
) of rank one, i.e. η
M
= |ϕ
M
ihφ
M
| for some |ϕ
M
i, |φ
M
i ∈ C
k
2
d
2
. Let us now write
|ϕ
M
i, |φ
M
i ∈ C
k
2
⊗ C
d
2
in their Schmidt decomposition:
|ϕ
M
i =
k
2
X
i=1
√
p
i
|α
i
β
i
i and |φ
M
i =
k
2
X
i=1
√
q
i
|γ
i
ζ
i
i,
with {p
i
}
16i6k
2
, {q
i
}
16i6k
2
subnormalized probability distributions and with {|α
i
i}
16i6k
2
,
{|γ
i
i}
16i6k
2
and {|β
i
i}
16i6k
2
, {|ζ
i
i}
16i6k
2
orthonormal families in C
k
2
and C
d
2
respec-
tively. We can hence write
M =
k
2
X
i,j=1
√
p
i
p
j
M
k
ij
⊗ M
d
ij
,
where M
k
ij
: L(k) → L(k) is defined as having Choi matrix η
M
k
ij
= |α
i
ihγ
j
| ∈ L(k
2
) and
M
d
ij
: L(d) → L(d) is defined as having Choi matrix η
M
d
ij
= |β
i
ihζ
j
| ∈ L(d
2
). We then
have by the triangle inequality
kΞk
,k
= k(id
k
⊗ Ξ) (M)k
6
k
2
X
i,j=1
√
p
i
q
j
kM
k
ij
⊗ Ξ(M
d
ij
)k
=
k
2
X
i,j=1
√
p
i
q
j
kΞ(M
d
ij
)k
.
To finish the proof, we then simply have to observe that
k
2
X
i,j=1
√
p
i
q
j
kΞ(M
d
ij
)k
6 kΞk
→
k
2
X
i,j=1
√
p
i
q
j
= kΞk
→
k
2
X
i=1
√
p
i
k
2
X
j=1
√
q
j
6 k
2
kΞk
→
,
where the first inequality is by definition of the diamond-to-diamond norm and the second
inequality is due to the Cauchy-Schwarz inequality.
Accepted in Quantum 2020-08-24, click title to verify. Published under CC-BY 4.0. 14
4 Application: Quantum non-malleable encryption against adversaries
with small quantum memory
Information-theoretically secure quantum encryption has been studied extensively. In par-
ticular, the one-time variants of security goals such as confidentiality, authenticity and
non-malleability have been defined for quantum encryption. When assessing the efficiency
of a symmetric-key encryption scheme, there are three main figures of merit, the run-
ning time of the encryption and decryption algorithms, the ciphertext length and the key
length. Here, we focus on the latter two figures of merit. Protocols have been designed
which achieve the optimal scaling with respect to key length (up to log factors). More
precisely, the results are as follows. The quantum one-time pad scheme, that encrypts a
quantum system by applying a random element of the Pauli group, requires 2 log d bits
of key [AMTDW00]. The quantum authentication scheme presented in [BCGST02] uses
2 log d + O(s) bits of key and log d + O(s) bits of ciphertext to achieve s bits of security.
And non-malleable encryption with unitaries (hence with plaintext space and ciphertext
space being the same) can be done with (4 + o(1)) log d bits of key [ABW09]. Here we
describe a construction for non-malleable encryption without adversarial side information
with unitaries using 2 log d + O(log log d) bits of key. In addition, our scheme has confi-
dentiality against adversaries with side information. In other words, it is an alternative to
the standard quantum one-time pad with the added property of non-malleability without
side information at only an additive logarithmic cost in terms of key length.
4.1 One-time-secure quantum encryption
We begin by defining more rigorously the different cryptographic notions mentioned above.
In the following, given a a finite set X, the notation E
x∈X
is used to denote the expectation
value of a random variable x distributed uniformly on X.
Definition 4.1 (Quantum encryption scheme). A triple (X, Enc, Dec) where
i) X is a finite set,
ii) {Enc
x
}
x∈X
is a family of quantum channels Enc
x
: L(d
M
) → L(d
C
),
iii) {Dec
x
}
x∈X
is a family of quantum channels Dec
x
: L(d
C
) → L(d
M
)
is called quantum encryption scheme if
∀ x ∈ X, Dec
x
◦ Enc
x
= id.
The parameters log
2
|X|, log
2
d
M
and log
2
d
C
are called key length, message length and
ciphertext length, respectively.
Given a quantum state σ ∈ D(d), define the quantum channel hσi ∈ C(d) by hσi(X) =
Tr(X)σ.
Definition 4.2 (Indistinguishability of ciphertexts). A quantum encryption scheme has
-indistinguishable ciphertexts, if there exists a quantum state σ ∈ D(d
C
) such that
kE
x∈X
[Enc
x
] − hσik
≤ .
A quantum encryption scheme has -indistinguishable ciphertexts against adversaries with-
out side information if the above inequality holds with the diamond norm replaced by the
one-to-one norm.
Accepted in Quantum 2020-08-24, click title to verify. Published under CC-BY 4.0. 15
Definition 4.3 (Non-malleability). A quantum encryption scheme is -non-malleable, if
there exists a quantum state σ ∈ D(d
C
) such that for all side information dimension d
E
and all Λ ∈ C(d
C
d
E
) there exist completely positive maps Λ
=
, Λ
6=
∈ L(d
E
) whose sum is
trace-preserving and p ∈ [0, 1] such that
kE
x∈X
[(Dec
x
⊗ id) ◦ Λ ◦ (Enc
x
⊗ id)] − (p id ⊗ Λ
=
+ (1 − p)hσi ⊗ Λ
6=
)k
≤ .
A quantum encryption scheme is -non-malleable against adversaries without side infor-
mation, if there exists a quantum state σ ∈ D(d
C
) such that for all Λ ∈ C(d
C
) there exists
p ∈ [0, 1] such that
kE
x∈X
[Dec
x
◦ Λ ◦ Enc
x
] − (p id + (1 − p)hσi)k
≤ .
4.2 Non-stabilized norms and adversaries without quantum side information
Any family of unitary matrices {U
x
}
x∈X
defines a quantum encryption scheme via, for
all x ∈ X, Enc
x
(X) = U
x
XU
∗
x
and Dec
x
= Enc
∗
x
. For such unitary quantum encryption
schemes, it is easy to see that -indistinguishability of ciphertexts implies that the family
of unitaries is a 2-approximate 1-design in diamond norm, and any -approximate 1-
design in diamond norm gives rise to a quantum encryption scheme with -indistinguishable
ciphertexts. The weaker property of -indistinguishability of ciphertexts against adversaries
without side information and the -approximate 1-design property measured in one-to-one
norm have the same relationship.
Similarly, if a unitary quantum encryption scheme is -non-malleable, then it is a 2-
approximate channel twirl in completely bounded diamond-to-diamond norm, and an -
approximate channel twirl in completely bounded diamond-to-diamond norm gives rise to a
quantum encryption scheme that is -non-malleable [ABW09; AM17]. Again, the weaker -
non-malleability against adversaries without side information and the -approximate chan-
nel twirl property measured in diamond-to-diamond norm have the same relationship.
The results in the previous section thus immediately imply the following for random
unitary encryption schemes:
Theorem 4.4. Let 0 < < 1. Assume that the probability measure µ on U(d) is a
2-design, and let U
1
, . . . , U
n
be sampled independently from µ. There exists a universal
constant C > 0 such that, if n > Cd
2
(log d)
6
/
2
, then with probability at least 1/2, the
quantum encryption scheme defined by the family of unitaries {U
1
, . . . , U
n
} has /
√
d-
indistinguishable ciphertexts and is -non-malleable against adversaries without side in-
formation.
Proof. Let us define
T
(1)
µ,n
: X ∈ L(d) 7→
1
n
n
X
i=1
U
i
XU
∗
i
and Θ
µ,n
: M ∈ L(d) 7→
1
n
n
X
i=1
U
i
M(U
∗
i
· U
i
)U
∗
i
. (10)
To begin with notice that, if µ is a 2-design then it is a fortiori a 1-design. Hence by
Corollary 3.13 (for t = 1 and /
√
d instead of ) and Corollary 3.14, the probability that
T
(1)
µ,n
is an /
√
d-approximate 1-design in one-to-one norm and the probability that Θ
µ,n
is an -approximate channel twirl in diamond-to-diamond norm are both at least 3/4
for n > Cd
2
(log d)
6
/
2
. By the union bound, both properties hold simultaneously with
probability at least 1/2. And as explained before, if this is so then the corresponding
unitary quantum encryption scheme has /
√
d-indistinguishable ciphertexts and is -non-
malleable against adversaries without side information.
Accepted in Quantum 2020-08-24, click title to verify. Published under CC-BY 4.0. 16
Using the result of Lemma 3.15, relating the k-bounded diamond norm to the one-to-
one norm and the k-bounded double diamond norm to the diamond-to-diamond norm, we
can immediately derive from Theorem 4.4 a generalisation of it that applies to the case
where the adversary has side information, but in bounded quantity.
Corollary 4.5. Let 0 < < 1. Assume that the probability measure µ on U(d) is a
2-design, and let U
1
, . . . , U
n
be sampled independently from µ. There exists a universal
constant C > 0 such that, if n > Cd
2
(log d)
6
k
4
/
2
, then with probability at least 1/2, the
quantum encryption scheme defined by the family of unitaries {U
1
, . . . , U
n
} has /k
√
d-
indistinguishable ciphertexts and is -non-malleable against adversaries with k-bounded
side information.
Proof. Let T
(1)
µ,n
, Θ
µ
be defined as in equation (10). We have shown in the proof of Theorem
4.4 that, for n > Cd
2
(log d)
6
/
2
, with probability larger than 1/2,
T
(1)
− T
(1)
µ,n
1→1
6
√
d
and kΘ − Θ
µ,n
k
→
6 .
Now by Lemma 3.15, we know that this implies that
T
(1)
− T
(1)
µ,n
,k
6
k
√
d
and kΘ − Θ
µ,n
k
,k
6 k
2
.
Hence redefining as k
2
, we get that, for n > Cd
2
(log d)
6
k
4
/
2
, with probability larger
than 1/2, T
(1)
µ,n
is an /k
√
d-approximate 1-design in k-bounded diamond norm and Θ
µ,n
is an -approximate channel twirl in k-bounded double diamond norm. And if this is so
then the corresponding unitary quantum encryption scheme has /k
√
d-indistinguishable
ciphertexts and is -non-malleable against adversaries with k-bounded side information.
4.3 A note on efficiency
While our scheme is more efficient in terms of key length and in terms of encryption and
decryption given the element of the design that needs to be applied (if instantiated with
an efficiently implementable 2-design, such as e.g. the Clifford group), specifying the ran-
domly chosen subset of the exact 2-design is inefficient. This is a problem shared by all
schemes based on the sub-sampling technique, i.e. in particular by the ones constructed in
[HLSW04] and [ABW09]. To construct efficiently specifiable approximate designs in the
weak norms we consider, that are still smaller than approximate designs in the diamond
norm, additional new techniques seem to be necessary. A possible approach would for
instance be to analyse random quantum circuits with respect to these norms. Indeed, all
results showing that random quantum circuits of a given size are expected to be approxi-
mate t-designs, following the seminal work [BHH16], use a metrics which is stronger than
the one we need for our cryptographic applications. It is thus probable that, for the latter,
shorter random quantum circuits are already working well.
It is also worth pointing out that our results can be easily generalized to the case where
the unitaries are sampled from an approximate rather than exact design. For instance, in
the case of Theorem 3.2 we would have the following result: If µ is an /d
t
-approximate
t-design in (1 → ∞)-norm, then we can obtain a 2/d
t
-approximate t-design in (1 → ∞)-
norm by sampling C(td)
t
(t log d)
6
/
2
unitaries from µ. Indeed, the proof of Theorem
3.2 relates the behaviour of the sampled twirling channel T
(t)
µ,n
to that of its average T
(t)
µ
,
independently of whether or not this average is the same as if taken over the Haar measure,
Accepted in Quantum 2020-08-24, click title to verify. Published under CC-BY 4.0. 17
i.e. equal or not to T
(t)
. Once you have proven that T
(t)
µ,n
is close to T
(t)
µ
, you just have to
use that, by assumption on µ, T
(t)
µ
is close to T
(t)
, and add the two approximation errors.
This provides a strategy to circumvent the difficulty of constructing exact t-designs for
t > 3, since on the contrary efficient constructions of approximate ones (even in a stronger
sense than the one we require) are known.
Acknowledgements
C.M. thanks David Gross for discussions on t-designs. We also thank the two anonymous
referees of this work for their numerous and insightful comments, which truly helped in
improving it. C.L. acknowledges financial support from the French CNRS (project PEPS
JCJC). C.M. was supported by a NWO VIDI grant (Project No. 639.022.519) and a NWO
VENI grant (Project No. VI.Veni.192.159).
References
[ABW09] Andris Ambainis, Jan Bouda, and Andreas Winter. Nonmalleable encryp-
tion of quantum information. Journal of Mathematical Physics, 50(4):042106,
2009. doi: 10.1063/1.3094756.
[ADHW09] Anura Abeyesinghe, Igor Devetak, Patrick Hayden, and Andreas Winter.
The mother of all protocols: restructuring quantum information’s family
tree. In Proceedings of the Royal Society of London A: Mathematical, Phys-
ical and Engineering Sciences, volume 465, pages 2537–2563. The Royal
Society, 2009. doi: 10.1098/rspa.2009.0202.
[AM17] Gorjan Alagic and Christian Majenz. Quantum non-malleability and au-
thentication. In Jonathan Katz and Hovav Shacham, editors, Advances in
Cryptology – CRYPTO 2017, pages 310–341, Cham. Springer International
Publishing, 2017. doi: 10.1007/978-3-319-63715-0_11.
[AMR19] Gorjan Alagic, Christian Majenz, and Alexander Russell. Efficient simula-
tion of random states and random unitaries. Cryptology ePrint Archive,
Report 2019/1204, 2019. url: https://eprint.iacr.org/2019/1204.
[AMTDW00] Andris Ambainis, Michele Mosca, Alain Tapp, and Ronald De Wolf. Private
quantum channels. In Proceedings 41st Annual Symposium on Foundations
of Computer Science, pages 547–553, 2000. doi: 10.1109/SFCS.2000.892142.
[Aub09] Guillaume Aubrun. On almost randomizing channels with a short Kraus
decomposition. Communications in Mathematical Physics, 288(3):1103–
1116, 2009. doi: 10.1007/s00220-008-0695-y.
[BCGST02] Howard Barnum, Claude Crepeau, Daniel Gottesman, Adam Smith, and
Alain Tapp. Authentication of quantum messages. In The 43rd Annual
IEEE Symposium on Foundations of Computer Science, 2002. Proceedings.
Pages 449–458, 2002. doi: 10.1109/SFCS.2002.1181969.
[BCR11] Mario Berta, Matthias Christandl, and Renato Renner. The quantum re-
verse Shannon theorem based on one-shot information theory. Communica-
tions in Mathematical Physics, 306(3):579–615, 2011. doi: 10.1007/s00220-
011-1309-7.
Accepted in Quantum 2020-08-24, click title to verify. Published under CC-BY 4.0. 18
[BHH16] Fernando G.S.L. Brandão, Aram W. Harrow, and Michał Horodecki. Local
random quantum circuits are approximate polynomial-designs. Communi-
cations in Mathematical Physics, 346(2):397–434, 2016. doi: 10.1007/s00220-
016-2706-8.
[BNRT20] Eiichi Bannai, Gabriel Navarro, Noelia Rizo, and Pham Huu Tiep. Unitary
t-groups. Journal of the Mathematical Society of Japan, 72(3):909–921,
2020. doi: 10.2969/jmsj/82228222.
[Chr06] Matthias Christandl. The structure of bipartite quantum states - Insights
from group theory and cryptography. PhD thesis, University of Cambridge,
2006. url: http://arxiv.org/abs/quant-ph/0604183.
[DBWR14] Frédéric Dupuis, Mario Berta, Jürg Wullschleger, and Renato Renner. One-
shot decoupling. Communications in Mathematical Physics, 328(1):251–
284, 2014. doi: 10.1007/s00220-014-1990-4.
[DCEL09] Christoph Dankert, Richard Cleve, Joseph Emerson, and Etera Livine. Ex-
act and approximate unitary 2-designs and their application to fidelity
estimation. Physical Review A, 80:012304, 1, 2009. doi: 10.1103/Phys-
RevA.80.012304.
[FH13] William Fulton and Joe Harris. Representation theory: a first course, vol-
ume 129. Springer, 2013.
[HHWY08] Patrick Hayden, Michał Horodecki, Andreas Winter, and Jon Yard. A de-
coupling approach to the quantum capacity. Open Systems & Information
Dynamics, 15(01):7–19, 2008. doi: 10.1142/S1230161208000043.
[HLSW04] Patrick Hayden, Debbie Leung, Peter W. Shor, and Andreas Winter. Ran-
domizing quantum states: constructions and applications. Communications
in Mathematical Physics, 250(2):371–391, 2004. doi: 10.1007/s00220-004-
1087-6.
[HOW07] Michał Horodecki, Jonathan Oppenheim, and Andreas Winter. Quantum
state merging and negative information. Communications in Mathematical
Physics, 269(1):107–136, 2007. doi: 10.1007%2Fs00220-006-0118-x.
[JLS18] Zhengfeng Ji, Yi-Kai Liu, and Fang Song. Pseudorandom quantum states.
In Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptol-
ogy – CRYPTO 2018, pages 126–152, Cham. Springer International Pub-
lishing, 2018. doi: 10.1007/978-3-319-96878-0_5.
[Kan15] Daniel Kane. Small designs for path-connected spaces and path-connected
homogeneous spaces. Transactions of the American Mathematical Society,
367(9):6387–6414, 2015. doi: 10.1090/tran/6250.
[LW17] Cécilia Lancien and Andreas Winter. Approximating quantum channels
by completely positive maps with small Kraus rank. Preprint, 2017. url:
https://arxiv.org/abs/1711.00697.
[MBDRC17] Christian Majenz, Mario Berta, Frédéric Dupuis, Renato Renner, and Matthias
Christandl. Catalytic decoupling of quantum information. Physical Review
Letters, 118:080503, 8, 2017. doi: 10.1103/PhysRevLett.118.080503.
[MSW19] Christian Majenz, Christian Schaffner, and Jeroen van Wier. Non-malleability
for quantum public-key encryption. Cryptology ePrint Archive, Report
2019/496, 2019. url: https://eprint.iacr.org/2019/496.
Accepted in Quantum 2020-08-24, click title to verify. Published under CC-BY 4.0. 19
[SDTR13] Oleg Szehr, Frédéric Dupuis, Marco Tomamichel, and Renato Renner. De-
coupling with unitary approximate two-designs. New Journal of Physics,
15(5):053022, 2013. doi: 10.1088/1367-2630/15/5/053022.
[SZ84] Paul D. Seymour and Thomas Zaslavsky. Averaging sets: a generalization
of mean values and spherical designs. Advances in Mathematics, 52(3):213–
240, 1984. doi: 10.1016/0001-8708(84)90022-7.
[Web16] Zak Webb. The Clifford group forms a unitary 3-design. Quantum Informa-
tion and Computation, 16(15&16):1379–1400, 2016. doi: 10.26421/QIC16.15-
16.
[Zhu17] Huangjun Zhu. Multiqubit Clifford groups are unitary 3-designs. Physical
Review A, 96:062336, 6, 2017. doi: 10.1103/PhysRevA.96.062336.
Accepted in Quantum 2020-08-24, click title to verify. Published under CC-BY 4.0. 20