# Knowledge-Driven Program Synthesis via Adaptive Replacement Mutation and
Auto-constructed Subprogram Archives

Yifan He  University of Tsukuba
Tsukuba, Japan
<EMAIL_ADDRESS>Claus Aranha  University of Tsukuba
Tsukuba, Japan
<EMAIL_ADDRESS>Tetsuya Sakurai  University of Tsukuba
Tsukuba, Japan
<EMAIL_ADDRESS>
###### Abstract

We introduce Knowledge-Driven Program Synthesis (KDPS) as a variant of the
program synthesis task that requires the agent to solve a sequence of program
synthesis problems. In KDPS, the agent should use knowledge from the earlier
problems to solve the later ones. We propose a novel method based on PushGP to
solve the KDPS problem, which takes subprograms as knowledge. The proposed
method extracts subprograms from the solution of previously solved problems by
the _Even Partitioning_ (EP) method and uses these subprograms to solve the
upcoming programming task using _Adaptive Replacement Mutation_ (ARM). We call
this method PushGP+EP+ARM. With PushGP+EP+ARM, no human effort is required in
the knowledge extraction and utilization processes. We compare the proposed
method with PushGP, as well as a method using subprograms manually extracted
by a human. Our PushGP+EP+ARM achieves better train error, success count, and
faster convergence than PushGP. Additionally, we demonstrate the superiority
of PushGP+EP+ARM when consecutively solving a sequence of six program
synthesis problems.

###### Index Terms:

program synthesis, PushGP, adaptive replacement mutation, subprogram archive

##  I Introduction

_Program Synthesis_ (PS) are techniques that automatically compose computer
programs to solve a certain task. PS is useful in fields such as automatic bug
fixing, automatic program completion, and low-level code development. PS is a
key issue in Artificial General Intelligence [1]. _Genetic Programming_ (GP)
[2] is an Evolutionary Algorithm that searches computer programs by selecting
and updating a population of program candidates. Some GP variants [3, 4, 5]
can solve problems in a famous PS benchmark suite [6] efficiently.

However, the difference between GP and a human programmer is still obvious. As
an Evolutionary Algorithm, GP heavily utilizes random sampling; while a human
programmer does not write random programs. Humans write programs based on
their knowledge, either the domain knowledge about the problem or the
programming skills from previous experiences.

Recently, several studies [7, 8, 9, 10, 11] have attempted to incorporate
knowledge in PS, improving the synthesis performance. However, some of these
methods have drawbacks in requiring extra information [7, 8] and human efforts
[11].

In our prior study, we proposed the _Adaptive Replacement Mutation_ (ARM)
[11]. The ARM is a mutation method designed for a well-known GP variant called
PushGP [3]. ARM uses subprograms from an archive as knowledge, automatically
selecting useful subprograms from the archive according to the search history.
Although the ARM provides a way to use existing knowledge from an archive, the
archive itself was made by a human. Moreover, it is questionable whether the
subprograms written by humans are included in the programs generated by
PushGP.

In this study, we focus on the task where an agent is required to solve a
sequence of PS problems. The agent should learn knowledge from each problem in
the sequence and apply this knowledge to improve its performance in later
problems. Ideally, this procedure should not require human interference or
extra external information. We call this task the _Knowledge-Driven Program
Synthesis_ (KDPS) problem (Section III).

We propose a novel method to solve the KDPS problem based on PushGP [3]. This
method takes subprograms as knowledge. The proposed method consecutively
solves programming tasks, extracts subprograms from the solution of solved
problems, and uses subprograms to solve an upcoming problem. To extract
subprograms, we propose _Even Partitioning_ (EP) which divides a solution into
several parts with equal lengths. To use these subprograms, we apply ARM [11].
We name our method PushGP+EP+ARM. The details of the proposed methods,
including EP and ARM, are given in Section IV.

We analyze the proposed method in two KDPS tasks. The “composite task”
(Section V) includes three “composite” PS problems. For each problem,
PushGP+EP+ARM prepares the knowledge archive based on the component problems.
The “sequential task” (Section VI) has six problems that must be solved in
sequence, including the composite and component problems of the previous
“composite task”. PushGP+EP+ARM updates the knowledge archive at each step of
the sequence. PushGP+EP+ARM achieves a better overall success rate and
convergence speed in the composite task, and in the later stages of the
sequential task, showing that it can create a useful knowledge archive.
However, the comparison with a human-curated archive shows that there is still
room for improvement.

Our main contributions are as follows.

  1. 1.

We introduce a new type of task called the KDPS problem. KDPS includes a
sequence of single PS problems. The agent is required to solve the single PS
problems, extract knowledge, and use it in the later PS problems.

  2. 2.

We propose EP to extract subprograms from the solution of a solved problem. We
propose PushGP+EP+ARM to solve KDPS problems based on EP and our previous work
on ARM [11].

  3. 3.

We provide our implementation of the proposed method based on PyshGP [12] and
experimental scripts in an online repository
111https://github.com/Y1fanHE/ssci2022

##  II Background

###  II-A Program Synthesis

PS, also known as automatic programming, focuses on building an intelligent
agent that writes computer programs to solve specific tasks with minimal human
effort. Programs are sequences of instructions and a task could be described
as a set of I/O examples. For instance, a task that adds two integers could be
describes as {[in=(1,1), out=2], [in=(1,2), out=3], ...}.

Therefore, PS can be formalized as the optimization problem in (1), which
searches a sequence of instructions to minimize the difference between actual
and expected program outputs. In (1), $\mathbf{p}$ is a program while
$P_{instr}$ includes all feasible programs based on the instruction set
$instr$; $in_{i}$ and $out_{i}$ are the $i$-th I/O example.

$\min_{\mathbf{p}\in{P_{instr}}}\Sigma_{i=1}^{N}||\mathbf{p}(in_{i})-out_{i}||$
(1)

###  II-B PushGP

Since Koza’s first work on his tree-based GP [2], several variants of GP [13,
14, 15, 3] have been applied to solve PS problems. Among these methods, we
highlight PushGP [14, 3, 5], which generates programs based on a Turing-
complete language called Push.

Push uses the list to store a program and runs it using multiple stacks of
different data types based on the following rules.

  1. 1.

To execute an instruction, the interpreter pops the required arguments from
the corresponding stacks.

  2. 2.

After executed the instruction, the results are pushed to the corresponding
stacks.

  3. 3.

If the interpreter cannot find enough arguments from the stacks, the
instruction will be skipped.

Based on the third rule, any sequence of Push instructions can form a valid
Push program. Helmuth et al. proposed a variant of PushGP using lexicase
selection and uniform mutation by addition and deletion (UMAD) [3]. This
variant was further improved by applying down-sampled lexicase selection [5].

###  II-C Incorporating knowledge in Program Synthesis

An obvious difference between GP and human programmers is that a human can
learn knowledge from his experiences and use knowledge in upcoming tasks.
Several recent works have attempted to incorporate knowledge in PS [8, 7, 9,
10, 11, 16]. Some studies require extra information such as text description
[7] and human-written code [8, 11, 16].

Helmuth et al. proposed to transfer the instructions from the solution of
other problems to construct the instruction set of PushGP [9]. Wick et al.
proposed to use the whole individuals of a problem as a part of the initial
population when solving similar problems [10]. Both studies [9, 10] extract
knowledge from the solutions of the problems that have been solved by GP.

Recently, we came up with a mutation method that allows using subprograms in a
prepared archive with PushGP [11]. Compared with the study by Helmuth [9], a
subprogram can capture more information from the solution than a single
instruction. Compared to Wick’s study [10], the way to use an external archive
of knowledge might be more efficient when the number of the problems to
transfer is large. However, in our prior study [11], the subprogram archives
are extracted by hand from human-written solutions. This step is non-trivial
and requires a lot of human effort. Also, considering the case where a GP is
able to extract knowledge from programs it wrote in the past, it is
questionable whether the source programs would look similar to human written
ones.

##  III Knowledge-Driven Program Synthesis

Human programmers can learn from the programming problems that they have
solved before and apply what they have learned to solve the upcoming problems.
We suggest that the ability of learning is vital for generating complex
programs.

Therefore, we introduce a type of task where an agent is required to solve a
sequence of PS problems. Usually, these PS problems are related to each other.
When solving a new problem, the agent should use the knowledge learned from
previously solved problems. We call this type of task _Knowledge-Driven
Program Synthesis_ (KDPS).

