# Metamorphic Testing and Debugging
of Tax Preparation Software

Saeid Tizpaz-Niari  University of Texas at El PasoUSA<EMAIL_ADDRESS>,  Morgan
Wagner  University of Texas at El PasoUSA<EMAIL_ADDRESS>,  Shiva
Darian  University of Colorado BoulderUSA<EMAIL_ADDRESS>,  Krystia
Reed  University of Texas at El PasoUSA<EMAIL_ADDRESS>and  Ashutosh Trivedi
University of Colorado BoulderUSA<EMAIL_ADDRESS>
###### Abstract.

This paper presents a data-driven debugging framework to improve the
trustworthiness of US tax preparation software. As the US tax law evolves to
adapt to ever-changing politico-economic realities, tax preparation software
plays a significant role in helping taxpayers navigate these complexities.
Given the legal implications of bugs in such software on its users, ensuring
the compliance and trustworthiness of tax preparation software is of paramount
importance. The key obstacles in developing debugging aids for tax preparation
systems, however, are the unavailability of explicit specifications and the
difficulty of obtaining oracles.

We posit that, since the US tax law adheres to the legal doctrine of
precedent, the specifications about the outcome of tax preparation software
for an individual taxpayer must be viewed in comparison with individuals that
are deemed similar. Consequently, these specifications are naturally available
as properties on the software requiring similar inputs provide similar
outputs. Inspired by metamorphic testing framework from software engineering,
we dub these relations metamorphic relations.

We explicated metamorphic relations for a set of properties by carefully
studying the US Form 1040 as implemented in an open-source tax preparation
software. We developed a randomized search strategy to explore the space of
metamorphic relations and explain the behaviors of software with a
classification tree algorithm. Our tool revealed $4$ types of failures in the
software and provided intuitive explanations to understand the failures.

Metamorphic Testing, Statistical Fault Localization, US 1040, Tax Preparation
Software

††copyright: none

##  1\. Introduction

The ever-increasing complexity of income tax laws in the United States has
rendered manual preparation of tax returns cumbersome and error-prone.
According to the IRS, $90$ percent of tax filers filed taxes electronically in
2020 (US-IRS, 2020). Consequently, US tax preparation has grown into a
$\$11.2$bn industry requiring the services of professional tax accountants or
commercial tax preparation software. The use of software is increasing, and in
2020, over 72 million people prepared their taxes without the help of tax
professionals, a 24 percent increase from 2019 (US.IRS, [n.d.]).

Even though there are some freely available open-source alternatives (Roberts,
2021; Grimshaw and Patterson, 2021; Garrone, 2021), such tax preparation
software and services are provided on “AS-IS” bases and may not go through
rigorous software development process. The impact of bugs in software are
aggravated by the fact that, in the US tax courts, individuals are accountable
for any errors resulting from software bugs in such packages:

> _Langley v. Comm’r, T.C. Memo. 2013-22. The misuse of tax preparation
> software, even if unintentional or accidental, is no defense to accuracy-
> related penalties under section 6662._

However, users might not be aware of errors in the software. And few checks
currently exist to ensure the correctness of tax software (Soled and Thomas,
2017). To protect consumers in the this process, we develop validation and
debugging aids for open-source tax preparation software. Particularly because
this problem has the potential to compound financial stresses of the lower
income earners, who are more likely to use freely available and unregulated
software (Soled and Thomas, 2017).

This paper presents a data-driven debugging framework to discover and explain
bugs in tax preparation software systems. There are three concrete obstacles
to this framework.

  * –

Absence of Oracle. The class of correctness requirements for tax preparation
systems are not explicitly available since the correct tax-filing is highly
subjective to individual taxpayers (this is known as oracle problem (Barr et
al., 2015)).

  * –

Lack of trustworthy dataset. While, in the absence of such explicit
specification, one can recourse to data-driven approaches, it is difficult to
obtain access to a valid dataset due to obvious privacy and legal concerns.

  * –

Computational infeasibility. Even when one can justify fabricating such a
dataset, the final challenge is computational in nature: detecting and
explaining the bug by comparing an individual decision to others over a large
dataset based on a given similarity measure is computationally intractable.

Metamorphic testing (Chen et al., 1998) is a software testing paradigm that
tackles the oracle problem by considering software properties where the
correctness of the software on an input does not require knowing the “ground
truth” for that input; rather, the correctness can be validated by comparing
the output of software for that input with the output of a slightly
_metamorphosed_ one. For instance, consider a software implementing a search
engine: while there is no way to verify that the results returned for a
particular keyword are correct (oracle problem), it is reasonable to expect
that a correct search engine should return fewer results for a more restricted
keyword.

This paper makes a case for the suitability of _metamorphic specifications_ in
testing and debugging tax preparation software (and by extension for legal
software systems). We address aforementioned challenges by integrating
metamorphic specifications with data-driven debugging as following:

  * –

Metamorphic Specifications. The first obstacle in developing the debugging
framework is to explicate an appropriate notion of correctness requirements.
Note that, given the relevant information about an individual, resolving the
correct decision for that individual requires accounting and law expertise.
Hence, obtaining the oracle for testing and debugging purposes is
impractically expensive. Fortuitously, since the US tax law is principally
derived from the _common law_ system, it implements _stare decisis_ , i.e. the
legal doctrine of precedent: similar cases must follow similar rulings. As a
corollary, the correctness of tax preparation software must also be viewed in
comparison with similar cases. In other words, the correctness properties must
be expressed as relations between two individual taxpayers with similar
situations. Following the metamorphic testing (Chen et al., 1998), we call
such properties _metamorphic specifications_.

In collaboration with the tax experts, we reviewed some critical correctness
properties of tax preparation outcomes and observed that they are naturally
expressible as metamorphic specifications. One key contribution of this paper
is to explicate formal representations of these properties from the latest
Internal Revenue System (IRS) documents.

  * –

Testcase Generation. While it is an arduous task to compare an individual
situation with the precedents, the availability of software artifacts
implementing the tax laws permit us to query the tax outcomes for fictitious
individuals similar to a given individual. This combined with the metamorphic
nature of the requirements allows us validate the software system by comparing
the results for a given (source) individual with its perturbed follow-ups. We
developed a random search strategy to sample source and follow-up test cases
from the space of metamorphic relations and label them as passed or failed.
This strategy provides statistical guarantees (hypothesis testing) on the
correctness.

  * –

Lexicographic Classification Trees. Given a set of test cases with ‘pass’ or
‘fail’ labels over a metamorphic relation, decision tree classifiers, as a
white-box ML model, are natural choice to discriminate between the classes and
synthesize circumstances under which the software fails (Tizpaz-Niari et al.,
2018). However, the nature of metamorphic test cases makes it difficult to
adapt straightforward classification tree algorithms due to dependencies
between source and follow-up features. This dependency, however, is
lexicographical in order, and thus, we modify standard algorithms to enforce
the order during the search, which results in more intuitive explanations.

The proposed framework is implemented as the tool TenForty (named after the US
individual tax return form 1040). We performed experiments on OpenTaxSolver
(Roberts, 2021) (tax year of 2020), a popular open-source tax preparation
software (Community, 2019; Cherry, 2020), in five aspects of
disability/credits/deductions that are known to be challenging and error-prone
(IRS, 2020). In particular, we explicated $16$ metamorphic relations in those
areas and use them to generate test cases as well as oracles. Our technique
generates tens of thousands of random test cases using metamorphic properties.
We explain the failures using the lexicographical decision trees implemented
by modifying standard CART tree (Breiman et al., 1984) in scikit-learn library
(Pedregosa et al., 2011). As a result, our tool revealed four types of
failures in OpenTaxSolver: missing some eligibility conditions (e.g., married
people filing separately are not eligible to take earned income credits),
credits are not applied in extreme conditions when tax returns get close to
zero, and itemized deductions are not applied for some values of income and
credits.

##  2\. Background

The US tax code is based on over 2,600 pages of legal statutes from congress.
These statutes are accompanied by IRS regulations, rulings, and
clarifications, together amounting to nearly 9,000 pages. The structure of the
US tax code has been extensively studied by Lawsky (Lawsky, 2017; Pertierra et
al., 2017). They pointing out the tax code is not adhered to as intended and
the growing needs for formal legal reasoning. While they mentioned the
difficulty to encode the tax code in first-order logic (FOL), we show the
feasibility with metamorphic relations.

Figure 1.  General Framework using EITC. Our approach specifies metamorphic
properties from relevant tax policies. Then, it generates random test cases
and infers decision trees to localize circumstances under which the software
fails to satisfy properties.

Previously, a written statement of Nina E. Olson (National Taxpayer Advocate)
published by IRS (IRS, 2006) analyzed several (free) tax filing software for
the tax year of 2005. They designed four fictitious scenarios, including some
in which the taxpayer qualified for special tax benefits enacted to help
Hurricane Katrina victims (See (IRS, 2006, p.11-p.19)). They found that
several of the software did not prompt the taxpayers about these provisions.
Therefore, taxpayers ended up not getting the benefits designed for them.
Despite being hypothetical, the approach showed the flaws in the programs and
urged IRS to pay more attentions to software quality, in addition to software
security. Our approach is geared towards automating these kind of discoveries
in tax preparation software using metamorphic relations.

Within tax domain, Merigoux et al. (Merigoux et al., 2021) developed a
compiler for the French tax code. They pointed out multiple limitations of $M$
programming language, developed by French Public Finances Directorate to write
tax rules (available at (des Finances Publiques (DGFiP), 2019)). Then, they
developed a domain-specific language that allows for specifying complicated
rules and lifting them to modern languages like Python. They also used a
dynamic random search to validate the software, as opposed to formal
verification, due to the large space of inputs, floating-point computations,
and various optimizations. In comparisons, the US has much less automation in
tax preparation with no available specifications and regulated test cases.

In the absence of logical specifications in tax doamin, we turn to metamorphic
testing. Metamorphic testing (Chen et al., 1998) is primarily developed to
overcome oracle problem (Barr et al., 2015) that decides given an input
whether the output of the system is correct or not. The idea is to establish
correctness by reasoning about relations between multiple input-output
behaviors (Segura et al., 2016). For example, consider a program that
implements sin(x) function. While we do not know the exact outcome of function
for an arbitrary $x$, we can establish that for any $x_{1}$ and its
metamorphosed $x_{2}=2*\pi+x_{1}$, sin($x_{1}$) = sin($x_{2}$). In this
example, $x_{1}$ is a source (base) test, and $x_{2}$ is a follow-up
constructed by transforming the source to satisfy the metamorphic relation
between $x_{1}$ and $x_{2}$ and check the equality between outcomes.
Metamorphic properties have been used to validate machine learning classifiers
(Xie et al., 2011), autonomous vehicle (Zhou and Sun, [n.d.]), Google/Yahoo
search engine (Zhou et al., 2012), and social media apps like Facebook
(Ahlgren et al., 2021), but not used for tax preparation software.

Tax preparation software are paradigmatic examples of legal-critical software
systems. As an example of legal-critical software consider the work by
Matthews el al. (Matthews et al., 2019; Matthews et al., 2020) on forensic DNA
software to understand the role of the black-box forensic software in moral
decision making in criminal justice. They conduct independent testing of
Forensic Statistical Tool (FST), a forensic DNA system developed in 2010 by
New York City’s Office of Chief Medical Examiner (OCME). Using a collection of
over 400 mixed DNA samples, they found that an undisclosed data-dropping
method in software impacts about 25% of the samples and leads to shifted
results toward false inclusion of individuals who were not present in an
evidence sample. We believe that the techniques developed in this paper to
reason with tax preparation software makes a case for the suitability of
metamorphic specifications in expressing, testing, and debugging general
legal-critical software systems.

##  3\. Overview

As a demonstration of our framework (shown in Figure 1), this section
describes how we tested OpenTaxSolver (Roberts, 2021) (version for tax year
2020) in one of $5$ domains considered in this paper: the Earned Income Tax
Credit ($EITC$). The earned income tax credit is designed to lower the tax
burden for low and moderate income workers.

Extract Scenarios. The first step involves carefully examining the rules and
regulations. For the $EIC$, we extract scenarios from Worksheet 1 in
Publication 596 (596, 2021).

