Discovering novel high-level concepts is one of the most important steps needed for human-level AI.
In inductive logic programming (ILP), discovering novel-high level concepts is known as predicate invention (PI).
Although seen as crucial since the founding of ILP, PI is notoriously difficult and most ILP systems do not support it.
In this paper, we introduce , an ILP system that formulates the PI problem as an answer set programming problem.
Our experiments show that (i) PI can drastically improve learning performance when useful, (ii) PI is not too costly when unnecessary, and (iii)  can substantially outperform existing ILP systems.

§ INTRODUCTION

Some of the greatest paradigm shifts in science come from the invention of new predicates, such as Galileo's invention of acceleration and Joule's invention of thermal energy [31].
32 argues that developing techniques to discover novel high-level concepts is one of the most important steps needed to reach human-level AI.

In inductive logic programming (ILP) [26], a form of logic-based machine learning, discovering novel high-level concepts is known as predicate invention (PI) [34].

A classical example of PI is learning the definition of grandparent given only the relations mother and father. An ILP system without PI can learn the hypothesis:

grandparent(A,B) $\leftarrow$ mother(A,C),mother(C,B)

grandparent(A,B) $\leftarrow$ mother(A,C),father(C,B)

grandparent(A,B) $\leftarrow$ father(A,C),mother(C,B)

grandparent(A,B) $\leftarrow$ father(A,C),father(C,B)

By contrast, a system with PI can learn the hypothesis:

grandparent(A,B) $\leftarrow$ inv(A,C),inv(C,B)

inv(A,B) $\leftarrow$ mother(A,B)

inv(A,B) $\leftarrow$ father(A,B)

The symbol inv is invented and can be understood as parent.
Introducing this symbol makes the hypothesis smaller, both in the number of literals and clauses, which is beneficial because the search complexity of ILP is often a function of the size of the smallest solution [6].

Although seen as crucial since the earliest days of ILP [23] and repeatedly stated as a major challenge [16, 24, 18], most ILP systems do not support PI [5].

As 17 states, PI is difficult because it is unclear when and how we should invent a symbol, how many arguments should it have, what its types are, etc.

Interest in PI has resurged due to  [25, 3], which uses metarules, second-order clauses, to reduce the complexity of PI by restricting the syntax of hypotheses.
The major limitation of  and other metarule-based approaches [36, 10, 15, 14] is the inherent need for metarules, which a user must provide.
Given insufficient metarules, these approaches cannot learn any solution, let alone one with PI [4].

To overcome this limitation, we introduce a PI approach based on learning from failures (LFF) [2], which frames the ILP problem as an answer set programming (ASP) problem [12].
We build on LFF by framing the PI problem as an ASP problem.
Compared to existing approaches, our approach does not need a user to manually provide metarules or specify the arity and argument types of an invented symbol [19], i.e. our approach supports automatic PI.
Moreover, our approach retains the benefits of LFF, notably scalability and the ability to learn recursive programs.
Overall, our contributions are:

* We extend LFF to support predicate invention.
We introduce a new type of redundancy constraint and show that it is sound with respect to optimal solutions.

* We introduce , a LFF implementation that supports automatic PI.

We experimentally show that (i) PI can drastically improve learning performance when useful, (ii) PI is not too costly when unnecessary, and (iii)  can substantially outperform existing ILP systems.

§ RELATED WORK

Early work on PI was based on the idea of inverse resolution and W operators [23].
Although these approaches could support PI, they never demonstrated completeness, partly because of the lack of a declarative bias to delimit the hypothesis space [25].