The formalization of KDPS is presented in (2). $S^{j}$ is one of the $M$ PS
problems in (1) to solve, containing $N_{j}$ pairs of I/O.
$\hat{\mathbf{p}}^{j}$ and $K^{j}$ are the solution program and the knowledge
that learned from solving $S^{j}$, respectively. $S^{j}$ is solved by
$\mathrm{Solve}(\cdot)$ based on the knowledge from the previously solved
problems $K^{j-1}\cup\dots K^{0}$. $K^{0}$ is the initial knowledge before
solving the first problem $S^{1}$. By default, $K^{0}$ is empty.

$\begin{cases}&\hat{\mathbf{p}}^{j},K^{j}\leftarrow\mathrm{Solve}(S^{j}|K^{j-1}\cup\dots\cup{K}^{0})\\\
s.t.&S=\\{S^{1},\dots,S^{M}\\}\\\
&S^{j}=\\{({in}^{j}_{1},{out}^{j}_{1}),\dots,({in}^{j}_{N_{j}},{out}^{j}_{N_{j}})\\}\\\
&K^{0}=\emptyset\end{cases}$ (2)

To learn knowledge from solving a problem, it is not necessary to use its
solution program. However, as an initial step, we assume all the knowledge
from solving $S^{j}$ are extracted from its solution programs
$\hat{\mathbf{p}}^{j}$ as in (3).

$K^{j}\leftarrow\mathrm{Extract}(\hat{\mathbf{p}}^{j})$ (3)

##  IV Proposed Method

Figure 1: An example of solving Knowledge-Driven Program Synthesis with the
proposed method. The method solves problems with PushGP, extract subprograms
with _Even Partitioning_ (EP), and uses subprograms with _Adaptive Replacement
Mutation_ (ARM).

To solve KDPS problems, we propose a method based on PushGP [3] to
consecutively solve programming tasks, extract knowledge from the solutions,
and utilize knowledge in the next problem. This method is entirely automated.

We use subprograms, the sub-sequences of Push instructions, as knowledge. The
subprograms hold partial information about the original program. Moreover, any
sequence of Push instructions is valid to run. Therefore, we can easily take a
subprogram and use it in a different program.

Fig. 1 illustrates an example of solving a KDPS problem (a sequence of three
PS problems) with our proposed method. Our method solves Problem 1 with PushGP
[3] and extracts Subprogram Archive (SA) 1 from its solution (Program 1) with
_Even Partitioning_ (EP). This archive is used by _Adaptive Replacement
Mutation_ (ARM) [11] when searching for the solution of Problem 2. Similarly,
we use SA 1 and SA 2 when solving Problem 3. The details of EP and ARM are
provided in the next two subsections.

###  IV-A Even Partitioning

EP is a simple method that divides a program into $n$ parts with equal
lengths. For example, a program with 15 instructions is divided into
subprograms with lengths of (3, 3, 3, 3, 3) if $n$ = 5; the same program is
divided into subprograms with lengths of (4, 4, 4, 3) if $n$ = 4.

Before dividing the solution program, a simplification operation is performed
to remove the redundant instructions (i.e., instructions without enough
arguments to execute). After the dividing step, the subprograms are stored
into an archive for the future use.

###  IV-B Adaptive Replacement Mutation

Algorithm 1 PushGP with Adaptive Replacement Mutation

0: subprogram archive $K$ where every subprogram $\mathbf{k}$ holds a quality
metric $Q_{\mathbf{k}}$ = 0;

1: $P$ ← initialize_population();

2: while termination criteria is not satisfied do

3: $P^{\prime}$ ← $\emptyset$;

4: for $i$ ← 1 to $|P|$ do

5: $\mathbf{p}$ ← lexicase_selection($P$);

6: if rand() $<$ $r_{arm}$ then

7: if rand() $<$ $r_{prop}$ then

8: $\mathbf{k}$ ← proportional_selection($K$);

9: else

10: $\mathbf{k}$ ← random_selection($K$);

11: $\mathbf{p}^{\prime}$ ← replacement_mutation($\mathbf{p}$, $\mathbf{k}$);

12: if $f(\mathbf{p}^{\prime})\prec f(\mathbf{p})$ then

13: $Q_{\mathbf{k}}$ ← $Q_{\mathbf{k}}$ \+ 1;

14: else

15: $\mathbf{p}^{\prime}$ ← umad_mutation($\mathbf{p}$);

16: $P^{\prime}$ ← $P^{\prime}$ $\cup$ {$\mathbf{p}^{\prime}$};

17: $P$ ← $P^{\prime}$;

ARM [11] is a mutation method proposed for PushGP, which incorporates a
prepared archive of subprograms during the search. ARM contains a Replacement
Mutation (RM) and an adaptive strategy.

RM requires a parent candidate (of length $l_{1}$) from the PushGP population
and a subprogram (of length $l_{2}$) from the prepared archive. RM replaces a
random partition (of length $l_{2}$) of the parent candidate using the
subprogram. If $l_{1}<l_{2}$, the entire parent is replaced by the subprogram.

The adaptive strategy in ARM is designed to automatically select helpful
subprograms when an archive contains both helpful and unhelpful subprograms.
The idea is similar to parameter adaptation in many Self-adaptive Evolutionary
Algorithms such as JADE [17]. Originally, ARM collects and stores the helpful
subprograms that improve the parent candidates by RM into a working archive.
This working archive, which consists of helpful subprograms, is used as one of
the sources to select subprograms in the later generations.

In this study, we use a slightly different implementation of ARM from the
original [11], using proportional selection to select subprograms rather than
collecting subprograms in an extra archive. The proportion to select a
subprogram depends on how many times that it improves parents.

We provide the pseudo code of PushGP (using lexicase selection and UMAD
mutation) with ARM in Algorithm 1. $Q_{\mathbf{k}}$ is the count that a
subprogram $\mathbf{k}$ improves the parents during the search. The
probability in proportional selection is computed as in (4).

$p(\mathbf{k})=\frac{Q_{\mathbf{k}}}{\Sigma_{\mathbf{k}_{i}\in{K}}Q_{\mathbf{k}_{i}}}$
(4)

$r_{arm}$ is the probability to perform ARM and $r_{prop}$ is the probability
to perform the proportional selection of subprograms. In Line 12 of Algorithm
1, the symbol “$\prec$” means “better than”. In our implementation, a solution
is better than another if it solves more I/O cases (i.e., contains more “0” in
its error vector).

In some cases, the subprograms may include more inputs than the current
problem (e.g., a subprogram contains input_3 while the current problem only
takes two inputs). We replace the input in the subprograms with a random input
of the current problem.

##  V Experiment I: Composite KDPS Task

In this experiment, we focus on an intermediate step of the KDPS problem (Fig.
1). That is, to solve a composite problem with our proposed method after
solving its sub-problems.

###  V-A Comparison methods

We compare the following three methods.

  * •

PushGP+EP+ARM: PushGP with ARM; the subprogram archives are extracted using
EP.

  * •

PushGP+HP+ARM: PushGP with ARM; the subprogram archives are extracted by human
(HP: human partitioning).

  * •

PushGP: the original PushGP [3].

###  V-B Experimental procedures

We use PushGP [3] to solve three problems in PSB1 [6]. They are “small or
large” (SL), “compare string lengths” (CSL), and “median” (MD). We take the
best and shortest solutions among 25 runs (after 5000 steps of simplification)
of the three problems to generate subprogram archives. For PushGP+EP+ARM, We
use EP to get five equal-length subprograms for every best and shortest
solution automatically. The subprograms used by PushGP+HP+ARM are partitions
of the same solutions, however, devised by a human.

We then solve the composite problems of SL, CSL, and MD. When solving a
composite problem, PushGP+EP+ARM and PushGP+HP+ARM will use subprogram
archives generated from solutions of the corresponded sub-problems by EP and
HP, respectively. We compare the three methods on three composite problems.

  * •

Median String Length (MDSLEN): given 3 strings, print the median of their
lengths.

  * •

Small or Large Median (SLMD): given 4 integers $a$, $b$, $c$, $d$, print
“small” if median($a$,$b$,$c$) $<$ $d$ and “large” if median($a$,$b$,$c$) $>$
$d$ (and nothing if median($a$,$b$,$c$) = $d$).

  * •