Metamorphic properties. We specify $4$ metamorphic relations for $EIC$, as
shown in Table 1 (properties #3-#6). Property #3 specifies that married filing
separately ($MFS$) is illegible to take $EIC$ credits. Property #4 describes
that individuals who are married filing jointly ($MFJ$) are illegible if their
adjusted gross income ($AGI$) is over $56,844$. Property #5 says that an
eligible individual with $EIC$ claim (Line $27$ of IRS $1040$) should have
higher returns compared to metamorphosed one who are not eligible due to their
$AGI$, dependents, or zero claim. Finally, property #6 establishes that among
two similarly eligible individuals, the one with the higher $EIC$ claims
should have a higher tax return.

Random Test-Case Generations. We generate test cases from these metamorphic
properties. We encode each metamorphic property as a search problem where the
objective is to find an individual and its metamorphosed one such that their
deviants from expected outcomes are maximum. We sample data points uniformly
at random to generate the source test case and perturb it to generate follow-
ups from its neighbors. Algorithm 1 shows the random search strategy. For
$EIC$, the random search generates over $61$k, $62$k, $64$k, and $31$k for
properties #3 to #6, respectively, in a $10$ minutes run. OpenTaxSolver failed
for properties #3-#4 and passed for properties #5-#6.

Explaining Failure Circumstances. Given the set of passed and failed inputs,
we use a modified CART decision tree algorithm (detailed in Section 5) to
infer what conditions distinguish failed test cases from passed ones. Since
the software fails all test cases for properties #3-#4, the premises of
metamorphic relations simply explain the failure circumstances. In these
cases, the software misses two eligibility conditions (married filing
separately and AGI) and consequently fails in relevant test cases. For
illustrations, Figure 1 (right) shows these circumstances, as compared to
properties #5-#6. Beyond $EIC$, one of failures found in this paper pinpoint
to conditions where the tax returns get close to zero (see Figure 3). A
similar bug has been observed for the French tax software due to rounding
algorithms (Merigoux et al., 2021).

##  4\. Problem Statement

The _functional_ model of tax software consists of a tuple $(X,\mathcal{F})$
where $X=\left\\{X_{1},X_{2},\ldots,X_{n}\right\\}$ is the set of variables
corresponding to various fields about an individual in the tax return form and
$\mathcal{F}:\mathcal{D}_{1}\times\mathcal{D}_{2}\times\cdots\times\mathcal{D}_{n}\to\mathbb{R}_{\geq
0}$ is the _federal tax return_ computed by the software, where
$\mathcal{D}_{i}$ is the domain of variable $X_{i}$. We write $\mathcal{D}$
for $\mathcal{D}_{1}\times\mathcal{D}_{2}\times\cdots\times\mathcal{D}_{n}$.

These variables correspond to intuitive labels such as ${\tt age}$ (numerical
variable), ${\tt blind}$ (Boolean variable), and ${\tt sts}$ (filing status
with values such as MFJ, married filing jointly, and MFS, married filing
separately). For an individual ${\bf x}\in\mathcal{D}$, we write ${\bf x}(i)$
for the value of $i$-th variable, or ${\bf x}.{\tt lab}$ for the value of
variable ${\tt lab}$. Let $\mathcal{L}$ be the set of all labels.

For labels $L\subseteq\mathcal{L}$ and inputs ${\bf x}\in\mathcal{D}$ and
${\bf y}\in\mathcal{D}$, we say that ${\bf y}$ is a metamorphose of ${\bf x}$
with the exceptions of labels $L$, and we write ${\bf x}\equiv_{L}{\bf y}$ if
$\forall\ell\not\in L\text{ we have that }{\bf x}.\ell={\bf y}.\ell$. A
metamorphic relation is a first-order logic formula with variables in $X$,
constants from domains in $\mathcal{D}$, relation $\equiv_{L}$, comparisons
$\left\\{<,\leq,=,\geq,>\right\\}$ over numeric variables, predicate $\neg$
(negation) for Boolean valued labels, real-valued function for federal tax
return $\mathcal{F}:\mathcal{D}\to\mathbb{R}$, Boolean connectives $\wedge$,
$\lor$, $\neg$, $\implies$, $\iff$, and quantifiers $\exists x.\phi(x)$ and
$\forall x.\phi(x)$ with natural interpretations. W.l.o.g., we assume that the
formulas are given in the prenex normal form, i.e. a block of quantifiers
followed by a quantifier free formula. Using metamorphic relations, we can
express the property,

> for two individuals that differ only in age, the federal tax return of the
> older individual must be greater than or equal to that of the younger one,

using the following metamorphic property $\phi$:

$\forall{\bf x},{\bf y}\>({\bf x}\equiv_{age}{\bf y})\wedge({\bf
x}.age\geq{\bf y}.age)\implies(\mathcal{F}({\bf x})\geq\mathcal{F}({\bf y})).$

Falsification Problem. Given a tax preparation software $(X,\mathcal{F})$ and
a metamorphic property $\phi$, the falsification problem is to explore the
input space of the software to discover inputs that falsify the property.
Metamorphic properties containing only one variable are classical properties
relating inputs to outputs; however for properties with more than one
quantified variables, multiple inputs are required to evaluate the property.
Observe that the metamorphic property falsification problem is PSPACE-hard as
it is expressive enough to encode True Quantified Boolean formula (TQBF)
problem (when the input variables are Boolean and program logic encode Boolean
constraints). Hence, it is intractable to provide an exhaustive search
procedure. To overcome this challenge, we propose randomized search-based
testing approach.

Depending upon the number and nature of of quantifiers, multiple inputs need
to be sampled to ascertain the status of the property. Moreover, when the
input space is large or infinite, we may not be able to falsify subformulae of
the form $\exists{\bf x}.\phi({\bf x})$ as it would require testing the whole
state space. To overcome this challenge in practice, we recourse to
statistical testing guided by randomized exploration of the state space. In
the next section, we present a sampling strategy to falsify properties of the
form $\forall x.\phi(x)$; this procedure can be recursively invoked to provide
the procedure for metamorphic properties with arbitrary quantification.

##  5\. Approach

Table 1. Metamorphic properties for five domains in the US tax policies. $\mathcal{F}$ is federal tax return where negative values mean the individual owns payment to the IRS, $sts$ is filing status, $s\\_lab$ is spouse’s field $lab$, $MFJ$: married filing jointly, $MFS$ is married filing separately, $AGI$ is adjusted gross income, $L27$ is line $27$ of IRS $1040$ for Earned Income Tax Credit (EITC), $QC$ is the number of qualified children, $OD$ is the number of other dependents, $CTC$ is child tax credits, $L29$ is line $29$ of IRS $1040$ for Education Tax Credit ($ETC$), $MDE$ is medical/dental expenses, $iz$ is to use itemized deductions ($ID$) vs. standard deductions, and $L12$ is total itemized deductions ($ID$) from schedule $A$. Id |  Domain |  Metamorphic Property
---|---|---
1 |  Disability |  $\forall{\bf x},{\bf y}(({\bf x}{\equiv_{age}}{\bf y})\wedge({\bf x}.age{\geq}65)\wedge({\bf y}.age{<}65))\lor(({\bf x}{\equiv_{blind}}{\bf y})\wedge({\bf x}.blind\wedge\neg{\bf y}.blind))\implies\mathcal{F}({\bf x})\geq\mathcal{F}({\bf y})$
2 |  Disability |  $\forall{\bf x}({\bf x}.sts=MFJ)\implies\forall{\bf y}(({\bf x}\equiv_{s\\_age}{\bf y})\wedge({\bf x}.s\\_age\geq 65)\wedge({\bf y}.s\\_age<65))\lor(({\bf x}\equiv_{s\\_blind}{\bf y})\wedge({\bf x}.s\\_blind\wedge\neg{\bf y}.s\\_blind))\implies\mathcal{F}({\bf x})\geq\mathcal{F}({\bf y})$
3 |  EITC |  $\forall{\bf x}({\bf x}.sts=MFS)\implies\forall{\bf y}({\bf x}{\equiv_{L27}}{\bf y}\wedge{\bf x}.L27>0.0\wedge{\bf y}.L27=0.0)\implies\mathcal{F}({\bf x}){=}\mathcal{F}({\bf y})$
4 |  EITC |  $\forall{\bf x}({\bf x}.sts{=}MFJ)\wedge({\bf x}.AGI{>}56,844)\implies\forall{\bf y}({\bf x}{\equiv_{L27}}{\bf y}\wedge{\bf x}.L27{>}0.0\wedge{\bf y}.L27{=}0.0){\implies}\mathcal{F}({\bf x}){=}\mathcal{F}({\bf y})$
5 |  EITC |  $\forall{\bf x}({\bf x}.sts{=}MFJ){\implies}\forall{\bf y}({\bf x}{\equiv_{AGI}}{\bf y}\wedge{\bf x}.AGI{\leq}56,844\wedge{\bf y}.AGI{>}56,844)\lor({\bf x}{\equiv_{L27}}{\bf y}\wedge{\bf x}.L27{>}0.0\wedge{\bf y}.L27{=}0.0)\lor({\bf x}{\equiv_{QC}}{\bf y}\wedge{\bf x}.QC{\geq}1\wedge{\bf y}.QC{=}0){\implies}\mathcal{F}({\bf x}){\geq}\mathcal{F}({\bf y})$
6 |  EITC |  $\forall{\bf x}({\bf x}.sts{=}MFJ){\wedge}({\bf x}.AGI{\leq}56,844){\wedge}({\bf x}.QC{\leq}3){\implies}\forall{\bf y}(({\bf x}{\equiv_{L27}}{\bf y}){\wedge}{\bf x}.L27{\geq}{\bf y}.L27){\implies}\mathcal{F}({\bf x}){\geq}\mathcal{F}({\bf y})$
7 |  CTC |  $\forall{\bf x}({\bf x}.sts{=}MFJ){\wedge}({\bf x}.AGI{\leq}200k)\forall{\bf y}(({\bf x}{\equiv_{L19}}{\bf y}){\wedge}({\bf x}.L19{\geq}{\bf y}.L19)){\implies}\mathcal{F}({\bf x}){\geq}\mathcal{F}({\bf y})$)
8 |  CTC |  $\forall{\bf x},{\bf x^{\prime}}({\bf x}.sts{=}{\bf x^{\prime}}.sts{=}MFJ){\wedge}({\bf x}.AGI{<}400k){\wedge}({\bf x^{\prime}}.AGI{\geq}400k){\wedge}{\lceil}{\bf x^{\prime}}.AGI{-}400k{\rceil}_{1k}*0.05{<}{\bf x^{\prime}}.QC*2k+{\bf x}.OD*0.5k{\implies}\forall{\bf y},{\bf y^{\prime}}({\bf x}{\equiv_{\\{QC,OD\\}}}{\bf y}){\wedge}({\bf x^{\prime}}{\equiv_{\\{QC,OD\\}}}{\bf y^{\prime}})\wedge(0{\leq}{\bf y}.QC{=}{\bf y^{\prime}}.QC{\leq}{\bf x}.QC{=}{\bf x^{\prime}}.QC\leq 10)\wedge(0{\leq}{\bf y}.OD{=}{\bf y^{\prime}}.OD\leq{\bf x}.OD{=}{\bf x^{\prime}}.OD\leq 10)\implies(\mathcal{F}({\bf x})-\mathcal{F}({y}))\geq(\mathcal{F}(x^{\prime})-\mathcal{F}(y^{\prime}))$
9 |  ETC |  $\forall{\bf x}({\bf x}.sts=MFS)\implies\forall{\bf y}({\bf x}{\equiv_{L29}}{\bf y}\wedge{\bf x}.L29>0.0\wedge{\bf y}.L29=0.0)\implies\mathcal{F}({\bf x}){=}\mathcal{F}({\bf y})$
10 |  ETC |  $\forall{\bf x}({\bf x}.sts{=}MFJ)\wedge({\bf x}.AGI{>}180k)\implies\forall{\bf y}({\bf x}{\equiv_{L29}}{\bf y}\wedge{\bf x}.L29{>}0.0\wedge{\bf y}.L29{=}0.0){\implies}\mathcal{F}({\bf x}){=}\mathcal{F}({\bf y})$
11 |  ETC |  $\forall{\bf x}({\bf x}.sts{=}MFJ)\wedge({\bf x}.AGI{<}160k)\implies\forall{\bf y}({\bf x}{\equiv_{L29}}{\bf y}\wedge{\bf x}.L29{\geq}{\bf y}.L29){\implies}\mathcal{F}({\bf x}){\geq}\mathcal{F}({\bf y})$
12 |  ETC |  $\forall{\bf x},{\bf x^{\prime}}({\bf x}.sts{=}{\bf x^{\prime}}.sts{=}MFJ)\wedge({\bf x}.AGI{\leq}160k)\wedge(160k{\leq}{\bf x^{\prime}}.AGI{\leq}180k)\implies\forall{\bf y},{\bf y^{\prime}}(({\bf x}\equiv_{L29}{\bf y})\wedge({\bf x^{\prime}}\equiv_{L29}{\bf y^{\prime}})\wedge({\bf x}.L29={\bf x^{\prime}}.L29\geq{\bf y}.L29={\bf y^{\prime}}.L29)){\implies}(\mathcal{F}({\bf x})-\mathcal{F}({y}))\geq(\mathcal{F}(x^{\prime})-\mathcal{F}(y^{\prime}))$
13 |  ID |  $\forall{\bf x}({\bf x}.MDE{\leq}{\bf x}.AGI*7.5\%)\implies\forall{\bf y}({\bf x}{\equiv_{L12}}{\bf y}\wedge{\bf x}.L12{>}0.0\wedge{\bf y}.L12{=}0.0)\implies\mathcal{F}({\bf x}){=}\mathcal{F}({\bf y})$
14 |  ID |  $\forall{\bf x}(\neg{\bf x}.iz)\implies\forall{\bf y}({\bf x}{\equiv_{L12}}{\bf y}\wedge{\bf x}.L12{>}0.0\wedge{\bf y}.L12{=}0.0)\implies\mathcal{F}({\bf x}){=}\mathcal{F}({\bf y})$
15 |  ID |  $\forall{\bf x}({\bf x}.sts{=}MFJ){\implies}\forall{\bf y}(({\bf x}{\equiv_{iz,L12}}{\bf y}){\wedge}({\bf x}.iz{\wedge}{\neg}{\bf y}.iz){\wedge}({\bf x}.L12{\leq}24.8k{\wedge}{\bf x^{\prime}}.L12{=}0.0)){\implies}\mathcal{F}({\bf x}){\leq}\mathcal{F}({\bf y})$
16 |  ID |  $\forall{\bf x}({\bf x}.sts{=}MFJ){\implies}\forall{\bf y}(({\bf x}{\equiv_{iz,L12}}{\bf y}){\wedge}({\bf x}.iz{\wedge}{\neg}{\bf y}.iz){\wedge}({\bf x}.L12{>}24.8k{\wedge}{\bf x^{\prime}}.L12{=}0.0)){\implies}\mathcal{F}({\bf x}){\geq}\mathcal{F}({\bf y})$