One PI approach is to use placeholders [20] to predefine invented symbols.
However, this approach requires that a user manually specify the arity and argument types of an `invented' symbol [19], which rather defeats the point, or requires enumerating every possible symbol [11].

By contrast,  does not need a user to manually pre-define predicates and can automatically infer argument types, i.e.  supports automatic PI.
[33] also uses ASP for PI, but only learns single-clause non-recursive programs.
By contrast,  learns recursive multi-clause programs.
PI can be performed by learning programs in a multi-task setting [21] or as a pre-/post-processing step [7, 6, 8, 9].
By contrast,  performs PI whilst learning.

uses metarules to restrict the syntax of hypotheses and drive PI.
For instance, the chain metarule ($P(A,B) \leftarrow Q(A,C), R(C,B)$) allows  to induce programs such as f(A,B) $\leftarrow$ tail(A,C),tail(C,B), which drops the first two elements from a list.
To induce longer clauses,  chains clauses together using PI, such as the following program which drops the first four elements from a list:

P = \left\{
\begin{array}{l}
\emph{f(A,B)} \leftarrow \emph{inv(A,C),inv(C,B)}\\
\emph{inv(A,B)} \leftarrow \emph{tail(A,C),tail(C,B)}\\
\end{array}
\right\}

The major limitation of metarule-driven PI approaches [36, 10, 15, 14] is their inherent need for user-supplied metarules, which, in some cases, are impossible to provide [4].

overcomes this major limitation because it does not need metarules.
Moreover, in Section <ref>, we show that  subsumes  because it can replicate its search strategy.

builds on the LFF system , which works in three repeating stages: generate, test, and constrain.
In the generate stage,  builds a logic program that satisfies a set of hypothesis constraints.
In the test stage,  tests a program against the examples.
A hypothesis fails when it is incomplete (does not entail all the positive examples) or inconsistent (entails a negative example).
If a hypothesis fails,  learns hypothesis constraints from the failure, which it then uses to restrict subsequent generate stages.
It repeats this process until it finds a complete and consistent program.
extends  to support automatic PI.

§ PROBLEM SETTING

We now define PI and extend LFF to support PI.
We assume familiarity with logic programming [22].

§.§ Predicate Invention

We focus on the ILP learning from entailment setting [29].

An ILP input is a tuple $(B,E^+,E^-,\mathcal{H})$, where $B$ is a logic program denoting background knowledge, $E^+$ and $E^-$ are sets of ground atoms which represent positive and negative examples respectively, and $\mathcal{H}$ is a hypothesis space (the set of all hypotheses).

In practice, the hypothesis space is restricted by a language bias, such as metarules or mode declarations.

The ILP problem is to find a solution:

Given an ILP input $(B,E^+,E^-,\mathcal{H})$, the ILP problem is to return a hypothesis $H \in \mathcal{H}$ such that
$\forall e \in E^+, H \cup B \models e$ and $\forall e \in E^-, H \cup B \not\models e$.

27 and 34 both provide definitions for PI, which we adapt.

We denote the predicate signature (the set of all predicate symbols) of a logic program $P$ as ps(P).

Let $(B,E^+,E^-,\mathcal{H})$ be an ILP input and $H \in \mathcal{H}$.

Then $H$ contains an invented predicate symbol if and only if $ps(H) \setminus ps(B \cup E^+ \cup E^-) \neq \emptyset$.

PI is necessary when needed to learn a solution:

Let $I = (B,E^+,E^-,\mathcal{H})$ be an ILP input.
Then PI is necessary for $I$ if no $H$ in $\mathcal{H}$ is a solution without PI.

PI is useful when it allows us to learn a better solution:

Let $(B,E^+,E^-,\mathcal{H})$ be an ILP input and $cost : \mathcal{H} \mapsto R$ be an arbitrary cost function.
Then PI is useful when (i) there is a $H \in \mathcal{H}$ such that $H$ is a solution with invented predicate symbols, and (ii) $\forall H' \in \mathcal{H}$, where $H'$ is a solution, $cost(H) \leq cost(H')$.

In this paper, we define the cost(H) to be the total number of literals in the logic program $H$.

§.§ Learning From Failures

We extend LFF to support PI.

LFF uses predicate declarations to restrict what predicate symbols may appear in a hypothesis.
A predicate declaration is a ground atom of the form $\emph{head\_pred}(\emph{p},a)$ or $\emph{body\_pred}(\emph{p},a)$ where p is a predicate symbol of arity $a$.
Given a set of predicate declarations $D$, a definite clause $C$ is declaration consistent when (i) if $\emph{p}/m$ is the predicate in the head of $C$, then $\emph{head\_pred}(\emph{p},m)$ is in $D$, and (ii) for all $\emph{q}/n$ predicate symbols in the body of $C$, $\emph{body\_pred}(\emph{q},n)$ is in $D$.
LFF uses hypothesis constraints to restrict the hypothesis space.
Let $\mathcal{L}$ be a language that defines hypotheses, i.e. a meta-language.
Then a hypothesis constraint is a constraint expressed in $\mathcal{L}$.
Let $C$ be a set of hypothesis constraints written in a language $\mathcal{L}$.
A set of definite clauses $H$ is consistent with $C$ if, when written in $\mathcal{L}$, $H$ does not violate any constraint in $C$.

We define the LFF problem:

The LFF input is a tuple $(E^+, E^-, B, D, C)$ where $E^+$ and $E^-$ are sets of ground atoms denoting positive and negative examples respectively; $B$ is a Horn program denoting background knowledge; $D$ is a set of predicate declarations; and $C$ is a set of hypothesis constraints.

A definite program is a hypothesis when it is consistent with both $D$ and $C$.
We denote the set of such hypotheses as $\mathcal{H}_{D,C}$.
We define a LFF solution:

Given an input tuple $(E^+, E^-, B, D, C)$, a hypothesis $H \in \mathcal{H}_{D,C}$ is a solution when $H$ is complete ($\forall e \in E^+, \; B \cup H \models e$) and consistent ($\forall e \in E^-, \; B \cup H \not\models e$).

If a hypothesis is not a solution then it is a failure or a failed hypothesis.
A hypothesis is incomplete when $\exists e \in E^+, \; H \cup B \not \models e$.
A hypothesis is inconsistent when $\exists e \in E^-, \; H \cup B \models e$.
A hypothesis is totally incomplete when $\forall e \in E^+, \; H \cup B \not \models e$.
We define an optimal solution:

Given an input tuple $(E^+, E^-, B, D, C)$, a hypothesis $H \in \mathcal{H}_{D,C}$ is optimal when (i) $H$ is a solution, and (ii) $\forall H' \in \mathcal{H}_{D,C}$, where $H'$ is a solution, $cost(H) \leq cost(H')$.

§.§ Redundancy Constraints

The key idea of LFF is to learn hypothesis constraints from failed hypotheses.
2 introduce constraints based on subsumption [28].
A clause $C_1$ subsumes a clause $C_2$ ($C_1 \preceq C_2$) if and only if there exists a substitution $\theta$ such that $C_1\theta \subseteq C_2$.
A clausal theory $T_1$ subsumes a clausal theory $T_2$ ($T_1 \preceq T_2$) if and only if $\forall C_2 \in T_2, \exists C_1 \in T_1$ such that $C_1$ subsumes $C_2$.

A clausal theory $T_1$ is a specialisation of a clausal theory $T_2$ if and only if $T_2 \preceq T_1$.
A clausal theory $T_1$ is a generalisation of a clausal theory $T_2$ if and only if $T_1 \preceq T_2$.

If a hypothesis $H$ is incomplete, a specialisation constraint prunes specialisations of $H$, as they are also guaranteed to be incomplete.
Likewise, if a hypothesis $H$ is inconsistent, a generalisation constraint prunes generalisations of $H$, as they are also guaranteed to be inconsistent.
2 show that generalisation and specialisation constraints are sound in that they never prune solutions from the hypothesis space.
The authors also introduce a third type of constraint called an elimination constraint and show it is sound for optimal solutions.
If a hypothesis $H$ is totally incomplete, then there is no need for $H$ (or a specialisation of it) to appear in a complete and separable hypothesis.
A separable hypothesis $H$ is one where no predicate symbol in the head of a clause in $H$ occurs in the body of a clause in $H$.
Elimination constraints are unsuitable for PI because an invented predicate should always appear in the body of a clause.

To overcome this limitation, we introduce redundancy constraints.

We adapt the standard notion of a dependency graph [1] of a program from predicates  to clauses:

The dependency graph for the definite program $P$ is a directed graph where the nodes are the clauses in $P$.
There is an edge between nodes $C_1$ and $C_2$ if the head predicate symbol of $C_2$ occurs in the body of $C_1$.
We say $C_1$ depends on $C_2$ if there is a path from $C_1$ to $C_2$.

We require that each clause in a hypothesis is reachable from a target predicate clause (a clause that generalises the examples).
We use the dependency relation to characterise when a program is at least as specific as another program:

Let $P$ and $Q$ be definite programs and $P' = \{C \in Q \;|\; \exists D \in P, D \preceq C\}$.

A clause $C \in P'$ $P$-specialises $Q$ if
(i) $C$ does not depend on any clause in $Q \setminus P'$, and
(ii) no clause in $Q \setminus P'$ depends on $C$.

The idea is that part of $Q$ cannot entail more than $P$, as the clauses of $Q$ on paths to $C$ specialise $P$, as we now illustrate:

Let $P = \{ C_1, C_2 \}$, $C_1 = \emph{f(A,B)} \leftarrow \emph{inv(A,C),inv(C,B)}$, $C_2 = \emph{inv(A,B)} \leftarrow \emph{tail(A,C),tail(C,B)}$, $C_Q = \emph{f(A,B) $\leftarrow$ reverse(A,B)}$, and $Q = P \cup \{ C_Q \}$.
In $Q$, neither $C_2$ nor $C_Q$ depend on one another, so $C_2$ $P$-specialises $Q$.
As $C_2$ cannot help $Q$ entail more than $P$ does, if $P$ is a totally incomplete hypothesis then $C_2$ is redundant in $Q$.

If the hypothesis $P$ is totally incomplete and there is a clause that $P$-specialises the hypothesis $Q$, we call $Q$ a redundant hypothesis.

We show that redundant hypotheses are not optimal:

Let $(E^+, E^-, B, D, C)$ be a LFF input, $H_1, H_2 \in \mathcal{H}_{D,C}$, and $H_1$ be totally incomplete.
If $H_2$ has a clause that $H_1$-specialises it, then $H_2$ is not an optimal solution.

The proof of Theorem <ref> is in Appendix A.
We call constraints that only prune redundant hypotheses redundancy constraints.
We show that redundancy constraints prune more than elimination constraints:

Let $(E^+, E^-, B, D, C)$ be a LFF input and $H \in \mathcal{H}_{D,C}$ be totally incomplete.
As (i) all separable hypotheses containing specialisations of $H$ are redundant, and
(ii) there exist $H' \in \mathcal{H}_{D,C}$ that are redundant but not separable,
redundancy constraints prune strictly more than elimination constraints.

For (i), let $H^*$ be a separable hypothesis containing a specialisation of $H$.
As separability implies no clause of $H^*$ depends on another, any clause of $H^*$ specialising a clause of $H$ is redundant.
For (ii) Example <ref> suffices, taking $H = P$ and $H' = Q$.
Hypothesis $Q$ is redundant but not separable.

extends  with a new PI module and the ability to learn redundancy constraints from failures.
Due to space limitations, we cannot describe  in detail, so we refer the reader to the original paper for a detailed explanation [2].
works in three repeating stages: generate, test, and constrain, which we now describe.

§.§.§ Generate

takes as input (i) predicate declarations, (ii) hypothesis constraints, and (iii) bounds on the maximum number of variables, literals, and clauses in a hypothesis.
returns an answer set which represents a definite program, if one exists.
For instance, consider an answer set with the following head (h_lit) and body (b_lit) literals:

h_lit(0,last,2,(0,1)), b_lit(0,tail,2,(0,2)),

b_lit(0,empty,1,(2,)), b_lit(0,head,2,(0,1)),

h_lit(1,last,2,(0,1)), b_lit(1,tail,2,(0,2)),

The first argument of each literal is the clause index, the second is the predicate symbol, the third is the arity, and the fourth is the literal variables, where 0 represents A, 1 represents B, etc.
This answer set corresponds to the definite program:

last(A,B):- tail(A,C), empty(C), head(A,B).

last(A,B):- tail(A,C), last(C,B).

Figure <ref> shows the base ASP program to generate programs.
extends  by allowing invented symbols (invented(P,A)) to appear in head and body literals.

uses ASP constraints to ensure that a program is declaration consistent and obeys hypothesis constraints.
For instance, to prune programs where the head literal appears in the body,  enforces the constraint:

By later adding learned hypothesis constraints,  eliminate answer sets and thus prunes the hypothesis space.

head_p(P,A):- head_pred(P,A).
head_p(P,A):- invented(P,A).
body_p(P,A):- body_pred(P,A).
body_p(P,A):- invented(P,A).
clause(0..N-1):- max_clauses(N).
h_lit(C,P,A,Vs):- head_p(P,A),vars(A,Vs),clause(C).
b_lit(C,P,A,Vs):- body_p(P,A),vars(A,Vs),clause(C).

Partial listing of the program generator in .

PI Module.

builds on  with a PI module, partially shown in Figure <ref>.

Lines 1-3 show the ASP choice rules which allow  to perform PI.
automatically adds $n-1$ choice rules to allow $n-1$ invented symbols, where $n$ is the maximum number of clauses allowed in a program.
This module contains many constraints specific to PI to prune redundant programs.

Lines 4-6 define an ordering over invented symbols, similar to , and line 9 enforces this ordering.
Lines 7-8 ensure that if an invented symbol is in the head of a clause then it must also appear in the body of a clause (and vice-versa).
Line 10 ensures that  uses invented predicates in order, e.g. to prevent the symbol inv2 from appearing in a program if inv1 does not already appear.
This module also includes code (omitted for brevity) to infer the argument types of an invented predicate by how it is used in the program and propagates the types through the program.

invented(inv1,1..A):- max_arity(A).
invented(inv2,1..A):- max_arity(A).
invented(inv3,1..A):- max_arity(A).
lower(P,Q):- head_pred(P,_), invented(Q).
:- invented(P,A), not h_lit(_,P,A,_).
:- invented(P,A), not b_lit(_,P,A,_).
:- invented(P,_), lower(Q,P), not invented(Q,_).
:- h_lit(C,P,_,_), b_lit(C,Q,_,_), lower(Q,P).

Partial listing of the PI module in .

§.§.§ Test and constrain

The test stage of  is identical to :  transforms an answer set to a definite program (a Prolog program) and tests it against the training examples.
If a hypothesis fails, then, in the constrain stage,  derives ASP constraints which it adds to the generator program to prune answer sets and constrain subsequent hypothesis generation.
For instance, suppose this hypothesis is inconsistent:

last(A,B):- reverse(A,C), head(C,B).

Then  generates a generalisation constraint to prune generalisations of this hypothesis:

seen(C,id1):- h_lit(C,last,2,(V0,V1)),
b_lit(C,reverse,2,(V0,V2)), b_lit(C,head,2,(V2,V1)).
:- seen(C,id1), clause_size(C,2).

extends  with redundancy constraints (Section <ref>).
For instance, suppose this program is totally incomplete:

f(A,B):- inv1(A,C), right(C,B).

inv1(A,B):- right(A,C), right(C,B).

Whereas  would only generate a specialisation constraint,  additionally generates a redundancy constraint:

seen(C,c1):- h_lit(C,f,2,(V0,V1)),
b_lit(C,inv1,2,(V0,V2)), b_lit(C,right,2,(V2,V1)).
seen(C,c2):- h_lit(C,inv1,2,(V0,V1)),
b_lit(C,right,2,(V0,V2)), b_lit(C,right,2,(V2,V1)).
seen(p1):- seen(C0,c1), seen(C1,c2).
:- seen(p1), num_clauses(f,1), num_recursive(inv1,0).
:- seen(p1), num_clauses(inv1,1), num_recursive(f,0).

Appendix B describes the algorithm  uses to build redundancy constraints.

repeats the generate/test/constraint loop.
To find an optimal solution,  increases the number of literals allowed in a program when the hypothesis space is empty at a certain program size (e.g. when there are no more programs to generate).
To improve efficiency,  uses Clingo's multi-shot solving [13] to maintain state between the three stages and thus remember learned conflicts.
This loop repeats until either (i)  finds an optimal solution, or (ii) there are no more hypotheses to test.

needs metarules to define the hypothesis space and drive PI.
can simulate metarules through hypothesis constraints [2].
By supporting PI,  subsumes .
In our experiments, we directly compare  against  when given identical metarules, which we call .

§ EXPERIMENTS

Few papers empirically evaluate PI [6, 14] and none in a systematic manner.
Therefore, our experiments try to answer the question:

Q1 How beneficial is PI when it is useful?

To answer Q1, Experiments <ref> and <ref> compare ILP systems with and without PI on problems purposely designed to benefit from PI.
Specifically, we compare (i)  against , and (ii)  against  without the ability to reuse invented predicates, which we denote as .

PI should improve performance when it is useful (Definition <ref>), but what about when it is unnecessary?
In other words, can PI be harmful?
To answer this question, our experiments try to answer the question:

Q2 How costly is PI when it is unnecessary?

To answer Q2, Experiment <ref> compares the same systems on a problem that should not benefit from PI.

To test our claim that  can go beyond existing systems that support PI, our experiments try to answer the question:

Q3 How well does  perform against other ILP systems?

To answer Q3, we compare   against .
We also compare  against , which is the only system that supports automatic PI and learning recursive programs.

We use  and  with the same settings as 2: at most 6 variables in a clause, at most 5 body literals, and at most 3 clauses[

cannot learn solutions in some of the experiments using these setting and quickly says that a problem is unsolvable, e.g. in Experiment <ref>  needs to learn a solution with 24 body literals.
However, when we allowed 24 body literals,  could still not learn a solution in the given time.
We therefore use these settings but when  cannot find a solution, we assign it the maximum learning time.
needs metarules.

We consider two sets of metarules: with and without recursion, listed in Appendix C.
uses the same metarules encoded as hypothesis constraints.
We use a 3.8 GHz 8-Core Intel Core i7 with 32GB of ram.
Note that all the ILP systems only use a single CPU.

§.§ Experiment 1 - Robot Planning

This experiment aims to answer Q1.
We therefore use a problem where PI should be useful.

A robot is in a $100^2$ grid world.

An example is an atom $f(x,y)$ where $x$ and $y$ are initial and final states respectively.
A state describes the position of the robot.
The problem is to learn a plan to move right $k$ times.
As BK, we provide the single dyadic predicate right, which moves the robot right one step.

For each $k$ in $\{4,8,12,16,20,24\}$, we generate 10 positive training examples of the robot moving right $k$ times and $k-1$ negative training examples of the robot moving right $i$ times for $i\dots k-1$.
The target solution is a chain of $k$ right actions.
As the value $k$ grows, PI should become more useful because a system can invent and reuse chains of actions.
We repeat the experiment five times.
We measure learning times and standard error.
We set a learning timeout of two minutes.

Figure <ref> shows the results.
Without recursion,  is the best performing system because it can chain invented predicate symbols, such as this program for when $k=16$, where each $f_i$ is invented:

f(A,B):- f1(A,C),f1(C,B).

f1(A,B):- f2(A,C),f2(C,B).

f2(A,B):- f3(A,C),f3(C,B).

f3(A,B):- right(A,C),right(C,B).

This reuse allows Metagol (and ) to move right $2^n$ times using only $n$ clauses, i.e. to move right $k>2$ times,  requires at most $\ln(k)$ clauses.
By contrast,  performs poorly because it cannot reuse invented symbols and to move right $k>2$ times requires $k-1$ clauses.

substantially outperforms .
To move right $k$ times,  must learn a program with a single clause formed of $k+1$ literals.
By contrast,  can learn a more compact program, such as a program which requires only 10 literals to move right 16 times:

f(A,B):- inv1(A,C),inv1(C,D),inv1(D,E),inv1(E,B).

inv1(A,B):- right(A,C),right(C,D),right(D,E),right(E,B).

With recursion,   performs poorly because of its inefficient search algorithm.
By contrast,  and  both perform well with recursion.

Overall, these results suggest that PI is extremely beneficial when useful (Q1) and that  can drastically outperform existing systems (Q3).

[legend columns=5,legend style=nodes=scale=0.6, transform shape,align=left,column sep=0ex,
legend entries=, , , , ]

every tick label/.append style=font=
xlabel=Grid size,
ylabel=Learning time (seconds),
ylabel style=yshift=-3mm,
label style=font=

+[blue,mark=*,mark options=fill=blue,error bars/.cd,y dir=both,y explicit]
table [
y error plus expr=error,
y error minus expr=error,
] data/robots/poppi-time.table;

+[red,mark=square*,mark options=color=red,error bars/.cd,y dir=both,y explicit]
table [
y error plus expr=error,
y error minus expr=error,
] data/robots/poppi-mil-time.table;

+[gray,mark=diamond*,dashed,error bars/.cd,y dir=both,y explicit]
table [
y error plus expr=error,
y error minus expr=error,
] data/robots/popper-time.table;

+[green,mark=triangle*,mark options=color=green,error bars/.cd,y dir=both,y explicit]
table [
y error plus expr=error,
y error minus expr=error,
] data/robots/metagol-time.table;

+[brown,mark=x,mark options=color=brown,error bars/.cd,y dir=both,y explicit]
table [
y error plus expr=error,
y error minus expr=error,
] data/robots/metagol-nopi-time.table;

Without recursion

every tick label/.append style=font=
scaled x ticks=false
xlabel=Grid size,

label style=font=

+[blue,mark=*,mark options=fill=blue,error bars/.cd,y dir=both,y explicit]
table [
y error plus expr=error,
y error minus expr=error,
] data/robots/poppi-rec-time.table;

+[red,mark=square*,mark options=color=red,error bars/.cd,y dir=both,y explicit]
table [
y error plus expr=error,
y error minus expr=error,
] data/robots/poppi-mil-rec-time.table;

+[gray,mark=diamond*,dashed,error bars/.cd,y dir=both,y explicit]
table [
y error plus expr=error,
y error minus expr=error,
] data/robots/popper-rec-time.table;

+[green,mark=triangle*,mark options=color=green,error bars/.cd,y dir=both,y explicit]
table [
y error plus expr=error,
y error minus expr=error,
] data/robots/metagol-rec-time.table;

+[brown,mark=x,mark options=color=brown,error bars/.cd,y dir=both,y explicit]
table [
y error plus expr=error,
y error minus expr=error,
] data/robots/metagol-nopi-rec-time.table;

With recursion

Robot experimental results.

§.§ Experiment 2 - List Transformation

This experiment aims to corroborate the results of Experiment 1 to answer Q1.
We therefore use a problem where PI should be useful.
This problem is modelled on the problems 30 use to model human intelligence.

The task is to learn a program to find the $kth$ element of a list.
An example is an atom $f(x,y)$, where $x$ is a list of characters and $y$ is a character.
A list is a random permutation of all the ASCII lowercase letters.
As BK, we provide the dyadic predicates head and tail.

For each $k$ in $\{2,4,8,10,12,14\}$, we generate 1 positive example where $y$ is the $kth$ element of the list $x$.
We generate a negative training example for every other element in the list.
The target solution is a chain of $k-1$ tail relations followed by a head relation.
As the value $k$ grows, PI should become more useful because a system can invent and reuse chains of actions.
We repeat the experiment five times.
We measure learning times and standard error.
We set a learning timeout of two minutes.

Figure <ref> shows the results, which largely match those from Experiment <ref> and again suggest that PI is extremely beneficial when useful (Q1) and that  can drastically outperform existing systems (Q3).

[legend columns=5,legend style=nodes=scale=0.6, transform shape,align=left,column sep=0ex,
legend entries=, , , , ]

every tick label/.append style=font=
xlabel=Grid size,
ylabel=Learning time (seconds),
ylabel style=yshift=-3mm,
label style=font=

+[blue,mark=*,mark options=fill=blue,error bars/.cd,y dir=both,y explicit]
table [
y error plus expr=error,
y error minus expr=error,
] data/tail/poppi-time.table;

+[red,mark=square*,mark options=color=red,error bars/.cd,y dir=both,y explicit]
table [
y error plus expr=error,
y error minus expr=error,
] data/tail/poppi-mil-time.table;

+[gray,mark=none,dashed,error bars/.cd,y dir=both,y explicit]
table [
y error plus expr=error,
y error minus expr=error,
] data/tail/popper-time.table;

+[green,mark=triangle*,mark options=color=green,error bars/.cd,y dir=both,y explicit]
table [
y error plus expr=error,
y error minus expr=error,
] data/tail/metagol-time.table;

+[brown,mark=x,mark options=color=brown,error bars/.cd,y dir=both,y explicit]
table [
y error plus expr=error,
y error minus expr=error,
] data/tail/metagol-nopi-time.table;

Without recursion

every tick label/.append style=font=
scaled x ticks=false
xlabel=Grid size,

label style=font=

+[blue,mark=*,mark options=fill=blue,error bars/.cd,y dir=both,y explicit]
table [
y error plus expr=error,
y error minus expr=error,
] data/tail/poppi-rec-time.table;

+[red,mark=square*,mark options=color=red,error bars/.cd,y dir=both,y explicit]
table [
y error plus expr=error,
y error minus expr=error,
] data/tail/poppi-mil-rec-time.table;

+[gray,mark=none,dashed,error bars/.cd,y dir=both,y explicit]
table [
y error plus expr=error,
y error minus expr=error,
] data/tail/popper-rec-time.table;

+[green,mark=triangle*,mark options=color=green,error bars/.cd,y dir=both,y explicit]
table [
y error plus expr=error,
y error minus expr=error,
] data/tail/metagol-rec-time.table;

+[brown,mark=x,mark options=color=brown,error bars/.cd,y dir=both,y explicit]
table [
y error plus expr=error,
y error minus expr=error,
] data/tail/metagol-nopi-rec-time.table;

With recursion

List transformation experimental results.

§.§ Experiment 3 - Programming Puzzles

Experiments 1 and 2 clearly show that PI can drastically improve performance when it is useful (Q1).
However, as we discussed at the start of Section <ref>, PI is not always useful.
The main purpose of this experiment is to answer Q2.
We therefore use problems where PI should not be useful.

We repeat the programming puzzles experiment from [2].
The first column in Table <ref> shows the problems.
Note that these problems are extremely difficult for ILP systems and  is the first system that can reliably learn solutions to them.

We describe all the experimental materials in Appendix D.

We generate 10 positive and 10 negative examples per problem.
Each example is randomly generated from lists up to length 50 formed of integers from 1-100.
We test on 1000 positive and 1000 negative randomly sampled examples.
We measure predictive accuracy and learning time.
We enforce a timeout of three minutes per task.
We repeat the experiment five times and measure the mean and standard error.

Table <ref> shows that mean predictive accuracies.
outperforms  and a McNemar's test confirms the significance at the $p < 0.01$ level.
Because it supports PI,  searches a larger hypothesis space than , which is why it takes longer on some tasks.
When the predictive accuracy of  is not 100%, it is because it did not learn a solution in the given time in some of the trials.
Table <ref> shows this difference in learning time.
As is clear,  outperforms  in all cases and a paired t-test confirms the significance at the $p < 0.01$ level, although the difference is always less than double.
Overall, these results suggest that PI is not too costly when not useful (Q2).
Moreover, as Table <ref> shows,  drastically outperforms  on all but three problems, where they both perform identically and helps answer (Q3).

addhead     100 $\pm$ 0     50 $\pm$ 0     100 $\pm$ 0     50 $\pm$ 0

dropk     100 $\pm$ 0     50 $\pm$ 0     100 $\pm$ 0     50 $\pm$ 0

droplast     100 $\pm$ 0     50 $\pm$ 0     100 $\pm$ 0     50 $\pm$ 0

evens     100 $\pm$ 0     50 $\pm$ 0     100 $\pm$ 0     50 $\pm$ 0

finddup     98 $\pm$ 0     80 $\pm$ 12     99 $\pm$ 0     50 $\pm$ 0

last     100 $\pm$ 0     50 $\pm$ 0     100 $\pm$ 0     100 $\pm$ 0

len     100 $\pm$ 0     50 $\pm$ 0     100 $\pm$ 0     50 $\pm$ 0

member     100 $\pm$ 0     100 $\pm$ 0     100 $\pm$ 0     100 $\pm$ 0

sorted     100 $\pm$ 0     50 $\pm$ 0     100 $\pm$ 0     50 $\pm$ 0

threesame     99 $\pm$ 0     50 $\pm$ 0     99 $\pm$ 0     99 $\pm$ 0

Programming puzzles predictive accuracies.
We round accuracies to integer values.
The error is standard error.

addhead     1 $\pm$ 0     120 $\pm$ 0.1     0.4 $\pm$ 0     120 $\pm$ 0

dropk     1 $\pm$ 0.1     0.1 $\pm$ 0     1 $\pm$ 0     0.2 $\pm$ 0

droplast     5 $\pm$ 1     120 $\pm$ 0.1     4 $\pm$ 0.8     120 $\pm$ 0

evens     8 $\pm$ 0.5     0.7 $\pm$ 0     6 $\pm$ 0.2     120 $\pm$ 0

finddup     91 $\pm$ 5     69 $\pm$ 22     48 $\pm$ 2     120 $\pm$ 0

last     4 $\pm$ 0.2     120 $\pm$ 0.1     3 $\pm$ 0.3     0.6 $\pm$ 0.3

len     25 $\pm$ 1     120 $\pm$ 0.1     16 $\pm$ 0.6     120 $\pm$ 0

member     0.7 $\pm$ 0.1     0.2 $\pm$ 0     0.2 $\pm$ 0     0.3 $\pm$ 0

sorted     32 $\pm$ 3     0.5 $\pm$ 0     35 $\pm$ 5     120 $\pm$ 0

threesame     0.2 $\pm$ 0     0.6 $\pm$ 0     0.2 $\pm$ 0     0.6 $\pm$ 0.2

Programming puzzles learning times.
We round times over 1 second to the nearest second.
The error is standard error.

§ CONCLUSIONS AND LIMITATIONS

Although seen as key to human-level AI [32] and repeatedly stated as a major challenge, most ILP systems do not support PI, and those that do have severe limitations (Section <ref>).
To overcome these limitations, we have extended LFF with redundancy constraints which are sound (Theorem <ref>) and more effective (Theorem <ref>) than existing constraints.
We implemented our approach in the ILP system , which supports automatic PI, i.e. does not need metarules nor requires a user manually predefine invented symbols.
We have experimentally shown that (i) PI can drastically improve learning performance when useful, (ii) PI is not too costly when unnecessary, and (iii)  can substantially outperform existing ILP systems.

There are limitations for future work to address.

Inefficient PI.
Although  convincingly outperforms , its PI technique is inefficient.
For instance, in Experiment <ref>, when learning to move right eight times,  considers this hypothesis:

f(A,B) :- inv1(A,C),right(C,D),right(D,B).

inv1(A,B) :- right(A,C),right(C,B).

This hypothesis fails, as it only moves right four times.
From this failure  learns constraints to prune specialisations of it.
However,  will still consider logically equivalent hypotheses, such as:

f(A,B) :- right(A,C),inv1(C,D),right(D,B).

inv1(A,B) :- right(A,C),right(C,B).

We could address this issue by reasoning about unfolded hypotheses [35].
In general, we expect to make further substantial efficiency improvements in .

Higher-arity invention.
can only learn monadic and dyadic programs because of the restrictions imposed by metarules.
Therefore, to perform a fair experimental comparison, our experiments only consider inventing monadic and dyadic predicates.
can, however, invent predicates with arity greater than two.
In future work, we want to apply  to more general problems with higher-arity invention.

[1]
Krzysztof R. Apt and Roland N. Bol.
Logic programming and negation: A survey.
J. Log. Program., 1994.

[2]
Andrew Cropper and Rolf Morel.
Learning programs by learning from failures.
Machine Learning, 2021.

[3]
Andrew Cropper and Stephen H. Muggleton.
Learning higher-order logic programs through abstraction and
In IJCAI, 2016.

[4]
Andrew Cropper and Sophie Tourret.
Logical reduction of metarules.
Machine Learning, 2020.

[5]
Andrew Cropper, Sebastijan Dumancic, and Stephen H. Muggleton.
Turning 30: New ideas in inductive logic programming.
In IJCAI, 2020.

[6]
Andrew Cropper.
Playgol: Learning programs through play.
IJCAI, 2019.

[7]
Sebastijan Dumancic and Hendrik Blockeel.
Clustering-based relational unsupervised representation learning with
an explicit distributed representation.
In IJCAI, 2017.

[8]
Sebastijan Dumancic, Tias Guns, Wannes Meert, and Hendrik Blockeel.
Learning relational representations with auto-encoding logic
IJCAI, 2019.

[9]
Sebastijan Dumancic, Tias Guns, and Andrew Cropper.
Knowledge refactoring for inductive program synthesis.
AAAI, 2021.

[10]
Richard Evans and Edward Grefenstette.
Learning explanatory rules from noisy data.
JAIR, 2018.

[11]
Richard Evans, José Hernández-Orallo, Johannes Welbl, Pushmeet Kohli, and
Marek Sergot.
Making sense of sensory input.
Artificial Intelligence, 2021.

[12]
Martin Gebser, Roland Kaminski, Benjamin Kaufmann, and Torsten Schaub.
Answer Set Solving in Practice.
Morgan & Claypool Publishers, 2012.

[13]
Martin Gebser, Roland Kaminski, Benjamin Kaufmann, and Torsten Schaub.
Multi-shot ASP solving with clingo.
TPLP, 2019.

[14]
Céline Hocquette and Stephen H. Muggleton.
Complete bottom-up predicate invention in meta-interpretive learning.
In IJCAI, 2020.

[15]
Tobias Kaminski, Thomas Eiter, and Katsumi Inoue.
Meta-interpretive learning using hex-programs.
In IJCAI, 2019.

[16]
Stanley Kok and Pedro M. Domingos.
Statistical predicate invention.
In ICML, 2007.

[17]
Stefan Kramer.
Predicate invention: A comprehensive view.
Technical report, 1995.

[18]
Stefan Kramer.
A brief history of learning symbolic higher-level representations
from data (and a curious look forward).
In IJCAI, 2020.

[19]
Mark Law, Alessandra Russo, and Krysia Broda.
Inductive learning of answer set programs.
In JELIA, 2014.

[20]
Gregor Leban, Jure Zabkar, and Ivan Bratko.
An experiment in robot discovery with ILP.

[21]
Dianhuan Lin, Eyal Dechter, Kevin Ellis, Joshua B. Tenenbaum, and Stephen
Bias reformulation for one-shot function induction.
In ECAI, 2014.

[22]
John W Lloyd.
Foundations of logic programming.
Springer Science & Business Media, 2012.

[23]
Stephen Muggleton and Wray L. Buntine.
Machine invention of first order predicates by inverting resolution.
In ICML, 1988.

[24]
Stephen Muggleton, Luc De Raedt, David Poole, Ivan Bratko, Peter A. Flach,
Katsumi Inoue, and Ashwin Srinivasan.
ILP turns 20 - biography and future challenges.
Machine Learning, 2012.

[25]
Stephen H. Muggleton, Dianhuan Lin, and Alireza Tamaddoni-Nezhad.
Meta-interpretive learning of higher-order dyadic Datalog:
predicate invention revisited.
Machine Learning, 2015.

[26]
Stephen Muggleton.
Inductive logic programming.
New Generation Comput., 1991.

[27]
Stephen Muggleton.
Predicate invention and utilization.
J. Exp. Theor. Artif. Intell., 1994.

[28]
G.D. Plotkin.
Automatic Methods of Inductive Inference.
PhD thesis, Edinburgh University, August 1971.

[29]
Luc De Raedt.
Logical and relational learning.
Cognitive Technologies. Springer, 2008.

[30]
Joshua S. Rule, Joshua B. Tenenbaum, and Steven T. Piantadosi.
The child as hacker.
Trends in Cognitive Sciences, 2020.

[31]
S.J. Russell and P. Norvig.
Artificial Intelligence: A Modern Approach.
Pearson, 2010.

[32]
Stuart Russell.
Human compatible: Artificial intelligence and the problem of
Penguin, 2019.

[33]
Peter Schüller and Mishal Benz.
Best-effort inductive logic programming via fine-grained cost-based
hypothesis generation.
Machine Learning, 2018.

[34]
Irene Stahl.
The appropriateness of predicate invention as bias shift operation in
Machine Learning, 1995.

[35]
Hisao Tamaki and Taisuke Sato.
Unfold/fold transformation of logic programs.
In ICLP, 1984.

[36]
William Yang Wang, Kathryn Mazaitis, and William W. Cohen.
A soft version of predicate invention based on structured sparsity.
In IJCAI, 2015.

§ APPENDIX: REDUNDANCY AND OPTIMALITY

Let $(E^+, E^-, B, D, C)$ be a LFF input, $H_1, H_2 \in \mathcal{H}_{D,C}$, and $H_1$ be totally incomplete.
If $H_2$ has a clause that $H_1$-specialises it, then $H_2$ is not an optimal solution.

Suppose $H_2$ is a solution and that its clause $C$ $H_1$-specialises $H_2$.
Let $H_2'$ be the clauses of $H_2$ not specialising a clause of $H_1$.
No clause of $H_2'$ depends on $C$ or has $C$ depend on it, meaning $C$ is only used by totally incomplete $H_2 \setminus H_2' \succeq H_1$.
Hence $C$ cannot have contributed to $H_2$ entailing positive examples.
Therefore $H_2 \setminus \{ C \}$ entails all positive examples and, due to the programs being definite, does not entail additional negative examples.
Conclude that $H_2$ is not optimal as a smaller solution exists.

§ APPENDIX: BUILDING REDUNDANCY CONSTRAINTS

We describe how redundancy constraints are derived.
Let $H$ be a totally incomplete hypothesis.
For each clause in $H$, we generate a seen clause rule.
For example, we assign the clause  the identifier  and we generate the rule:

seen(C,c1):- head_lit(C,f,2,(V0,V1)),

We assign each hypothesis an identifier, e.g. .
Suppose that $H$ has  clauses.
Then the head of the following seen program rule is true precisely when the program contains a specialisation of $H$:
seen(h1):- seen(_,c1),...,seen(_,cN).

We then consider all predicates defined by $H$.
When a predicate  depends on itself (is recursive), we say  is recursively called.
For each predicate  of $H$ that is not recursively called, we generate a constraint.
For fixed , let , …,  be all the predicates of $H$ except .
Let  denote the number of clauses defining predicate $P$ in $H$.
denotes the number of recursive clauses of $P$.
Each non-recursively called predicate of $H$ then causes a redundancy constraint of the following shape to be generated:

:- seen(h1),

§ APPENDIX: METARULES

§.§ Experiments <ref> and <ref>

[frame=single,caption=Metarules without recursion.]
metarule([P,Q], [P,A,B], [[Q,A,B]]).
metarule([P,Q,R], [P,A,B], [[Q,A,B],[R,A]]).
metarule([P,Q,R], [P,A,B], [[Q,A,B],[R,B]]).
metarule([P,Q,R], [P,A,B], [[Q,A,C],[R,C,B]]).

[frame=single,caption=Metarules with recursion.]
metarule([P,Q], [P,A,B], [[Q,A,B]]).
metarule([P,Q,R], [P,A,B], [[Q,A,B],[R,A]]).
metarule([P,Q,R], [P,A,B], [[Q,A,B],[R,B]]).
metarule([P,Q,R], [P,A,B], [[Q,A,C],[R,C,B]]).
metarule([P,Q], [P,A,B], [[Q,A,C],[P,C,B]]).

§.§ Experiment <ref>

[frame=single, caption=Metarules used in Experiment <ref>]
metarule([P,Q], [P,A], [[Q,A]]).
metarule([P,Q], [P,A], [[Q,A]]).
metarule([P,Q,R], [P,A], [[Q,A,B],[R,B]]).
metarule([P,Q], [P,A], [[Q,A,B],[P,B]]).
metarule([P,Q,R], [P,A], [[Q,A,B],[R,A,B]]).
metarule([P,Q], [P,A,B], [[Q,A,B]]).
metarule([P,Q,R], [P,A,B], [[Q,A,B],[R,A,B]]).
metarule([P,Q,R], [P,A,B], [[Q,A],[R,A,B]]).
metarule([P,Q,R], [P,A,B], [[Q,A,B],[R,B]]).
metarule([P,Q,R], [P,A,B], [[Q,A,C],[R,C,B]]).
metarule([P,Q], [P,A,B], [[Q,A,C],[P,C,B]]).
metarule([P,Q], [P,A,B], [[Q,A,B]]).

§ APPENDIX: PROGRAMMING PUZZLE EXPERIMENTAL DETAILS

We give each system the following dyadic relations head, tail, decrement, geq and the monadic relations empty, zero, one, even, and odd.
We also include the dyadic relation increment in the len experiment.
We had to remove this relation from the BK for the other experiments because when given this relation  runs into infinite recursion on almost every problem and could not find any solutions.
We also include member/2 in the find duplicate problem.
We also include cons/3 in the addhead, dropk, and droplast experiments.
We exclude this relation from the other experiments because  does not easily support triadic relations.

We set  to use at most five unique variables, at most five body literals, and at most two clauses.
For each BK relation, we also provide both systems with simple types and argument directions (whether input or output).
Because  can generate non-terminating Prolog programs, we set both systems to use a testing timeout of 0.1 seconds per example.
If a program times out, we view it as a failure.


# A simpler security proof for 6-state quantum key distribution

Kaan Akyuz  Middle East Technical University, Turkey Boris Škorić  TU
Eindhoven, The Netherlands

###### Abstract

Six-state Quantum Key Distribution (QKD) achieves the highest key rate in the
class of qubit-based QKD schemes. The standard security proof, which has been
developed since 2005, invokes complicated theorems involving smooth Rényi
entropies.

In this paper we present a simpler security proof for 6-state QKD that
entirely avoids Rényi entropies. This is achieved by applying state smoothing
directly in the Bell basis. We furthermore show that the same proof technique
can be used for 6-state quantum key recycling.

##  1 Introduction

Early security proofs for quantum key distribution [15, 3, 14, 8, 9, 21] were
not formulated in the universal composability framework. The universal
composability approach has been followed for QKD since 2005 [17, 1, 11, 18,
19]. This has led to security proofs in which the Leftover Hash Lemma (LHL)
against quantum adversaries plays a central role. The LHL provides an upper
bound on the distinguishability between the generated QKD key and a completely
random string, given all classical and quantum information held by the
adversary. All the various versions of the LHL work with smooth Rényi
entropies [10, 16] and invoke theorems about their properties. Hence, reading
a QKD security proof requires an understanding of rather advanced concepts and
a heavy theoretical toolbox.

In this paper we provide a more ‘schoolbook’ security proof for 6-state QKD
that entirely avoids Rényi entropies. We rely on postselection [5] to lift
security against collective attacks to security against general attacks. We
follow a number of steps familiar from the LHL, but at the point where one
would usually rewrite expressions in terms of Rényi entropies we work with
expressions that are diagonalized in the Bell basis, so that square roots of
operators can be explicitly computed. We apply smoothing (cutting off
probability tails) in the Bell basis, in a way that resembles smoothing of
classical probability distributions. This yields a finite-size result for the
key rate, with ${\mathcal{O}}(1/\sqrt{n})$ finite-size contributions, which is
the same order that the standard security proof gives.

We focus on 6-state QKD for several reasons: (i) Among qubit-based QKD schemes
it stands out as the one with the highest key rate as a function of the
quantum bit error rate (QBER). (ii) For BB84 very powerful proofs exist that
immediately yield general security without needing to go via collective
attacks and postselection. These do not work for the high rate of 6-state QKD.
(iii) The level of simplification that our proof provides is more compelling
for 6-state than for BB84.

The outline of the paper is as follows. In the preliminaries (Section 2) we
briefly review the standard security proof for 6-state QKD, and we list a
number of lemmas that we will use. We present our simplified proof in Section
3, and we plot key rates as a function of QBER for various finite sizes,
showing convergence to the asymptotic rate. In Section 5 we discuss possible
improvements. In the Appendix we show that the proof technique can also be
applied to 6-state quantum key recycling.

##  2 Preliminaries

###  2.1 Notation

Classical Random Variables are denoted with capital letters, and their
realisations with lowercase letters. Sets are denoted in calligraphic font.
The probability that $X$ takes value $x$ is written as $\rm Pr[X=x]$. The
expectation with respect to $X$ is denoted as
$\mathbb{E}_{x}f(x)=\sum_{x\in\mathcal{X}}{\rm Pr}[X=x]f(x)$. The notation
’log’ stands for the logarithm with base 2. We write the binary entropy
function as
$h(p)=p\log{\textstyle\frac{1}{p}}+(1-p)\log{\textstyle\frac{1}{1-p}}$, and
more generally
$h(p_{1},\ldots,p_{N})=\sum_{i=1}^{N}p_{i}\log{\textstyle\frac{1}{p_{i}}}$.
The inverse of a bit $b\in\\{0,1\\}$ is $\bar{b}=1-b$. The Hamming weight of a
string $x$ is written as $w(x)=|\\{i:w_{i}\neq 0\\}|$. We write $\mathbb{I}$
for the identity matrix. The notation $\operatorname{tr}$ stands for trace.
The Hermitian conjugate of an operator $A$ is written as $A^{\dagger}$. Let
$A$ have eigenvalues $\lambda_{i}$. The 1-norm of $A$ is written as
$\|A\|_{1}=\operatorname{tr}\sqrt{A^{\dagger}A}=\sum_{i}\left|\lambda_{i}\right|$.
$\mathcal{S}(\mathcal{H})$ denotes the space of positive semidefinite
operators on the Hilbert space $\mathcal{H}$. The trace distance between
operators $\rho,\sigma$ is $\|\rho-\sigma\|_{\rm
tr}=\frac{1}{2}\|\rho-\sigma\|_{1}$.

###  2.2 ‘Standard’ security proof for 6-state QKD

We briefly review the security analysis for 6-state QKD with a single-photon
source, with one-way classical postprocessing and without artificial
preprocessing noise. We focus on the proof technique developed by Renner et
al. [17, 11, 18, 19, 5], which yields the highest key rate while satisfying
universal composability [1, 19]. An important ingredient is the use of post-
selection [5], which makes it possible to upgrade a security proof in case of
collective attacks to a security proof in case of general attacks.iii More
recent techniques based on entropic uncertainty relations [23, 22] do not need
such a step and immediately yield finite-size results for any attack. However,
they do not work for the high rates of 6-state QKD.  The cost of this upgrade
is a modest reduction of the key length, by $30\log(n+1)$ bits. A second main
ingredient is symmetrisation [17, 18]. Alice and Bob share $n$ noisy EPR
pairs. The security of the protocol does not change if they both apply the
same Pauli operations on their own qubits, chosen at random independently for
each EPR pair. The joint effect of postselection and symmetrisation is that it
suffices to consider states of the form $(\sigma^{AB})^{\otimes n}$, where
$\sigma^{AB}$ is a two-qubit density matrix that is diagonal in the Bell basis
and depends only on the QBER. For states $(\sigma^{AB})^{\otimes n}$ that
successfully pass the parameter estimation step of the QKD protocol, we may
write

$\sigma^{AB}=(1-{\textstyle\frac{3}{2}}\gamma)|\Psi^{-}\rangle\langle\Psi^{-}|+{\textstyle\frac{\gamma}{2}}|\Phi^{-}\rangle\langle\Phi^{-}|+{\textstyle\frac{\gamma}{2}}|\Psi^{+}\rangle\langle\Psi^{+}|+{\textstyle\frac{\gamma}{2}}|\Phi^{+}\rangle\langle\Phi^{+}|$
(1)

where $\gamma$ is the maximum allowed QBER. (Here we have taken the EPR pairs
to be singlet states.) As a worst-case assumption it is considered that Eve
holds the purification of the AB system. Using notation similar to [12] one
can write the purification as

$|\Psi^{ABE}\rangle=\sqrt{1-{\textstyle\frac{3}{2}}\gamma}|\Psi^{-}\rangle|0\rangle+\sqrt{{\textstyle\frac{\gamma}{2}}}\Big{(}-|\Phi^{-}\rangle|1\rangle+i|\Psi^{+}\rangle|2\rangle+|\Phi^{+}\rangle|3\rangle\Big{)}$
(2)

which leads to a simple form for Eve’s post-measurement state. Alice and Bob
do a measurement in a basis that is characterised by spin direction ${\bf
e}_{j}$ on the Bloch sphere, where $j\in\\{1,2,3\\}$ stands for the
$x,y,z$-axis respectively. Alice’s outcome is $x\in\\{0,1\\}$ and Bob’s
outcome is $y\in\\{0,1\\}$. Eve’s post-measurement state, conditioned on
outcomes $x,y$, is $\sigma^{j}_{xy}=|E^{j}_{xy}\rangle\langle E^{j}_{xy}|$
with

$\displaystyle|E^{j}_{x\bar{x}}\rangle$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{1-\gamma}}\Big{[}\sqrt{1-{\textstyle\frac{3}{2}}\gamma}|0\rangle+(-1)^{x}\sqrt{{\textstyle\frac{\gamma}{2}}}|j\rangle\Big{]}$
(3) $\displaystyle|E^{j}_{xx}\rangle$ $\displaystyle\propto$
$\displaystyle\frac{1}{\sqrt{2}}\Big{[}|j+1\rangle+i(-1)^{x+1}|j+2\rangle\Big{]}$
(4)

where the indices $j+1$, $j+2$ are understood to cycle back into
$\\{1,2,3\\}$. (This state of Eve is also obtained from optimal attacks
analysis [20].) The full post-measurement state is

$\displaystyle\rho^{JXYE}$ $\displaystyle=$
$\displaystyle\sum_{j\in\\{1,2,3\\}^{n}}{\rm
Pr}[J=j]\sum_{x,y\in\\{0,1\\}^{n}}p_{xy}|j,x,y\rangle\langle
j,x,y|\otimes\rho^{E}_{jxy}$ (5) $\displaystyle p_{xy}$ $\displaystyle=$
$\displaystyle 2^{-n}\gamma^{w(\bar{x}\oplus y)}(1-\gamma)^{n-w(\bar{x}\oplus
y)}$ (6) $\displaystyle\rho^{E}_{jxy}$ $\displaystyle=$
$\displaystyle\bigotimes_{i=1}^{n}\sigma^{j_{i}}_{x_{i}y_{i}}.$ (7)

Alice sends the syndrome of $x$ to Bob, one-time-pad encrypted. This allows
Bob to reconstruct $x$ from $y$ and the syndrome. (If the reconstruction fails
then Alice and Bob abort.) The QKD key $z\in{\mathcal{Z}}$ is derived from $x$
as $z=\Phi(u,x)$, where $\Phi$ is a universal hash function and
$u\in{\mathcal{U}}$ is a public seed. The security proof amounts to upper
bounding the statistical distance (trace distance) between on the one hand $Z$
given all of Eve’s information and on the other hand a uniform variable on
${\mathcal{Z}}$. The encrypted syndrome does not enter into this analysis
since the one-time pad key is entirely independent; the sending of this
ciphertext ends up only as a penalty term in the QKD key rate due to the
expenditure of key material. The quantity to be upper bounded is

$D=\|\rho^{ZUJE}-\mu^{Z}\otimes\rho^{UJE}\|_{\rm tr}.$ (8)

It can be written as $D={\textstyle\frac{1}{2}}{\rm tr}\sum_{j}{\rm
Pr}[J=j]\sum_{z,u}\frac{1}{|{\mathcal{U}}|}\sqrt{(p_{z|u}\rho^{E}_{jzu}-\frac{1}{|{\mathcal{Z}}|}\rho^{E}_{ju})^{2}}$.
The first step is to pull the sums $\sum_{zu}$ into the square root with a
Jensen inequality, and make use of the universal hash properties to evaluate
these sums. The result is $D\leq{\textstyle\frac{1}{2}}\sum_{j}{\rm
Pr}[J=j]{\rm tr}\sqrt{|{\mathcal{Z}}|\sum_{x}p_{x}^{2}(\rho^{E}_{jx})^{2}}$.
However, Jensen’s inequality is so un-tight that it pays off to take a
different starting point before applying the inequality. A smoothed state
$\bar{\rho}$ is considered, which lies close to $\rho$. It holds that

$\displaystyle D$ $\displaystyle\leq$ $\displaystyle
2\|\rho^{ZUJE}-\bar{\rho}^{ZUJE}\|_{\rm tr}+\bar{D}$ (9)
$\displaystyle\bar{D}$ $\displaystyle\stackrel{{\scriptstyle\rm def}}{{=}}$
$\displaystyle\|\bar{\rho}^{ZUJE}-\mu^{Z}\otimes\bar{\rho}^{UJE}\|_{\rm
tr}\leq{\textstyle\frac{1}{2}}\sum_{j}{\rm Pr}[J=j]{\rm
tr}\sqrt{|{\mathcal{Z}}|\sum_{x}p_{x}^{2}(\bar{\rho}^{E}_{jx})^{2}}.$ (10)

Next the trace too is pulled into the square root with Jensen, which yields an
extra factor support$(\rho^{E}_{j})$ inside the square root. Then it is noted
that the expression $\log\sum_{x}p_{x}^{2}(\bar{\rho}^{E}_{jx})^{2}$ is a
Rényi 2-entropy, whereas log(support$(\bar{\rho}^{E}_{j}))$ is a Rényi
0-entropy. Finally a number of ‘sledgehammer’ theorems are invoked to bound
entropies of $\bar{\rho}$ by smooth entropies of $\rho$ [19, 17] and finally
to bound the smooth Rényi entropies by von Neumann entropies [17], in
particular the von Neumann entropy of the averaged state
$\rho^{E}=\sum_{jxy}p_{j}p_{xy}\rho^{E}_{jxy}$ which is identical in form to
$\sigma^{AB}$ (1). The end result is that asymptotically
$\bar{D}\leq{\textstyle\frac{1}{2}}\mathbb{E}_{j}\sqrt{|{\mathcal{Z}}|2^{-n}2^{S(E|j)-S(E|Xj)}}$
$={\textstyle\frac{1}{2}}\sqrt{2^{\ell-n}2^{nh(1-{\textstyle\frac{3}{2}}\gamma,{\textstyle\frac{\gamma}{2}},{\textstyle\frac{\gamma}{2}},{\textstyle\frac{\gamma}{2}})-nh(\gamma)}}$.
(Here $S$ stands for von Neumann entropy, and we have written
$|{\mathcal{Z}}|=2^{\ell}$.) Hence the QKD key length $\ell$ can be set to
slightly below
$n-nh(1-{\textstyle\frac{3}{2}}\gamma,{\textstyle\frac{\gamma}{2}},{\textstyle\frac{\gamma}{2}},{\textstyle\frac{\gamma}{2}})+nh(\gamma)$.
Taking into account the key material spent on sending the syndrome, which
asymptotically has size $nh(\gamma)$, the asymptotic key rate is given by
$\frac{1}{n}[\ell-nh(\gamma)]$,

$\mbox{6-state QKD asymptotic key rate =
}1-h(1-{\textstyle\frac{3}{2}}\gamma,{\textstyle\frac{\gamma}{2}},{\textstyle\frac{\gamma}{2}},{\textstyle\frac{\gamma}{2}}).$
(11)

###  2.3 Useful Lemmas

######  Lemma 2.1 (Lemma A.2.8 in [17]).

Let $\rho,\bar{\rho}\in{\cal P}(\cal H)$ with $\bar{\rho}=P\rho P$ for some
projector $P$ on $\cal H$. Then

$\displaystyle\|\rho-\bar{\rho}\|_{1}\leq
2\sqrt{\operatorname{tr}\rho\,\operatorname{tr}(\rho-\bar{\rho})}.$ (12)

######  Lemma 2.2.

(Bretagnolle–Huber–Carol inequality. Proposition 2 in [4].) Let
$(Z_{1},\ldots,Z_{t})$ be a multinomial-distributed vector with parameters
$(\pi_{1},\ldots,\pi_{t})$, satisfying $\sum_{s=1}^{t}Z_{s}=n$. Then

${\rm Pr}\left[\sum_{s=1}^{t}|Z_{s}-n\pi_{s}|\geq\alpha\sqrt{n}\right]\leq
2^{t}e^{-\frac{1}{2}\alpha^{2}}.$ (13)

##  3 Simplified security proof for 6-state QKD

###  3.1 Diagonal form in the Bell basis

We present a relatively simple security proof for 6-state QKD that uses
smoothing but avoids Rényi entropies altogether. We take advantage of
postselection and symmetrisation just like the proof discussed in Section 2.2.
The point where we start to depart from the standard approach is (9,10). We
note that the expression $A_{j}\stackrel{{\scriptstyle\rm
def}}{{=}}\sum_{x}p_{x}^{2}(\rho^{E}_{jx})^{2}$ is diagonal in the Bell basis.
We apply a smoothing procedure that acts as a projection $P_{\mathcal{S}}$
onto a subspace of Eve’s Hilbert space ${\mathcal{H}}_{E}^{\otimes n}$. We
choose this subspace such that $P_{\mathcal{S}}A_{j}P_{\mathcal{S}}$ is still
diagonal. We define the set $\mathcal{G}=\\{0,1,2,3\\}^{n}$. For
$g\in\mathcal{G}$ we define the state $|g\rangle\in{\mathcal{H}}_{E}^{\otimes
n}$ as

$|g\rangle=\bigotimes_{i=1}^{n}|g_{i}\rangle.$ (14)

######  Lemma 3.1.

Let $j\in\\{0,1,2,3\\}$ and $r\in\\{0,1\\}$.

$\frac{1}{2}\sum_{x\in\\{0,1\\}}\sigma^{j}_{x,\bar{x}\oplus
r}=\left\\{\begin{array}[]{ll}r=0:&\frac{1-{\textstyle\frac{3}{2}}\gamma}{1-\gamma}|0\rangle\langle
0|+\frac{\gamma/2}{1-\gamma}|j\rangle\langle j|\\\
r=1:&\frac{1}{2}|j+1\rangle\langle j+1|+\frac{1}{2}|j+2\rangle\langle
j+2|\end{array}\right.$ (15)

Proof: Follows directly from $\sigma^{j}_{xy}=|E^{j}_{xy}\rangle\langle
E^{j}_{xy}|$ with $|E^{j}_{xy}\rangle$ as given in (3),(4). $\square$

######  Lemma 3.2.

Let $j\in\\{1,2,3\\}^{n}$ and $g\in\mathcal{G}$. Let
$t_{0}(g)=|\\{i:g_{i}=0\\}|$ be the tally of zeroes in $g$. Let $t_{\rm
eq}(g,j)=|\\{i:g_{i}=j_{i}\\}|$ be the tally of places where $t$ and $j$
coincide. Similarly, let $t_{+1}(g,j)=|\\{i:g_{i}=j_{i}+1\\}|$ and
$t_{+2}(g,j)=|\\{i:g_{i}=j_{i}+2\\}|$ where it is understood that $j+1$ and
$j+2$ cycle back into the set $\\{1,2,3\\}$. Then it holds that

$\displaystyle\sum_{x}p_{x}^{2}(\rho^{E}_{jx})^{2}$ $\displaystyle=$
$\displaystyle\sum_{g\in\mathcal{G}}\lambda_{g}(j)|g\rangle\langle g|$ (16)
$\displaystyle\lambda_{g}(j)$ $\displaystyle=$ $\displaystyle
2^{-n}\Big{[}(1-\gamma)(1-{\textstyle\frac{3}{2}}\gamma)\Big{]}^{t_{0}(g)}\Big{[}{\textstyle\frac{\gamma}{2}}(1-\gamma)\Big{]}^{t_{\rm
eq}(g,j)}\Big{[}{\textstyle\frac{1}{2}}\gamma^{2}\Big{]}^{t_{+1}(g,j)+t_{+2}(g,j)}.$
(17)

Proof: We have
$\rho^{E}_{jx}=\bigotimes_{i=1}^{n}[(1-\gamma)\sigma^{j_{i}}_{x_{i}\overline{x_{i}}}+\gamma\sigma^{j_{i}}_{x_{i}x_{i}}]$.
Using the fact that the sigma matrices with $x=y$ are orthogonal to those with
$x\neq y$ we get
$(\rho^{E}_{jx})^{2}=\bigotimes_{i=1}^{n}[(1-\gamma)^{2}\sigma^{j_{i}}_{x_{i}\overline{x_{i}}}+\gamma^{2}\sigma^{j_{i}}_{x_{i}x_{i}}]$.
Next we use $p_{x}=2^{-n}$ to obtain
$A_{j}=\sum_{x}p_{x}^{2}(\rho^{E}_{jx})^{2}$
$=2^{-n}\bigotimes_{i=1}^{n}[(1-\gamma)^{2}\frac{\sigma^{j_{i}}_{01}+\sigma^{j_{i}}_{10}}{2}+\gamma^{2}\frac{\sigma^{j_{i}}_{00}+\sigma^{j_{i}}_{11}}{2}]$.
Lemma 3.1 tells us that this expression is diagonal in the Bell basis. The
eigenvectors are of the form (14). We find the eigenvalues by computing
$A|g\rangle$. We see that every occurrence of $g_{i}=0$ generates a factor
$(1-\gamma)^{2}\frac{1-{\textstyle\frac{3}{2}}\gamma}{1-\gamma}=(1-\gamma)(1-{\textstyle\frac{3}{2}}\gamma)$.
Similarly, each occurrence $g_{i}=j_{i}$ yields a factor
$(1-\gamma)^{2}\frac{\gamma/2}{1-\gamma}={\textstyle\frac{\gamma}{2}}(1-\gamma)$.
Finally, $g_{i}\notin\\{0,j_{i}\\}$ leads to a factor
$\gamma^{2}\cdot{\textstyle\frac{1}{2}}$. Counting how often each factor
occurs yields (17). $\square$

If no smoothing is applied at all, Lemma 3.2 directly yields a bound on the
trace distance $D$ (8).

######  Lemma 3.3 (Without smooting).

The distance $D=\|\rho^{ZUJE}-\mu^{Z}\otimes\rho^{UJE}\|_{\rm tr}$ for the
state
$\rho^{E}_{jx}=\bigotimes_{i=1}^{n}[(1-\gamma)\sigma^{j_{i}}_{x_{i}\overline{x_{i}}}+\gamma\sigma^{j_{i}}_{x_{i}x_{i}}]$
can be bounded as

$D\leq\frac{1}{2}\sqrt{2^{\ell-n}}\Big{[}\sqrt{(1-\gamma)(1-{\textstyle\frac{3}{2}}\gamma)}+\sqrt{{\textstyle\frac{\gamma}{2}}(1-\gamma)}+2\sqrt{\gamma^{2}/2}\Big{]}^{n}.$
(18)

Proof: We substitute (16) into (10) without smoothing. The resulting
expression contains ${\rm tr}\sqrt{\sum_{x}p_{x}^{2}(\rho^{E}_{jx})^{2}}$
$=\sum_{g\in\mathcal{G}}\sqrt{\lambda_{g}(j)}$. Substituting (17) yields a
summand that depends only on tallies. The sum $\sum_{g\in\mathcal{G}}$ then
simplifies to the form $\sum_{\rm tallies}{n\choose{\rm tallies}}$ which is
evaluated using the multinomial sum rule. $\square$

Lemma 3.3 yields a rate that is decidedly worse than the standard result (11).

###  3.2 Explicit recipe for smoothing

We pick a subset
${\mathcal{T}}\subset\\{(a,b,c,d)\in{\mathbb{N}}^{4}|a+b+c+d=n\\}$. This will
represent the set of tallies that remain after smoothing. We define sets

$\mathcal{S}_{j}\stackrel{{\scriptstyle\rm
def}}{{=}}\\{g\in\mathcal{G}|\Big{(}t_{0}(g),t_{\rm
eq}(g,j),t_{+1}(g,j),t_{+2}(g,j)\Big{)}\in{\mathcal{T}}\\}.$ (19)

We introduce projection operators

$P^{j}\stackrel{{\scriptstyle\rm
def}}{{=}}\sum_{g\in\mathcal{S}_{j}}|g\rangle\langle g|.$ (20)

For each combination of classical variables $(j,x,y)$ with
$j\in\\{1,2,3\\}^{n}$ and $x,y\in\\{0,1\\}^{n}$ we apply smoothing as follows

$\bar{\rho}^{E}_{jxy}=P^{j}\rho^{E}_{jxy}P^{j}.$ (21)

######  Lemma 3.4.

It holds that

$\|\rho^{ZUJE}-\bar{\rho}^{ZUJE}\|_{\rm
tr}\leq\sqrt{\sum_{(\tau_{0},\tau_{1},\tau_{2},\tau_{3})\notin{\mathcal{T}}}{n\choose\tau_{0},\tau_{1},\tau_{2},\tau_{3}}(1-{\textstyle\frac{3}{2}}\gamma)^{\tau_{0}}({\textstyle\frac{\gamma}{2}})^{\tau_{1}+\tau_{2}+\tau_{3}}}.$
(22)

Proof: The state $\rho^{ZUJE}$ (9) is given by

$\rho^{ZUJE}=\sum_{zuj}p_{j}\frac{1}{|{\mathcal{U}}|}|z,u,j\rangle\langle
z,u,j|\otimes\sum_{xy}p_{xy}p_{z|ux}\rho^{E}_{jxy}$ (23)

and hence the smoothed version is

$\bar{\rho}^{ZUJE}=\sum_{zuj}p_{j}\frac{1}{|{\mathcal{U}}|}|z,u,j\rangle\langle
z,u,j|\otimes\sum_{xy}p_{xy}p_{z|ux}\bar{\rho}^{E}_{jxy}.$ (24)

This is a sub-normalised state, with trace

$\displaystyle{\rm tr}\;\bar{\rho}^{ZUJE}$ $\displaystyle=$ $\displaystyle{\rm
tr}_{E}\sum_{j}p_{j}\sum_{xy}p_{xy}P^{j}\rho^{E}_{jxy}P^{j}$ (25)
$\displaystyle=$ $\displaystyle\sum_{j}p_{j}{\rm
tr}_{E}P^{j}\rho^{E}_{j}P^{j}$ (26) $\displaystyle=$
$\displaystyle\sum_{j}p_{j}{\rm
tr}_{E}P^{j}\Big{\\{}(1-\frac{3}{2}\gamma)|0\rangle\langle
0|+\frac{\gamma}{2}\sum_{k=1}^{3}|k\rangle\langle k|\Big{\\}}^{\otimes
n}P^{j}$ (27) $\displaystyle=$
$\displaystyle\sum_{j}p_{j}\sum_{g\in\mathcal{S}_{j}}({\textstyle\frac{\gamma}{2}})^{w(g)}(1-{\textstyle\frac{3}{2}}\gamma)^{n-w(g)}$
(28) $\displaystyle=$
$\displaystyle\sum_{(\tau_{0},\tau_{1},\tau_{2},\tau_{3})\in{\mathcal{T}}}{n\choose\tau_{0},\tau_{1},\tau_{2},\tau_{3}}\cdot(1-{\textstyle\frac{3}{2}}\gamma)^{\tau_{0}}({\textstyle\frac{\gamma}{2}})^{\tau_{1}+\tau_{2}+\tau_{3}}$
(29)

Finally we use Lemma 2.1 to get $\|\rho^{ZUJE}-\bar{\rho}^{ZUJE}\|_{\rm
tr}\leq\sqrt{1\cdot(1-{\rm tr}\bar{\rho}^{ZUJE})}$. $\square$

######  Theorem 3.5.

$\bar{D}\leq{\textstyle\frac{1}{2}}\sqrt{2^{\ell-n}}\sum_{(\tau_{0},\tau_{1},\tau_{2},\tau_{3})\in{\mathcal{T}}}{n\choose\tau_{0},\tau_{1},\tau_{2},\tau_{3}}\left[\sqrt{(1-\gamma)(1-{\textstyle\frac{3}{2}}\gamma)}\right]^{\tau_{0}}\left[\sqrt{{\textstyle\frac{\gamma}{2}}(1-\gamma)}\right]^{\tau_{1}}\left[\sqrt{{\textstyle\frac{1}{2}}\gamma^{2}}\right]^{\tau_{2}+\tau_{3}}.$
(30)

Proof: We use
$P^{j}(\rho^{E}_{jx})^{2}P^{j}-P^{j}\rho^{E}_{jx}P^{j}\rho^{E}_{jx}P^{j}$
$=P^{j}\rho^{E}_{jx}(\mathbb{I}-P^{j})\rho^{E}_{jx}P^{j}$
$=(P_{\mathcal{S}}\rho^{E}_{jx}[\mathbb{I}-P^{j}])(P_{\mathcal{S}}\rho^{E}_{jx}[\mathbb{I}-P^{j}])^{\dagger}$
$\geq 0$ to conclude that $(\bar{\rho}^{E}_{jx})^{2}\leq
P^{j}(\rho^{E}_{jx})^{2}P^{j}$. From Lemma 3.2 we then get
$\sum_{x}p_{x}^{2}(\bar{\rho}^{E}_{jx})^{2}$
$\leq\sum_{g\in\mathcal{S}_{j}}\lambda_{g}(j)|g\rangle\langle g|$.
Substitution into (10) yields

$\displaystyle\bar{D}$ $\displaystyle\leq$
$\displaystyle{\textstyle\frac{1}{2}}\sqrt{2^{\ell}}\sum_{j}p_{j}\sum_{g\in\mathcal{S}_{j}}\sqrt{\lambda_{g}(j)}$
(31)

with the eigenvalues $\lambda_{g}(j)$ as defined in (17). Since these
eigenvalues depend only on the tallies, the sum over strings
$g\in\mathcal{S}_{j}$ reduces to a sum over tallies in ${\mathcal{T}}$ with
multiplicity factor ${n\choose t_{0},t_{\rm eq},t_{+1},t_{+2}}$. Then, since
the set ${\mathcal{T}}$ has no dependence on $j$, the $\sum_{j}p_{j}$ reduces
to 1. $\square$

Note that (30) can also be suggestively written as

$\bar{D}\leq{\textstyle\frac{1}{2}}\sqrt{2^{\ell-n}}\sum_{(\tau_{0},\tau_{1},\tau_{2},\tau_{3})\in{\mathcal{T}}}{n\choose\tau_{0},\tau_{1},\tau_{2},\tau_{3}}\sqrt{(1-{\textstyle\frac{3}{2}}\gamma)^{\tau_{0}}({\textstyle\frac{\gamma}{2}})^{\tau_{1}+\tau_{2}+\tau_{3}}\cdot(1-\gamma)^{\tau_{0}+\tau_{1}}\gamma^{n-\tau_{0}-\tau_{1}}}$
(32)
$={\textstyle\frac{1}{2}}\sqrt{2^{\ell-n}}\sum_{(\tau_{0},\tau_{1},\tau_{2},\tau_{3})\in{\mathcal{T}}}{n\choose\tau_{0},\tau_{1},\tau_{2},\tau_{3}}(1-{\textstyle\frac{3}{2}}\gamma)^{\tau_{0}}({\textstyle\frac{\gamma}{2}})^{\tau_{1}+\tau_{2}+\tau_{3}}\sqrt{\frac{(1-\gamma)^{\tau_{0}+\tau_{1}}\gamma^{n-\tau_{0}-\tau_{1}}}{(1-{\textstyle\frac{3}{2}}\gamma)^{\tau_{0}}({\textstyle\frac{\gamma}{2}})^{\tau_{1}+\tau_{2}+\tau_{3}}}}.$
(33)

The last line resembles an expectation of the square root expression, with a
multinomial probability distribution.

######  Theorem 3.6.

Let $m=(m_{0},m_{1},m_{2},m_{3})\stackrel{{\scriptstyle\rm
def}}{{=}}(n[1-{\textstyle\frac{3}{2}}\gamma],n{\textstyle\frac{\gamma}{2}},n{\textstyle\frac{\gamma}{2}},n{\textstyle\frac{\gamma}{2}})$.
Let ${\mathcal{T}}$ be the set of tallies in an $\alpha$-neighborhood of $m$,
defined as

${\mathcal{T}}=\\{(\tau_{0},\tau_{1},\tau_{2},\tau_{3})\;|\;\tau_{0}+\tau_{1}+\tau_{2}+\tau_{3}=n\;\wedge\;\sum_{a=0}^{3}|\tau_{a}-m_{a}|<\alpha\sqrt{n}\\}.$
(34)

Then

$\displaystyle\sum_{(\tau_{0},\tau_{1},\tau_{2},\tau_{3})\in{\mathcal{T}}}{n\choose\tau_{0},\tau_{1},\tau_{2},\tau_{3}}(1-{\textstyle\frac{3}{2}}\gamma)^{\tau_{0}}({\textstyle\frac{\gamma}{2}})^{\tau_{1}+\tau_{2}+\tau_{3}}>1-16e^{-\frac{1}{2}\alpha^{2}}$
(35) $\displaystyle\|\rho^{ZUJE}-\bar{\rho}^{ZUJE}\|_{\rm tr}\leq
4e^{-\frac{1}{4}\alpha^{2}}$ (36)
$\displaystyle\bar{D}<{\textstyle\frac{1}{2}}\sqrt{2^{\ell-n}}\sqrt{2^{nh(1-{\textstyle\frac{3}{2}}\gamma,{\textstyle\frac{\gamma}{2}},{\textstyle\frac{\gamma}{2}},{\textstyle\frac{\gamma}{2}})-nh(\gamma)}2^{\alpha\sqrt{n}{\textstyle\frac{1}{2}}\log[\frac{2}{\gamma}(1-{\textstyle\frac{3}{2}}\gamma)]}}.$
(37)

Proof: The summation in (22) is a partial sum over a multinomial distribution
which exactly matches the probability in Lemma 2.2. That proves (35). The
upper bound (36) immediately follows. Next, the summation in (33) can be
interpreted (up to a factor $1-16e^{-{\textstyle\frac{1}{2}}\alpha^{2}}<1$) as
an expectation of the square root expression, for a multinomial distribution
restricted to the set ${\mathcal{T}}$. We upper bound the expectation by the
maximum attainable value on the set ${\mathcal{T}}$,

$\bar{D}<{\textstyle\frac{1}{2}}\sqrt{2^{\ell-n}}\max_{(\tau_{0},\tau_{1},\tau_{2},\tau_{3})\in{\mathcal{T}}}\sqrt{\frac{(1-\gamma)^{\tau_{0}+\tau_{1}}\gamma^{n-\tau_{0}-\tau_{1}}}{(1-{\textstyle\frac{3}{2}}\gamma)^{\tau_{0}}({\textstyle\frac{\gamma}{2}})^{\tau_{1}+\tau_{2}+\tau_{3}}}}.$
(38)

The fraction under the square root equals
$[\frac{1-\gamma}{1-{\textstyle\frac{3}{2}}\gamma}]^{\tau_{0}}[{\textstyle\frac{2}{\gamma}}(1-\gamma)]^{\tau_{1}}2^{\tau_{2}+\tau_{3}}$.
This is maximized by increasing $\tau_{1}$ as much as possible, at the cost of
$\tau_{0}$, i.e. $\tau_{0}=m_{0}-{\textstyle\frac{1}{2}}\alpha\sqrt{n}$,
$\tau_{1}=m_{1}+{\textstyle\frac{1}{2}}\alpha\sqrt{n}$, $\tau_{2}=m_{2}$,
$\tau_{3}=m_{3}$. Substitution into (38) yields (37). $\square$

##  4 Key rate

We discuss the key rate that follows from Theorem 3.6. Say that we want both
$\bar{D}$ and the expression $\|\rho^{ZUJE}-\bar{\rho}^{ZUJE}\|_{\rm tr}$ to
be upper bounded by a constant $\varepsilon$. Then according to (36) we need
to set $\alpha=2\sqrt{\ln(4/\varepsilon)}$. Substituting $\alpha$ into (37) we
find that $\ell$ must be set to

$\ell(\varepsilon)=n+2-nh(1-{\textstyle\frac{3}{2}}\gamma,{\textstyle\frac{\gamma}{2}},{\textstyle\frac{\gamma}{2}},{\textstyle\frac{\gamma}{2}})+nh(\gamma)-\sqrt{n\ln{\textstyle\frac{4}{\varepsilon}}}\cdot\log[\frac{2}{\gamma}(1-{\textstyle\frac{3}{2}}\gamma)]-2\log\frac{1}{\varepsilon}.$
(39)

The rate is obtained by subtracting from $\ell$ the size of the syndrome and
the postselection penalty $30\log(n+1)$, and then normalising by a factor $n$.
We assume the existence of an almost-perfect error correcting code, such that
the size of the syndrome is close to $nh(\gamma)$.

${\rm Rate}\approx
1-h(1-{\textstyle\frac{3}{2}}\gamma,{\textstyle\frac{\gamma}{2}},{\textstyle\frac{\gamma}{2}},{\textstyle\frac{\gamma}{2}})-\frac{1}{\sqrt{n}}\sqrt{\ln{\textstyle\frac{4}{\varepsilon}}}\cdot\log[\frac{2}{\gamma}(1-{\textstyle\frac{3}{2}}\gamma)]-\frac{30\log
n}{n}-\frac{2}{n}\log\frac{1}{\varepsilon}.$ (40)

Note that (i) for $n\to\infty$ the asymptotic rate (11) is recovered; (ii)
leading-order finite size corrections of order
$\sqrt{{\textstyle\frac{1}{n}}\ln{\textstyle\frac{1}{\varepsilon}}}$ occur in
the standard proof technique too. In Fig. 1 we show how the obtained rate
tends to the asymptotic result as $n$ increases.

RateQBER$\varepsilon=2^{-128}$

${\scriptstyle{\rm asymptotic}}$

${\scriptstyle{\rm no\;smoothing}}$

${\scriptstyle n=10^{5}}$

${\scriptscriptstyle n=10^{6}}$

Figure 1: Solid curves: The rate (40) as a function of the QBER ($\gamma$) at
$\varepsilon=2^{-128}$, plotted for $n=10^{5}$, $n=10^{6}$ and $n=10^{7}$. The
dotted curve is the asymptotic rate (11). The dashed curve is the rate
obtained from the without-smoothing bound (18) at $n=10^{5}$.

##  5 Discussion

The standard approach to smoothing departs from the Bell-diagonal structure of
$\sum_{x}p_{x}^{2}(\rho^{E}_{jx})^{2}$. We have shown that it is possible to
get a good finite-size result by retaining this structure. It is interesting
to note that our smoothing procedure is a simple restriction from full
summation over $\mathcal{G}=\\{0,1,2,3\\}^{n}$ to the typical set
$\mathcal{S}_{j}\subset\mathcal{G}$. In contrast, the smoothing in [19]
requires two different operations, one to reduce a Rényi-0 entropy and one to
increase a Rényi-2 entropy.

We suggest a number of topics for future work. (i) We did not try to get the
sharpest possible bounds. We expect that the constant in the
${\mathcal{O}}(1/\sqrt{n})$ finite-size contribution can be reduced. In
particular, the rate dip at small QBER may be avoided. At low QBER one can
just switch to the result without smoothing, but that is not very elegant.
(ii) The proof method may be applied to other qubit-based schemes.

Acknowledgments
Part of this work was supported by NGF Quantum Delta NL KAT-2.

##  Appendix A Appendix: Key Recycling

###  A.1 6-state Quantum Key Recycling

In Quantum Key Recycling (QKR) [2, 6, 7, 24, 13] the measurement bases are
known beforehand, as part of a secret key shared by Alice and Bob. In case of
an accept, it is safe to re-use this secret. Not having to discuss the
measurement bases can eliminate one round of communication between Alice and
Bob. Furthermore, there are no basis mismatches and hence no qubits have to be
discarded.

A 6-state QKR scheme was studied in [13]. It encrypts an $\ell$-bit plaintext
into a ciphertext that consists of $n$ qubits and some classical data,
including a one-time padded syndrome. Part of the $\ell$-bit plaintext is
reserved to carry the one-time pad for the next round. The security analysis
is very close to QKD. A quantity $\bar{D}_{\rm qkr}$ similar to the trace
distance $\bar{D}$ (10) needs to be made small. It was shown that
$\bar{D}_{\rm qkr}\leq{\textstyle\frac{1}{2}}\sqrt{2^{\ell-n}}{\rm
tr}\sqrt{\mathbb{E}_{jx}(\bar{\rho}^{E}_{jx})^{2}}$, where $j$ is uniform.
Further analysis yields exactly the same Rényi entropies as for QKD and the
same asymptotic rate (11). (The QKR rate is defined as the length of the
actual message divided by the number of qubits).

It was noted in [13] that the expression $\mathbb{E}_{jx}(\rho^{E}_{jx})^{2}$,
i.e. without smoothing, is diagonal in the Bell basis. This was exploited to
obtain, without smoothing, a finite-size result for the QKR rate. However,
this rate is significantly lower than (11).

###  A.2 Double smoothing

The explicit-smoothing analysis for QKR is a bit more involved than for QKD.
The additional average over the basis choices $j\in\\{1,2,3\\}^{n}$ washes
away the distinction between three of the tallies, and allows for multiple
values of the noise $r=\bar{x}\oplus y\in\\{0,1\\}^{n}$ to fit a string
$g\in\mathcal{G}$, whereas in QKD the $r$ is entirely fixed by $g$. Hence the
eigenvalues of $\mathbb{E}_{j}\sum_{x}p_{x}^{2}(\rho^{E}_{jx})^{2}$ involve an
additional summation over $r$, whose domain we need to restrict separately in
order to get a good result for the rate. This leads to a two-step smoothing
procedure that resembles the approach in [19]. First we restrict summations
over $r$ to a subset of Hamming weights
${\mathcal{W}}\subset\\{0,\ldots,n\\}$. We write the truncated version of
$\rho^{E}_{jx}$ as $\varphi^{E}_{jx}$,

$\varphi^{E}_{jx}=\sum_{r:w(r)\in{\mathcal{W}}}\mu_{r}\bigotimes_{i=1}^{n}\sigma^{j_{i}}_{x_{i},\bar{x}_{i}\oplus
r_{i}}\mbox{ with }\mu_{r}=(1-\gamma)^{n-w(r)}\gamma^{w(r)}.$ (41)

Next we apply a projection $P_{\mathcal{S}}$ that restricts $\mathcal{G}$ to a
subset $\mathcal{S}\subset\mathcal{G}$, but now not dependent on $j$. We get
$\bar{\rho}^{E}_{jx}=P_{\mathcal{S}}\varphi^{E}_{jx}P_{\mathcal{S}}$. Next we
bound $(\bar{\rho}^{E}_{jx})^{2}\leq
P_{\mathcal{S}}(\varphi^{E}_{jx})^{2}P_{\mathcal{S}}$, analogous to the QKD
case, to obtain $\mathbb{E}_{j}\sum_{x}p_{x}^{2}(\bar{\rho}^{E}_{jx})^{2}\leq$
$P_{\mathcal{S}}\mathbb{E}_{j}\sum_{x}p_{x}^{2}(\varphi^{E}_{jx})^{2}P_{\mathcal{S}}$.
We write
$(\varphi^{E}_{jx})^{2}=\sum_{r:w(r)\in{\mathcal{W}}}\mu_{r}^{2}\bigotimes_{i=1}^{n}\sigma^{j_{i}}_{x_{i},\bar{x}_{i}\oplus
r_{i}}$. The averaged version of Lemma 3.1 is

$\mathbb{E}_{jx}\sigma^{j}_{x,\bar{x}\oplus
r}=\left\\{\begin{array}[]{ll}r=0:&\frac{1-{\textstyle\frac{3}{2}}\gamma}{1-\gamma}|0\rangle\langle
0|+\frac{\gamma/6}{1-\gamma}\sum_{j=1}^{3}|j\rangle\langle j|\\\
r=1:&{\textstyle\frac{1}{3}}\sum_{j=1}^{3}|j\rangle\langle
j|\end{array}\right.$ (42)

This leads to a version of Lemma 3.2 with different constants and different
tallies,

$P_{\mathcal{S}}\mathbb{E}_{j}\sum_{x}p_{x}^{2}(\varphi^{E}_{jx})^{2}P_{\mathcal{S}}=\sum_{g\in\mathcal{S}}\Lambda_{g}|g\rangle\langle
g|$ (43)

with

$\displaystyle\Lambda_{g}$ $\displaystyle=$ $\displaystyle
2^{-n}\sum_{\stackrel{{\scriptstyle r:w(r)\in{\mathcal{W}}}}{{g_{i}=0\implies
r_{i}=0}}}\mu_{r}^{2}(\frac{1-{\textstyle\frac{3}{2}}\gamma}{1-\gamma})^{t_{0}(g)}(\frac{1}{3})^{w(r)}(\frac{\gamma/6}{1-\gamma})^{n-t_{0}(g)-w(r)}$
(44) $\displaystyle=$ $\displaystyle
2^{-n}(1-\gamma)^{t_{0}(g)}(1-{\textstyle\frac{3}{2}}\gamma)^{t_{0}(g)}(\frac{\gamma}{6})^{n-t_{0}(g)}\sum_{w\in{\mathcal{W}}}{n-t_{0}(g)\choose
w}(2\gamma)^{w}(1-\gamma)^{n-t_{0}(g)-w}.$ (45)

The $r$-summation in (44) is restricted to those strings $r\in\\{0,1\\}^{n}$
that have $r_{i}=0$ in all locations $i$ where $g_{i}=0$. This leads to the
combinatorial factor ${n-t_{0}\choose w}$. Note that taking the full summation
$\sum_{w=0}^{n-t_{0}}$ would reproduce the unsmoothed eigenvalues from [13].
Compared to the QKD proof, we need extra inequalities to bound the
$w$-summation. Let $w_{\rm min}$ be the lowest value in ${\mathcal{W}}$. We
bound $\Lambda_{g}$ as

$\Lambda_{g}<2^{-n}(1-{\textstyle\frac{3}{2}}\gamma)^{t_{0}}({\textstyle\frac{\gamma}{2}})^{n-t_{0}}({\textstyle\frac{1}{3}})^{n-t_{0}}|{\mathcal{W}}|{n-t_{0}\choose
w_{\rm min}}(2\gamma)^{w_{\rm min}}(1-\gamma)^{n-w_{\rm min}}$ (46)

Using Stirling’s approximation $\sqrt{2\pi
n}(\frac{n}{e})^{n}e^{\frac{1}{12n+1}}<n!<\sqrt{2\pi
n}(\frac{n}{e})^{n}e^{\frac{1}{12n}}$ for the binomial we get

$\displaystyle\Lambda_{g}$ $\displaystyle<$ $\displaystyle
2^{-n}(1-{\textstyle\frac{3}{2}}\gamma)^{t_{0}}({\textstyle\frac{\gamma}{2}})^{n-t_{0}}\gamma^{w_{\rm
min}}(1-\gamma)^{n-w_{\rm min}}$ (47)
$\displaystyle\cdot\frac{|{\mathcal{W}}|}{\sqrt{2\pi w_{\rm
min}}}\cdot\frac{2^{w_{\rm
min}}({\textstyle\frac{1}{3}})^{n-t_{0}}(1-\frac{t_{0}}{n})^{n-t_{0}+{\textstyle\frac{1}{2}}}}{(\frac{w_{\rm
min}}{n})^{w_{\rm min}}(1-\frac{t_{0}}{n}-\frac{w_{\rm
min}}{n})^{n-t_{0}-w_{\rm min}+{\textstyle\frac{1}{2}}}}.$

Note that for $(t_{0}\approx n-n{\textstyle\frac{3}{2}}\gamma,w_{\rm
min}\approx n\gamma)$ and $|{\mathcal{W}}|\propto\sqrt{n\gamma(1-\gamma)}$
both fractions in (47) are almost constants. Analogous to (33) we can obtain a
bound

$\displaystyle\bar{D}_{\rm qkr}$ $\displaystyle<$
$\displaystyle{\textstyle\frac{1}{2}}\sqrt{2^{\ell-n}}\sum_{(\tau_{0}\cdots\tau_{3})\in{\mathcal{T}}}{n\choose\tau_{0},\tau_{1},\tau_{2},\tau_{3}}(1-{\textstyle\frac{3}{2}}\gamma)^{\tau_{0}}({\textstyle\frac{\gamma}{2}})^{\tau_{1}+\tau_{2}+\tau_{3}}\sqrt{\frac{\gamma^{w_{\rm
min}}(1-\gamma)^{n-w_{\rm
min}}}{(1-{\textstyle\frac{3}{2}}\gamma)^{\tau_{0}}({\textstyle\frac{\gamma}{2}})^{\tau_{1}+\tau_{2}+\tau_{3}}}}$
(48) $\displaystyle\cdot\sqrt{\frac{|{\mathcal{W}}|}{\sqrt{2\pi w_{\rm
min}}}\cdot\frac{2^{w_{\rm
min}}({\textstyle\frac{1}{3}})^{n-\tau_{0}}(1-\frac{\tau_{0}}{n})^{n-\tau_{0}+{\textstyle\frac{1}{2}}}}{(\frac{w_{\rm
min}}{n})^{w_{\rm min}}(1-\frac{\tau_{0}}{n}-\frac{w_{\rm
min}}{n})^{n-\tau_{0}-w_{\rm min}+{\textstyle\frac{1}{2}}}}}$

which has the form of an incomplete multinomial expectation of the square root
expression. We can set ${\mathcal{T}}$ as in Theorem 3.6 and similarly upper
bound the mean by the maximum; the maximum is again attained by setting
$\tau_{0}=\tau_{0}^{*}\stackrel{{\scriptstyle\rm
def}}{{=}}n(1-{\textstyle\frac{3}{2}}\gamma)-{\textstyle\frac{1}{2}}\alpha\sqrt{n}$.
Thus the obtained bound is

$\displaystyle\bar{D}_{\rm qkr}$ $\displaystyle<$
$\displaystyle{\textstyle\frac{1}{2}}\sqrt{2^{\ell-n}}\sqrt{2^{nh(1-{\textstyle\frac{3}{2}}\gamma,{\textstyle\frac{\gamma}{2}},{\textstyle\frac{\gamma}{2}},{\textstyle\frac{\gamma}{2}})}\gamma^{w_{\rm
min}}(1-\gamma)^{n-w_{\rm
min}}(\frac{\gamma/2}{1-{\textstyle\frac{3}{2}}\gamma})^{-{\textstyle\frac{1}{2}}\alpha\sqrt{n}}}$
(49) $\displaystyle\cdot\sqrt{\frac{|{\mathcal{W}}|}{\sqrt{2\pi w_{\rm
min}}}\cdot\frac{2^{w_{\rm
min}}({\textstyle\frac{1}{3}})^{n-\tau_{0}^{*}}(1-\frac{\tau_{0}^{*}}{n})^{n-\tau_{0}^{*}+{\textstyle\frac{1}{2}}}}{(\frac{w_{\rm
min}}{n})^{w_{\rm min}}(1-\frac{\tau_{0}^{*}}{n}-\frac{w_{\rm
min}}{n})^{n-\tau_{0}^{*}-w_{\rm min}+{\textstyle\frac{1}{2}}}}}.$

The asymptotic rate is the same as for QKD.

## References

  * [1] M. Ben-Or, M. Horodecki, D.W. Leung, D. Mayers, and J. Oppenheim.  The universal composable security of quantum key distribution.  In Theory of Cryptography, volume 3378 of LNCS, pages 386–406, 2005.
  * [2] C.H. Bennett, G. Brassard, and S. Breidbart.  Quantum Cryptography II: How to re-use a one-time pad safely even if P=NP.  Unpublished manuscript, 1983.
  * [3] E. Biham, M. Boyer, P.O. Boykin, T. Mor, and V. Roychowdhury.  A proof of the security of Quantum Key Distribution.  In Symposium on the Theory of Computing, pages 715–724. ACM, 2000\.
  * [4] J. Bretagnolle and C. Huber.  Lois empiriques et distance de Prokhorov.  In P.A. Meyer C. Oellacherie and M. Weil, editors, Séminaire de Probabilités XII, pages 332–341, 1978.  Lecture notes in mathematics 649.
  * [5] M. Christandl, R. König, and R. Renner.  Postselection technique for quantum channels with applications to quantum cryptography.  Phys. Rev. Lett., 102:020504, Jan 2009.
  * [6] I. Damgård, T. B. Pedersen, and L. Salvail.  A quantum cipher with near optimal key-recycling.  In Advances in Cryptology - CRYPTO 2013, pages 494–511. Springer, Berlin, Heidelberg, 2013.
  * [7] S. Fehr and L. Salvail.  Quantum authentication and encryption with key recycling.  In Advances in Cryptology - ASIACRYPT 2017, pages 611–641. Springer, Cham, 2017.
  * [8] D. Gottesman and H.-K. Lo.  Proof of security of quantum key distribution with two-way classical communications.  IEEE Trans. Inf. Theory, 49:457, 2003.
  * [9] H. Inamori.  Security of EPR-based Quantum Key Distribution using three bases, 2000\.  https://arxiv.org/abs/quant-ph/0008076.
  * [10] R. König, R. Renner, and C. Schaffner.  The operational meaning of min- and max-entropy.  IEEE Trans. on Information Theory, 55(9):4337, 2009.
  * [11] B. Kraus, N. Gisin, and R. Renner.  Lower and upper bounds on the secret key rate for quantum key distribution protocols using one-way classical communication.  Phys.Rev.Lett., 95:080501, 2005.
  * [12] D. Leermakers and B. Škorić.  Optimal attacks on qubit-based Quantum Key Recycling.  Quantum Information Processing, 17(3):57, 2018.
  * [13] D. Leermakers and B. Škorić.  Security proof for quantum key recycling with noise.  Quantum Information and Computation, 19(11-12):913–934, 2019.
  * [14] H.-K. Lo.  Proof of unconditional security of six-state quantum key distribution scheme.  Quantum Information and Computation, 1(2):81–94, 2001.
  * [15] D. Mayers.  Quantum key distribution and string oblivious transfer in noisy channels.  In CRYPTO 1996, pages 343–357. Springer Berlin, 1996.  Lecture Notes in Computer Science, Vol. 1109.
  * [16] M. Müller-Lennert, F. Dupuis, O. Szehr, S. Fehr, and M. Tomamichel.  On quantum Rényi entropies: a new generalization and some properties .  J. Math. Phys., 54:122203, 2013.
  * [17] R. Renner.  Security of quantum key distribution.  International Journal of Quantum Information, 6(01):1–127, 2008\.
  * [18] R. Renner, N. Gisin, and B. Kraus.  Information-theoretic security proof for quantum-key-distribution protocols.  Phys.Rev.A, 72:012332, 2005.
  * [19] R. Renner and R. König.  Universally composable privacy amplification against quantum adversaries.  In Theory of Cryptography, volume 3378 of LNCS, pages 407–425, 2005.
  * [20] Z. Shadman, H. Kampermann, T. Meyer, and D. Bruß.  Optimal eavesdropping on noisy states in quantum key distribution.  Int. J. of Quantum Information, 07(01):297, 2009.
  * [21] P. Shor and J. Preskill.  Simple proof of security of the BB84 quantum key distribution protocol.  Phys.Rev.Lett., 85:441, 2000.
  * [22] M. Tomamichel and A. Leverrier.  A largely self-contained and complete security proof for quantum key distribution.  Quantum, 1:14, 2017.
  * [23] M. Tomamichel, C.C.W. Lim, N. Gisin, and R. Renner.  Tight finite-key analysis for quantum cryptography .  Nature Communications, 3, 2012.  article number 634.
  * [24] B. Škorić and M. de Vries.  Quantum Key Recycling with 8-state encoding (The Quantum One-Time Pad is more interesting than we thought).  International Journal of Quantum Information, 15(3):1750016, 2017\.