Small or Large String (SLSTR): given a string $n$, print “small” if len($n$)
$<$ 100 and “large” if len($n$) $\geq$ 200 (and nothing if 100 $\leq$ len($n$)
$<$ 200).

MDSLEN is the composite problem of MD and CSL; SLMD is composed from SL and
MD; SLSTR is a composite of SL and CSL.

###  V-C Parameter settings

For all three methods, we use a population size of 1000 and a maximum
generation of 300. The UMAD mutation in all three methods is set with addition
rate of 0.09 and deletion rate of 0.0826 based on Helmuth’s study [3]. For
PushGP+EP+ARM and PushGP+HP+ARM, the rate to perform ARM $r_{arm}$ is 0.1 and
the rate to perform the proportional selection of subprograms $r_{prop}$ is
0.5 based on the original paper of ARM [11]. For every algorithm, we run 25
repetitions on every problem.

###  V-D Experimental results

Figure 2: Experiment I: Train error in 25 runs. The value on a line segment is
the p-value of Wilcoxon rank sum test between two groups. The p-value is
marked with an asterisk and red color if the difference between two groups is
significant. PushGP+ARM+EP holds a significantly lower train error than PushGP
and a comparable train error compared to PushGP+ARM+HP. Figure 3: Experiment
I: Test success count in 25 runs. The number above a bar is the success count.
The value on a line segment is the p-value of Fisher’s exact test between two
groups. The p-value is marked with an asterisk and red color if the difference
between two groups is significant. PushGP+ARM+EP holds higher success counts
than PushGP but without statistical significance. Figure 4: Experiment I:
Average of the best train error in the population by generations.
PushGP+ARM+EP converges much faster than PushGP but slightly slower (SLSTR) or
at the similar speed (MDSLEN and SLMD) compared to PushGP+ARM+HP.

Fig. 2 presents the error in the training period of the three methods in 25
runs. The value on a line segment is the p-value of the Wilcoxon rank sum test
between two groups. The p-value is marked with an asterisk and red color if
the difference between two groups is significant with a 95% family confidence
level (i.e., the individual confidence level is computed by Šidák
correction222The individual confidence levels in Section V and Section VI are
99.4% and 99.1%, respectively.). The proposed PushGP+EP+ARM outperforms the
original PushGP with a significant difference in the training error. However,
compared with PushGP+HP+ARM, the difference is not statistically significant.

Fig. 3 shows the success counts in the test period of the three comparison
methods in 25 runs. We count a run as a successful run only when it passes all
I/O cases in both training and testing data. In Fig. 3, the number above a bar
is the success count; the value on a line segment is the p-value of Fisher’s
exact test between two groups. The p-value is marked with an asterisk and red
color if the difference between two groups is significant with a 95% family
confidence level (i.e., the individual confidence level is computed by Šidák
correction22footnotemark: 2). Compared to PushGP, our PushGP+EP+ARM achieves
higher success counts, however, without statistical significance. Compared to
the method using human-made subprograms (PushGP+HP+ARM), our proposed method
achieves a lower success count on MDSLEN, a higher success count on SLMD, and
an equal success count on SLSTR. However, these differences are not
significant.

We provide a comparison of the best train error by generations in Fig. 4.
PushGP+EP+ARM holds a much faster convergence speed compared to PushGP;
however, it is slightly slower than PushGP+HP+ARM.

In the case of solving the sub-problems and then the composite problems,
PushGP+EP+ARM achieves a better performance in train error, success count, and
faster convergence, compared to the original PushGP [3]. However, its
performance in both success count and convergence speed is worse than
PushGP+HP+ARM without statistical significance.

##  VI Experiment II: Sequential KDPS Task

In this second experiment, we test the entire KDPS process in Fig. 1. That is,
using PushGP+ARM+EP to solve a sequence of problems. They are the six problems
in the last experiment, namely SL, CSL, MD, MDSLEN, SLMD, and SLSTR. Every
time a problem is solved, we extract subprograms from its solution and store
them in the archive. This archive will be used when solving the next problem.

###  VI-A Comparison methods

  * •

PushGP+EP+ARM: solving a sequence of PS problems with PushGP+EP+ARM in the way
as in Fig. 1; every time a problem is solved, the subprograms are extracted by
EP from its solution and added to the archive. This archive is used by
PushGP+ARM when solving the next problem.

  * •

PushGP: solving a sequence of PS problems independently using PushGP [3].

###  VI-B Experimental procedures

We solve six problems, namely MD, CSL, SL, MDSLEN, SLMD, and SLSTR. The first
three problems are from PSB1 [6]. They do not share any sub-problems. The last
three problems are the composite problems of MD, CSL, and SL (Section V). Any
pair of the three composite problems share a sub-problem.

For PushGP+EP+ARM, we run a procedure as in Fig. 1. We solve the first problem
(MD) with the original PushGP (i.e., PushGP+ARM with an empty archive) and the
rest problems with PushGP+ARM. We initialize an empty subprogram archive when
solving the first problem. For every problem, we run 25 repetitions and take
the best and shortest program. We use EP to extract five subprograms from the
best and shortest programs. These subprograms are stored in the archive that
we initialized before and used in solving the later problems by PushGP+ARM.
For PushGP, we solve the six problems independently in the same order with
PushGP+EP+ARM. However, no subprograms are stored and used.

We provide results of solving the six problems in two different orders. Order
1 solves simple problems at first and later harder ones while Order 2 is a
reverse order of Order 1.

  * •

Order 1: MD→CSL→SL→MDSLEN→SLMD→SLSTR

  * •

Order 2: SLSTR→SLMD→MDSLEN→SL→CSL→MD

We use the same parameter settings as in Section V. We present the results and
the statistical test in a similar manner as in Section V.

###  VI-C Experimental results of Order 1

Figure 5: Experiment II, Order 1: Train error in 25 runs. The value on a line
segment is the p-value of Wilcoxon rank sum test between two groups. The
p-value is marked with an asterisk and red color if the difference between two
groups is significant. PushGP+EP+ARM holds a significantly lower train error
than PushGP on MDSLEN, SLMD, and SLSTR. Figure 6: Experiment II, Order 1: Test
success count in 25 runs. The number above a bar is the success count. The
value on a line segment is the p-value of Fisher’s exact test between two
groups. The p-value is marked with an asterisk and red color if the difference
between two groups is significant. PushGP+EP+ARM holds a higher success count
than PushGP on MD, MDSLEN, SLMD, and SLSTR; however, without statistical
significance. Figure 7: Experiment II, Order 1: Average of the best train
error in the population by generations. PushGP+EP+ARM converges much faster
than PushGP on the five problems except MD.

In Fig. 5, PushGP+EP+ARM holds a significantly lower train error than PushGP
on the three composite problems, while the difference on the rest three
problems is not significant. Fig. 6 shows the test success count of
PushGP+EP+ARM and PushGP. The test success count of PushGP+EP+ARM is lower
than PushGP on CSL and SL but higher than PushGP on MSDLEN, SLMD, and SLSTR.
All these difference is not statistically significant through Fisher’s exact
test. On MD, the difference between the two methods is very small since it is
solved by two equivalent methods. Fig. 7 provides the best error in the
population by generations of both methods. It is obvious that PushGP+EP+ARM
converges faster than PushGP on all problems except MD.

###  VI-D Experimental results of Order 2

In Fig. 8, PushGP+EP+ARM holds a lower train error than PushGP on all problems
without statistical significance. Fig. 9 shows the test success count of
PushGP+EP+ARM and PushGP. The test success count of PushGP+EP+ARM is higher
than PushGP on on most of the problems except MD. Especially on CSL,
PushGP+EP+ARM gets 16 success while PushGP only gets 8. However, all these
difference is not statistically significant through Fisher’s exact test. Fig.
10 provides the best error in the population by generations of both methods.
It is obvious that PushGP+EP+ARM converges faster than PushGP on all problems
except SLMD.

Therefore, when solving a sequence of problems, PushGP+EP+ARM achieves a
better optimization performance (i.e., train error and convergence speed).
This performance finally leads to a higher test success count, however,
without statistical significance.

###  VI-E Discussion

We find that the PushGP+EP+ARM in Section V is better than the PushGP+EP+ARM
in Section VI with Order 1, in terms of test success on the three composite
problems. Though their algorithms are the same, they have at least two
differences.

  1. 1.