We develop an efficient metamorphic testing and debugging to uncover bugs in
the tax preparation software.

Input: Tax preparation software $\mathcal{P}$, initial input seeds $I$,
metamorphic property $p$, a tolerance threshold $\delta$, a Bayes factor $B$,
a lower-bound on the confidence $\theta$, and timeout $T$.

Output: Passed/Failed, test cases, decision tree

1

2$(x_{m},\Delta_{FTR},res)$ $\leftarrow$ Sample($I$), 0, ${\tt True}$

3while  _time() - $start\\_time$ $<$ T_ do

4 $k$ $\leftarrow$ 0

5 $x_{1}$ $\leftarrow$ UniformPerturb($x_{m}$, $p$)

6 $x_{2}$ $\leftarrow$ UniformPerturb($x_{1}$, $p$)

7 $\Delta$ $\leftarrow$ Dist($\mathcal{P}(x_{1})$, $\mathcal{P}(x_{2})$)

8 if  _$\Delta$ $>$ $\delta$_ then

9 $I$.Add(($x_{1}$,$x_{2}$),‘failed’)

10 if  _$\Delta$ $>$ $\Delta_{FTR}$_ then

11 $x_{m}$ $\leftarrow$ $x_{1}$

12 $\Delta$ $\leftarrow$ $\Delta_{FTR}$

13

14 $res$ $\leftarrow$ ${\tt False}$

15 else

16 $I$.Add(($x_{1}$,$x_{2}$),‘passed’)

17 $k$ $\leftarrow$ $k$ \+ $1$

18 if  _$k$ $<$ $\frac{-\log B}{\log\theta}$_ then

19 Go to $5$

20

21

22if  _$I[$ ‘passed’$]$ = {} $\lor$ $I[$‘failed’$]$ = {}_ then

23 return $p$

24else

25 $t$ $\leftarrow$ LexicographicDTClassifier($I$)

26

return $res$, $I$, $t$.

Algorithm 1 RandomTestCaseGeneration

Algorithm 1 sketches different steps in our approach. We start from some
initial seed inputs $I$. In each step, the search strategy selects and
perturbs inputs from the set of promising inputs (those maximizing the deviant
from the expect outcome) and generates a base test case (line $4$). Then, it
perturbs the base to generate follow-up cases (line $5$). Next, it executes
the base and follow-up inputs on the target software and quantify the deviant
between the outcomes (line $6$). If the deviant is more than a threshold, it
adds the inputs with ‘failed’ label (line $8$). Furthermore, if the deviant is
higher than any previous ones, it adds the inputs as promising ones (line
$9$). Otherwise, it adds the inputs with ‘passed’ label (line $12$). However,
the absence of evidence for failures does not mean the correctness. This is
indeed an important shortcoming for metamorphic-based random test generations.
Our algorithm instead uses a statistical hypothesis testing to provide
statistical confidence on the absence of failures, starting from the base test
case. The null and alternative hypotheses are

$\mathcal{H}_{0}:\mathbb{P}(x_{1})\geq\theta,~{}~{}\mathcal{H}_{1}:\mathbb{P}(x_{1})<\theta$

where $\mathbb{P}(x_{1})$ is the probability that follow-up test cases,
starting from $x_{1}$ as the source test, are passed, $\theta$ is the lower-
bound on the probability, $\mathcal{H}_{0}$ is null hypothesis, and
$\mathcal{H}_{1}$ is the alternative. Our goal is to witness enough passed
test cases to accept $\mathcal{H}_{0}$ as opposed to $\mathcal{H}_{1}$. There
are multiple ways to conduct such statistical testing. The sequential
probability ratio test and a Bayes factor are examples. We follow Jeffreys
test (Jha et al., 2009; Sankaranarayanan et al., 2013), a variant of Bayes
factor, with a uniform prior to find a lower-bound on the number of successive
samples $K$ that sufficient for us to convince $\mathcal{H}_{0}$:

$K\geq\lceil(-\log_{2}B)/(\log_{2}\theta)\rceil$

where $B$ in numerator is Bayes factor and can be set to $100$ for a very
strong evidence. For instance, to achieve a $\theta=0.95$, we are required to
set $K\geq 90$ to be highly confident on accepting $\mathcal{H}_{0}$. Lines
13-15 show this hypothesis testing.

After generating the test suite, our algorithm uses a data-driven approach to
infer circumstances under which the software fails. Given the set of test
cases with ‘passed’ and ‘failed’ labels, the problem appears to be a standard
classification to discriminate between the two labels (Kampmann et al., 2020).
However, the generated samples are not independent as the follow-up samples
are dependent on the base samples. To overcome this challenge, we modified the
classical CART tree inference to enforce a lexicographical order between
features. This modified procedure is invoked in Algorithm 1 (line 19). Observe
that each test sample is a valuation for base and follow-up features. The
decision tree inference algorithm picks a feature and a split upon it that
minimize a selection criterion (e.g., impurity or entropy) among all other
features and splits in each step. To integrate lexicographic ordering within
features, we modified the split functionality and calculated the amount of
association between a follow-up feature and its prefixes. Mutual information
and linear correlations can be used to quantify such associations.

##  6\. Experiments

Figure 2.  Left. Tax returns are clustered into $5$ groups, varying values of
variables in properties #1,#2; Right. DT explains the number of yes answers to
four senior/disability (age above 65, blindness, spouse age over 65, and
spouse blindness) explains different returns.

Implementations. We implement test-case generations in Python using the XML
parser library to define the tax field variables and their domains. We
implement the lexicographic decision trees in scikit-learn framework
(Pedregosa et al., 2011). In particular, we implement the modifications in
_splitter.pyx (a Cypthon class) in sklearn.tree directory as a part of
node_split() function.

Tax Policies. We consider aspects in the US individual income tax return that
deal with credits/deductions and are notoriously challenging (IRS, 2020). We
focus on fields related to senior and disable individuals; Earned Income Tax
Credit (EITC) (596, 2021); Child Tax Credit (CTC) that reduces the taxes owed
on each qualifying child under the age of 17 (8812, 2021); Educational Tax
Credit (ETC) that help students with the cost of higher education by lowering
their owed taxes or increasing their refund (8863, 2021); and itemized
deductions (ID) that is an option to taxpayers with significant tax deductible
expenses (Schedule-A, 2021).

Metamorphic Relations. We use scenarios and examples described in these
policies to synthesize metamorphic relations. Table 1 shows $16$ metamorphic
relations in $5$ domains. Next, we provide a brief explanation of some of
these properties.

  * –

Property #1. An individual with disability must receive similar or better tax
benefits when compared with a person without disability who is similar in
every other aspect.

  * –

Property #2. An individual with the married filing jointly ($MFJ$) status with
disabled spouse must receive similar or higher tax benefits compared to a
similar individual but without the disability of the spouse.

  * –

Property #3. An individual with the married filing separately ($MFS$) status
is not eligible for EITC. This is based on tax year 2020. The eligibility has
since changed, and $MFS$ with EITC claims may be eligible for tax year 2021.

  * –

Property #4. An individual with the married filing jointly ($MFJ$) status with
$AGI$ over $56,844$ is ineligible for EITC in tax year 2020. The $AGI$
threshold changes every tax years.

  * –

Property #5. An individual who qualifies for EITC must receive a higher return
than a similar unqualified one.

  * –

Property #6. Among two qualified individuals with EITC, one with higher EITC
claims receives higher or equal benefits.

  * –

Property #7. Among two qualified married filing jointly ($MFJ$) individuals,
one with higher child tax credits receives higher or equal tax return
benefits.

  * –

Property #8. This property requires a comparison between four “similar”
individuals since there is a relation between two variables of interests:
$AGI$ and the number of qualified children/others to claim a CTC. A individual
with more qualified dependents must receive higher or similar tax return
benefits than an individual with fewer dependents after adjusting for the
effects of income levels on the calculations of both final return and the
amounts of CTC claims. Expressing this property requires holding the income of
two individuals same per each qualified number of children/others.

  * –

Property #9. An individual with the married filing separately ($MFS$) status
is is ineligible for ETC in tax year 2020.

  * –

Property #10. An individual with the married filing jointly ($MFS$) status
with $AGI$ over $180k$ is ineligible for ETC.

  * –

Property #11. A qualified individual with $AGI$ below $160k$ who claims ETC
received higher or similar tax return benefits compared to a similar
individual who is ineligibility or does not claim ETC for tax year 2020.

  * –

Property #12. This property requires a comparison between four four similar
individuals as the rule changes for individuals with $AGI$ below $160k$ and
between $160k$ and $18k$. By holding $AGI$ constant between two individuals
with $AGI$ below $160k$ (varying the $ETC$ claims) and two individuals with
$AGI$ between $160k$ and $180k$ (varying the $ETC$ claims with the same rate),
the property requires that individuals with income below $160k$ receives
higher or similar tax returns without the influence of $AGI$ in the
computation.

  * –

Property #13. An individual who files with medical/dental expenses ($MDE$)
below 7.5% of their $AGI$ and itemizes their deductions receives the same
return as a similar individual with no $MDE$ claims.

  * –

Property #14. When filing with a standard deduction, total itemized deduction
(Line $12$) must have no effect on the tax returns.

  * –

Property #15. An individual who files with itemized deductions below the
standard deductions receive a lower or similar tax return benefits compared to
a similar individual who used the standard deductions.

  * –

Property #16. An individual who files with itemized deductions above the
standard deductions receive a higher or similar tax return benefits compared
to a similar individual who claims standard deductions.

Table 2. Experimental results on OpenTaxSolver using the $16$ metamorphic
relations. Test-case generation time-outs at $10$ mins.

Property ID | Random Test-Case Generations | DT Models or FOL if all cases are passed/failed
---|---|---
#test cases |  #fail |  #pass | 1st failure(s) | Max. $\Delta_{FTR}$ | type | Computation(s) | Accuracy | Height |  #Leaf Nodes
Disability (1) | 68,893 | 0 | 68,893 | N/A | 0 | FOL | 0.0 | 100% | 2 | 2
Disability (2) | 64,244 | 0 | 64,244 | N/A | 0 | FOL | 0.0 | 100% | 3 | 2
EIC (3) | 61,592 | 61,592 | 0 | 0.1 | 1,000 | FOL | 0.0 | 100% | 2 | 1
EIC (4) | 62,253 | 62,253 | 0 | 0.1 | 1,000 | FOL | 0.0 | 100% | 4 | 1
EIC (5) | 64,581 | 0 | 64,581 | N/A | 0 | FOL | 0.0 | 100% | 3 | 3
EIC (6) | 31,886 | 0 | 31,886 | N/A | 0 | FOL | 0.0 | 100% | 5 | 1
CTC (7) | 59,823 | 0 | 59,823 | N/A | 0 | FOL | 0.0 | 100% | 4 | 1
CTC (8) | 33,343 | 0 | 33,343 | N/A | 0 | FOL | 0.0 | 100% | 13 | 1
ETC (9) | 66,596 | 66,596 | 0 | 0.1 | 1,000 | FOL | 0.0 | 100% | 2 | 1
ETC (10) | 63,562 | 63,562 | 0 | 0.1 | 1,000 | FOL | 0.0 | 100% | 4 | 1
ETC (11) | 31,112 | 2,356 | 28,756 | 0.3 | 177 | DT | 5.2 | 98% | 5 | 12
ETC (12) | 33,330 | 0 | 33,330 | N/A | 0 | FOL | 0.0 | 100% | 8 | 1
ID (13) | 65,801 | 889 | 64,912 | 114.4 | 245 | DT | 5.4 | 100% | 4 | 5
ID (14) | 31,823 | 0 | 31,823 | N/A | 0 | FOL | 0.0 | 100% | 3 | 1
ID (15) | 32,754 | 0 | 32,754 | N/A | 0 | FOL | 0.0 | 100% | 5 | 1
ID (16) | 32,474 | 785 | 31,689 | 0.8 | 160 | DT | 5.4 | 98% | 9 | 22