In Section VI, PushGP+EP+ARM adds five subprograms to the archive after
solving one problem. Therefore, the size of the archive is 15, 20, and 25 when
solving MDSLEN, SLMD, and SLSTR, respectively. However, in Section V,
PushGP+EP+ARM uses archives with 10 subprograms (five for one sub-problem). A
larger subprogram archive makes it harder to select helpful subprograms by the
adaptive strategy in Algorithm 1.

  2. 2.

CSL and SL are solved in different conditions in the two experiments. In
Section VI, CSL is solved with subprograms from MD; SL is solved with
subprograms from MD and CSL. However, no subprogram is used when solving MD,
CSL, and SL in Section V (i.e., they are solved by the original PushGP [3]).
Moreover, MD, CSL, and SL do not share the same sub-problems. Therefore,
solving CSL and SL with PushGP+EP+ARM is not as good as with the original
PushGP (as shown in the first three subfigures of Fig. 6). Thus, the
subprograms extracted in Section VI is not as good as in Section V. These
subprograms further influence the performance of PushGP+EP+ARM in Section VI
in solving the later problems MDSLEN, SLMD, and SLSTR. This issue is called
“negative transfer”.

In Section VI (problems in Order 2), we find that PushGP+EP+ARM holds a lower
success count on MD. However, on MD, the training error of all runs with
PushGP+EP+ARM is 0 (Fig. 8). Moreover, Fig. 10 shows PushGP+EP+ARM converges
much faster than PushGP. This observation may indicate an over-fitting issue
with the proposed method.

##  VII Conclusions

In this study, we introduced a problem called Knowledge-Driven Program
Synthesis (KDPS) problem. KDPS requires an agent to solve a sequence of
related PS problems. To solve KDPS, we proposed a method based on PushGP [3].
This method consecutively solves programming tasks, extracts subprograms from
the solutions as knowledge, and uses these subprograms to solve the next
problem. To extract subprograms from the solution of a solved problem, we
proposed the Even Partitioning (EP) method; to use these subprograms, we
applied Adaptive Replacement Mutation (ARM) [11].

We compared our proposed method (PushGP+EP+ARM) with the original PushGP [3]
and a method extracting subprograms by humans (PushGP+HP+ARM). Our
PushGP+EP+ARM achieved a significantly better train error, success count, and
convergence speed than PushGP. The performance of our proposed method is
slightly worse than PushGP+HP+ARM. We further compared our PushGP+EP+ARM with
the original PushGP in solving a sequence of problems. Our method achieved a
better train error and convergence speed. Our PushGP+EP+ARM also holds a
higher test success count, however, without statistical significance.

The current method to automatically construct the subprogram archive is rather
naive. We would like to improve this method in our future work. In the
discussion section in Section VI, PushGP+EP+ARM has limitations in dealing
with the growing subprogram archive after solving more problems. Moreover,
PushGP+EP+ARM also suffers from the “negative transfer” of the subprograms
from the unrelated problems. A part of our future work is to fix these issues.
Methods such as a more efficient adaptation or filtering strategy on
subprograms are promising to solve the two limitations. Additionally, the
strategy of extracting and using knowledge could be applied to problems other
than program synthesis, such as training soft robotics [18].

Figure 8: Experiment II, Order 2: Train error in 25 runs. The value on a line
segment is the p-value of Wilcoxon rank sum test between two groups. The
p-value is marked with an asterisk and red color if the difference between two
groups is significant. PushGP+EP+ARM holds a lower train error than PushGP on
all the problems without statistical significance. Figure 9: Experiment II,
Order 2: Test success count in 25 runs. The number above a bar is the success
count. The value on a line segment is the p-value of Fisher’s exact test
between two groups. The p-value is marked with an asterisk and red color if
the difference between two groups is significant. PushGP+EP+ARM holds a higher
success count than PushGP on SLSTR, SLMD, MDSLEN, SL, and CSL; however,
without statistical significance. Figure 10: Experiment II, Order 2: Average
of the best train error in the population by generations. PushGP+EP+ARM
converges much faster than PushGP on the five problems except SLMD.

## References

  * [1] M. O’Neill and L. Spector, “Automatic programming: The open issue?” _Genetic Programming and Evolvable Machines_ , vol. 21, no. 1, pp. 251–262, 2020.
  * [2] J. Koza, “On the programming of computers by means of natural selection,” _Genetic programming_ , 1992.
  * [3] T. Helmuth, N. F. McPhee, and L. Spector, “Program synthesis using uniform mutation by addition and deletion,” in _Proceedings of the Genetic and Evolutionary Computation Conference_ , 2018, pp. 1127–1134.
  * [4] J. Kelly, E. Hemberg, and U.-M. O’Reilly, “Improving genetic programming with novel exploration-exploitation control,” in _European Conference on Genetic Programming_. Springer, 2019, pp. 64–80.
  * [5] T. Helmuth and L. Spector, “Explaining and exploiting the advantages of down-sampled lexicase selection,” in _ALIFE 2020: The 2020 Conference on Artificial Life_. MIT Press, 2020, pp. 341–349.
  * [6] T. Helmuth and L. Spector, “General program synthesis benchmark suite,” in _Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation_ , 2015, pp. 1039–1046.
  * [7] E. Hemberg, J. Kelly, and U.-M. O’Reilly, “On domain knowledge and novelty to improve program synthesis performance with grammatical evolution,” in _Proceedings of the Genetic and Evolutionary Computation Conference_ , 2019, pp. 1039–1046.
  * [8] D. Sobania and F. Rothlauf, “Teaching gp to program like a human software developer: using perplexity pressure to guide program synthesis approaches,” in _Proceedings of the Genetic and Evolutionary Computation Conference_ , 2019, pp. 1065–1074.
  * [9] T. Helmuth, E. Pantridge, G. Woolson, and L. Spector, “Genetic source sensitivity and transfer learning in genetic programming,” in _ALIFE 2020: The 2020 Conference on Artificial Life_. MIT Press, 2020, pp. 303–311.
  * [10] J. Wick, E. Hemberg, and U.-M. O’Reilly, “Getting a head start on program synthesis with genetic programming,” in _European Conference on Genetic Programming (Part of EvoStar)_. Springer, 2021, pp. 263–279.
  * [11] Y. He, C. Aranha, and T. Sakurai, “Incorporating sub-programs as knowledge in program synthesis by pushgp and adaptive replacement mutation,” in _Proceedings of the Genetic and Evolutionary Computation Conference Companion_ , 2022.
  * [12] E. Pantridge and L. Spector, “Pyshgp: Pushgp in python,” in _Proceedings of the Genetic and Evolutionary Computation Conference Companion_ , 2017, pp. 1255–1262.
  * [13] M. O’Neill and C. Ryan, “Grammatical evolution,” _IEEE Transactions on Evolutionary Computation_ , vol. 5, no. 4, pp. 349–358, 2001.
  * [14] L. Spector, “Autoconstructive evolution: Push, pushgp, and pushpop,” in _Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001)_ , vol. 137, 2001.
  * [15] S. Forstenlechner, D. Fagan, M. Nicolau, and M. O’Neill, “Extending program synthesis grammars for grammar-guided genetic programming,” in _International Conference on Parallel Problem Solving from Nature_. Springer, 2018, pp. 197–208.
  * [16] J. Lehman, J. Gordon, S. Jain, K. Ndousse, C. Yeh, and K. O. Stanley, “Evolution through large models,” _arXiv preprint arXiv:2206.08896_ , 2022\.
  * [17] J. Zhang and A. C. Sanderson, “Jade: adaptive differential evolution with optional external archive,” _IEEE Transactions on evolutionary computation_ , vol. 13, no. 5, pp. 945–958, 2009.
  * [18] F. Pigozzi, Y. Tang, E. Medvet, and D. Ha, “Evolving modular soft robots without explicit inter-module communication using local self-attention,” _arXiv preprint arXiv:2204.06481_ , 2022.


# Enhancing the efficiency of quantum measurement-based engines with
entangling measurements

Franco Mayo<EMAIL_ADDRESS>Departamento de Física, FCEyN, UBA, Pabellón 1,
Ciudad Universitaria, 1428 Buenos Aires, Argentina  Instituto de Física de
Buenos Aires, UBA CONICET, Pabellón 1, Ciudad Universitaria, 1428 Buenos
Aires, Argentina  Augusto J. Roncaglia<EMAIL_ADDRESS>Departamento de
Física, FCEyN, UBA, Pabellón 1, Ciudad Universitaria, 1428 Buenos Aires,
Argentina  Instituto de Física de Buenos Aires, UBA CONICET, Pabellón 1,
Ciudad Universitaria, 1428 Buenos Aires, Argentina

###### Abstract

We study the impact of entangling measurements on the efficiency of quantum
measurement-based engines. We first show that for engines comprising many
subsystems their efficiency can be enhanced by performing entangling
measurements, as opposed to local measurements over each subsystem. When the
collective measurement produces the same local state for the subsystems as
individual local measurements, the improvement in the efficiency is
proportional to the amount of correlations. Finally, we show that for two
level systems these type of engine can operate at perfect efficiency while
yielding a finite amount of work, in the limit large the number of subsystems.

##  I Introduction

As thermal machines drove the development of classical thermodynamics, quantum
thermodynamics has gained interesting insights from the study of quantum heat
engines and refrigerators binder2019thermodynamics ; vinjanampathy2016quantum
. For instance, we can mention the development of shortcuts to adiabaticity
torrontegui2013shortcuts  and shortcuts to equilibrium dann2019shortcut ;
pancotti2020speed , that allow thermal machines to increase their power
without loosing efficiency, or the role that quantum features play in
thermodynamics. The study of quantum thermal machines includes autonomous
thermal machines linden2010small ; brunner2012virtual , heat engines operating
with quantum coherence dann2020quantum ; camati2019coherence ;
hammam2021optimizing  and quantum correlations hewgill2018quantum . Also,
experimental realizations of heat engines on the quantum scale have been made
rossnagel2016single ; von2019spin .

In recent years, the idea of quantum engines in which the fuel is not heat
from a thermal reservoir but quantum measurements performed on it arose
jordan2020quantum . These engines take advantage of the fact that performing
some measurement on a system can change its energy, provided that the
measurement does not commute with the system’s hamiltonian. In this way, the
heat provided by a thermal reservoir can be replaced by the energy supplied by
a measurement. Several quantum measurement engines (QMEs) have been introduced
during the last years; these include single qubit engines
elouard2017extracting , a quantum Otto engine in which the hot bath is
replaced by a non-selective quantum measurement yi2017single , a quantum
Carnot engine fadler2023efficiency , a climbing particle assisted by a quantum
measurement elouard2018efficient , a measurement engine fueled by entanglement
bresque2021two  and a refrigerator buffoni2019quantum . In addition, there
were also different proposals that use incompatible measurements to fuel
quantum measurement engines opatrny2021work ; manikandan2021efficiently  and
other engines that work without using feedback das2019measurement ;
ding2018measurement , as well as works considering multilevel systems
de2021efficiency ; anka2021measurement  or interacting qubits
bhandari2023measurement . The thermodynamics of quantum measurements have been
also studied for instance by considering the cost to perform quantum
measurements guryanova2020ideal ; sagawa2009minimal ; jacobs2009second ;
jacobs2012quantum ; abdelkhalek2016fundamental ; deffner2016quantum ;
linpeng2022energetic ; perna2023fundamental , the role of quantum coherence
lin2021suppressing  and the classicality of the heat produced during
measurements mohammady2021classicality . These machines have some very
interesting properties compared to traditional thermal machines. For instance,
its efficiency is not bounded by Carnot’s efficiency, as there is only one
temperature to consider, and the maximum efficiency can be achieved at maximum
power elouard2017extracting . This is in contradiction to what happens to
thermal machines, where there is a trade-off between power and efficiency.

In this work we aim to look at an interesting feature of quantum mechanics
that might lead to interesting results in the realm of quantum thermodynamics,
collective entangling measurements. We show that if one considers QMEs
composed of many subsystems, it is possible to obtain a higher efficiency when
collective entangling measurements as opposed to local ones over each
individual subsystem. We also find that perfect efficiency can be achieved in
the limit of a large number of subsystems.

Figure 1: Schematic representation of the (top) individual or parallel and
(bottom) collective process. The QME cycle starts with a measurement that
increases the system’s energy. Afterwards, work is extracted by performing a
feedback operation $U_{\rm feedback}$ leaving the system in its initial state.
The cycle ends after erasing the information about the measurement result. In
the parallel process both measurement and feedback (work extraction) are
performed independently on each system, while in the collective one both
operations are performed globally on all systems. As indicated by the size of
the arrows, the collective process can lead to smaller erasure cost.

The paper is organized as follows. In Sec. II we introduce quantum measurement
engines and discussed how its efficiency is defined. Afterwards in Sec. III we
show how the use of global entangling measurements enhances the efficiency of
QMEs. Finally, in Sec. IV we present some discussions and the conclusions.

##  II Efficiency of quantum measurement engines

Let us first recall how a typical measurement engine works. The working body
consists of a system $\mathcal{S}$ with hamiltonian $H_{\mathcal{S}}$ that
starts in a given pure state, and there is an environment at equilibrium with
temperature $T$. Thus, the QME can be described in terms of the following
steps:

_(a) Projective measurement_ : Initially, the system is in a pure state
$\ket{\psi_{\rm i}}$, with energy $E_{\rm
i}=\expectationvalue{H_{\mathcal{S}}}{\psi_{\rm i}}$, and is measured on some
basis $\\{\ket{k}\\}$ that does not commute with $H_{\mathcal{S}}$. After the
measurement, the system is left in the state $\ket{k}$ with probability
$p_{k}=\absolutevalue{\innerproduct{k}{\psi_{\rm i}}}^{2}$, and its averaged
energy (considering all possible measurement outcomes) is ${E_{\rm
f}=\sum_{k}p_{k}\expectationvalue{H_{\mathcal{S}}}{k}}$. If the measurement
basis is chosen properly, then $E_{\rm f}>E_{\rm i}$ and the measurement has
increased the systems energy by $\Delta E=E_{\rm f}-E_{\rm i}$.

_(b) Feedback & work extraction_: If the outcome of the measurement was
$\ket{k}$ the system is restored to the initial state $\ket{\psi_{\rm i}}$
with some unitary operation $U_{\text{feedback}}^{(k)}$. During this process
an amount of work
$W_{k}=\expectationvalue{H_{\mathcal{S}}}{k}-\expectationvalue{H_{\mathcal{S}}}{\psi_{\rm
i}}$ can be extracted. On average, the amount of extracted work is
$W_{\text{ext}}=\Delta E$.

_(c) Erasure_ : The cycle ends once the classical memory that stores the
result of the measurements is erased. According to Landauer’s principle
landauer1961irreversibility  this can be done quasi-statically using some work
$W_{\text{er}}$ that is equal to the amount of heat
${Q_{\text{er}}=k_{B}TS_{\rm f}}$ dissipated to the environment, and $S_{\rm
f}$ is the Shannon entropy of the memory. This entropy is also equal to the
von Neumann entropy of the system after the measurement ${S_{\rm f}\equiv
H\\{p_{i}\\}=-\sum_{k}p_{k}\log p_{k}}$.

The aforementioned cycle is designed in such a way that, on average, the
system absorbs an amount of energy $\Delta E$ from the measurement, while the
output work is ${W=W_{\text{ext}}-W_{\text{er}}=\Delta E-W_{\text{er}}}$.
Thus, in general it works like an engine, provided the temperature of the
reservoir is low enough so that $\Delta E>W_{\text{er}}$.

Given that the measurement generally leads to an increase of the system
entropy, this form of energy is commonly referred to as ‘quantum heat’
elouard2017role . However, in other frameworks, this energy is referred to as
work sagawa2009minimal ; jacobs2009second  since it can leave the system in a
non-equilibrium state. We agree with this second interpretation, associated to
the external work required to couple the system with a measurement apparatus.
In this way, the rise in entropy is just a direct consequence of the
correlations established during the interaction. Hence, we can interpret these
engines as transducers of energy from measurements. Thus, the efficiency of
this cycle is

$\eta=\frac{W}{\Delta E}.$ (1)

Notably the efficiency can attain values close to one elouard2017extracting ;
elouard2018efficient , for instance, when the outcomes of the measurement have
low dispersion. However, in this situation the amount of extracted work is
vanishing small, so there is a trade-off between efficiency and extracted
work.