Test-Case Generations. We employed our random test-case generation algorithm
to generate base and follow-ups that satisfy the relation between inputs and
negate the relation between outcomes. In Algorithm 1, we set $B$ to $100$ and
$\delta$ to $0.95$. We run each experiment for 10 mins. Table 2 shows the
results of random test-case generations. We report the number of passed and
failed test cases as well as the maximum observed differences in tax returns
in failures. Overall, we found evidences of failures for $7$ properties out of
$16$. Our search algorithm often finds the evidences for failure below $1$
second, except one case that took close to $2$ minutes (property #13). The
maximum deviant observed is $$1,000$. We restricted the claimed credits for
EITC, CTC, and ETC to be at most $$1,000$, and itemized deductions to be up to
$$100,000$.

Figure 3.  Left. CART DT shows circumstances under which failed test cases
(orange leaves) are distinguished from passed ones (green leaves) for itemize
deductions with medical expenses; Middle. Lexicographic trees provide richer
information for the same task as one in the left; Right. Failure circumstances
in Education Tax Credits (ETC): failed cases have a federal tax return in an
interval that includes $0$. Note that features ending with _1 and _2 are bases
and ending with _3 and _4 are metamorphosed ones.

Decision Tree Explanations. Table 2 shows the scalability and performance of
DT for experiments with both failed and passed cases. We only use DT
explanations for cases with some passes and other failures. We report the
computation times, accuracy, the height of tree, and the number of leaf nodes.
Though software passes all test cases for properties #1 and #2, we first use
them to overview DT-based explanatory model as a debugging tool in high-level.
Then, we show the efficacy for cases with failure and success test cases.
Figure 2 (left) shows $5$ clusters of federal tax returns (FTR). The next step
is to find out what features (fields in tax filing) distinguish different
clusters. Figure 2 (right) shows the corresponding DT model for explanations.
Each path from root nodes to the leaf defines a predicate function per
cluster. For example, the lowest cluster (orange) is explained by a predicate
where their age and their spouse’s age are less than $65$, and none of them
are blind whereas one higher cluster has exactly one ‘yes’ to these options.

We use a similar technique to explain circumstances under which the software
fails to satisfy the metamorphic properties. We label failed test cases with
orange colors and passed ones with green colors. Note that if all test cases
are failed or passed, we just report the premises of corresponding metamorphic
property. As we discussed before, standard decision trees do not capture
dependencies and have poor explanatory features. Figure 3 (left) shows
explanations for property #13 with standard decision trees. As we can see, the
explanation is only based on follow-up cases (features end with _2) and does
not provide intuitions on how base tests contribute to witness a failure.
Figure 3 (middle) shows corresponding decision tree for property #13. The
decision tree shows that failures happened when the base income is over
$151$k, the base cases have medical expenses below $13$k, the itemized
deductions are selected, and the follow-up cases have medical expenses over
$13$k. Figure 3 (right) shows DT model for failure circumstances for the
property #11 where the failures correlate with an FTR interval that includes
zero.

In summary, we found and explained four types of bugs: i) missing eligibility
conditions completely (properties #3-#4 and #9-#10); ii) unexpected outcomes
when the federal tax returns get close to zero (property #11); iii) applying
itemized deductions when expenses are less than $7.5\%$ of AGI (property #13);
and iv) itemized deductions slightly exceed a standard deduction, but result
in a lower tax return (property #16).

Performance of Lexicographic DT algorithm. We did not find a significant
performance degradation using the proposed decision tree inferences. We
performed experiments on growing number of samples/features and observed that
the computation times grow from $2.69$(s) to $5.15$(s) for standard DT and
from $2.72$(s) to $5.23$(s) for lexicographic DT, a maximum slow-down of 100
ms.

##  7\. Conclusion

Tax preparation software are increasingly indispensable in navigating the
complex tax structure. Since the legal responsibilities of bugs in such
software rest on the end-users, most of whom cannot afford expensive
accountants or commercial software, developing debugging aids for such systems
is our social responsibility.

This paper presented a data-driven debugging framework for metamorphic
specifications expressed in a first-order logic. We hope that our experience
in capturing the tax-preparation software requirements convinced the reader
that the first-order logic based metamorphic specifications are both intuitive
and unambiguous in expressing the comparative nature of legal requirements.
The experimental results also demonstrated that search-based software
engineering approaches are useful in uncovering and explaining bugs in a
popular open-source tax preparation software. We believe that the proposed
approach provides a blueprint for formal testing and debugging for other
legal-critical software systems.

## References

  * (1)
  * 596 (2021) IRS 596. 2021.  Earned Income Credit (EIC).  https://www.irs.gov/pub/irs-pdf/p596.pdf.  Online.
  * 8812 (2021) IRS 8812. 2021.  Credits for Qualifying Children and Other Dependents.  https://www.irs.gov/forms-pubs/about-schedule-8812-form-1040.  Online.
  * 8863 (2021) IRS 8863. 2021.  Education Credits.  https://www.irs.gov/pub/irs-pdf/f8863.pdf.  Online.
  * Ahlgren et al. (2021) John Ahlgren, Maria Eugenia Berezin, Kinga Bojarczuk, Elena Dulskyte, Inna Dvortsova, Johann George, Natalija Gucevska, Mark Harman, Maria Lomeli, Erik Meijer, et al. 2021\.  Testing Web Enabled Simulation at Scale Using Metamorphic Testing. In _ICSE-SEIP_. IEEE, 140–149.
  * Barr et al. (2015) Earl T. Barr, Mark Harman, Phil McMinn, Muzammil Shahbaz, and Shin Yoo. 2015.  The Oracle Problem in Software Testing: A Survey.  _IEEE Transactions on Software Engineering_ 41, 5 (2015), 507–525.  https://doi.org/10.1109/TSE.2014.2372785
  * Breiman et al. (1984) L. Breiman, J.H. Friedman, R.A. Olshen, and C.I. Stone. 1984.  _Classification and regression trees_.  Wadsworth: Belmont, CA.
  * Chen et al. (1998) T. Y. Chen, S. C. Cheung, and S.M. Yiu. 1998.  _Metamorphic Testing: A New Approach for Generating Next Test Cases_.  Technical Report HKUST-CS98-01.  https://arxiv.org/abs/2002.12543
  * Cherry (2020) Jessica Cherry. 2020\.  Use OpenTaxSolver as an open source alternative to TurboTax.  https://opensource.com/article/20/2/open-source-taxes.  Online.
  * Community (2019) Reddit Linux Community. 2019\.  Open source alternative to turbotax called Open-source Tax Solver.  https://www.reddit.com/r/linux/comments/bhp3cq/open_source_alternative_to_turbotax_called/.  Online.
  * des Finances Publiques (DGFiP) (2019) Direction Générale des Finances Publiques (DGFiP). 2019.  Les règles du moteur de calcul de l’impôt sur le revenu et de l’impôt sur la fortune immobilière.  https://gitlab.adullact.net/dgfip/ir-calcul.  online.
  * Garrone (2021) Antonin Garrone. 2021\.  Openfisca France.  https://github.com/openfisca/openfisca-france.  Online.
  * Grimshaw and Patterson (2021) Aidan Grimshaw and Zak Patterson. 2021.  UsTaxes: a free open-source tax filing application.  https://github.com/ustaxes/UsTaxes.  Online.
  * IRS (2006) IRS. 2006.  Written Statement of Nina E. Olson National Taxpayer Advocate Before the Committee on Finance United States Senate Hearing on Tax Return Preparation Options for Taxpayers.  https://www.irs.gov/pub/tas/ntatestimonysfc_tax_return_preparation_process040406.pdf.  Online.
  * IRS (2020) US IRS. 2020.  Filing taxes 101: Common errors taxpayers should avoid.  https://www.irs.gov/newsroom/filing-taxes-101-common-errors-taxpayers-should-avoid.  Online.
  * Jha et al. (2009) Sumit K Jha, Edmund M Clarke, Christopher J Langmead, Axel Legay, André Platzer, and Paolo Zuliani. 2009.  A bayesian approach to model checking biological systems. In _CMSB_. Springer, 218–234.
  * Kampmann et al. (2020) Alexander Kampmann, Nikolas Havrikov, Ezekiel O Soremekun, and Andreas Zeller. 2020.  When does my program do this? learning circumstances of software behavior. In _FSE_. 1228–1239.
  * Lawsky (2017) Sarah B. Lawsky. 2017\.  Formalizing the Code.  _Northwestern Public Law Research Paper_ (2017).  https://doi.org/10.2139/ssrn.2987065
  * Matthews et al. (2019) Jeanna Matthews, Marzieh Babaeianjelodar, Stephen Lorenz, Abigail Matthews, Mariama Njie, Nathaniel Adams, Dan Krane, Jessica Goldthwaite, and Clinton Hughes. 2019.  The Right To Confront Your Accusers: Opening the Black Box of Forensic DNA Software. In _Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society_ _(AIES ’19)_. 321–327.  https://doi.org/10.1145/3306618.3314279
  * Matthews et al. (2020) Jeanna Neefe Matthews, Graham Northup, Isabella Grasso, Stephen Lorenz, Marzieh Babaeianjelodar, Hunter Bashaw, Sumona Mondal, Abigail Matthews, Mariama Njie, and Jessica Goldthwaite. 2020.  _When Trusted Black Boxes Don’t Agree: Incentivizing Iterative Improvement and Accountability in Critical Software Systems_.  Association for Computing Machinery, 102–108.  https://doi.org/10.1145/3375627.3375807
  * Merigoux et al. (2021) Denis Merigoux, Raphaël Monat, and Jonathan Protzenko. 2021.  A Modern Compiler for the French Tax Code. In _Proceedings of the 30th ACM SIGPLAN International Conference on Compiler Construction_ _(CC 2021)_. Association for Computing Machinery, 71–82.  https://doi.org/10.1145/3446804.3446850
  * Pedregosa et al. (2011) F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. 2011.  Scikit-learn: Machine Learning in Python.  _Journal of Machine Learning Research_ (2011), 2825–2830.
  * Pertierra et al. (2017) Marcos A. Pertierra, Sarah Lawsky, Erik Hemberg, and Una-May O’Reilly. 2017.  Towards Formalizing Statute Law as Default Logic through Automatic Semantic Parsing. In _Proceedings of the Second Workshop on Automated Semantic Analysis of Information in Legal Texts_.  http://ceur-ws.org/Vol-2143/paper9.pdf
  * Roberts (2021) Aston Roberts. 2021\.  Open Tax Solver.  https://sourceforge.net/projects/opentaxsolver/.  Online.
  * Sankaranarayanan et al. (2013) Sriram Sankaranarayanan, Aleksandar Chakarov, and Sumit Gulwani. 2013.  Static analysis for probabilistic programs: inferring whole program properties from finitely many paths. In _PLDI_. 447–458.
  * Schedule-A (2021) IRS Schedule-A. 2021\.  Itemized Deductions.  https://www.irs.gov/pub/irs-pdf/f1040sa.pdf.  Online.
  * Segura et al. (2016) S. Segura, G. Fraser, A. B. Sanchez, and A. Ruiz-Cortés. 2016\.  A Survey on Metamorphic Testing.  _IEEE Transactions on Software Engineering_ 42, 9 (Sept 2016), 805–824.
  * Soled and Thomas (2017) Jay A. Soled and Kathleen DeLaney Thomas. 2017.  Regulating Tax Return Preparation.  _Boston College Law Review_ 58 (2017), 152–204.
  * Tizpaz-Niari et al. (2018) Saeid Tizpaz-Niari, Pavol Cerny, Bor-Yuh Evan Chang, and Ashutosh Trivedi. 2018.  Differential performance debugging with discriminant regression trees. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 32.
  * US-IRS (2020) US-IRS. 2020.  Six reasons 90 percent of people will e-file their tax returns.  https://www.irs.gov/pub/irs-utl/oc-e-file.pdf/.  online.
  * US.IRS ([n.d.]) US.IRS. [n.d.].  Filing statistics for week ending December 11 2020.  filing-season-statistics-for-week-ending-december-11-2020.  online.
  * Xie et al. (2011) Xiaoyuan Xie, Joshua W. K. Ho, Christian Murphy, Gail Kaiser, Baowen Xu, and Tsong Yueh Chen. 2011\.  Testing and Validating Machine Learning Classifiers by Metamorphic Testing.  _Journal of Systems and Software (JSS)_ (2011), 544–558.  https://doi.org/10.1016/j.jss.2010.11.920
  * Zhou and Sun ([n.d.]) Zhi Quan Zhou and Liqun Sun. [n.d.].  Metamorphic Testing of Driverless Cars.  _Commun. ACM_ 62, 3 ([n. d.]), 61–67.
  * Zhou et al. (2012) Zhi Quan Zhou, ShuJia Zhang, Markus Hagenbuchner, TH Tse, Fei-Ching Kuo, and Tsong Yueh Chen. 2012\.  Automated functional testing of online search services.  _Software Testing, Verification and Reliability_ (2012), 221–243.


# Transformations in quantum networks via local operations assisted by
finitely many rounds of classical communication

Cornelia Spee  Institute for Theoretical Physics, University of Innsbruck,
Technikerstraße 21A, 6020 Innsbruck, Austria  Institute for Quantum Optics and
Quantum Information (IQOQI), Austrian Academy of Sciences, Boltzmanngasse 3,
1090 Vienna, Austria  Tristan Kraft  Institute for Theoretical Physics,
University of Innsbruck, Technikerstraße 21A, 6020 Innsbruck, Austria
Naturwissenschaftlich-Technische Fakultät, Universität Siegen, Walter-Flex-
Straße 3, 57068 Siegen, Germany

###### Abstract

Recent advances have lead towards first prototypes of a quantum internet in
which entanglement is distributed by sources producing bipartite entangled
states with high fidelities. This raises the question which states can be
generated in quantum networks based on bipartite sources using local
operations and classical communication. In this work we study state
transformations under finite rounds of local operations and classical
communication in networks based on maximally entangled two-qubit states. We
first derive the symmetries for arbitrary network structures as these
determine which transformations are possible. Then we show that contrary to
tree graphs for which it has already been shown that any state within the same
entanglement class can be reached there exist states which can be reached
probabilistically but not deterministically if the network contains a cycle.
Furthermore, we provide a systematic way to determine states which are not
reachable in networks consisting of a cycle. Moreover, we provide a complete
characterization of the states which can be reached in a cycle network with a
protocol where each party measures only once and each step of the protocol
results in a deterministic transformation. Finally, we present an example
which cannot be reached with such a simple protocol.

Introduction.— In the last decades a lot of effort has been devoted to realize
the first prototypes of a quantum network Kimble2008 ; Wehner2018 , based on
various physical platforms Cirac1997 ; Duan2010 ; Reiserer2015 . Quantum
networks offer promising platforms for quantum information processing tasks
such as long-distance quantum communication Duan2001 , or distributed quantum
computing Cirac1999 ; Spiller2006 . Moreover, they are also interesting from a
theoretical point of view since they require novel tools to study the
correlations that can arise from such networks, which is in itself a
challenging problem, and to evaluate their performance Elkouss2020  (and Refs.
therein). Nevertheless, a lot of progress has recently been made concerning
the characterization of correlations Gisin2020  (and Refs. therein) and
entanglement Kraft2020triangle ; Navascues2020 ; Luo2020 ; Kraft2020 ;
Aberg2020 .

In quantum networks, entanglement is distributed by multiple sources, rather
than a single source. Subsequently, the entanglement created in the network
can be manipulated, e.g., by means of entanglement swapping teleport , and can
thus be spread over the entire network Acin2007 . Entanglement swapping is an
instance of a much larger and important class of local operations assisted by
classical communication (LOCC). The general question consists in identifying
which state transformations are possible via LOCC and which are the most
useful states under such a restriction. In the bipartite case this question is
answered by the Nielsen majorization criterion Nielsen . In case the
transformation is not required to be deterministically, one arrives at the so-
called stochastic LOCC (SLOCC) operations. For instance, in the case of three
qubits it is known that there exist only six classes of states that are
equivalent under SLOCC Duer . For four parties the number of SLOCC classes is
already infinite Verstraete .

Despite the fact that the class of LOCC operations is of fundamental
importance for many quantum information tasks it is notoriously difficult to
characterize (see e.g. Donald2002 ; Chitambar2011 ; Chitambar2012 ; WinterLOCC
; Cohen2017 ). Despite many difficulties, significant progress has been made,
e.g., in the case where only finitely many rounds of classical communication
(finite-round LOCC) are considered, in recent years Turgut1 ; Turgut2 ;
finiteroundLU ; Vicente2013 ; Schwaiger2015 ; Spee2016 ; Hebenstreit2016 .

Figure 1: Schematic illustration of the procedure that allows to identify the
symmetries of the triangle network. the first and the second picture are
identical up to rearrangement of the parties and nodes. In order to transform
the second picture into the third one we used that $Y\otimes\mbox{$1{\bf
l}$}\left|\Phi^{+}\right>=\mbox{$1{\bf l}$}\otimes
Y^{T}\left|\Phi^{+}\right>$. This, together with the fact that all symmetries
of the $\left|\Phi^{+}\right>$ state are of the form $Y\otimes Y^{-T}$, proves
that Eq. (3) holds.

In this work we will study the transformation of entanglement in quantum
networks under LOCC. We emphasize, that in case the parties have access to
many copies of maximally entangled states they can use teleportation in order
to realize an arbitrary entangled state. In our scenario however, we consider
the more realistic scenario where sources distribute single copies of
bipartite maximally entangled states according to some predefined network
structure and then perform an LOCC transformation involving only a finite
number of rounds.

In Ref. Hayata  it has already been shown that if the graph is a tree graph
then any state within this SLOCC class can be realized. As we will show for
any network that contains a cycle, i.e., that is not a tree graph, this no
longer holds true. We will determine pure states which can/cannot be reached
within such a scenario. First, we will show that, surprisingly, in such a
network all local symmetries are of a very specific form. This allows us to
provide a systematic approach to rule out a large class of states which can
never be realized within networks consisting of a cycle. Moreover, we identify
all states which can be obtained in such networks under the restriction that
each party performs at most one non-trivial measurement. Finally, we show that
there exist states which cannot be reached with a protocol where each party
measures only once.

Symmetries of Quantum Networks.— Let us first fix the following notation: any
network consists of nodes $1,\dots,n$ connected by edges $e\in E$ that
correspond to maximally entangled two-qubit states $\left|\Phi^{+}\right>$.
Thus, the initial state of the network is $\bigotimes_{e\in
E}\left|\Phi^{+}\right>_{e}$. In the following we will restrict to
transformations among pure states that preserve the ranks of the local reduced
density matrices. Obviously, in this case Duer  it is not possible to reach
any state outside of the SLOCC class $h_{1}\otimes\ldots\otimes
h_{n}\prod_{e\in E}\left|\Phi^{+}\right>_{e}$ via a finite-round LOCC
protocol, where $h_{i}$ is an invertible operator acting on all the particles
node $i$ has received from the sources. Moreover, we will define
$e_{j}\equiv\\{e_{j}^{i},e_{j}^{k}\\}\in E$, where $j$ labels the source, and
$i,k$ label the nodes that are connected by the source $j$.

We will use the following condition Gour , which is a necessary condition on
finite round LOCC transformations to exist measuroutcdonotexist  in the
described scenario:

$\sum_{i}p_{i}S_{i}^{\dagger}HS_{i}=r\mbox{$1{\bf l}$},$ (1)

where $\\{p_{i}\\}$ is a probability distribution, $r\in\mathbb{R}$, $S_{i}$
are local symmetries of the initial state, i.e.,
$S_{i}\in\mathbf{S}(\bigotimes_{e\in E}\left|\Phi^{+}\right>_{e})$ with
$\mathbf{S}(\bigotimes_{e\in E}\left|\Phi^{+}\right>_{e})=\\{S=\otimes
S^{(j)}:S^{(j)}\in GL(d_{j}),S\bigotimes_{e\in
E}\left|\Phi^{+}\right>_{e}=\bigotimes_{e\in E}\left|\Phi^{+}\right>_{e}\\}$
and $d_{j}$ being the local dimension of party $j$, and
$H=\otimes_{j}H_{j}=\otimes_{j}h_{j}^{\dagger}h_{j}$ is determined by the
final state $h_{1}\otimes\ldots\otimes h_{n}\prod_{e\in
E}\left|\Phi^{+}\right>_{e}$. It is the symmetries of the state which allow
the transformation to be deterministic. In MPS  the symmetries and SLOCC
transformations of translationally invariant matrix product states (which
include certain network structures) have been characterized. In the following,
we characterize the symmetries of arbitrary networks of bipartite sources
which distribute maximally entangled two-qubit states. For simplicity we will
only provide the explicit proof for the symmetries of the triangle network,
which is shown in Fig. 1, however the proof can be straightforwardly
generalized to arbitrary network structures.

In order to derive the symmetries we will use the property of
$\left|\Phi^{+}\right>$ that $Y\otimes\mbox{$1{\bf
l}$}\left|\Phi^{+}\right>=\mbox{$1{\bf l}$}\otimes
Y^{T}\left|\Phi^{+}\right>$. With this we have that (see Fig. 1)

$\displaystyle S^{(1)}\otimes S^{(2)}\otimes
S^{(3)}\left|\Phi^{+}\right>_{e^{1}_{1}e_{1}^{2}}\left|\Phi^{+}\right>_{e_{2}^{2}e_{2}^{3}}\left|\Phi^{+}\right>_{e_{3}^{3}e_{3}^{1}}=$
$\displaystyle S^{(1)}\otimes\mbox{$1{\bf
l}$}_{e_{2}^{3}}\otimes\bigg{[}(S^{(2)}\otimes\mbox{$1{\bf
l}$}_{e_{3}^{3}})\\{(S^{{(3)}})^{T_{e_{2}^{2}}}\otimes\mbox{$1{\bf
l}$}_{e^{2}_{1}}\\}\bigg{]}\left|\Phi^{+}\right>^{\otimes 3},$ (2)

where $T_{e_{2}^{2}}$ denotes the partial transpose on $e_{2}^{2}$. Using that
the well known symmetries of $\left|\Phi^{+}\right>$ are $Y\otimes Y^{-T}$
this implies that

$\displaystyle(S^{(2)}\otimes\mbox{$1{\bf
l}$}_{e^{3}_{3}})[(S^{{(3)}})^{T_{e_{2}^{2}}}\otimes\mbox{$1{\bf
l}$}_{e^{2}_{1}}]=(S^{(1)}_{e_{1}^{2}e_{3}^{3}})^{-T}\otimes\mbox{$1{\bf
l}$}_{e^{2}_{2}}.$ (3)

Remarkably, this condition can only be satisfied if $S^{(2)}$ and
$(S^{{(3)}})^{T_{e_{2}^{2}}}$, and thus, also $S^{(3)}$, factorize. More
precisely, one can show (see Lemma 4 in Appendix A) that

$X_{AB}Z_{BC}=Y_{AC}\otimes\mbox{$1{\bf l}$}_{B}$ (4)

with system $B$ being two-dimensional and $X,Z$ invertible operators implies
that $X$ and $Z$ factorize with respect to the splitting $A|B$ and $B|C$
respectively. Note that therefore $S_{2}$ and $S_{3}$ factorize for any
symmetry of the triangle. The triangle is invariant under cyclic permutation
of the parties and therefore via an analogous argumentation one can show that
also $S_{1}$ has to factorize for any symmetry. Moreover, we emphasize that
the same argument can straightforwardly be extended to any network structure.
More precisely, one repeatedly uses that $Y\otimes\mbox{$1{\bf
l}$}\left|\Phi^{+}\right>=\mbox{$1{\bf l}$}\otimes Y^{T}\left|\Phi^{+}\right>$
and that Eq. (4) implies that the operators factorize (see Fig. 2). Then one
employs that the symmetries of the maximally entangled state are known.

With this we have that there can only exist symmetries acting locally on
$e^{i}_{j}$ and $e^{k}_{j}$ for any $e_{j}\equiv\\{e^{i}_{j},e^{k}_{j}\\}\in
E$. Using that the local symmetries of $\left|\Phi^{+}\right>$ are $X\otimes
X^{-T}$ we obtain that the set of symmetries is given by $\bigotimes_{e\in
E}(X_{e}\otimes X_{e}^{-T})_{e}$. Note that here $X_{e}$ can be different for
any edge $e$. This results in the following observation.

######  Observation 1.

For any network structure the local symmetries of $\prod_{e\in
E}\left|\Phi^{+}\right>_{e}$ are given by $\bigotimes_{e\in E}(X_{e}\otimes
X_{e}^{-T})_{e}$.

Figure 2: Schematic illustration of the procedure that allows to identify the
symmetries for the example of the double-triangle network. In order to
transform one picture into the other $Y\otimes\mbox{$1{\bf
l}$}\left|\Phi^{+}\right>=\mbox{$1{\bf l}$}\otimes Y^{T}\left|\Phi^{+}\right>$
is used, as well as that Eq. (4) implies that the operators factorize. From
the last picture it follows that all symmetries factorize.

Hence, only symmetries acting locally on single qubits can contribute and
enable transformations.

States which cannot be prepared via finite round LOCC transformations in
networks.— Within a tree graph network any state in the corresponding SLOCC
class is reachable Hayata . Here we will show that if a network contains a
cycle this is no longer true. For convenience we will consider here and in the
following as initial state $\bigotimes_{e\in E}\left|\Psi^{-}\right>_{e}$
which is local unitary (LU) equivalent to $\bigotimes_{e\in
E}\left|\Phi^{+}\right>_{e}$ and therefore has the symmetries
$\bigotimes_{e\in E}(X_{e}\otimes X_{e})_{e}$ with $\det(X_{e})=1$. We make
the following observation.

######  Observation 2.

An example for a class of states which cannot be reached via finite round LOCC
from the initial network state containing a cycle is given by $(\otimes_{i\in
cycle}h_{i}\otimes_{j\not\in cycle}\mbox{$1{\bf l}$})\prod_{e\in
E}\left|\Psi^{-}\right>_{e}$ with $H_{i}=(\mbox{$1{\bf
l}$}/4+\alpha_{i}\sigma_{z}\otimes\sigma_{z})\otimes_{\not\in
cycle}\mbox{$1{\bf l}$}$ acting non-trivially only on the two qubits which are
part of the cycle and $\prod_{i\in Cycle}\alpha_{i}>0$.

Consider the projection of Eq. (1) with $H_{i}$ being of this form on
$\left|\Psi^{-}\right>_{e}$ for all edges except one edge that is part of the
cycle, i.e., on $\bigotimes_{E\backslash\tilde{e}\in
cycle}\left|\Psi^{-}\right>_{e}$, one obtains that in order for the
transformation to be possible it has to hold that

$\sum_{i}p_{i}(X_{i}\otimes X_{i})^{\dagger}J(X_{i}\otimes
X_{i})=r\mbox{$1{\bf l}$},$ (5)

with $J=\mbox{$1{\bf l}$}/4^{N}+\prod_{j\in
cycle}\alpha_{j}\sigma_{z}\otimes\sigma_{z}$ and $N$ the number of parties
within the cycle. From the projection of this equation on
$\left|\Psi^{-}\right>$ one obtains that $r=1/4^{N}-\prod_{j\in
Cycle}\alpha_{j}$.

Considering then the trace leads to an equation of the following form

$\displaystyle\sum_{i}p_{i}1/4^{N}\\{[|a_{i}|^{2}+|c_{i}|^{2}+|b_{i}|^{2}+|d_{i}|^{2}]^{2}-4\\}$
$\displaystyle+\\{[|a_{i}|^{2}+|c_{i}|^{2}-(|b_{i}|^{2}+|d_{i}|^{2})]^{2}+4\\}\prod_{j\in
Cycle}\alpha_{j}=0,$ (6)

where $a_{i}d_{i}-b_{i}c_{i}=1$ for any $i$. As
$[|a_{i}|^{2}+|c_{i}|^{2}+|b_{i}|^{2}+|d_{i}|^{2}]^{2}\geq 4$ for
$a_{i}d_{i}-b_{i}c_{i}=1$ and
$[|a_{i}|^{2}+|c_{i}|^{2}-(|b_{i}|^{2}+|d_{i}|^{2})]^{2}+4>0$ this equation
can not be fulfilled if $\prod_{j\in Cycle}\alpha_{j}>0$.

Before providing all states which can be reached with simple LOCC protocols in
networks consisting of a cycle we first present a systematic way which allows
to decide whether a state is reachable or not for many cases.

Systematic way to determine finite round LOCC transformations which are not
possible in a cycle network.— In the following we will restrict to networks
which correspond to a cycle of size $N$ (which we will call cycle networks).
Moreover, we will use the following necessary and sufficient condition for a
transformation to be possible if party $k$ performs a generalized measurement,
communicates the outcome to the other parties and these apply LUs. Note that
this corresponds to a single round within a LOCC protocol. Such a
transformation is solely possible among pure states if the initial state is of
the form $h_{1}\otimes\ldots\otimes g_{k}\otimes h_{k+1}\ldots
h_{N}\left|\Psi\right>$ and the final state is (up to LUs)
$h_{1}\otimes\ldots\otimes h_{k}\otimes h_{k+1}\ldots h_{N}\left|\Psi\right>$
and there exist local symmetries $S_{i}=\otimes
S_{i}^{(j)}\in\mathbf{S}(\left|\Psi\right>)$ and probabilities $\\{p_{i}\\}$
such that

$(S_{i}^{(j)})^{\dagger}H_{j}S_{i}^{(j)}\propto H_{j}$ (7)

for parties $j=1,\ldots,k-1,k+1,\ldots N$ and for party $k$

$\sum_{i}p_{i}(S_{i}^{(k)})^{\dagger}H_{k}S_{i}^{(k)}=rG_{k}=rg_{k}^{\dagger}g_{k},$
(8)

for some $r\in\mathbb{R}$. These condition have been shown to be true for
unitary symmetries in finiteroundLU , but can be generalized to arbitrary
symmetry groups finiteroundgeneral .

Note that for any finite round LOCC protocol transforming a pure state into
some other pure state the final round is exactly of the form described above,
i.e., it has to transform deterministically one pure state into another within
a single round. Hence, for any state which is reachable via a finite-round
LOCC protocol there have to exist symmetries for which Eq. (7) holds true for
$N-1$ parties and for at least one symmetry $S_{i}$ for which Eq. (7) holds

$\displaystyle(S_{i}^{(k)})^{\dagger}H_{k}S_{i}^{(k)}\not\propto H_{k}$ (9)

for the remaining party (in order for an operator $G_{k}\not\propto H_{k}$ to
possibly exist) finiteroundgeneral . In order to decide whether a given $H$
fulfills this requirement one can first determine the local operators
$X_{j}\otimes Y_{j}$ which fulfill Eq. (7) locally for a given $H_{j}$, i.e.,

$(X_{j}\otimes Y_{j})^{\dagger}H_{j}(X_{j}\otimes Y_{j})\propto H_{j}.$ (10)

Then one considers for these local operators $\otimes_{j\neq k}X_{j}\otimes
Y_{j}$ and determines whether there exists a symmetry such that
$\otimes_{j\neq k}S_{i}^{(j)}=\otimes_{j\neq k}(X_{j}\otimes Y_{j})$. In case
this is possible one can consider all the symmetries $S_{i}$ for which this is
true and check whether Eq. (9) holds.

In the following we present a systematic way to evaluate for a given $H_{j}$
which operators fulfill Eq. (10) locally. In order to do so we use ideas which
have also been used in Ref. Spee2016  to determine the symmetries of four-
qubit states. Eq. (11) holds true if and only if

$(\tilde{X}_{j}\otimes\tilde{Y}_{j})^{\dagger}\tilde{H}_{j}(\tilde{X}_{j}\otimes\tilde{Y}_{j})\propto\tilde{H}_{j}$
(11)

with $\tilde{H}_{j}=(M\otimes\bar{M})^{\dagger}H_{j}(M\otimes\bar{M})$ and
$\tilde{X}_{j}\otimes\tilde{Y}_{j}=M^{-1}X_{j}M\otimes\bar{M}^{-1}Y_{j}\bar{M}$
for any $M,\bar{M}$ invertible. We then choose $M\otimes\bar{M}$ such that
$\tilde{H}_{j}$ is Bell diagonal denoted by $H_{j}^{B}$. Note that it has been
shown Belldiagonal  that this is always possible. We will call in the
following $H_{j}^{B}$ the local standard form of $H_{j}$ and we obtain

$(\tilde{X}_{j}^{B}\otimes\tilde{Y}_{j}^{B})^{\dagger}\tilde{H}_{j}^{B}(\tilde{X}_{j}^{B}\otimes\tilde{Y}_{j}^{B})\propto\tilde{H}_{j}^{B}.$
(12)

Transforming then $H_{j}^{B}$ and $\tilde{X}_{j}^{B}\otimes\tilde{Y}_{j}^{B}$
into the magic basis, i.e., $H_{j}^{mb}=U^{\dagger}\tilde{H}_{j}^{B}U$ and
$O_{j}=U^{\dagger}\tilde{X}_{j}^{B}\otimes\tilde{Y}_{j}^{B}U$ where
$U=\left|\Phi^{+}\right>\left<00\right|-i\left|\Phi^{-}\right>\left<01\right|+\left|\Psi^{-}\right>\left<10\right|-i\left|\Psi^{+}\right>\left<11\right|$
we obtain that $H_{j}^{mb}$ is a diagonal matrix with real non-zero entries
(as $H_{j}$ is a positive definite matrix) and $O_{j}$ is a special orthogonal
matrix. With this we have that

$A_{j}=O_{j}^{\dagger}H_{j}^{mb}O_{j}\propto H_{j}^{mb}.$ (13)

This implies that

$A_{j}^{T}A_{j}=(O_{j})^{T}(H_{j}^{mb})^{T}H_{j}^{mb}O_{j}=(H_{j}^{mb})^{T}H_{j}^{mb}.$
(14)

Note that as this is a similarity transformation the set of eigenvalues has to
stay invariant. As the eigenvalues of $(H_{j}^{mb})^{T}H_{j}^{mb}$ have to be
real and positive this implies that there is no proportionality factor.
Alternatively, Eq. (14) can be written as
$[(H_{j}^{mb})^{T}H_{j}^{mb},O_{j}]=0$ and it is straightforward to solve this
equation. From the resulting matrices $O_{j}$ one obtains potential candidates
for $\tilde{X}_{j}^{B}\otimes\tilde{Y}_{j}^{B}=UO_{j}U^{\dagger}$. We then
insert them into Eq. (12) and evaluate the ones that indeed leave $H_{j}^{B}$
invariant up to a factor. Note that if one knows the local operators
$\tilde{X}_{j}^{B}\otimes\tilde{Y}_{j}^{B}$ which fulfill Eq. (12) for the
local standard forms one can directly calculate the ones which fulfill Eq.
(10) for a given $H_{j}$ via the relations
$H_{j}=(M^{-1}\otimes\bar{M}^{-1})^{\dagger}H_{j}^{B}(M^{-1}\otimes\bar{M}^{-1})$
and $X\otimes
Y=M\tilde{X}_{j}^{B}M^{-1}\otimes\bar{M}\tilde{Y}_{j}^{B}\bar{M}^{-1}$. The
explicit symmetries for all local standard forms can be found in Appendix B.
Using the method presented in Belldiagonal  one can identify the matrices $M$
and $\bar{M}$ which relate $H_{j}$ to its local standard form and with this it
is easy to determine the matrices $X$ and $Y$ which fulfill Eq. (10).
Determining from the so obtained operators whether there exists a way of
concatenating them to form a symmetry on $N-1$ party allows to
straightforwardly employ the necessary conditions in Eqs. (7) and (9) to
identify states that cannot be reached via finite round LOCC protocols in
cycle networks. In the following we will use Eqs. (7) and (8) also to
determine the class of states which can be reached with a LOCC protocol where
each party measures solely once.

A simple class of finite round LOCC protocols in cycle networks.— In case the
necessary conditions in the previous section are fulfilled a transformation
may be possible. In particular, these conditions provide a complete
characterization of states which can be realized with protocols where each
party measures once in a cycle network. In order for a state to be reachable
from the network of maximally entangled states with a protocol where each
party measures only once the conditions in Eqs. (7) and (8) have to be
fulfilled for some choice of $k$ and $G_{k}=A^{\dagger}A\otimes B^{\dagger}B$
for some $A,B\in SL(2)$. If they do not hold true, the state cannot be reached
via such a protocol, as can be seen as follows. For a successful
transformation the initial state in the final round has to be of the form
$\otimes_{i\neq k}h_{i}\otimes g_{k}\left|\Psi\right>$ where $k$ is the party
measuring in the final round. It is easy to see that for the considered class
of protocols $g_{k}$ has to be of the form $A\otimes B$, as party $k$ did not
perform any measurement yet and the only way how one may obtain a non-trivial
$g_{k}$ is via the symmetries. However, if the conditions are not fulfilled
the transformation in the final round cannot be deterministic. In case they
hold true one can devise a protocol implementing the transformation (see
Appendix C). This results in the following observation.

######  Observation 3.

A state $h\left|\Psi\right>$ can be reached from the initial network via LOCC,
where each party measures only once, and each step of the protocol is
deterministic, if and only if the conditions in Eqs. (7) and (8) are fulfilled
for some choice of $k$ and $G_{k}=A^{\dagger}A\otimes B^{\dagger}B$ for some
$A,B\in SL(2)$.

Unfortunately, however this provides no complete characterization of finite
round LOCC transformations in cycle networks as the following example
illustrates.

Example of a transformation that requires one party to measure more than
once.— Analogous to the case of unitary symmetries it may be that
probabilistic steps are required finiteroundLU . Moreover, even if one
restricts to protocols for which each LOCC round corresponds to a
deterministic transformation among pure states (and therefore Eqs. (7) and (8)
have to hold true for each round) it is not straightforward to find these
protocols as parties may be required to measure more than once as the
following example illustrates. Note that in this case the main difficulty is
to identify the order in which the parties have to measure and the
intermediate states.

For an example which requires one party to measure more than once we consider
the triangle and the SLOCC operators $H_{j}=\mbox{$1{\bf
l}$}+\sum_{i=1,2}a_{i}^{(j)}\sigma_{i}\otimes\sigma_{i}$ for $j\in\\{1,2\\}$
and $H_{3}=U_{1}^{\dagger}\otimes U_{1}^{\dagger}(\mbox{$1{\bf
l}$}+c\sigma_{z}\otimes\sigma_{z})U_{1}\otimes U_{1}$ with $a_{i}^{(j)}\neq
0$, $a_{1}^{(j)}\neq\pm a_{2}^{(j)}$, $c\neq 0$ and
$U_{1}=e^{i\alpha_{1}\sigma_{x}}$ with $\alpha_{x}\neq 0,m\pi/4$ and $m$ being
an integer. The detailed proof that shows that this state is indeed not
reachable with a protocol where each party measures solely once and the finite
round LOCC protocol which transforms the initial network state into the
desired final state can be found in Appendix D. In particular, we show there
that for all symmetries for which Eq. (7) is fulfilled for two parties, Eq.
(8) with $g_{k}=\mbox{$1{\bf l}$}$ (i.e., party $k$ has not performed a
measurement yet) does not hold true for the remaining party $k$. If party 3 is
allowed to measure twice the state can be reached and we provide an explicit
protocol achieving this transformation.

Conclusion and Outlook.— In this work we have studied finite-round LOCC
transformation in networks. We first provided the symmetries for arbitrary
network structures, if the sources distribute two-qubit states. Which finite-
round LOCC transformations can be implemented is determined by the symmetries
Gour ; measuroutcdonotexist ; finiteroundgeneral  and we use this to show that
(in contrast to tree networks Hayata ) for networks that contain a cycle there
exist states which are not reachable. For cycle networks we provide a
systematic way to determine classes of states that cannot be reached via
finite-round LOCC transformations. Moreover, we characterize all states which
can be reached with protocols where each party measures once, and each step of
the protocol is deterministic. Finally, we provide an example of a state which
is not reachable with simple protocols where each party measures solely once
showing that in general more involved protocols have to be considered.

In this work we have only considered qubit sources. One may generalize our
approach to derive the symmetries to higher-dimensional systems and use this
to characterize finite-round LOCC transformations in networks distributing
qudit states. Furthermore, the scenario we consider, namely a network
distributing single copies of bipartite states accompanied with finite-round
LOCC transformations, is highly relevant for quantum communication tasks and
of practical relevance. Hence, it would be desirable to develop a general
resource theory of network entanglement and introduce corresponding
entanglement measures.

###### Acknowledgements.

We thank Hayata Yamasaki, Martin Hebenstreit, Barbara Kraus and Otfried Gühne
for discussions and comments. This work has been supported by the the Austrian
Science Fund (FWF): J 4258-N27, Y879-N27 and P 32273-N27, the Austrian Academy
of Sciences, the ERC (Consolidator Grant 683107/TempoQ), and the Deutsche
Forschungsgemeinschaft (DFG, German Research Foundation - 447948357 and
440958198).

##  Appendix A Appendix A: Proof of Lemma 4

In the following we provide a proof for the fact that the local symmetry
operators $S_{2}$ and $S_{3}$ in Eq. (3) in the main text have to factorize.

######  Lemma 4.

The relation $X_{AB}Z_{BC}=Y_{AC}\otimes\mbox{$1{\bf l}$}_{B}$ with system $B$
being two-dimensional and $X,Z$ invertible can only hold true if
$X_{AB}=\bar{X}_{A}\otimes X_{B}$ and $Z_{BC}=\bar{Z}_{B}\otimes Z_{C}$ for
some choice of invertible operators $\bar{X}_{A},X_{B},\bar{Z}_{B}$ and
$Z_{C}$, i.e. the operators factorize.

###### Proof.

We will show that $X_{AB}Z_{BC}=Y_{AC}\otimes\mbox{$1{\bf l}$}_{B}$ with
system $B$ being two-dimensional and $X,Z$ invertible implies that
$X_{AB}=\tilde{X}_{A}\otimes X_{B}$ and $Z_{BC}=\tilde{Z}_{B}\otimes Z_{C}$.
As we have explained in the main text (see also Fig. 1 in the main text) this
implies that in any network the local symmetries have to factorize with
respect to the different particles the parties receive from the sources.

So let us consider the equation

$X_{AB}Z_{BC}=Y_{AC}\otimes\mbox{$1{\bf l}$}_{B}$ (A1)

Note that this equation holds true if and only if

$\tilde{X}_{AB}\tilde{Z}_{BC}=Y_{AC}\otimes\mbox{$1{\bf l}$}_{B}$ (A2)

with $\tilde{Q}=M_{B}^{-1}QM_{B}$ for $Q=X,Z$. Note further that $Q$
factorizes with respect to the splitting B versus rest if and only if
$\tilde{Q}$ does. We will decompose the operators $\tilde{X}$ and $\tilde{Z}$
in an operator basis $\\{\lambda_{i}\otimes\sigma_{j}\\}$, where $\sigma_{j}$
is acting on system B and correspond to the Pauli operators, i.e.
$\tilde{X}_{AB}=\sum_{i,j}x_{ij}\lambda_{i}\otimes\sigma_{j}$ and
$\tilde{Z}_{BC}=\sum_{k,l}z_{kl}\sigma_{k}\otimes\lambda_{l}=\sum_{l}W_{l}\otimes\lambda_{l}$.
Moreover, we will choose M such that $W_{0}=\sum_{k}z_{k0}\sigma_{k}$ is in
Jordan decomposition. Here we chose without loss of generality to bring the
matrix $W_{0}$ acting on B for the component $\lambda_{0}$ into Jordan form,
however, in case this component does vanish we relabel the basis for C such
that some non-zero component is referred to as $\lambda_{0}$. The matrix
$W_{0}$ can then either be diagonal or have a Jordan block of size 2. We will
first discuss the diagonal case. Then in order for Eq. (A2) to hold true we
have that for all $i$ and $j\in{1,2,3}$

$\displaystyle\mathrm{tr}[(\tilde{X}_{AB}\tilde{Z}_{BC})(\lambda_{i}\otimes\sigma_{j}\otimes\lambda_{0})]=$
$\displaystyle\mathrm{tr}[(\tilde{X}_{AB}\\{\mbox{$1{\bf l}$}_{A}\otimes
W_{0}\\})(\lambda_{i}\otimes\sigma_{j})]=0$ (A3)

This is equivalent to

$\displaystyle x_{i1}z_{00}+ix_{i2}z_{30}=0$ $\displaystyle
x_{i2}z_{00}-ix_{i1}z_{30}=0$ $\displaystyle x_{i3}z_{00}+x_{i0}z_{30}=0.$
(A4)

These equations can also be written as

$\displaystyle\vec{v}^{j}_{i}\cdot\vec{\omega}=0$ (A5)

with $\vec{\omega}=(z_{00},z_{03})^{T}$,
$\vec{v}^{1}_{i}=(x_{i1},ix_{i2})^{T}$,$\vec{v}^{2}_{i}=(x_{i2},-ix_{i1})^{T}$
and $\vec{v}^{3}_{i}=(x_{i3},ix_{i0})^{T}$. From Eq. (A5) for $j=1$ and $j=2$
we have that $\vec{v}^{2}_{i}=c_{i}\vec{v}^{2}_{i}$ with $c_{i}$ being some
proportionality factor, which can be straightforwardly be shown to be $\pm i$.
With this we have that $x_{i2}=\pm ix_{i1}$. In case $x_{i1}\neq 0$ it
therefore follows that $z_{00}=\pm z_{03}$. This implies that $x_{i2}=\pm
ix_{i1}$ for all $i$, i.e. it is the same sign for all $i$, and also
$x_{i3}=\mp x_{i0}$ for all $i$. It should be noted that these constraints
lead to a matrix $W_{i}$ which has a kernel. The corresponding eigenvector is
$(1,0)^{T}$ for $x_{i2}=ix_{i1}$ or $(0,1)^{T}$ for $x_{i2}=-ix_{i1}$. As any
$W_{i}$ has the same kernel this solution is only possible if $\tilde{Z}$ is
not invertible (which contradicts our assumption). Hence, it has to hold that
$x_{i2}=x_{i1}=0$. From Eq. (A5) for $j=3$ it follows that all vectors
$\vec{v}^{3}_{i}$ have to be parallel (or the zero vector), which corresponds
to the case that $\tilde{X}$ factorizes. It can be straightforwardly seen that
in this case also $\tilde{Z}$ has to factorize.

It remains to consider the case that $W_{0}$ is a Jordan block of size 2, i.e.
$z_{30}=0$ and $z_{20}=iz_{10}=i/2$. Then Eq. (A1) is fulfilled only if for
all $i$

$\displaystyle x_{i1}z_{00}+i(x_{i0}+x_{i3})z_{10}=0$ $\displaystyle
x_{i2}z_{00}+i(x_{i0}+x_{i3})z_{10}=0$ $\displaystyle
x_{i3}z_{00}+i(ix_{i1}-x_{i2})z_{10}=0.$ (A6)

Let us first consider the case that $z_{00}=0$. Then for all $i$ it has to
hold that $x_{i2}=ix_{i1}$ and $x_{i0}=-x_{i3}$. As before this would imply in
contradiction to our assumption that $\tilde{Z}$ is not invertible.
Considering the case $z_{00}\neq 0$ it can be easily seen that
$x_{i2}=ix_{i1}$ and $x_{i3}=0$. We can then write the first Eq. in (A6) as

$\displaystyle 0=x_{i1}z_{00}+ix_{i0}z_{10}\equiv\vec{r}_{i}\cdot\vec{s}$

with $\vec{r}_{i}=(x_{i1},x_{i0})^{T}$ and $\vec{s}=(z_{00},iz_{10})^{T}$.
Hence, for all $i$ the vectors $\vec{r}_{i}$ have to be parallel (or the zero
vector). This implies that $\tilde{X}$ and hence also $\tilde{Z}$ has to
factorize, which completes the proof that in order for Eq. (A1) to hold $X$
and $Z$ have to factorize. ∎

##  Appendix B Appendix B: Symmetries for the local standard form

The local standard form is chosen such that $H_{j}^{mb}$ is diagonal with real
positive entries. Which symmetries are possible will depend on the degeneracy.
Note that one can always permute the diagonal entries of $H_{j}^{mb}$ to bring
it in a form mentioned below, e.g., one can permute
$\left|\Psi^{+}\right>\left<\Psi^{+}\right|$ and
$\left|\Psi^{-}\right>\left<\Psi^{-}\right|$ (leaving at the same time
$\left|\Phi^{\pm}\right>\left<\Phi^{\pm}\right|$ invariant) by conjugation
with $\sqrt{i\sigma_{z}}\otimes\sqrt{-i\sigma_{z}}$. Via the procedure
outlined in the main text one can determine the symmetries of $H_{j}^{B}$. We
obtain the following results:

  1. (i)

No degeneracy, i.e., $H_{j}^{mb}=diag(a,b,c,d)$: The local operators which
leave $H_{j}^{B}$ invariant are $\sigma_{i}\otimes\sigma_{i}$ (see also
Spee2016 ).

  2. (ii)

A double-degenerate and two different eigenvalues, i.e.,
$H_{j}^{mb}=diag(a,a,b,c)$: The operators $[Z(\phi)\otimes
Z(\phi)](\sigma_{x}\otimes\sigma_{x})^{k}$ with
$Z(\phi)=diag(e^{i\phi},e^{-i\phi})$ and $k\in\\{0,1\\}$ are the only local
ones which leave $H_{j}^{B}$ invariant.

  3. (iii)

Two double-degenerate eigenvalues, i.e., $H_{j}^{mb}=diag(a,a,b,b)$: The
symmetries of $H_{j}^{B}$ are $[Z(\phi_{1})\otimes
Z(\phi_{2})](\sigma_{x}\otimes\sigma_{x})^{k}$ with $k\in\\{0,1\\}$.

  4. (iv)

Triple degenerate eigenvalues, i.e., $H_{j}^{mb}=diag(a,a,a,b)$: The local
symmetries of $H_{j}^{B}$ are given by $Z(\phi_{1})X(\alpha)Z(\phi_{2})\otimes
Z(\phi_{1})X(-\alpha)Z(\phi_{2})$ with $X(\alpha)=e^{i\alpha\sigma_{x}}$.

  5. (v)

Four degenerate eigenvalues, i.e., $H_{j}^{mb}=\mbox{$1{\bf l}$}$: All local
unitaries leave $H_{j}^{B}$ invariant.

##  Appendix C Appendix C: Simple deterministic protocol in a cycle network

If the conditions in Observation 3 hold, the following protocol allows us to
reach the state $h\left|\Psi\right>$ deterministically. First note that we
consider in the following the SLOCC operator $H$ for which
$\mathrm{tr}_{e_{j-1}^{j}}(H_{j})=2\mbox{$1{\bf l}$}$ holds for
$j\in\\{3,\ldots,N-1\\}$ and
$\mathrm{tr}_{e_{1}^{2}}(B^{-\dagger}_{e_{1}^{2}}H_{2}B^{-1}_{e_{1}^{2}})=2\mbox{$1{\bf
l}$}$. Here we use that $S^{\dagger}HS$ with $S\in\mathbf{S}(\Psi)$ defines
the same state as $H$ (see also Vicente2013 ). Hence, there is some ambiguity
in the choice of H and we will make use of this to ensure the desired
property. Note that for any state in a cycle network it is possible to
transform a given $H$ in such a form (if we choose to normalize the operator
accordingly). We further denote here without loss of generality $k=1$ and
enumerate the parties and edges consecutively, i.e.
$e_{j}=(e_{j}^{j},e_{j}^{j+1})\in E$. First, party $N$ applies the generalized
measurement
$\\{1/4h_{N}[(A^{-1}\sigma_{i})_{e_{N}^{N}}\otimes(\sigma_{k})_{e_{N-1}^{N}}]\\}$,
with $\mathrm{tr}(A^{-\dagger}H_{N}A^{-1})=4$ for normalization. Depending on
the measurement outcome party $1$ and party $N-1$ apply $\sigma_{i}$ and
$\sigma_{k}$ respectively on the qubit that is connected to party $N$. Then,
beginning with party $N-1$ and proceeding in decreasing order party
$j\in\\{3,\ldots,N\\}$ applies the generalized measurement
$\\{1/2h_{j}(\mbox{$1{\bf
l}$}_{e_{j}^{j}}\otimes(\sigma_{i})_{e_{j-1}^{j}})\\}$ and for outcome $i$
party $j-1$ applies $\sigma_{i}$ on $e_{j-1}^{j-1}$ before it measures in the
subsequent round. Finally, party $2$ applies the measurement
$\\{1/2h_{2}(\mbox{$1{\bf
l}$}_{e_{2}^{2}}\otimes(B^{-1}\sigma_{i})_{e_{1}^{2}})\\}$ and for outcome $i$
party $1$ implements $\sigma_{i}$. With this the initial state in the final
round is given by $A\otimes B\otimes_{i=2}^{N}h_{i}\left|\Psi\right>$. In the
last round party $1$ applies the generalized measurement
$\\{h_{1}S_{i}^{(1)}\\}$ which is a valid POVM due to Eq. (8). For outcome $i$
all other parties apply the unitary $V_{i}^{(j)}$ such that
$V_{i}^{(j)}h_{j}=h_{j}S_{i}^{(j)}$. These unitaries exist due to Eq. (7).
This protocol allows to reach the state $h\left|\Psi\right>$
deterministically.

##  Appendix D Appendix D: Example of a transformation that requires one party
to measure more than once

As mentioned in the main text we consider the triangle network. The final
state is determined (up to local unitaries) by $H_{j}=\mbox{$1{\bf
l}$}+\sum_{i=1,2}a_{i}^{(j)}\sigma_{i}\otimes\sigma_{i}$ for $j\in\\{1,2\\}$
and $H_{3}=U_{1}^{\dagger}\otimes U_{1}^{\dagger}(\mbox{$1{\bf
l}$}+c\sigma_{z}\otimes\sigma_{z})U_{1}\otimes U_{1}$ with $a_{i}^{(j)}\neq
0$, $a_{1}^{(j)}\neq\pm a_{2}^{(j)}$, $c\neq 0$ and
$U_{1}=e^{i\alpha_{1}\sigma_{x}}$ with $\alpha_{x}\neq 0,m\pi/4$ and $m$ being
an integer. This state cannot be reached from the initial network state via a
protocol where each party measures solely once.

In order to see that we will make use of the necessary conditions in Eqs. (7)
and (8) and the systematic approach explained in the main text that allows to
identify the local operators which fulfill Eq. (7). Note that for party $1$
and $2$ $H_{i}$ is already Bell diagonal and corresponds to the non-degenerate
case which implies that for party $1$ and $2$ the symmetries that can
potentially be used locally in the last round are
$\sigma_{i}\otimes\sigma_{i}$ and for party $3$ they are
$U_{1}^{\dagger}\otimes U_{1}^{\dagger}\\{[Z(\phi_{1})\otimes
Z(\phi_{2})](\sigma_{x}\otimes\sigma_{x})^{k}\\}U_{1}\otimes U_{1}$ with
$k\in\\{0,1\\}$ and $Z(\phi)=diag(e^{i\phi},e^{-i\phi})$ as the local standard
form has two double degenerate eigenvalues (see Appendix B).

The only operators $\otimes_{j\neq k}X_{j}\otimes Y_{j}$ on two parties which
have a non-zero intersection with a symmetry restricted to two parties are (a)
$\sigma_{i}^{\otimes 4}$ on party $1$ and $2$ (with corresponding symmetries
$\sigma_{i}^{\otimes 6}$) or (b)
$U_{1}^{\dagger}Z(\phi)U_{1}\otimes\mbox{$1{\bf l}$}^{\otimes 3}$ and
$\sigma_{x}^{\otimes 4}$ on party $3$ and one of the other parties (with
corresponding symmetries $U_{1}^{\dagger}Z(\phi)U_{1}\otimes\mbox{$1{\bf
l}$}^{\otimes 4}\otimes U_{1}^{\dagger}Z(\phi)U_{1}$ and $\sigma_{x}^{\otimes
6}$).

Let us first consider case (a) in which the party measuring in the last round
is party $3$. It is straightforward to see that the final state is not
reachable in a protocol where this party has not performed any measurement
before and therefore $g_{3}=A\otimes B$. This is due to the fact that
$\sum_{i}p_{i}\sigma_{i}\otimes\sigma_{i}H_{3}\sigma_{i}\otimes\sigma_{i}\not\propto
G_{3}=A^{\dagger}A\otimes B^{\dagger}B$ for any probability distribution
$p_{i}$ (see Observation 3 in the main text). Analogously, we have that for
case (b) $\sum_{i}p_{i}U_{1}^{\dagger}Z(-\phi_{i})U_{1}\otimes\mbox{$1{\bf
l}$}H_{j}U_{1}^{\dagger}Z(\phi_{i})U_{1}\otimes\mbox{$1{\bf l}$}\not\propto
A^{\dagger}A\otimes B^{\dagger}B$ for $j\in\\{1,2\\}$ and therefore also in
this case it is not possible to reach the final state if each party measures
only once. Note here that the symmetry $\sigma_{x}^{\otimes 6}$ does not need
to be taken into account as $\sigma_{x}^{\otimes 6}$ commutes with $H$ and
hence is equivalent to the identity in our analysis.

However, it can be reached via the following protocol. First party $3$
measures
$\\{\frac{1}{\sqrt{2}}\tilde{h}_{3},\frac{1}{\sqrt{2}}\tilde{h}_{3}(\mbox{$1{\bf
l}$}\otimes\sigma_{y})\\}$ with $\tilde{h}_{3}=\sqrt{\mbox{$1{\bf
l}$}+\tilde{c}\sigma_{z}\otimes\sigma_{z}}$ and
$\tilde{c}=1/4\mathrm{tr}(H_{3}\sigma_{z}\otimes\sigma_{z})$ which corresponds
to a valid POVM. In case of the second outcome party 2 applies $\sigma_{y}$ on
the qubit which is entangled with the second qubit of party 3. With this they
reach deterministically the state $(\mbox{$1{\bf l}$}\otimes\mbox{$1{\bf
l}$}\otimes\tilde{h}_{3})(\otimes_{e\in E}\left|\Phi^{+}\right>_{e})$. Then
party 1 and 2 measure
$\\{\frac{1}{\sqrt{2}}h_{j},\frac{1}{\sqrt{2}}h_{j}(\mbox{$1{\bf
l}$}\otimes\sigma_{z})\\}$ where for the second outcome $\sigma_{z}$ is acting
on the qubit that is connected to the third party and in case this outcome is
obtained party 3 applies $\sigma_{z}$ on the qubit which originated from the
same source. By doing so they obtain deterministically the state
$(h_{1}\otimes h_{2}\otimes\tilde{h}_{3})(\otimes_{e\in
E}\left|\Phi^{+}\right>_{e})$. Finally, party 3 implements the measurement
$\\{\frac{1}{\sqrt{2}}h_{3}(\sigma_{i}\otimes\sigma_{i})\tilde{h}_{3}^{-1}\\}$
with $i=0,3$. This is a valid POVM and party $j=1,2$ apply for outcome $i$ the
unitary $V_{ij}$ with the property that
$V_{ij}h_{j}=h_{j}(\sigma_{i}\otimes\sigma_{i})$ (which have to exist as
$[H_{j},(\sigma_{i}\otimes\sigma_{i})]=0$). This transformation
deterministically reaches the desired state.

## References

  * (1) H. J. Kimble, Nature 453, 1023 (2008).
  * (2) S. Wehner, D. Elkouss and R. Hanson, Science 362, 9288 (2018).
  * (3) J. I. Cirac, P. Zoller, H. J. Kimble, and H. Mabuchi, Phys. Rev. Lett. 78, 3221 (1997).
  * (4) L.-M. Duan and C. Monroe, Rev. Mod. Phys. 82, 1209 (2010).
  * (5) A. Reiserer and G. Rempe, Rev. Mod. Phys. 87,1379 (2015).
  * (6) L.-M. Duan, M. D. Lukin, J. I. Cirac, P. Zoller, Nature 414, 413 (2001).
  * (7) J. I. Cirac, A. K. Ekert, S. F. Huelga, and C. Macchiavello, Phys. Rev. A 59, 4249 (1999).
  * (8) T. P. Spiller, K. Nemoto, S. L. Braunstein, W. J. Munro, P. van Loock, and G. J. Milburn, New J. Phys. 8, 30 (2006).
  * (9) K. Azuma, S. Bäuml, T. Coopmans, D. Elkouss, B. Li, arXiv:2012.06764 (2020).
  * (10) N. Gisin, J.-D. Bancal, Y. Cai, P. Remy, A. Tavakoli, E. Zambrini Cruzeiro, S. Popescu, N. Brunner, Nat. Commun. 11, 2378 (2020).
  * (11) T. Kraft, S. Designolle, C. Ritz, N.Brunner, O. Gühne, and M. Huber, Phys. Rev. A. 103, L060401 (2021).
  * (12) M.-X. Luo, Adv. Quantum Technol., 2000123 (2021).
  * (13) M. Navascués, E. Wolfe, D. Rosset, and A. Pozas-Kerstjens, Phys. Rev. Lett. 125, 240505 (2020).
  * (14) J. Åberg, R. Nery, C. Duarte, R. Chaves, Phys. Rev. Lett. 125, 110505 (2020).
  * (15) T. Kraft, C. Spee, X.-D. Yu, and O. Gühne, Phys. Rev. A 103, 052405 (2021).
  * (16) C. H. Bennett, G. Brassard, C. Crépeau, R. Jozsa, A. Peres, and W. K. Wootters, Phys. Rev. Lett. 70, 1895 (1993).
  * (17) A. Acín, J. Cirac, M. Lewenstein, Nature Physics 3, 256 (2007).
  * (18) M. A. Nielsen, Phys. Rev. Lett. 83, 436 (1999).
  * (19) W. Dür, G. Vidal, and J.I. Cirac, Phys. Rev. A 62,062314 (2000).
  * (20) F. Verstraete, J. Dehaene, B. De Moor, and H. Verschelde, Phys. Rev. A 65, 052112 (2002).
  * (21) M. J. Donald, M. Horodecki, and O. Rudolph, J. Math. Phys. 43, 4252 (2002).
  * (22) E. Chitambar, Phys. Rev. Lett. 107, 190502 (2011).
  * (23) E. Chitambar, W. Cui, and H.-K-. Lo, Phys. Rev. Lett. 108, 240504 (2012).
  * (24) E. Chitambar, D. Leung, L. Mancinska, M. Ozols, A. Winter, Commun. Math. Phys. 328, 303 (2014).
  * (25) S. M. Cohen, Phys. Rev. Lett. 118, 020501 (2017).
  * (26) S. Turgut, Y. Gül, and N.K. Pak,Phys. Rev. A 81, 012317 (2010).
  * (27) S. Kintas and S. Turgut, J. Math. Phys. 51, 092202 (2010).
  * (28) C. Spee, J.I. de Vicente, D. Sauerwein, B. Kraus, Phys. Rev. Lett. 118, 040503 (2017); J.I. de Vicente, C. Spee, D. Sauerwein, B. Kraus, Phys. Rev. A 95, 012323 (2017).
  * (29) J. I. de Vicente, C. Spee, and B. Kraus, Phys. Rev. Lett. 111, 110502 (2013).
  * (30) K. Schwaiger, D. Sauerwein, M. Cuquet, J.I. de Vicente, B. Kraus, Phys. Rev. Lett. 115, 150502 (2015).
  * (31) C. Spee, J. I. de Vicente, B. Kraus, J. Math. Phys. 57, 052201 (2016).
  * (32) M. Hebenstreit, C. Spee, and B. Kraus, Phys. Rev. A 93, 012339 (2016).
  * (33) H. Yamasaki, A. Soeda, and M. Murao, Phys. Rev. A 96, 032330 (2017).
  * (34) G. Gour and N. R. Wallach, New J. Phys. 13, 073013 (2011); G Gour and N. R. Wallach, New J. Phys. 21, 109502 (2019).
  * (35) M. Hebenstreit, M. Englbrecht, C. Spee, J. I. de Vicente, and B. Kraus, New J. Phys. 23, 033046 (2021).
  * (36) D. Sauerwein, A. Molnar, J. I. Cirac, and B. Kraus, Phys. Rev. Lett. 123, 170504 (2019).
  * (37) M. Hebenstreit, C. Spee, N. K. H. Li, B. Kraus, J. I. de Vicente, arXiv:2107.13949 (2021).
  * (38) F. Verstraete, J. Dehaene, and B. De Moor, Phys. Rev.A 64, 010101(R) (2001).