In order to analyze the performance of these engines in more general
scenarios, we will introduce an alternative way of writing the efficiency.
Since the net work is $W=E_{\rm f}-E_{\rm i}-k_{B}TS_{\rm f}$, it is easy to
notice that efficiency can also be expressed as: $\eta={\Delta F}/{\Delta E}$,
where $F=\expectationvalue{E}-k_{B}TS(\rho)$ is the free energy, and
differences are taken between averaged states after and before measurement,
that is: $\rho_{\rm f}=\sum_{k}p_{k}\outerproduct{k}{k}$ and $\rho_{\rm
i}\equiv\outerproduct{\psi_{\rm i}}{\psi_{\rm i}}$, respectively, and $\Delta
E=\tr[H_{\mathcal{S}}\rho_{\rm f}]-\tr[H_{\mathcal{S}}\rho_{\rm i}]$ is the
difference in the mean energy between the same states. As we know, $\Delta F$
is also the maximum (minimum) work that can be extracted (yielded) in the
transformation $\rho_{\rm f}\rightarrow\outerproduct{\psi_{\rm i}}{\psi_{\rm
i}}$ in contact with a heat bath at temperature $T$. Therefore, one could
disregard the specific feedback or transformation implemented to extract work
and solely focus on the maximum work that can be extracted during the
transformation from the post-measurement state to the initial one. This shows
that the energetics involved in a QME is equivalent to a two-step cycle where:
$(i)$ a decoherence process (in the measurement basis) over the initial state,
and $(ii)$ a transformation in contact with a heat bath that restores the
system to its initial state, during which some work is extracted.

As we shall see, this picture is useful as it enables us to explore more
general QME, and the straightforward evaluation of their efficiency in
situations involving collective measurements.

##  III Collective measurements

So far we have discussed engines in which there is a single quantum system. We
now consider the case where there is an engine consisting of $N$ subsystems
where the $N-$QME Hamiltonian is $H=\sum_{\mu=1}^{N}h_{\mu}$, and focus on the
difference between performing local measurements and collective measurements,
as it is sketched out in Fig. 1. The aim of this section is to show that it is
possible to improve the performance of these engines by implementing
collective measurements. In this way one can enlarge the working range of the
engine, extracting more work at larger efficiencies.

Let us first consider a QME running in parallel, that is each measurement is
done locally. In this case, on average the energy provided by the measurement
is just ${\Delta E}=\sum_{\mu}\Delta E_{\mu}$, where $\Delta
E_{\mu}=\tr[h_{\mu}(\rho_{{\rm f},\mu}-\rho_{\rm i,\mu})]$ is the energy
provided by each single engine. Then, if $W_{\mu}$ is the net extracted work
of each QME, one can define the efficiency of the parallel process as
$\eta_{\|}=\sum_{\mu}W_{\mu}/\sum_{\mu}\Delta E_{\mu}\equiv
1-k_{B}T\sum_{\mu}S_{\mu}/\sum_{\mu}\Delta E_{\mu}$, where $S_{\mu}$ is the
entropy generated by the $\mu-$th engine whose post measurement state is
$\rho_{{\rm f},\mu}$.

Now, one can compare this efficiency with the efficiency of an engine
subjected to a collective measurement that outputs the same mean energy. For
instance, this can be done by imposing that the post-measurement $N$-partite
state $\rho_{\rm f}$ is such that is locally equivalent to the one associated
with the parallel process:

$\Tr_{-\mu}[\rho_{\rm f}]=\rho_{\rm f,\mu}$ (2)

this ensures that on average the energy provided by the measurement is the
same in both processes.

Then, the efficiency of the collective process is defined as:
$\eta_{\sharp}=1-k_{B}{TS_{\sharp}}/{\sum_{\mu}\Delta E_{\mu}}$, where
$S_{\sharp}$ is the entropy generated by the collective measurement. Now we
can express this entropy in terms of the multipartite mutual information
watanabe1960information ; kumar2017multiparty  as
$S_{\sharp}=\sum_{\mu}^{N}S_{\mu}-\mathcal{I}$,

where $S_{\mu}$ is the entropy of each subsystem and $\mathcal{I}$ is the
multipartite mutual information, that accounts for all the correlations
created during the measurement. This allows us to write the efficiency of the
collective process as:

$\eta_{\sharp}=\eta_{\|}+\frac{k_{B}T\ \mathcal{I}}{\sum_{\mu}\Delta
E_{\mu}}.$ (3)

Thus, we can see that performing a collective measurement that generates
correlations between the subsystems enhances the efficiency of the QMEs. It is
worth noting that the last expression does not indicate an increase in the
efficiency with temperature. Considering that the first term is also
temperature-dependent, the efficiency could potentially be negative at high
temperatures. Hence, it is not straightforward to determine the significance
of this improvement. Below, we will show that in the symmetric QME scenario,
the efficiency could be close to one while still extracting a finite amount of
net work per subsystem.

###  III.1 Symmetric QME

We will consider a _symmetric QME_ , that is an engine composed by identical
subsystems, i.e. they start in the same initial state, are subjected to the
same measurement, and have the same hamiltonian. In this case, it is easy to
see that ${\sum_{\mu}W_{\mu}=NW_{1}}$, ${\Delta E=N\Delta E_{1}}$,
$\eta_{\|}=\eta_{1}$, and therefore
${\eta_{\sharp}=\eta_{\|}+k_{B}T\mathcal{I}/(N\Delta E_{1})}$ (where the
subindex 1 indicates that the quantity is associated to a single QME).

Let us start by considering a simple example, an engine composed by two two-
level systems. When this engine runs in parallel, each system is measured on a
given basis that we call $\\{\ket{0},\ket{1}\\}$, and starts in a general pure
state that can be written in this basis as ${\ket{\psi_{\rm
i}}=\sqrt{q}\ket{0}+\sqrt{p}\ket{1}}$, where we choose positive real numbers
without loss of generality. Therefore, if the Hamiltonian for a single system
is $h_{1}$, $E_{\rm i}=q\bra{0}h_{1}\ket{0}+p\bra{1}h_{1}\ket{1}+2\sqrt{qp}\
\mathrm{Re}\\{\langle 0|h_{1}|1\rangle\\}$, and it has an efficiency
$\eta_{1}=1-k_{B}TS_{1}/{\Delta E_{1}}$, where $S_{1}=-q\log q-p\log p$ and
$\Delta E_{1}=-2\sqrt{qp}\ \mathrm{Re}\\{\langle 0|h_{1}|1\rangle\\}$.

Now we will show that by using a collective measurement that generates
correlations between both systems, one can fuel the engine with the same
amount of energy as in the parallel process, but with a higher efficiency. In
this case the initial state is $\ket*{\psi^{(2)}_{\rm i}}\equiv\ket{\psi_{\rm
i}}\otimes\ket{\psi_{\rm i}}$, that can be written as:

$\ket{\psi^{(2)}_{\rm i}}=q\ket{00}+p\ket{11}+\sqrt{qp}\
({\ket{01}+\ket{10}})$ (4)

For the collective measurement basis we make the following choice:
$\\{\ket{00},\ket{11},\frac{\ket{01}+\ket{10}}{\sqrt{2}},\frac{\ket{01}-\ket{10}}{\sqrt{2}}\\}$.
It is easy to see that for this choice, the post-measurement state is
$\rho^{(2)}_{{\rm
f},\sharp}=p^{2}\outerproduct{00}{00}+q^{2}\outerproduct{11}{11}+pq(\ket{01}+\ket{10})(\bra{01}+\bra{10})$,
which is locally equivalent to that of the parallel process: $\rho_{{\rm
f},1}=\rho_{{\rm f},2}=q\outerproduct{0}{0}+p\outerproduct{1}{1}$. Therefore,
both the local and the collective measurements will increase the systems’
energy by the same amount: ${\Delta E^{(2)}=2\Delta E_{1}}$. However, it is
interesting to notice that the probability of obtaining the last element of
the measurement basis is zero, which in turn reduces the entropy of the post-
measurement state. This entropy is ${S^{(2)}_{\sharp}=2(-q\log q-p\log
p)-2pq\log 2=2S_{1}-2pq\log 2}$, i.e, $S^{(2)}_{\sharp}\leq 2S_{1}$, and the
net extracted work is:

$W_{\sharp}^{(2)}=W_{\|}^{(2)}+qp\frac{k_{B}T\log 2}{\Delta E_{1}}.$ (5)

Therefore, since this example is valid for an arbitrary local measurement, it
tells us that for every parallel engine of this type, there exists a
collective measurement that enhances its efficiency. Naturally, this also
requires a collective unitary operation as a feedback.

In the following, we will generalize this idea for an arbitrary number $N$ of
systems. For $N$ two-level systems, the initial state is associated to the
following tensor product:

$\ket{\psi_{\rm i}}^{\otimes N}=\sum_{i}\sqrt{q^{(N-i)}p^{i}}\
\mathbf{S}\left(\ket{0}^{\otimes{N-i}}\ket{1}^{\otimes i}\right),$ (6)

where $\mathbf{S}=\sum_{\pi}P_{\pi}$ is a symmetrization operator and
$P_{\pi}$ is a permutation operator running over all permutations $\pi$. In
this way, we can see that the state is a linear combination of $N$ orthonormal
vectors:
$\ket{i_{\sharp}}\equiv\mathbf{S}\left(\ket{0}^{\otimes{N-i}}\ket{1}^{\otimes
i}\right)/\sqrt{{N\choose i}}$ labelled by the index $i$, which can be
associated to the Hamming weight or the “occupation number”. These vectors
span a subspace of the Hilbert space of the $N$ systems $\mathcal{H}^{\otimes
N}$ that is invariant under all permutations, and we call it
$\mathcal{H}_{+}^{\otimes N}$. Now, we can define a collective measurement
basis that contains the $N$ elements $\\{\ket{i_{\sharp}}\\}$ expanding
$\mathcal{H}_{+}^{\otimes N}$, and the remaining elements are composed by an
arbitrary basis expanding the orthogonal projection of
$\mathcal{H}_{+}^{\otimes N}$ to $\mathcal{H}^{\otimes N}$. In this way, one
can show that the post-measurement state is

$\rho_{{\rm f},\sharp}=\sum_{i}{N\choose i}\ q^{N-i}p^{i}\
\outerproduct{i_{\sharp}}{i_{\sharp}}.$ (7)

Where the probability associated to the different outcomes are determined by a
binomial distribution. Therefore, the change in entropy after the measurement
is just the entropy of the binomial distribution, whose expression for a large
$N$ is knessl1998integral :

$S_{\sharp}=\frac{1}{2}\,\log(2\pi eNqp)+\mathcal{O}\left(\frac{1}{N}\right).$
(8)

If we compare this situation with the local or parallel measurement scheme, in
that case the entropy of the measurement is $S_{\|}=NS_{1}$, while in the
global measurement scenario it scales as $S_{\sharp}\sim\log N$. However,

it is easy to see that the energy provided by the measurement is the same in
both cases: given that
$\bra{i_{\sharp}}\sum_{j}h_{\mu}\ket{i_{\sharp}}=(N-i)\bra{0}h_{1}\ket{0}+i\bra{1}h_{1}\ket{1}$,
and using Eq. (7) it is easy to verify that $E_{\rm
i}=N(q\bra{0}h_{1}\ket{0}+p\bra{1}h_{1}\ket{1})$. Thus, as $\Delta E=N\Delta
E_{1}$, the efficiency of the collective engine is therefore

$\eta_{\sharp}=1-k_{B}T\frac{\log(2\pi
eNpq)/2+\mathcal{O}(\frac{1}{N})}{N\Delta E_{1}},$

Therefore, we can see that for large $N$ it scales as:

$\eta_{\sharp}\sim 1-\frac{k_{B}T}{\Delta E_{1}}\frac{\log N}{N},$ (9)

and one can approach $\eta_{\sharp}\xrightarrow[N\to\infty]{}1$.

Quantum measurement engines have been show to approach efficiency one in
elouard2017extracting , however, this was done at the expense of obtaining a
vanishing amount of work. In this case, we find that for every local
measurement, there is a collective one that allow us to extract the same
amount of work (per system) with unit efficiency in the large $N$ limit. In
Fig. 2 we show that one can surpass the efficiency of every possible single
two-level QME, and even for a small number of systems one can attain
efficiency one for every local measurement.

It is interesting to notice that the above strategy works for any initial pure
state and local measurement basis, however it is not optimal. For instance,
one can consider $N$ two-level systems starting in the ground state
$\ket*{\psi_{\rm i}^{(N)}}=\ket{g}^{\otimes N}$, and the following collective
measurement basis:

$\mathcal{B}_{\sharp}=\left\\{\frac{\ket{g}^{\otimes N}+\ket{e}^{\otimes
N}}{\sqrt{2}},\frac{\ket{g}^{\otimes N}-\ket{e}^{\otimes
N}}{\sqrt{2}},\mathcal{C}\right\\},$

consisting of two orthogonal GHZ states along with a basis $\mathcal{C}$ that
expands their orthogonal complement. It is easy to see that the equivalent
parallel process is the one where each system is measured in the local basis
$\\{\frac{\ket{g}+\ket{e}}{\sqrt{2}},\frac{\ket{g}-\ket{e}}{\sqrt{2}}\\}$
where the post-measurement state of each subsystem is proportional to the
identity. It is easy to see that the same happens for the collective strategy.
In this case, the measurement has only two possible outcomes regardless of the
value of $N$, and both outcomes happens with the same probability. Therefore
the entropy after the measurement is always $S_{\sharp}=\log 2$. Thus, the
efficiency of this engine is:

$\eta_{\sharp}=1-\frac{k_{B}T}{\Delta E_{1}}\frac{\log 2}{N}.$

In particular, this scaling is optimal, since the generated entropy does not
increase with the number of systems.

Figure 2: Extractable work as a function of the energy provided by the
measurement $\Delta E/N=\Delta E_{1}$ for different number of two-level
systems. The shaded blue area depicts the full range of single two-level QMEs,
where each point corresponds to a specific initial state and measurement
basis. The curves correspond to the collective strategies that are locally
equivalent to the optimal parallel QMEs, represented by the blue curve.
Results are shown for $N=1$ (blue), $N=2$ (dotted), $N=6$ (dot-dashed), $N=10$
(dashed) and $N=20$ (solid). We can observe that as $N$ grows so does the
efficiency of these engines. In fact, for $N=20$ the slope of the curve is
almost one, indicating almost perfect efficiency.

Therefore, we have found a way of enhancing the efficiency of measurement
engines by using collective measurements while maintaining the energy of the
measurement constant. This enhancement happens for every initial state and
choice of local measurement basis, but is not necessarily optimal. We also
define a process in which the optimal collective advantage is achieved.
Measuring multiple two level systems in a collective way is not realistic in
practice; however, we find that there are considerable enhancements in the
efficiency even for the case of two two-level systems, a scenario that has
been realized experimentally several times, for example with measurements in
the Bell basis welte2021nondestructive . Also, in order to obtain the
efficiency enhancement one must perform the feedback globally, i.e. using a
global unitary over all the systems. Finally, it should be noted that for
collective measurements one can obtain perfect efficiency in the limit
$N\rightarrow\infty$, i.e. the process becomes reversible. In this case the
energy supplied by the measurements is more work-like, and it can be described
as a transducer of the measurement energy.

##  IV Conclusions

We have studied the behaviour of quantum measurement based engines under
collective measurements. We have shown that this type of measurements can
generate correlations between the subsystems, enhancing the efficiency the
cycle as they are able to reduce the entropy production. In this way, it is
possible to obtain an efficiency as high as desired by adding subsystems,
while extracting a finite amount of work. It has been shown in previous works
that the efficiency of quantum measurement engines attain values close to one,
in the limit of vanishing work extraction. Practical implementations of global
measurements is challenging, however we have shown that a significant
enhancement can still be achieved with a small amount of systems. Our findings
also shed light on the nature of the energy provided by the measurement.

###### Acknowledgements.

This work was partially supported by CONICET, UBACyT (20020130100406BA) and
ANPCyT (PICT-2019-04349 and PICT-2021-01288).

## References

  * (1) Felix Binder, Luis A Correa, Christian Gogolin, Janet Anders, and Gerardo Adesso.  Thermodynamics in the quantum regime: fundamental aspects and new directions, volume 195.  Springer, 2019.
  * (2) Sai Vinjanampathy and Janet Anders.  Quantum thermodynamics.  Contemporary Physics, 57(4):545–579, 2016.
  * (3) Erik Torrontegui, Sara Ibánez, Sofia Martínez-Garaot, Michele Modugno, Adolfo del Campo, David Guéry-Odelin, Andreas Ruschhaupt, Xi Chen, and Juan Gonzalo Muga.  Shortcuts to adiabaticity.  Advances in atomic, molecular, and optical physics, 62:117–169, 2013.
  * (4) Roie Dann, Ander Tobalina, and Ronnie Kosloff.  Shortcut to equilibration of an open quantum system.  Physical review letters, 122(25):250402, 2019.
  * (5) Nicola Pancotti, Matteo Scandi, Mark T Mitchison, and Martí Perarnau-Llobet.  Speed-ups to isothermality: Enhanced quantum thermal machines through control of the system-bath coupling.  Physical Review X, 10(3):031015, 2020.
  * (6) Noah Linden, Sandu Popescu, and Paul Skrzypczyk.  How small can thermal machines be? the smallest possible refrigerator.  Physical review letters, 105(13):130401, 2010.
  * (7) Nicolas Brunner, Noah Linden, Sandu Popescu, and Paul Skrzypczyk.  Virtual qubits, virtual temperatures, and the foundations of thermodynamics.  Physical Review E, 85(5):051117, 2012.
  * (8) Roie Dann and Ronnie Kosloff.  Quantum signatures in the quantum carnot cycle.  New Journal of Physics, 22(1):013055, 2020.
  * (9) Patrice A Camati, Jonas FG Santos, and Roberto M Serra.  Coherence effects in the performance of the quantum otto heat engine.  Physical Review A, 99(6):062103, 2019.
  * (10) Kenza Hammam, Yassine Hassouni, Rosario Fazio, and Gonzalo Manzano.  Optimizing autonomous thermal machines powered by energetic coherence.  New Journal of Physics, 23(4):043024, 2021.
  * (11) Adam Hewgill, Alessandro Ferraro, and Gabriele De Chiara.  Quantum correlations and thermodynamic performances of two-qubit engines with local and common baths.  Physical Review A, 98(4):042102, 2018.
  * (12) Johannes Roßnagel, Samuel T Dawkins, Karl N Tolazzi, Obinna Abah, Eric Lutz, Ferdinand Schmidt-Kaler, and Kilian Singer.  A single-atom heat engine.  Science, 352(6283):325–329, 2016.
  * (13) David Von Lindenfels, Oliver Gräb, Christian T Schmiegelow, Vidyut Kaushal, Jonas Schulz, Mark T Mitchison, John Goold, Ferdinand Schmidt-Kaler, and Ulrich G Poschinger.  Spin heat engine coupled to a harmonic-oscillator flywheel.  Physical review letters, 123(8):080602, 2019.
  * (14) Andrew N Jordan, Cyril Elouard, and Alexia Auffèves.  Quantum measurement engines and their relevance for quantum interpretations.  Quantum Studies: Mathematics and Foundations, 7(2):203–215, 2020\.
  * (15) Cyril Elouard, David Herrera-Martí, Benjamin Huard, and Alexia Auffeves.  Extracting work from quantum measurement in maxwell’s demon engines.  Physical Review Letters, 118(26):260603, 2017.
  * (16) Juyeon Yi, Peter Talkner, and Yong Woon Kim.  Single-temperature quantum engine without feedback control.  Physical Review E, 96(2):022108, 2017.
  * (17) Paul Fadler, Alexander Friedenberger, and Eric Lutz.  Efficiency at maximum power of a carnot quantum information engine.  Physical Review Letters, 130(24):240401, 2023.
  * (18) Cyril Elouard and Andrew N Jordan.  Efficient quantum measurement engines.  Physical review letters, 120(26):260601, 2018.
  * (19) Léa Bresque, Patrice A Camati, Spencer Rogers, Kater Murch, Andrew N Jordan, and Alexia Auffèves.  Two-qubit engine fueled by entanglement and local measurements.  Physical Review Letters, 126(12):120605, 2021.
  * (20) Lorenzo Buffoni, Andrea Solfanelli, Paola Verrucchi, Alessandro Cuccoli, and Michele Campisi.  Quantum measurement cooling.  Physical review letters, 122(7):070603, 2019.
  * (21) Tomas Opatrnỳ, Avijit Misra, and Gershon Kurizki.  Work generation from thermal noise by quantum phase-sensitive observation.  Physical review letters, 127(4):040602, 2021.
  * (22) Sreenath K Manikandan, Cyril Elouard, Kater W Murch, Alexia Auffèves, and Andrew N Jordan.  Efficiently fuelling a quantum engine with incompatible measurements.  Physical Review E, 105(4):044137, 2022.
  * (23) Arpan Das and Sibasish Ghosh.  Measurement based quantum heat engine with coupled working medium.  Entropy, 21(11):1131, 2019.
  * (24) Xuehao Ding, Juyeon Yi, Yong Woon Kim, and Peter Talkner.  Measurement-driven single temperature engine.  Physical Review E, 98(4):042122, 2018.
  * (25) Thiago R de Oliveira and Daniel Jonathan.  Efficiency gain and bidirectional operation of quantum engines with decoupled internal levels.  Physical Review E, 104(4):044133, 2021.
  * (26) Maron F Anka, Thiago R de Oliveira, and Daniel Jonathan.  Measurement-based quantum heat engine in a multilevel system.  Physical Review E, 104(5):054128, 2021.
  * (27) Bibek Bhandari, Robert Czupryniak, Paolo Andrea Erdman, and Andrew N Jordan.  Measurement-based quantum thermal machines with feedback control.  Entropy, 25(2):204, 2023.
  * (28) Yelena Guryanova, Nicolai Friis, and Marcus Huber.  Ideal projective measurements have infinite resource costs.  Quantum, 4:222, 2020.
  * (29) Takahiro Sagawa and Masahito Ueda.  Minimal energy cost for thermodynamic information processing: measurement and information erasure.  Physical review letters, 102(25):250602, 2009.
  * (30) Kurt Jacobs.  Second law of thermodynamics and quantum feedback control: Maxwell’s demon with weak measurements.  Physical Review A, 80(1):012322, 2009.
  * (31) Kurt Jacobs.  Quantum measurement and the first law of thermodynamics: The energy cost of measurement is the work value of the acquired information.  Physical Review E, 86(4):040106, 2012.
  * (32) Kais Abdelkhalek, Yoshifumi Nakata, and David Reeb.  Fundamental energy cost for quantum measurement.  arXiv preprint arXiv:1609.06981, 2016.
  * (33) Sebastian Deffner, Juan Pablo Paz, and Wojciech H Zurek.  Quantum work and the thermodynamic cost of quantum measurements.  Physical Review E, 94(1):010103, 2016.
  * (34) Xiayu Linpeng, Léa Bresque, Maria Maffei, Andrew N Jordan, Alexia Auffèves, and Kater W Murch.  Energetic cost of measurements using quantum, coherent, and thermal light.  Physical Review Letters, 128(22):220506, 2022.
  * (35) Guillermo Perna and Esteban Calzetta.  Limits on quantum measurement engines.  Phys. Rev. E, 109:044102, Apr 2024.
  * (36) Zhiyuan Lin, Shanhe Su, Jingyi Chen, Jincan Chen, and Jonas FG Santos.  Suppressing coherence effects in quantum-measurement-based engines.  Physical Review A, 104(6):062210, 2021.
  * (37) M Hamed Mohammady.  Classicality of the heat produced by quantum measurements.  Physical Review A, 104(6):062202, 2021.
  * (38) Rolf Landauer.  Irreversibility and heat generation in the computing process.  IBM journal of research and development, 5(3):183–191, 1961.
  * (39) Cyril Elouard, David A Herrera-Martí, Maxime Clusel, and Alexia Auffèves.  The role of quantum measurement in stochastic thermodynamics.  npj Quantum Information, 3(1):1–10, 2017.
  * (40) Satosi Watanabe.  Information theoretical analysis of multivariate correlation.  IBM Journal of research and development, 4(1):66–82, 1960.
  * (41) Asutosh Kumar.  Multiparty quantum mutual information: An alternative definition.  Physical Review A, 96(1):012332, 2017.
  * (42) C Knessl.  Integral representations and asymptotic expansions for shannon and renyi entropies.  Applied mathematics letters, 11(2):69–74, 1998.
  * (43) Stephan Welte, Philip Thomas, Lukas Hartung, Severin Daiss, Stefan Langenfeld, Olivier Morin, Gerhard Rempe, and Emanuele Distante.  A nondestructive bell-state measurement on two distant atomic qubits.  Nature Photonics, 15(7):504–509, 2021.