Copyright for this paper by its authors.
Use permitted under Creative Commons License Attribution 4.0
International (CC BY 4.0).

Joint Proceedings of the ACM IUI 2021 Workshops,
April 13–17, 2021, College Station, USA

A Study on Fairness and Trust Perceptions in Automated Decision Making

1]Jakob Schoeffer[
[1]Karlsruhe Institute of Technology (KIT), Germany

1]Yvette Machowski

1]Niklas Kuehl[

Automated decision systems are increasingly used for consequential decision making—for a variety of reasons.

These systems often rely on sophisticated yet opaque models, which do not (or hardly) allow for understanding how or why a given decision was arrived at.

This is not only problematic from a legal perspective, but non-transparent systems are also prone to yield undesirable (e.g., unfair) outcomes because their sanity is difficult to assess and calibrate in the first place.

In this work, we conduct a study to evaluate different attempts of explaining such systems with respect to their effect on people's perceptions of fairness and trustworthiness towards the underlying mechanisms.

A pilot study revealed surprising qualitative insights as well as preliminary significant effects, which will have to be verified, extended and thoroughly discussed in the larger main study.

Automated Decision Making Fairness Trust Transparency Explanation Machine Learning

§ INTRODUCTION

Automated decision making has become ubiquitous in many domains such as hiring [Kuncel et al., 2014], bank lending [Townson, 2020], grading [Satariano, 2020], and policing [Heaven, 2020], among others.

As automated decision systems (ADS) are used to inform increasingly high-stakes consequential decisions, understanding their inner workings is of utmost importance—and undesirable behavior becomes a problem of societal relevance.

The underlying motives of adopting ADS are manifold: They range from cost-cutting to improving performance and enabling more robust and objective decisions [Kuncel et al., 2014, Harris and Davenport, 2005].

One widespread assumption is that ADS can also avoid human biases in the decision making process [Kuncel et al., 2014].

However, ADS are typically based on artificial intelligence (AI) techniques, which, in turn, generally rely on historical data.

If, for instance, this underlying data is biased (e.g., because certain socio-demographic groups were favored in a disproportional way in the past), an ADS may pick up and perpetuate existing patterns of unfairness [Barocas et al., 2019].

Two prominent examples of such behavior from the recent past are the discrimination of black people in the realm of facial recognition [Buolamwini and Gebru, 2018] and recidivism prediction [Angwin et al., 2016].

These and other cases have put ADS under enhanced scrutiny, jeopardizing trust in these systems.

In recent years, a significant body of research has been devoted to detecting and mitigating unfairness in automated decision making

[Barocas et al., 2019].

Yet, most of this work has focused on formalizing the concept of fairness and enforcing certain statistical equity constraints, often without explicitly taking into account the perspective of individuals affected by such automated decisions.

In addition to how researchers may define and enforce fairness in technical terms,

we argue that it is vital to understand people's perceptions of fairness—vital not only from an ethical standpoint but also with respect to facilitating trust in and adoption of (appropriately deployed) socio-technical systems like ADS.

Srivastava et al., 2019, too, emphasize the need for research to gain a deeper understanding of people's attitudes towards fairness in ADS.

A separate, yet very related, issue revolves around how to explain automated decisions and the underlying processes to affected individuals so as to enable them to appropriately assess the quality and origins of such decisions.

Srivastava et al., 2019 also point out that subjects should be presented with more information about the workings of an algorithm and that research should evaluate how this additional information influences people's fairness perceptions.

In fact,

the EU General Data Protection Regulation (GDPR)[<https://eur-lex.europa.eu/eli/reg/2016/679/oj> (last accessed Jan 3, 2021)], for instance, requires to disclose “the existence of automated decision-making, including […] meaningful information about the logic involved […]” to the “data subject”.

Beyond that, however, such regulations remain often vague and little actionable.

To that end, we conduct a study to examine in more depth the effect of different explanations on people's perceptions of fairness and trustworthiness towards the underlying ADS in the context of lending, with a focus on

* the amount of information provided,

* the background and experience of people,

* the nature of the decision maker (human vs. automated).

§ BACKGROUND AND RELATED WORK

It is widely understood that AI-based technology can have undesirable effects on humans.

As a result, topics of fairness, accountability and transparency have become important areas of research in the fields of AI and human-computer interaction (HCI), among others.

In this section, we provide an overview of relevant literature and highlight our contributions.

Overview of related work.

Reference     Explanation styles provided     Amount of provided information evaluated     Understandability tested     Computer / AI experience evaluated      Human involvement in context considered

Binns et al., 2018     distinct     no     single question     no      no

Dodge et al., 2019     distinct     no     not mentioned     no     no

Lee, 2018     distinct     no     no     knowledge of algorithms     individual in management context

Lee and Baykal, 2017     n/a due to study setup     no     no     programming / algorithm knowledge     group decision in fair division context

Wang et al., 2020     distinct     partly     no     computer literacy     algorithmic decision, reviewed by group in crowdsourcing  context

Our work     distinct and combined     yes     construct with multiple items     AI literacy     individual in provider-customer context

Explainable AI

Despite being a popular topic of current research, explainable AI (XAI) is a natural consequence of designing ADS and, as such, has been around at least since the 1980s [Goebel et al., 2018].

Its importance, however, keeps rising as increasingly sophisticated (and opaque) AI techniques are used to inform evermore consequential decisions.

XAI is not only required by law (e.g., GDPR, ECOA[Equal Credit Opportunity Act: <https://www.consumer.ftc.gov/articles/0347-your-equal-credit-opportunity-rights> (last accessed Jan 3, 2021)]); Eslami et al., 2019, for instance, have shown that users' attitudes towards algorithms change when transparency is increased.

When sufficient information is not presented, users sometimes rely too heavily on system suggestions [Bussone et al., 2015].

Yet, both quantity and quality of explanations matter: Kulesza et al., 2013 explore the effects of soundness and completeness of explanations on end users' mental models and suggest, among others, that oversimplification is problematic.

We refer to [Goebel et al., 2018, Molnar, 2020, Adadi and Berrada, 2018] for more in-depth literature on the topic of XAI.

Perceptions of fairness and trustworthiness
A relatively new line of research in AI and HCI has started focusing on perceptions of fairness and trustworthiness in automated decision making.

For instance, Binns et al., 2018 and Dodge et al., 2019 compare fairness perceptions in ADS for four distinct explanation styles.

Lee, 2018 compares perceptions of fairness and trustworthiness depending on whether the decision maker is a person or an algorithm in the context of managerial decisions.

Lee and Baykal, 2017 explore how algorithmic decisions are perceived in comparison to group-made decisions.

Wang et al., 2020 combine a number of manipulations, such as favorable and unfavorable outcomes, to gain an overview of fairness perceptions.

An interesting finding by Lee et al., 2019 suggests that fairness perceptions decline for some people when gaining an understanding of an algorithm if their personal fairness concepts differ from those of the algorithm.

Regarding trustworthiness, Kizilcec, 2016, for instance, concludes that it is important to provide the right amount of transparency for optimal trust effects, as both too much and too little transparency can have undesirable effects.

Our contribution
We aim to complement existing work to better understand how much of which information of an ADS should be provided to whom so that people are optimally enabled to understand the inner workings and appropriately assess the quality (e.g., fairness) and origins of such decisions.

Specifically, our goal is to add novel insights in the following ways: First, our approach combines multiple explanation styles in one condition, thereby disclosing varying amounts of information.

This differentiates our method from the concept of distinct individual explanations adopted by, for instance, Binns et al., 2018.

We also evaluate the understandability of explanations through multiple items; and we add a novel analysis of the effect of people's AI literacy [Long and Magerko, 2020] on their perceptions of fairness and trustworthiness.

Finally, we investigate whether perceptions of fairness and trustworthiness differ between having a human or an automated decision maker, controlling for the provided explanations.

For brevity, we have summarized relevant aspects where our work can complement existing literature in Table <ref>.

§ STUDY DESIGN AND METHODOLOGY

With our study, we aim to contribute novel insights towards answering the following main questions:

Q1 Do people perceive a decision process to be fairer and/or more trustworthy if more information about it is disclosed?

Q2 Does people's experience / knowledge in the field of AI have an impact on their perceptions of fairness and trustworthiness towards automated decision making?

Q3 How do people perceive human versus automated (consequential) decision making with respect to fairness and trustworthiness?

We choose to explore the aforementioned relationships in the context of lending—an example of a provider-customer encounter.

Specifically, we confront study participants with situations where a person was denied a loan.

We choose a between-subjects design with the following conditions: First, we reveal that the loan decision was made by a human or an ADS (i.e., automated).

Then we provide one of four explanation styles to each study participant.

Figure <ref> contains an illustration of our study setup, the elements of which will be explained in more detail shortly.

Eventually, we measure four different constructs: understandability (of the given explanations), procedural fairness [Colquitt et al., 2001], informational fairness [Colquitt et al., 2001], and trustworthiness (of the decision maker); and we compare the results across conditions.

Additionally, we measure AI literacy of the study participants.

Please refer to Appendix <ref> for a list of all constructs and associated measurement items for the case of automated decisions.

Note that for each construct we measure multiple items.

(n0) at (0,0) ;

[style=rectangle, draw=black, fill=gray!10, minimum width=3.5cm, minimum height=0.5cm, text centered, anchor=east] (n1) at (-0.5,-1) Decision Maker: Human;

[style=rectangle, draw=black, fill=gray!40, minimum width=3.5cm, minimum height=0.5cm, text centered, anchor=west] (n2) at (0.5,-1) Decision Maker: ADS;

[style=rectangle, draw=black, fill=gray!10, minimum height=0.5cm, text centered, anchor=east] (n3) at (-0.5,-4) Counterfactuals;

[style=anchor=center, minimum height=0.5cm] (txt1) at (0,-4) (CF);

[style=rectangle, draw=black, fill=gray!10, minimum height=0.5cm, text centered, above=0.2cm of n3.north, anchor=south] (n4) Counterfactuals;

[style=left=0cm of n4.west] (plus1) +;

[style=rectangle, draw=black, fill=gray!10, minimum height=0.5cm, text centered, left=0cm of plus1] (n5) Feature Importance;

[style=left=0cm of n5.west] (plus2) +;

[style=rectangle, draw=black, fill=gray!10, minimum height=0.5cm, text centered, left=0cm of plus2] (n6) Features;

[style=above=0.2cm of txt1.north, anchor=south, minimum height=0.5cm] (txt2) (FFICF);

[style=rectangle, draw=black, fill=gray!10, minimum height=0.5cm, text centered, above=0.2cm of n5.north, anchor=south] (n7) Feature Importance;

[style=left=0cm of n7.west] (plus3) +;

[style=rectangle, draw=black, fill=gray!10, minimum height=0.5cm, text centered, left=0cm of plus3] (n8) Features;

[style=above=0.2cm of txt2.north, anchor=south, minimum height=0.5cm] (txt3) (FFI);

[style=rectangle, draw=black, fill=gray!10, minimum height=0.5cm, text centered, above=0.2cm of n8.north, anchor=south] (n9) Features;

[style=above=0.2cm of txt3.north, anchor=south, minimum height=0.5cm] (txt4) (F);

[style=rectangle, draw=black, fill=gray!40, minimum height=0.5cm, text centered, anchor=west] (n10) at (0.5,-4) Counterfactuals;

[style=rectangle, draw=black, fill=gray!40, minimum height=0.5cm, text centered, above=0.2cm of n10.north, anchor=south] (n11) Counterfactuals;

[style=right=0cm of n11.east] (plus4) +;

[style=rectangle, draw=black, fill=gray!40, minimum height=0.5cm, text centered, right=0cm of plus4] (n12) Feature Importance;

[style=right=0cm of n12.east] (plus5) +;

[style=rectangle, draw=black, fill=gray!40, minimum height=0.5cm, text centered, right=0cm of plus5] (n13) Features;

[style=rectangle, draw=black, fill=gray!40, minimum height=0.5cm, text centered, above=0.2cm of n12.north, anchor=south] (n14) Feature Importance;

[style=right=0cm of n14.east] (plus6) +;

[style=rectangle, draw=black, fill=gray!40, minimum height=0.5cm, text centered, right=0cm of plus6] (n15) Features;

[style=rectangle, draw=black, fill=gray!40, minimum height=0.5cm, text centered, above=0.2cm of n15.north, anchor=south] (n16) Features;

[->, -latex] (n0) -| (n1);
[->, ultra thick, -latex] (n0) -| (n2);

[->, -latex] (n1.west) – (-8.25,-1) |- (n9.west);
[->, -latex] (n1.west) – (-8.25,-1) |- (n8.west);
[->, -latex] (n1.west) – (-8.25,-1) |- (n6.west);
[->, -latex] (n1.west) – (-8.25,-1) |- (n3.west);

[->, ultra thick, -latex] (n2.east) – (8.25,-1) |- (n16.east);
[->, ultra thick, -latex] (n2.east) – (8.25,-1) |- (n15.east);
[->, ultra thick, -latex] (n2.east) – (8.25,-1) |- (n13.east);
[->, -latex] (n2.east) – (8.25,-1) |- (n10.east);

Graphical representation of our study setup. Thick lines indicate the subset of conditions from our pilot study.

Our analyses are based on a publicly available dataset on home loan application decisions[<https://www.kaggle.com/altruistdelhite04/loan-prediction-problem-dataset> (last accessed Jan 3, 2021)], which has been used in multiple  competitions.

Note that comparable data—reflecting a given finance company's individual circumstances and approval criteria—might in practice be used to train ADS.

The dataset at hand consists of 614 labeled (loan Y/N) observations and includes the following features: applicant income, co-applicant income, credit history, dependents, education, gender, loan amount, loan amount term, marital status, property area, self-employment.

After removing data points with missing values, we are left with 480 observations, 332 of which (69.2%) involve the positive label (Y) and 148 (30.8%) the negative label (N).

We use 70% of the dataset for training purposes and the remaining 30% as a holdout set.

As groundwork, after encoding and scaling the features, we trained a random forest classifier with bootstrapping to predict the held-out labels, which yields an out-of-bag accuracy estimate of 80.1%.

Our first explanation style, (F), consists of disclosing the features including corresponding values for an observation (i.e., an applicant) from the holdout set whom our model denied the loan.

We refer to such an observation as a setting.

In our study, we employ different settings in order to ensure generalizability.

Please refer to Appendix <ref> for an excerpt of questionnaires for one exemplary setting (male applicant).

Note that all explanations are derived from the data—they are not concocted.

Next, we computed permutation feature importances [Breiman, 2001] from our model and obtained the following hierarchy, using “$\succ$” as a shorthand for “is more important than”: credit history $\succ$ loan amount $\succ$ applicant income $\succ$ co-applicant income $\succ$ property area $\succ$ marital status $\succ$ dependents $\succ$ education $\succ$ loan amount term $\succ$ self-employment $\succ$ gender.

Revealing this ordered list of feature importances in conjunction with (F) makes up our second explanation style (FFI).

To construct our third and fourth explanation styles, we conducted an online survey with 20 quantitative and qualitative researchers to ascertain which of the aforementioned features are actionable—in a sense that people can (hypothetically) act on them in order to increase their chances of being granted a loan.

According to this survey, the top-5 actionable features are: loan amount, loan amount term, property area, applicant income, co-applicant income.

Our third explanation style (FFICF) is then—in conjunction with (F) and (FFI)—the provision of three counterfactual scenarios where one actionable feature each is (minimally) altered such that our model predicts a loan approval instead of a rejection.

The last explanation style is (CF), without additionally providing features or feature importances.

This condition aims at testing the effectiveness of counterfactual explanations in isolation, as opposed to providing them in conjunction with other explanation styles.

We employ only model-agnostic explanations [Adadi and Berrada, 2018] in a way that they could plausibly be provided by both humans and ADS.

§ PRELIMINARY ANALYSES AND FINDINGS

Pearson correlations between constructs for pilot study.

Construct 1     Construct 2     Pearson's $\boldsymbol{r}$

Procedural Fairness     Informational Fairness     0.47

Procedural Fairness     Trustworthiness     0.78

Procedural Fairness     Understandability     0.23

Informational Fairness     Trustworthiness     0.72

Informational Fairness     Understandability     0.69

Trustworthiness     Understandability     0.41

Based on Section <ref>, we conducted an online pilot study with 58 participants to infer preliminary insights regarding Q1 and Q2 and to validate our study design.

Among the participants were 69% males, 29% females, and one person who did not disclose their gender; 53% were students, 28% employed full-time, 10% employed part-time, 3% self-employed, and 5% unemployed.

The average age was 25.1 years, and 31% of participants have applied for a loan before.

For this pilot study, we only included the ADS settings (right branch in Figure <ref>) and limited the conditions to (F), (FFI), and (FFICF).

The study participants were randomly assigned to one of the three conditions, and each participant was provided with two consecutive questionnaires associated with two different settings—one male and one female applicant.

Participants for this online study were recruited from all over the world via [<https://www.prolific.co/>] [Palan and Schitter, 2018] and asked to rate their agreement with multiple statements on 5-point Likert scales, where a score of 1 corresponds to “strongly disagree”, and a score of 5 denotes “strongly agree”.

Additionally, we included multiple open-ended questions in the questionnaires to be able to carry out a qualitative analysis as well.

§.§ Quantitative Analysis

As mentioned earlier, we measured four different constructs: understandability (of the given explanations), procedural fairness [Colquitt et al., 2001], informational fairness [Colquitt et al., 2001], and trustworthiness (of the decision maker); see Appendix <ref> for the associated measurement items.

Note that study participants responded to the same (multiple) measurement items per construct, and these measurements were ultimately averaged to obtain one score per construct.

We evaluated the reliability of the constructs through Cronbach's alpha—all values were larger than 0.8 thus showing good reliability for all constructs [Cortina, 1993].

We proceeded to measure correlations between the four constructs with Pearson's $r$ to obtain an overview of the relationships between our constructs.

Table <ref> provides an overview of these relationships: Procedural fairness and informational fairness are each strongly correlated with trustworthiness, and informational fairness is strongly correlated with understandability.

Overall, we found significant correlations ($p < 0.05$) between all constructs besides procedural fairness and understandability.

Insights regarding Q1
We conducted multiple ANOVAs followed by Tukey's tests for post-hoc analysis to examine the effects of our three conditions.

The individual scores for each construct and condition are provided in Table <ref>.

We found a significant effect between different conditions on fairness perceptions for procedural fairness ($F(2,55) = 3.56, p = 0.035$) as well as for informational fairness ($F(2,55) = 10.90, p < 0.001$).

Tukey's test for post-hoc analysis showed that the effect for procedural fairness was only significant between the conditions (F) and (FFICF) ($p = 0.040$).

When controlling for different variables, such as study participants' gender, the effect for procedural fairness is reduced to marginal significance

($p > 0.05$).

For informational fairness the effect in the post-hoc analysis without control variables is significant between (F) and (FFICF) ($p < 0.001$) as well as between (FFI) and (FFICF) ($p = 0.042$), and it is marginally significant between (F) and (FFI) ($p = 0.072$).

Controlling for study participants' gender reduces the significance between (FFI) and (FFICF) to marginal significance ($p = 0.059$); controlling for study participants' age removes the significance between these two conditions altogether.

Interestingly, significant effects on understandability between conditions ($F(2,55) = 7.52, p = 0.001$) came from (F) and (FFICF) ($p = 0.001$) as well as (F) and (FFI) ($p = 0.020$).

Significant effects of the conditions on trustworthiness ($F(2,55) = 4.94, p = 0.011$) could only be observed between (F) and (FFICF) ($p = 0.007$).

In general, we urge to exercise utmost caution when interpreting the quantitative results of our pilot study as the sample size is extremely small.

We hope to generate more reliable and extensive insights with our main study and a much larger number of participants.

Construct scores by condition for pilot study. The scores, ranging from 1 (low) to 5 (high), were obtained by averaging across all measurement items for each construct.

(F)     (FFI)     (FFICF)

Understandability     3.17     3.87     4.12

Procedural Fairness     3.28     3.40     3.91

Informational Fairness     2.79     3.33     3.92

Trustworthiness     2.92     3.39     3.83

Insights regarding Q2

We calculated Pearson's $r$ between each of our fairness measures including trustworthiness and the study participants' AI literacy.

All three measures, procedural fairness ($r = 0.35, p = 0.006$), informational fairness ($r = 0.52, p < 0.001$) and trustworthiness ($r = 0.48, p < 0.001$) demonstrate a significant positive correlation with AI literacy.

Therefore, within the scope of our pilot study, we found that participants with more knowledge and experience in the field of AI tend to perceive the decision making process and the provided explanations of the ADS at hand to be fairer and more trustworthy than participants with less knowledge and experience in this field.

§.§ Qualitative Analysis

In the following, we provide a summary of insightful responses to open-ended questions from our questionnaires.

Regarding automated decision making
Perhaps surprisingly, many participants approved of the ADS as the decision maker.

They perceived the decision to be less biased and argued that all applicants are treated equally, because the ADS makes its choices based on facts, not based on the likeability of a person:

“I think that an automated system treats every individual fairly because everybody is judged according to the same rules.”

Some participants directly compared the ADS to human decision makers:

“I think that [the decision making procedures] are fair because they are objective, since they are automated. Humans usually [can't] make decisions without bias.”

Other participants responded with a (somewhat expected) disapproval towards the ADS.

Participants criticized, for instance, that the decisions “are missing humanity in them” and how an automated decision based “only on statistics without human morality and ethics” simply cannot be fair.

One participant went so far as to formulate positive arguments for human bias in decision making procedures:

“I do not believe that it is fair to assess anything that greatly affects an individual's life or [livelihood] through an automated decision system. I believe some bias and personal opinion is often necessary to uphold ethical and moral standards.”

Finally, some participants had mixed feelings because they saw the trade-off between a “cold approach” that lacks empathy and a solution that promotes “equality with others” because it “eliminates personal bias”.

Regarding explanations Study participants had strong opinions on the features considered in the loan decision.

Most participants found gender to be the most inappropriate feature.

The comments on this feature ranged from “I think the gender of the person shouldn't matter” to considering gender as a factor being “ethically wrong” or even “borderline illegal”.

Education and property area were named by many participants as being inappropriate factors as well:

“I think education, gender, property area […] are inappropriate factors and should not be considered in the decision making process.”

On average, the order of feature importance was rated as equally appropriate as the features themselves.

Some participants assessed the order of feature importance in general and came to the conclusion that it is appropriate:

“The most important is credit history in this decision and least gender so the order is appropriate.”

At the same time, a few participants rated the order of feature importance as inappropriate, for instance because “some things are irrelevant yet score higher than loan term.”

In the first of two settings, the counterfactual for property area was received negatively by some:

“It shouldn't matter where the property is located.”

Yet, most participants found the counterfactual explanations
in the second setting
to be appropriate:

“The three scenarios represent plausible changes the individual could perform

§ OUTLOOK

The potential of automated decision making and its benefits over purely human-made decisions are obvious.

However, several instances are known where such automated decision systems (ADS) are having undesirable effects—especially with respect to fairness and transparency.

With this work, we aim to contribute novel insights to better understand people's perceptions of fairness and trustworthiness towards ADS, based on the provision of varying degrees of information about such systems and their underlying processes.

Moreover, we examine how these perceptions are influenced by people's background and experience in the field of artificial intelligence.

As a first step, we have conducted an online pilot study and obtained preliminary results for a subset of conditions.

Next, we will initiate our main study with a larger sample size and additional analyses.

For instance, we will also explore whether people's perceptions of fairness and trustworthiness change when the decision maker is claimed to be human (as opposed to purely automated).

We hope that our contribution will ultimately help in designing more equitable decision systems as well as stimulate future research on this important topic.

[Kuncel et al., 2014]
authorN. R. Kuncel, authorD. S. Ones,
authorD. M. Klieger,
titleIn hiring, algorithms beat instinct,
journalHarvard Business Review  (year2014).

[Townson, 2020]
authorS. Townson,
titleAI can make bank loans more fair,
journalHarvard Business Review  (year2020).

[Satariano, 2020]
authorA. Satariano,
titleBritish grading debacle shows pitfalls of automating
journalThe New York Times  (year2020).

[Heaven, 2020]
authorW. D. Heaven,
titlePredictive policing algorithms are racist. They
need to be dismantled,
journalMIT Technology Review  (year2020).

[Harris and Davenport, 2005]
authorJ. G. Harris, authorT. H. Davenport,
titleAutomated decision making comes of age,
journalMIT Sloan Management Review
(year2005). <https://sloanreview.mit.edu/article/automated-decision-making-comes-of-age/>.

[Barocas et al., 2019]
authorS. Barocas, authorM. Hardt,
authorA. Narayanan, titleFairness and machine
learning, year2019. <http://www.fairmlbook.org>.

[Buolamwini and Gebru, 2018]
authorJ. Buolamwini, authorT. Gebru,
titleGender shades: Intersectional accuracy disparities in
commercial gender classification,
in: booktitleConference on Fairness, Accountability and
Transparency, year2018, pp. pages77–91.

[Angwin et al., 2016]
authorJ. Angwin, authorJ. Larson,
authorS. Mattu, authorL. Kirchner,
titleMachine bias,
journalProPublica  (year2016). <https://www.propublica.org/article/machine-bias-risk-assessments-in-criminal-sentencing>.

[Srivastava et al., 2019]
authorM. Srivastava, authorH. Heidari,
authorA. Krause,
titleMathematical notions vs. human perception of
fairness: A descriptive approach to fairness for machine learning,
in: booktitleProceedings of the 25th ACM SIGKDD
International Conference on Knowledge Discovery & Data Mining,
year2019, pp. pages2459–2468.

[Binns et al., 2018]
authorR. Binns, authorM. Van Kleek,
authorM. Veale, authorU. Lyngs,
authorJ. Zhao, authorN. Shadbolt,
title`It's reducing a human being to a percentage';
perceptions of justice in algorithmic decisions,
in: booktitleProceedings of the 2018 CHI Conference on
Human Factors in Computing Systems, year2018, pp.

[Dodge et al., 2019]
authorJ. Dodge, authorQ. V. Liao,
authorY. Zhang, authorR. K. Bellamy,
authorC. Dugan,
titleExplaining models: An empirical study of how
explanations impact fairness judgment,
in: booktitleProceedings of the 24th International
Conference on Intelligent User Interfaces, year2019, pp.

[Lee, 2018]
authorM. K. Lee,
titleUnderstanding perception of algorithmic decisions:
Fairness, trust, and emotion in response to algorithmic management,
journalBig Data & Society volume5
(year2018) pages1–16.

[Lee and Baykal, 2017]
authorM. K. Lee, authorS. Baykal,
titleAlgorithmic mediation in group decisions: Fairness
perceptions of algorithmically mediated vs. discussion-based social
in: booktitleProceedings of the 2017 ACM Conference on
Computer-Supported Cooperative Work and Social Computing,
year2017, pp. pages1035–1048.

[Wang et al., 2020]
authorR. Wang, authorF. M. Harper,
authorH. Zhu,
titleFactors influencing perceived fairness in algorithmic
decision-making: Algorithm outcomes, development procedures, and individual
in: booktitleProceedings of the 2020 CHI Conference on
Human Factors in Computing Systems, year2020, pp.

[Goebel et al., 2018]
authorR. Goebel, authorA. Chander,
authorK. Holzinger, authorF. Lecue,
authorZ. Akata, authorS. Stumpf,
authorP. Kieseberg, authorA. Holzinger,
titleExplainable AI: The new 42?,
in: booktitleInternational Cross-Domain Conference for
Machine Learning and Knowledge Extraction, year2018, pp.

[Eslami et al., 2019]
authorM. Eslami, authorK. Vaccaro,
authorM. K. Lee, authorA. Elazari Bar On,
authorE. Gilbert, authorK. Karahalios,
titleUser attitudes towards algorithmic opacity and
transparency in online reviewing platforms,
in: booktitleProceedings of the 2019 CHI Conference on
Human Factors in Computing Systems, year2019, pp.

[Bussone et al., 2015]
authorA. Bussone, authorS. Stumpf,
authorD. O'Sullivan,
titleThe role of explanations on trust and reliance in
clinical decision support systems,
in: booktitleIEEE International Conference on Healthcare
Informatics, year2015, pp. pages160–169.

[Kulesza et al., 2013]
authorT. Kulesza, authorS. Stumpf,
authorM. Burnett, authorS. Yang,
authorI. Kwan, authorW.-K. Wong,
titleToo much, too little, or just right? Ways
explanations impact end users' mental models,
in: booktitle2013 IEEE Symposium on Visual Languages and
Human-Centric Computing, year2013, pp. pages3–10.

[Molnar, 2020]
authorC. Molnar, titleInterpretable machine learning,
year2020. <https://christophm.github.io/interpretable-ml-book/>.

[Adadi and Berrada, 2018]
authorA. Adadi, authorM. Berrada,
titlePeeking inside the black-box: A survey on explainable
artificial intelligence (XAI),
journalIEEE Access volume6
(year2018) pages52138–52160.

[Lee et al., 2019]
authorM. K. Lee, authorA. Jain, authorH. J.
Cha, authorS. Ojha, authorD. Kusbit,
titleProcedural justice in algorithmic fairness:
Leveraging transparency and outcome control for fair algorithmic mediation,
journalProceedings of the ACM on Human-Computer
Interaction volume3 (year2019)

[Kizilcec, 2016]
authorR. F. Kizilcec,
titleHow much information? Effects of transparency on
trust in an algorithmic interface,
in: booktitleProceedings of the 2016 CHI Conference on
Human Factors in Computing Systems, year2016, pp.

[Long and Magerko, 2020]
authorD. Long, authorB. Magerko,
titleWhat is AI literacy? Competencies and design
in: booktitleProceedings of the 2020 CHI Conference on
Human Factors in Computing Systems, year2020, pp.

[Colquitt et al., 2001]
authorJ. A. Colquitt, authorD. E. Conlon,
authorM. J. Wesson, authorC. O. Porter,
authorK. Y. Ng,
titleJustice at the millennium: A meta-analytic review
of 25 years of organizational justice research,
journalJournal of Applied Psychology volume86
(year2001) pages425–445.

[Breiman, 2001]
authorL. Breiman,
titleRandom forests,
journalMachine Learning volume45
(year2001) pages5–32.

[Palan and Schitter, 2018]
authorS. Palan, authorC. Schitter,
titleProlific.ac—a subject pool for online experiments,
journalJournal of Behavioral and Experimental Finance
volume17 (year2018) pages22–27.

[Cortina, 1993]
authorJ. M. Cortina,
titleWhat is coefficient alpha? An examination of theory
and applications,
journalJournal of Applied Psychology volume78
(year1993) pages98–104.

[McKinney et al., 2002]
authorV. McKinney, authorK. Yoon,
authorF. M. Zahedi,
titleThe measurement of web-customer satisfaction: An
expectation and disconfirmation approach,
journalInformation Systems Research volume13
(year2002) pages296–315.

[Colquitt and Rodell, 2015]
authorJ. A. Colquitt, authorJ. B. Rodell,
titleMeasuring justice and fairness,
in: editorR. S. Cropanzano, editorM. L.
Ambrose (Eds.), booktitleThe Oxford Handbook of Justice in the
Workplace, publisherOxford University Press,
year2015, pp. pages187–202.

[Chiu et al., 2009]
authorC.-M. Chiu, authorH.-Y. Lin,
authorS.-Y. Sun, authorM.-H. Hsu,
titleUnderstanding customers' loyalty intentions towards
online shopping: An integration of technology acceptance model and fairness
journalBehaviour & Information Technology
volume28 (year2009) pages347–360.

[Carter and Bélanger, 2005]
authorL. Carter, authorF. Bélanger,
titleThe utilization of e-government services: Citizen
trust, innovation and acceptance factors,
journalInformation Systems Journal volume15
(year2005) pages5–25.

[Wilkinson et al., 2010]
authorA. Wilkinson, authorJ. Roberts,
authorA. E. While,
titleConstruction of an instrument to measure student
information and communication technology skills, experience and attitudes to
journalComputers in Human Behavior volume26
(year2010) pages1369–1376.

[Kuncel et al., 2014]
authorN. R. Kuncel, authorD. S. Ones,
authorD. M. Klieger,
titleIn hiring, algorithms beat instinct,
journalHarvard Business Review  (year2014).

[Townson, 2020]
authorS. Townson,
titleAI can make bank loans more fair,
journalHarvard Business Review  (year2020).

[Satariano, 2020]
authorA. Satariano,
titleBritish grading debacle shows pitfalls of automating
journalThe New York Times  (year2020).

[Heaven, 2020]
authorW. D. Heaven,
titlePredictive policing algorithms are racist. They
need to be dismantled,
journalMIT Technology Review  (year2020).

[Harris and Davenport, 2005]
authorJ. G. Harris, authorT. H. Davenport,
titleAutomated decision making comes of age,
journalMIT Sloan Management Review
(year2005). <https://sloanreview.mit.edu/article/automated-decision-making-comes-of-age/>.

[Barocas et al., 2019]
authorS. Barocas, authorM. Hardt,
authorA. Narayanan, titleFairness and machine
learning, year2019. <http://www.fairmlbook.org>.

[Buolamwini and Gebru, 2018]
authorJ. Buolamwini, authorT. Gebru,
titleGender shades: Intersectional accuracy disparities in
commercial gender classification,
in: booktitleConference on Fairness, Accountability and
Transparency, year2018, pp. pages77–91.

[Angwin et al., 2016]
authorJ. Angwin, authorJ. Larson,
authorS. Mattu, authorL. Kirchner,
titleMachine bias,
journalProPublica  (year2016). <https://www.propublica.org/article/machine-bias-risk-assessments-in-criminal-sentencing>.

[Srivastava et al., 2019]
authorM. Srivastava, authorH. Heidari,
authorA. Krause,
titleMathematical notions vs. human perception of
fairness: A descriptive approach to fairness for machine learning,
in: booktitleProceedings of the 25th ACM SIGKDD
International Conference on Knowledge Discovery & Data Mining,
year2019, pp. pages2459–2468.

[Binns et al., 2018]
authorR. Binns, authorM. Van Kleek,
authorM. Veale, authorU. Lyngs,
authorJ. Zhao, authorN. Shadbolt,
title`It's reducing a human being to a percentage';
perceptions of justice in algorithmic decisions,
in: booktitleProceedings of the 2018 CHI Conference on
Human Factors in Computing Systems, year2018, pp.

[Dodge et al., 2019]
authorJ. Dodge, authorQ. V. Liao,
authorY. Zhang, authorR. K. Bellamy,
authorC. Dugan,
titleExplaining models: An empirical study of how
explanations impact fairness judgment,
in: booktitleProceedings of the 24th International
Conference on Intelligent User Interfaces, year2019, pp.

[Lee, 2018]
authorM. K. Lee,
titleUnderstanding perception of algorithmic decisions:
Fairness, trust, and emotion in response to algorithmic management,
journalBig Data & Society volume5
(year2018) pages1–16.

[Lee and Baykal, 2017]
authorM. K. Lee, authorS. Baykal,
titleAlgorithmic mediation in group decisions: Fairness
perceptions of algorithmically mediated vs. discussion-based social
in: booktitleProceedings of the 2017 ACM Conference on
Computer-Supported Cooperative Work and Social Computing,
year2017, pp. pages1035–1048.

[Wang et al., 2020]
authorR. Wang, authorF. M. Harper,
authorH. Zhu,
titleFactors influencing perceived fairness in algorithmic
decision-making: Algorithm outcomes, development procedures, and individual
in: booktitleProceedings of the 2020 CHI Conference on
Human Factors in Computing Systems, year2020, pp.

[Goebel et al., 2018]
authorR. Goebel, authorA. Chander,
authorK. Holzinger, authorF. Lecue,
authorZ. Akata, authorS. Stumpf,
authorP. Kieseberg, authorA. Holzinger,
titleExplainable AI: The new 42?,
in: booktitleInternational Cross-Domain Conference for
Machine Learning and Knowledge Extraction, year2018, pp.

[Eslami et al., 2019]
authorM. Eslami, authorK. Vaccaro,
authorM. K. Lee, authorA. Elazari Bar On,
authorE. Gilbert, authorK. Karahalios,
titleUser attitudes towards algorithmic opacity and
transparency in online reviewing platforms,
in: booktitleProceedings of the 2019 CHI Conference on
Human Factors in Computing Systems, year2019, pp.

[Bussone et al., 2015]
authorA. Bussone, authorS. Stumpf,
authorD. O'Sullivan,
titleThe role of explanations on trust and reliance in
clinical decision support systems,
in: booktitleIEEE International Conference on Healthcare
Informatics, year2015, pp. pages160–169.

[Kulesza et al., 2013]
authorT. Kulesza, authorS. Stumpf,
authorM. Burnett, authorS. Yang,
authorI. Kwan, authorW.-K. Wong,
titleToo much, too little, or just right? Ways
explanations impact end users' mental models,
in: booktitle2013 IEEE Symposium on Visual Languages and
Human-Centric Computing, year2013, pp. pages3–10.

[Molnar, 2020]
authorC. Molnar, titleInterpretable machine learning,
year2020. <https://christophm.github.io/interpretable-ml-book/>.

[Adadi and Berrada, 2018]
authorA. Adadi, authorM. Berrada,
titlePeeking inside the black-box: A survey on explainable
artificial intelligence (XAI),
journalIEEE Access volume6
(year2018) pages52138–52160.

[Lee et al., 2019]
authorM. K. Lee, authorA. Jain, authorH. J.
Cha, authorS. Ojha, authorD. Kusbit,
titleProcedural justice in algorithmic fairness:
Leveraging transparency and outcome control for fair algorithmic mediation,
journalProceedings of the ACM on Human-Computer
Interaction volume3 (year2019)

[Kizilcec, 2016]
authorR. F. Kizilcec,
titleHow much information? Effects of transparency on
trust in an algorithmic interface,
in: booktitleProceedings of the 2016 CHI Conference on
Human Factors in Computing Systems, year2016, pp.

[Long and Magerko, 2020]
authorD. Long, authorB. Magerko,
titleWhat is AI literacy? Competencies and design
in: booktitleProceedings of the 2020 CHI Conference on
Human Factors in Computing Systems, year2020, pp.

[Colquitt et al., 2001]
authorJ. A. Colquitt, authorD. E. Conlon,
authorM. J. Wesson, authorC. O. Porter,
authorK. Y. Ng,
titleJustice at the millennium: A meta-analytic review
of 25 years of organizational justice research,
journalJournal of Applied Psychology volume86
(year2001) pages425–445.

[Breiman, 2001]
authorL. Breiman,
titleRandom forests,
journalMachine Learning volume45
(year2001) pages5–32.

[Palan and Schitter, 2018]
authorS. Palan, authorC. Schitter,
titleProlific.ac—a subject pool for online experiments,
journalJournal of Behavioral and Experimental Finance
volume17 (year2018) pages22–27.

[Cortina, 1993]
authorJ. M. Cortina,
titleWhat is coefficient alpha? An examination of theory
and applications,
journalJournal of Applied Psychology volume78
(year1993) pages98–104.

[McKinney et al., 2002]
authorV. McKinney, authorK. Yoon,
authorF. M. Zahedi,
titleThe measurement of web-customer satisfaction: An
expectation and disconfirmation approach,
journalInformation Systems Research volume13
(year2002) pages296–315.

[Colquitt and Rodell, 2015]
authorJ. A. Colquitt, authorJ. B. Rodell,
titleMeasuring justice and fairness,
in: editorR. S. Cropanzano, editorM. L.
Ambrose (Eds.), booktitleThe Oxford Handbook of Justice in the
Workplace, publisherOxford University Press,
year2015, pp. pages187–202.

[Chiu et al., 2009]
authorC.-M. Chiu, authorH.-Y. Lin,
authorS.-Y. Sun, authorM.-H. Hsu,
titleUnderstanding customers' loyalty intentions towards
online shopping: An integration of technology acceptance model and fairness
journalBehaviour & Information Technology
volume28 (year2009) pages347–360.

[Carter and Bélanger, 2005]
authorL. Carter, authorF. Bélanger,
titleThe utilization of e-government services: Citizen
trust, innovation and acceptance factors,
journalInformation Systems Journal volume15
(year2005) pages5–25.

[Wilkinson et al., 2010]
authorA. Wilkinson, authorJ. Roberts,
authorA. E. While,
titleConstruction of an instrument to measure student
information and communication technology skills, experience and attitudes to
journalComputers in Human Behavior volume26
(year2010) pages1369–1376.

§ CONSTRUCTS AND ITEMS FOR AUTOMATED DECISIONS

All items within the following constructs were measured on a 5-point Likert scale and mostly drawn (and adapted) from previous studies.

* Understandability

Please rate your agreement with the following statements:

* The explanations provided by the automated decision system are clear in meaning. [McKinney et al., 2002]

* The explanations provided by the automated decision system are easy to comprehend. [McKinney et al., 2002]

* In general, the explanations provided by the automated decision system are understandable for me. [McKinney et al., 2002]

* Procedural Fairness

The statements below refer to the procedures the automated decision system uses to make decisions about loan applications. Please rate your agreement with the following statements:

* Those procedures are free of bias. [Colquitt and Rodell, 2015]

* Those procedures uphold ethical and moral standards. [Colquitt and Rodell, 2015]

* Those procedures are fair.

* Those procedures ensure that decisions are based on facts, not personal biases and opinions. [Colquitt and Rodell, 2015]

* Overall, the applying individual is treated fairly by the automated decision system. [Colquitt and Rodell, 2015]

* Informational Fairness

The statements below refer to the explanations the automated decision system offers with respect to the decision-making procedures. Please rate your agreement with the following statements:

* The automated decision system explains decision-making procedures thoroughly. [Colquitt and Rodell, 2015]

* The automated decision system’s explanations regarding procedures are reasonable. [Colquitt and Rodell, 2015]

* The automated decision system tailors communications to meet the applying individual’s needs. [Colquitt and Rodell, 2015]

* I understand the process by which the decision was made. [Binns et al., 2018]

* I received sufficient information to judge whether the decision-making procedures are fair or unfair.

* Trustworthiness

The statements below refer to the automated decision system. Please rate your agreement with the following statements:

* Given the provided explanations, I trust that the automated decision system makes good-quality decisions. [Lee, 2018]

* Based on my understanding of the decision-making procedures, I know the automated decision system is not opportunistic. [Chiu et al., 2009]

* Based on my understanding of the decision-making procedures, I know the automated decision system is trustworthy. [Chiu et al., 2009]

* I think I can trust the automated decision system. [Carter and Bélanger, 2005]

* The automated decision system can be trusted to carry out the loan application decision faithfully. [Carter and Bélanger, 2005]

* In my opinion, the automated decision system is trustworthy. [Carter and Bélanger, 2005]

* AI Literacy

* How would you describe your knowledge in the field of artificial intelligence?

* Does your current employment include working with artificial intelligence?

Please rate your agreement with the following statements:

* I am confident interacting with artificial intelligence. [Wilkinson et al., 2010]

* I understand what the term artificial intelligence means.

§ EXPLANATION STYLES FOR AUTOMATED DECISIONS AND ONE EXEMPLARY SETTING (MALE APPLICANT)

[breakable, enhanced jigsaw, sharp corners, opacityback=0, fonttitle=, colframe=black, boxrule=1pt, title=Explanation Style (F)]

[enhanced jigsaw, sharp corners, colframe=black, boxrule=1pt]
A finance company offers loans on real estate in urban, semi-urban and rural areas. A potential customer first applies online for a specific loan, and afterwards the company assesses the customer's eligibility for that loan.

An individual applied online for a loan at this company. The company denied the loan application. The decision to deny the loan was made by an automated decision system and communicated to the applying individual electronically and in a timely fashion.

The automated decision system explains that the following factors (in alphabetical order) on the individual were taken into account when making the loan application decision:

* Applicant Income: $3,069 per month

* Co-Applicant Income: $0 per month

* Credit History: Good

* Dependents: 0

* Education: Graduate

* Gender: Male

* Loan Amount: $71,000

* Loan Amount Term: 480 months

* Married: No

* Property Area: Urban

* Self-Employed: No

[breakable, enhanced jigsaw, sharp corners, opacityback=0, fonttitle=, colframe=black, boxrule=1pt, title=Explanation Style (FFI)]

[enhanced jigsaw, sharp corners, colframe=black, boxrule=1pt]
A finance company offers loans on real estate in urban, semi-urban and rural areas. A potential customer first applies online for a specific loan, and afterwards the company assesses the customer's eligibility for that loan.

An individual applied online for a loan at this company. The company denied the loan application. The decision to deny the loan was made by an automated decision system and communicated to the applying individual electronically and in a timely fashion.

The automated decision system explains …

* …that the following factors (in alphabetical order) on the individual were taken into account when making the loan application decision:

* Applicant Income: $3,069 per month

* Co-Applicant Income: $0 per month

* Credit History: Good

* Dependents: 0

* Education: Graduate

* Gender: Male

* Loan Amount: $71,000

* Loan Amount Term: 480 months

* Married: No

* Property Area: Urban

* Self-Employed: No

* …that different factors are of different importance in the decision. The following list shows the order of factor importance, from most important to least important:
Credit History $\succ$ Loan Amount $\succ$ Applicant Income $\succ$ Co-Applicant Income $\succ$ Property Area $\succ$ Married $\succ$ Dependents $\succ$ Education $\succ$ Loan Amount Term $\succ$ Self-Employed $\succ$ Gender

[breakable, enhanced jigsaw, sharp corners, opacityback=0, fonttitle=, colframe=black, boxrule=1pt, title=Explanation Style (FFICF)]

[enhanced jigsaw, sharp corners, colframe=black, boxrule=1pt]
A finance company offers loans on real estate in urban, semi-urban and rural areas. A potential customer first applies online for a specific loan, and afterwards the company assesses the customer's eligibility for that loan.

An individual applied online for a loan at this company. The company denied the loan application. The decision to deny the loan was made by an automated decision system and communicated to the applying individual electronically and in a timely fashion.

The automated decision system explains …

* …that the following factors (in alphabetical order) on the individual were taken into account when making the loan application decision:

* Applicant Income: $3,069 per month

* Co-Applicant Income: $0 per month

* Credit History: Good

* Dependents: 0

* Education: Graduate

* Gender: Male

* Loan Amount: $71,000

* Loan Amount Term: 480 months

* Married: No

* Property Area: Urban

* Self-Employed: No

* …that different factors are of different importance in the decision. The following list shows the order of factor importance, from most important to least important:
Credit History $\succ$ Loan Amount $\succ$ Applicant Income $\succ$ Co-Applicant Income $\succ$ Property Area $\succ$ Married $\succ$ Dependents $\succ$ Education $\succ$ Loan Amount Term $\succ$ Self-Employed $\succ$ Gender

* …that the individual would have been granted the loan if—everything else unchanged—one of the following hypothetical scenarios had been true:

* The Co-Applicant Income had been at least $800 per month

* The Loan Amount Term had been 408 months or less

* The Property Area had been Rural


# Spatial entanglement between two quantum walkers with exchange symmetric
coins

Ibrahim Yahaya Muhammad  Theoretical and Computational Physics (TCP) Group,
Department of Physics, Faculty of Science, King Mongkut’s University of
Technology Thonburi, Bangkok 10140, Thailand  Theoretical and Computational
Science Center (TaCS), Faculty of Science, King Mongkut’s University of
Technology Thonburi, Bangkok 10140, Thailand  Tanapat Deesuwan
<EMAIL_ADDRESS>Theoretical and Computational Physics (TCP) Group,
Department of Physics, Faculty of Science, King Mongkut’s University of
Technology Thonburi, Bangkok 10140, Thailand  Theoretical and Computational
Science Center (TaCS), Faculty of Science, King Mongkut’s University of
Technology Thonburi, Bangkok 10140, Thailand  Quantum Computing and Theory
Center (QX), King Mongkut’s University of Technology Thonburi, Bangkok 10140,
Thailand  Sikarin Yoo-Kong  The Institute for Fundamental Study (IF), Naresuan
University, Phitsanulok 65000, Thailand  Suwat Tangwancharoen  Theoretical and
Computational Physics (TCP) Group, Department of Physics, Faculty of Science,
King Mongkut’s University of Technology Thonburi, Bangkok 10140, Thailand
Theoretical and Computational Science Center (TaCS), Faculty of Science, King
Mongkut’s University of Technology Thonburi, Bangkok 10140, Thailand  Monsit
Tanasittikosol<EMAIL_ADDRESS>Theoretical and Computational Physics
(TCP) Group, Department of Physics, Faculty of Science, King Mongkut’s
University of Technology Thonburi, Bangkok 10140, Thailand

###### Abstract

We investigate the dynamics of the spatial entanglement between two initially
independent walkers that perform discrete-time quantum walk with respect to
symmetric and anti-symmetric initial coin states. By considering the symmetry
associated with the setting and post-selecting the states of the two coins
accordingly, we show that, for the anti-symmetric initial coin state, the
entanglement corresponding to all the anti-symmetric results are always
constant, while that corresponding to the symmetric result is underdamped-like
with period of oscillation ($T$) being inversely proportional to the coin
operator parameter ($\theta$). The results are the opposite way around for the
case of symmetric initial coin states. We also discover that the underdamped-
like behaviour of the spatial entanglement show up in the cases of both
initial coin states when the post-selected results have no symmetry. Our
findings reveal some interesting aspects of symmetry and entanglement dynamics
in quantum walk, which may be useful for applications in quantum communication
and other quantum technology.

##  1 Introduction

The significance of classical random walk for the design of classical
algorithms motivates the study of quantum walk to implement quantum algorithms
[1, 2] that are flexible and solve problems more efficiently. Quantum walks
have become an interesting area of research in quantum information and quantum
computation [3, 4, 5, 6]. Quantum walk was first studied by Aharonov  et al in
$1993$ [7]. Quantum properties such as superposition, entanglement that occur
in the quantum walks allow it to have more advantages over classical random
walk [8, 9, 10]. The physical implementation of quantum walk in some physical
systems such as trapped ions [11, 12], nuclear magnetic resonance [13], cold
atoms [14, 15], integrated photonics [16, 17], and superconducting qubits [18,
19], show its promising role in future quantum technologies. An introductory
overview and a review of the quantum walk can be found in [20, 21].

One of the fundamental aspects of quantum walk that has been discussed since
the invention of the scheme is the entanglement among the walkers and the
coins. For example, in [22, 23], the dynamics of the entanglement between one
walker and one coin were shown to change with the walking step similar to how
a damped oscillator moves. Also, entanglement in two-particle quantum walks
have been studied in several literature [24, 25, 26, 27, 28, 29, 30].
Moreover, the entanglement between many particles undergoing quantum walk can
be found in [31]. The spatial entanglement between two walkers sharing one
coin state have been studied in [32, 33], by performing measurement on the
coin basis to generate entanglement between the two walkers.

In this paper, starting with two entangled coins state that has symmetric and
anti-symmetric exchange symmetry, we study the dynamics of spatial
entanglement between two walkers undergoing discrete-time quantum walk on a
one-dimensional lattice, with and without post-selection on the coin states.
Particularly, we investigate how the initial exchange symmetry of the coins
affect the entanglement between the walkers. The structure of the paper is the
following. In Section 2, we present a brief overview of the quantum walk for
one walker with one coin and two walkers with two identical coins. In Section
3, we show the entanglement dynamics between two walkers and discuss our key
results. The final section 4 provides the conclusion of our study.

##  2 Quantum walk

Let us first start with an overview of the one walker and two walkers quantum
walk together with the mathematical notations which will be used throughout
the text.

###  2.1 One walker with one coin

To introduce the discrete-time quantum walk with one walker in one dimension,
we imagine the motion of a walker on a one-dimensional lattice. The position
of the walker lattice point $i$ is assigned by the state $\ket{i}$, where $i$
$\in$ $\mathbb{Z}$, belonging to the walker Hilbert space $\mathcal{H}_{w}$.
In order to make the walker move randomly, a coin is needed to assign to the
walker and the coin Hilbert space $\mathcal{H}_{c}$ is defined by two
orthonormal states: $\ket{\uparrow}$ and $\ket{\downarrow}$. The total state
of the system (walker+coin) then belongs to the product space
$\mathcal{H}=\mathcal{H}_{c}\otimes\mathcal{H}_{w}$. There are 3 operations
involved in the quantum walk as follows:

  * •

Operation 1: Apply the coin operator $\hat{C}_{1}(\theta)$ to the coin state.
The coin operator is defined as where $\theta$ is the angle that determines
how biased the coin is. For example, $\theta=\pi/4$ means we have an unbiased
coin, while $\theta=n\pi,$ where $n$ is an integer means only one side of the
coin always show up, i.e., we have a maximally biased coin.

  * •

Operation 2: Apply the shift operation $\hat{S}_{1}$ to the walker state. The
shift operator is defined as

$\displaystyle\hat{S}_{1}=\ket{\uparrow}\bra{\uparrow}\otimes\displaystyle\sum_{i}\ket{i+1}\bra{i}$
$\displaystyle+\ket{\downarrow}\bra{\downarrow}\otimes\displaystyle\sum_{i}\ket{i-1}\bra{i}.$
(1)

Note that the first two operations can be combined into a single unitary
operator:

$\displaystyle\hat{U}_{1}=\hat{S}_{1}(\hat{C}_{1}\otimes\hat{I}).$ (2)

where $\hat{I}$ is the identity operator acting on the position state of the
walker. The operator $\hat{U}_{1}$ will be applied to the system as many times
as one needs before proceeding to the last operation. We will say the $n^{th}$
steps of the walk is done after $\hat{U}_{1}$ is applied to the system $n$
times.

    * –

Operation 3: Perform measurement on the coin state. The measurement basis is
usually formed by the following operators,

$\displaystyle\hat{M}_{\uparrow}=\ket{\uparrow}\bra{\uparrow}\;,\;\hat{M}_{\downarrow}=\ket{\downarrow}\bra{\downarrow}.$
(3)

###  2.2 Two walkers with two identical coins

Let us now consider two walkers, each of which _separately_ but _identically_
evolves according to the previously discussed one walker protocol with respect
to each own coin. The Hilbert space of the total system, in this case, is the
product space $\mathcal{H}$ given by
$\mathcal{H}=\mathcal{H}_{1}\otimes\mathcal{H}_{2}=(\mathcal{H}_{c}\otimes\mathcal{H}_{w})_{1}\otimes(\mathcal{H}_{c}\otimes\mathcal{H}_{w})_{2},$
where $\mathcal{H}_{1}$ is the combined Hilbert space of walker 1 and coin 1,
and $\mathcal{H}_{2}$ is the combined Hilbert space of walker 2 and coin 2.
The coin operator in this case is

$\displaystyle\hat{C}(\theta)=\hat{C}_{1}(\theta)\otimes\hat{C}_{2}(\theta).$
(4)

We only consider the case where the angles for the two coins operators are the
same. The shift operator is

$\displaystyle\hat{S}$ $\displaystyle=\hat{S}_{1}\otimes\hat{S}_{2}$
$\displaystyle=\ket{\uparrow\uparrow}\bra{\uparrow\uparrow}\otimes\sum_{ij}\ket{i+1,j+1}\bra{i,j}$
$\displaystyle+\ket{\uparrow\downarrow}\bra{\uparrow\downarrow}\otimes\sum_{ij}\ket{i+1,j-1}\bra{i,j}$
$\displaystyle+\ket{\downarrow\uparrow}\bra{\downarrow\uparrow}\otimes\sum_{ij}\ket{i-1,j+1}\bra{i,j}$
$\displaystyle+\ket{\downarrow\downarrow}\bra{\downarrow\downarrow}\otimes\sum_{ij}\ket{i-1,j-1}\bra{i,j}.$
(5)

Thus, the combination of these two operators gives the evolution operator in
the form,

$\displaystyle\hat{U}(\theta)=\hat{S}(\hat{C}(\theta)\otimes I).$ (6)

Furthermore, the measurement basis considered in this case are composed of the
following operators,

$\displaystyle\hat{M}_{\uparrow\uparrow}$
$\displaystyle=\ket{\uparrow\uparrow}\bra{\uparrow\uparrow}\;,\;\hat{M}_{\uparrow\downarrow}=\ket{\uparrow\downarrow}\bra{\uparrow\downarrow}$
$\displaystyle\hat{M}_{\downarrow\uparrow}$
$\displaystyle=\ket{\downarrow\uparrow}\bra{\downarrow\uparrow}\;,\;\hat{M}_{\downarrow\downarrow}=\ket{\downarrow\downarrow}\bra{\downarrow\downarrow}\;.$
(7)

Note that all of these are basically two copies of the one walker quantum walk
operators that apply to the two walkers separately. The fact that all the
operations considered are “local” implies that the entanglement between the
two walkers cannot be increased by these operations.

##  3 Our settings and results

Suppose that the initial state of the system can be written in the following
form,

$\displaystyle\ket{\psi}_{0}$ $\displaystyle=\ket{Bell}\otimes\ket{0,0},$ (8)

where $\ket{Bell}$ is one of the Bell states
($\ket{\Psi^{\pm}}=\frac{\ket{\uparrow,\downarrow}\pm\ket{\downarrow,\uparrow}}{\sqrt{2}}$,
$\ket{\Phi^{\pm}}=\frac{\ket{\uparrow,\uparrow}\pm\ket{\downarrow,\downarrow}}{\sqrt{2}}$).
We can classify the initial coin states above according to the exchange
symmetry into two types, symmetric ($\ket{\Psi^{+}}$, $\ket{\Phi^{\pm}}$) and
anti-symmetric state ($\ket{\Psi^{-}}$). The symmetric state represents the
states of two bosons while the anti-symmetric state represents the state of
two fermions. Without loss of generality, we will choose the initial positions
of the walkers to be at the origin but in principle, we can choose it to be at
any point as long as they are the same.

Now, we will investigate the entanglement dynamics between the two walkers.
Each of the walkers undergoes an identical but separate discrete-time quantum
walk as is discussed in the previous section. Throughout this work, we will
use the logarithmic negativity

$\displaystyle
E(\rho)=\log_{2}\big{[}\sum_{j}(\absolutevalue{\lambda_{j}}-\lambda_{j})+1\big{]}.$
(9)

as the entanglement measure. Here $\lambda_{j}$ are the eigenvalues of the
partial transpose of the density matrix $\rho$ with respect to subsystem 1 or
subsystem 2. To start with, let us first proof the following two Theorems

######  Theorem 1.

Given a bipartite system, a completely positive map that is symmetric under
the exchange of the order of the input state cannot change the symmetric
property of the whole system.

###### Proof.

Let us define an exchange operator $\hat{P}$, which is simultaneously
Hermitian and unitary operator. Now, we apply $\hat{P}$ to the state
$\ket{a,b}$.

$\displaystyle\hat{P}\ket{a,b}=\pm\ket{b,a};\quad\hat{P}^{2}=\hat{I}$

The value $+1$ means the state is symmetric and $-1$ means the state is anti-
symmetric. We also consider a completely positive operator
$\hat{\varphi}_{ab}$, where $\hat{\varphi}_{ab}=\hat{\varphi}_{ba}$. In other
words, the way this operator works does not depend on the order of the input
states. Then

$\displaystyle\hat{P}\hat{\varphi}_{ab}\ket{\psi}_{ab}$
$\displaystyle=\hat{P}\hat{\varphi}_{ab}\hat{P}^{2}\ket{\psi}_{ab}$
$\displaystyle\hat{P}\hat{\varphi}_{ab}\ket{\psi}_{ab}$
$\displaystyle=\hat{\varphi}_{ba}\hat{P}\ket{\psi}_{ab}$
$\displaystyle(\hat{P}\hat{\varphi}_{ab}-\hat{\varphi}_{ba}\hat{P})\ket{\psi}_{ab}$
$\displaystyle=0$
$\displaystyle\big{[}\hat{P},\hat{\varphi}_{ab}\big{]}\ket{\psi}_{ab}$
$\displaystyle=0.$ (10)

∎

Therefore $\big{[}\hat{P},\hat{\varphi}_{ab}\big{]}=0$ which indicates that
the operator $\hat{\varphi}_{ab}$ do not change the symmetric property of the
system.

######  Corollary 1.

Two identical local operations cannot change the symmetric property of a
system.

###### Proof.

Let us define two local operator $\Omega_{a}$ and $\Omega_{b}$, where
$\Omega_{a}=\Omega_{b}=\Omega$ and
$\Omega_{ab}=\Omega_{a}\otimes\Omega_{b}=\Omega\otimes\Omega$. It is clear
that $\Omega_{ab}=\Omega_{ba}$, hence $\Omega_{ab}$ does not affect the
exchange symmetry of the system according to Theorem 1. ∎

######  Theorem 2.

If the initial state of a walker is pure, then the reduced density matrix of
that walker after post-selection on the corresponding coin state always has at
most rank 2.

###### Proof.

Let us consider our scenario but only on Alice’s side. Without loss of
generality, we choose Alice’s initial state to be

$\displaystyle\rho_{A}=(q_{1}\ket{\uparrow}\bra{\uparrow}+q_{2}\ket{\downarrow}\bra{\downarrow})\otimes\ket{w}\bra{w}$
(11)

where $q_{1}+q_{2}=1$ and $\ket{w}$ is the initial state of the walker. Note
that this does not mean the walker has to occupy only at one definite point
initially. A superposition of points is allowed as long as the state is pure.
Now if we run quantum walk by applying the operator $\hat{U}$ in Eq. (2),

$\displaystyle\hat{U}\ket{\uparrow}\ket{w}=\lambda_{1}\ket{\uparrow}\ket{w_{1}}+\lambda_{2}\ket{\downarrow}\ket{w_{2}}$
(12)
$\displaystyle\hat{U}\ket{\downarrow}\ket{w}=\lambda_{3}\ket{\uparrow}\ket{w_{3}}+\lambda_{4}\ket{\downarrow}\ket{w_{4}}$
(13)

where $\lambda_{i}$ are probability amplitudes. Suppose we post-selected in
$\ket{\uparrow}\bra{\uparrow}$, the state becomes

$\displaystyle\rho_{A}^{\uparrow}$
$\displaystyle=\ket{\uparrow}\bra{\uparrow}\otimes\rho_{w}^{\uparrow},$ (14)

where
$\rho_{w}^{\uparrow}=\frac{|\lambda_{1}|^{2}\ket{w_{1}}\bra{w_{1}}+|\lambda_{3}|^{2}\ket{w_{3}}\bra{w_{3}}}{|\lambda_{1}|^{2}+|\lambda_{3}|^{2}}$
is the corresponding walker state. Note that $\ket{w_{1}}\bra{w_{1}}$ and
$\ket{w_{3}}\bra{w_{3}}$ are individually pure state and pure state always has
rank 1. Using the relation

$\displaystyle rank(M+N)\leq rank(M)+rank(N),$ (15)

we can conclude that

$\displaystyle rank(\rho_{w}^{\uparrow})\leq 2$ (16)

Note that this is also true if we post-select in
$\ket{\downarrow}\bra{\downarrow}$ state. In other words, the walker
effectively becomes a qubit after post-selection. ∎

###  3.1 With post-selection

Now, we will consider the post-selection case where the measurement basis is
formed by the “local” measurement operators described in Eq. (7). The reason
we are interested in post-selection is that, in many situations, post-
selection can reveal some hidden correlations between the systems which then
may be used to perform some interesting tasks that would be impossible
otherwise, for example, quantum teleportation or quantum key distribution. And
the reason we are interested in local measurement operators is that local
measurement cannot increase entanglement between the systems and in many real-
world situations is very difficult to do the non-local measurement.

Without loss of generality, we will only consider the cases where we post-
select the outcomes that are corresponding to the operators
$\hat{M}_{\uparrow\uparrow}$ and $\hat{M}_{\uparrow\downarrow}$. The reason we
can do this is because the outcome of $\hat{M}_{\downarrow\downarrow}$ will be
the same as $\hat{M}_{\uparrow\uparrow}$ and the result of
$\hat{M}_{\downarrow\uparrow}$ will be the same as
$\hat{M}_{\uparrow\downarrow}$ due to the symmetry of the setting.

####  3.1.1 Anti-symmetric Coin State (ACS)

The initial state of the system is given by

$\displaystyle\ket{\psi}_{0}=\ket{\Psi^{-}}\otimes\ket{0,0}.$ (17)

This state is anti-symmetric. We will perform the quantum walk with the
unitary operator $\hat{U}(\pi/4)$ in Eq. (6). This choice of angle is just for
the sake of convenience but the result does not actually depend on any
particular value of the chosen angle $\theta$ as long as $\hat{U}(\theta)$
satisfies Theorem 1. Now we will consider, for example, the state after the
second step of the quantum walk.

$\ket{\psi}_{2}=\frac{1}{2\sqrt{2}}\big{[}\ket{\uparrow\uparrow}(\ket{0,2}-\ket{2,0})+\ket{\uparrow\downarrow}(\ket{2,-2}+\ket{0,0})-\ket{\downarrow\uparrow}(\ket{0,0}+\ket{-2,2})+\ket{\downarrow\downarrow}(\ket{0,-2}-\ket{-2,0})\big{]}.$
(18)

We can see that the state of the system after the second step is still anti-
symmetric under the exchange of coins and walkers. This is because $\hat{U}$
acts symmetrically on both sides. In fact, with Theorem 1, it is clear that
the state $\ket{\psi}_{n}$ after any $n^{th}$ steps must be anti-symmetric.
Now let us perform measurements on the coins. After the second step, the state
of the walkers for the post-selected outcomes of $\hat{M}_{\uparrow\uparrow}$,
$\hat{M}_{\uparrow\downarrow}$, $\hat{M}_{\downarrow\uparrow}$ and
$\hat{M}_{\downarrow\downarrow}$ are

$\displaystyle\ket{\psi}_{2,w}^{\hat{M}_{\uparrow\uparrow}}$
$\displaystyle=\frac{1}{\sqrt{2}}(\ket{0,2}-\ket{2,0}),$
$\displaystyle\ket{\psi}_{2,w}^{\hat{M}_{\uparrow\downarrow}}$
$\displaystyle=\frac{1}{\sqrt{2}}\ket{\uparrow\downarrow}(\ket{2,-2}+\ket{0,0}),$
$\displaystyle\ket{\psi}_{2,w}^{\hat{M}_{\downarrow\uparrow}}$
$\displaystyle=-\frac{1}{\sqrt{2}}\ket{\downarrow\uparrow}(\ket{0,0}+\ket{-2,2}),$
$\displaystyle\ket{\psi}_{2,w}^{\hat{M}_{\downarrow\downarrow}}$
$\displaystyle=\frac{1}{\sqrt{2}}\ket{\downarrow\downarrow}(\ket{0,-2}-\ket{-2,0}).$
(19)

We can see that the states of the two walkers are anti-symmetric for
$\\{\hat{M}_{\uparrow\uparrow},\hat{M}_{\downarrow\downarrow}\\}$ because we
post-selected with the outcomes that are identical on both sides. In fact,
according to Theorem 1, the state of the two walkers must also be anti-
symmetric if the $\ket{\uparrow\uparrow}$ or $\ket{\downarrow\downarrow}$ is
post-selected after any $n^{th}$ steps. We can write the general form of an
anti-symmetric bipartite state as

$\displaystyle\ket{\xi}=\sum_{ij}\alpha^{\prime}_{ij}(\ket{a_{i},a_{j}}-\ket{a_{j},a_{i}})$
(20)

where $\\{\ket{a_{i}}\\}$ forms an orthonormal basis. With the use of Theorem
2, the reduced density matrix of a single walker in Eq. (20) can only have
rank 2 at most. In other words, the state is equivalent to a qubit. Therefore,
only one pair would remain in Eq. (20). Without loss of generality, we choose
that pair to be of the form $\frac{1}{\sqrt{2}}(\ket{a,b}-\ket{b,a})$. This
form is equivalent to $\ket{\Psi^{-}}$, which is the only state that is anti-
symmetric, and its reduced density matrix has at most rank 2. This explains
the reason why we have constant entanglement for
$\\{\hat{M}_{\uparrow\uparrow},\hat{M}_{\downarrow\downarrow}\\}$ post-
selection as shown in Fig. 1(a).

For $\\{\hat{M}_{\uparrow\downarrow},\hat{M}_{\downarrow\uparrow}\\}$ post-
selection, Theorem 2 is still satisfied. However, the walkers’ state has no
symmetry because the states of the coins being post-selected are not identical
according to Theorem 1. Therefore, the walkers’ state cannot be a Bell state
and would not have constant maximum entanglement as in the previous case. This
is shown by the plot in Fig. 1(b).

From the above analysis, the only way we can get a Bell state is when the
state of the two walkers after post-selection is anti-symmetric. To support
this claim, let us change $\hat{M}_{\uparrow\downarrow}$ and
$\hat{M}_{\downarrow\uparrow}$ in the measurement basis of Eq. (7) to
$\hat{M}_{+}=\frac{1}{2}(\ket{\uparrow\downarrow}+\ket{\downarrow\uparrow})(\bra{\uparrow\downarrow}+\bra{\downarrow\uparrow})$
and
$\hat{M}_{-}=\frac{1}{2}(\ket{\uparrow\downarrow}-\ket{\downarrow\uparrow})(\bra{\uparrow\downarrow}-\bra{\downarrow\uparrow})$
which, together with $\hat{M}_{\uparrow\uparrow}$ and
$\hat{M}_{\downarrow\downarrow}$ still forms a complete basis. Now our
measurement basis consists of non-local measurement operators $\hat{M}_{+}$
and $\hat{M}_{-}$. However, these non-local measurement operators may come
with the concern of increasing entanglement of the system and also most of the
time is very difficult task to perform in the real-world application. We may
call this new basis the triplet-singlet basis. The reason we change to this
basis is to make sure that no matter which post-selection outcome we obtain,
the state of the two walkers is always either symmetric or anti-symmetric. To
be more precise, the state of the walkers is always anti-symmetric for
$\hat{M}_{+}$ post-selection and symmetric for $\hat{M}_{-}$ post-selection.

As an illustration, we will consider the state after the second step of the
quantum walk Eq. (18), the state of the walkers for the post-selection outcome
of $\hat{M}_{+}$ and $\hat{M}_{-}$ are given by

$\displaystyle\ket{\psi}_{2,w}^{\hat{M}_{+}}$
$\displaystyle=\frac{1}{\sqrt{2}}(\ket{2,-2}-\ket{-2,2}),$
$\displaystyle\ket{\psi}_{2,w}^{\hat{M}_{-}}$
$\displaystyle=\frac{1}{\sqrt{6}}(\ket{2,-2}+2\ket{0,0}+\ket{-2,2}).$ (21)

The walkers’ state corresponding to $\hat{M}_{+}$ is anti-symmetric while
$\hat{M}_{-}$ is symmetric as expected. Figure 1(c) shows that the
entanglement dynamics is constant for $\hat{M}_{+}$ post-selection. But the
entanglement dynamics of $\hat{M}_{-}$ post-selection is oscillating as shown
in Fig. 1(d).

Figure 1:  Entanglement between two walkers for ACS case (as in Eq. (17))
using operator $\hat{U}(\pi/4)$ for different post-selection (a)
$\hat{M}_{\uparrow\uparrow}$, (b) $\hat{M}_{\uparrow\downarrow}$, (c)
$\hat{M}_{+}$ (d) $\hat{M}_{-}$.

####  3.1.2 Symmetric Coin State (SCS)

The initial state of the system which is symmetric is given by

$\displaystyle\ket{\psi}_{0}=\ket{\Psi^{+}}\otimes\ket{0,0}.$ (22)

We can use Theorem 1 to show that the state $\ket{\psi}_{n}$ after the
$n^{th}$ steps is symmetric, for instance, the state after the second step of
the quantum walk using the unitary operator $\hat{U}(\pi/4)$ is

$\ket{\psi}_{2}=\frac{1}{2\sqrt{2}}\big{[}\ket{\uparrow\uparrow}(\ket{2,2}-\ket{0,0})+\ket{\uparrow\downarrow}(\ket{2,0}+\ket{0,-2})+\ket{\downarrow\uparrow}(\ket{0,2}+\ket{-2,0})+\ket{\downarrow\downarrow}(\ket{0,0}-\ket{-2,-2})\big{]},$
(23)

which is symmetric under the exchange of both coins and walkers. Now, let us
measure the state after the second step. The walkers’ state for the post-
selected outcomes of $\hat{M}_{\uparrow\uparrow}$,
$\hat{M}_{\uparrow\downarrow}$, $\hat{M}_{\downarrow\uparrow}$ and
$\hat{M}_{\downarrow\downarrow}$ are provided by

$\displaystyle\ket{\psi}_{2,w}^{\hat{M}_{\uparrow\uparrow}}$
$\displaystyle=\frac{1}{\sqrt{2}}(\ket{2,2}-\ket{0,0}),$
$\displaystyle\ket{\psi}_{2,w}^{\hat{M}_{\uparrow\downarrow}}$
$\displaystyle=\frac{1}{\sqrt{2}}(\ket{2,0}+\ket{0,-2}),$
$\displaystyle\ket{\psi}_{2,w}^{\hat{M}_{\downarrow\uparrow}}$
$\displaystyle=\frac{1}{2}(\ket{0,2}+\ket{-2,0})\;,$
$\displaystyle\ket{\psi}_{2,w}^{\hat{M}_{\downarrow\downarrow}}$
$\displaystyle=\frac{1}{\sqrt{2}}(\ket{0,0}-\ket{-2,-2}).$ (24)

It can be seen that if we post-select with the symmetric measurement operators
$\\{\hat{M}_{\uparrow\uparrow},\hat{M}_{\downarrow\downarrow}\\}$, the state
of the two walkers is symmetric under the exchange. In fact, according to
Theorem 1, the state of the walkers after any $n^{th}$ step is symmetric as
long as you post-select the outcomes corresponding to these two operators. In
general, a symmetric bipartite state is of the form

$\displaystyle\ket{\xi}=\sum_{i\neq
j}\big{[}\frac{\alpha^{\prime}_{ij}}{2}(\ket{a_{i},a_{j}}+\ket{a_{j},a_{i}})+\beta^{\prime}_{i}\ket{a_{i},a_{i}}\big{]},$
(25)

where $\\{\ket{a_{i}}\\}$ form an orthonormal basis and
$\alpha^{\prime}_{ij}=\alpha^{\prime}_{ji}$. However, with Theorem 2, the
reduced density matrix of one walker has at most rank 2. This means at most
only one $\alpha^{\prime}_{ij}$ and two $\beta^{\prime}_{i}$ are non-zero.
Without loss of generality, Eq. (25) may be written as

$\displaystyle\ket{\xi}=\frac{\alpha^{\prime}_{ab}}{2}(\ket{a,b}+\ket{b,a})+\beta^{\prime}_{a}\ket{a,a}+\beta^{\prime}_{b}\ket{b,b}.$
(26)

In general, the state of this form would not be a Bell state except for the
following two special cases,

    * –

If $\beta^{\prime}_{a}=\beta^{\prime}_{b}=0$

The two walkers completely occupy different space. The state becomes
$\frac{1}{\sqrt{2}}(\ket{a,b}+\ket{b,a})$ which is equivalent to the Bell
state $\ket{\Psi^{+}}$.

  * –

If $\alpha^{\prime}_{ab}=0$ and
$\absolutevalue{\beta^{\prime}_{a}}=\absolutevalue{\beta^{\prime}_{b}}$ The
state becomes $\frac{1}{\sqrt{2}}(\ket{a,a}\pm\ket{b,b})$ which is equivalent
to Bell state $\ket{\Phi^{\pm}}$.

Theoretically, since there is no other constraint that will guarantee either
of the above condition is always satisfied, it is very unlikely in general
that the entanglement between the walkers will always be constant at maximum.
This is confirmed numerically as shown in Fig. 2(a) for
$\\{\hat{M}_{\uparrow\uparrow},\hat{M}_{\downarrow\downarrow}\\}$ post-
selection outcomes.

Let us now consider the other two possible post-selections that are
corresponding to the measurement operators,
$\\{\hat{M}_{\uparrow\downarrow},\hat{M}_{\downarrow\uparrow}\\}$. Similar to
the ACS cases, the state of the two walkers cannot be a Bell state and the
entanglement would not be constant as shown in Fig. 2(b).

Before proceeding further, let us elaborate that, unlike ACS, no post-
selection with respect to the measurement basis
$\\{\hat{M}_{\uparrow\uparrow},\hat{M}_{\uparrow\downarrow},\hat{M}_{\downarrow\uparrow},\hat{M}_{\downarrow\downarrow}\\}$
yields constant entanglement. In fact, this is also true for any local
measurement basis because the only way one can obtain constant entanglement is
when the reduced state of the walkers effectively become the anti-symmetric
state ($\ket{\Psi^{-}}$). However, given that the initial state of the whole
system is symmetric, this is achievable if and only if one can post-select an
anti-symmetric coin state. Since no local measurement could collapse the state
being measured into an anti-symmetric state, it is impossible for the reduced
state of the walkers to be equivalent to $\ket{\Psi^{-}}$. In a sense, anti-
symmetry really is a non-local property.

Now we will change from the computational basis to the triplet-singlet basis.
This replaces two local measurement operators
($\hat{M}_{\uparrow\downarrow},\hat{M}_{\downarrow\uparrow}$) in the previous
case with two non-local ones ($\hat{M}_{+},\hat{M}_{-}$), hence it is not
possible to post-select an anti-symmetric result. The state of the two walkers
is always symmetric for $\hat{M}_{+}$ post-selection and anti-symmetric for
$\hat{M}_{-}$ post-selection. Consider, for example, the post-selection
outcomes of $\hat{M}_{+}$ and $\hat{M}_{-}$ after the second step of the
quantum walk given as

$\ket{\psi}_{2,w}^{\hat{M}_{+}}=\frac{1}{2}\big{[}\\{(\ket{2}+\ket{-2})\otimes\ket{0}\\}+\\{\ket{0}\otimes(\ket{2}+\ket{-2})\\}\big{]}\;,\ket{\psi}_{2,w}^{\hat{M}_{-}}=\frac{1}{2}\big{[}\\{(\ket{2}-\ket{-2})\otimes\ket{0}\\}-\\{\ket{0}\otimes(\ket{2}-\ket{-2})\\}\big{]}.$
(27)

We can see that the walkers state is symmetric for $\hat{M}_{+}$ and the
entanglement dynamics is oscillating as shown in Fig. 2(c). On the other hand,
post-selection with the singlet basis $\hat{M}_{-}$ forces the state of the
walkers to be anti-symmetric. The state of the walkers become $\ket{\Psi^{-}}$
now, similar to the ACS with post-selected in triplet outcomes and the
entanglement between the two walkers is constant as shown in Fig. 2(d).

Figure 2:  Entanglement between two walkers for SCS case (as in Eq. (22))
using operator $\hat{U}(\pi/4)$ for different post-selection (a)
$\hat{M}_{\uparrow\uparrow}$, (b) $\hat{M}_{\uparrow\downarrow}$, (c)
$\hat{M}_{+}$ (d) $\hat{M}_{-}$.

Another initial state of the system which is SCS is

$\displaystyle\ket{\psi}_{0}=\ket{\Phi^{\pm}}\otimes\ket{0,0}.$ (28)

After we perform quantum walk for $n^{th}$ steps, the state $\ket{\psi}_{n}$
is also symmetric. Similar to the $\ket{\Psi^{+}}$ case above, if we post-
select with the operators
$\\{\hat{M}_{\uparrow\uparrow},\hat{M}_{\downarrow\downarrow},\hat{M}_{+}\\}$,
the state of the two walkers becomes symmetric under exchange in accordance
with Theorem 1. We observe oscillating behaviour in the entanglement dynamics
between the walkers for these post-selections. However, if we post-select with
operator $\hat{M}_{-}$, the state of the two walkers become anti-symmetric
(i.e. $\ket{\Psi^{-}}$) and the entanglement is constant.

####  3.1.3 Period of oscillation

In the cases where we have damped oscillation, even though we still do not
fully understand the mechanism behind the oscillation, we observe that the
relationship between the period per repeated pattern of the entanglement
dynamics and the angle parameter of the coins is

$\displaystyle T=n\pi/\theta$ (29)

where $n$ is the number of cycles per repeated pattern as shown Fig. 3(a) and
Fig. 3(b). We believe that this observation is a significant step toward the
fully understanding of the damping behaviour in this scenario.

Figure 3:  Entanglement between two walkers for SCS with different
$U(\theta)$, but with the same $\hat{M}_{\uparrow\uparrow}$ post-selection :
(a) $\hat{U}(\pi/6)$ : each repeated pattern contains 6 points and 1 cycle (b)
$\hat{U}(2\pi/9)$ : each repeated pattern contains 9 points and 2 cycles.

###  3.2 Without post-selection

Figure 4 shows the entanglement between the two walkers at the end of each
step of the quantum walk process, using the triplet-singlet basis, without
post-selecting the coin states. The damped oscillating behaviour of the
entanglement, showing up in part of “with post-selection" above, is still
featured in these two non-post-selecting circumstances, all with the same
period of oscillation. This is to be expected since the non-post-selecting
case is basically an average of all the post-selecting cases. Note that,
without post-selection, the hidden relation between the symmetry of the
initial coin state and the measurement result will be very obscure, especially
for the constant entanglement cases discussed above.

Figure 4: Entanglement between two walkers using $\hat{U}(\pi/4)$ for the
initial state (a) SCS (b) ACS

##  4 Conclusion

We present our analytical and numerical study of the behaviour of the spatial
entanglement between two walkers, given that: 1. The initial state of each
walker is pure, 2. Each one of them undergoes a discrete-time quantum walk
process with respect to its corresponding coin, and 3.The state of two coins
are initially bosonic (symmetric coin state: SCS) or fermionic (anti-symmetric
coin state: ACS). First, we find that the state of the individual walker after
its corresponding coin is measured and post-selected is always equivalent to a
qubit, no matter how many steps the walker has already moved. We also discover
the combined state of the two walkers is always equivalent to the singlet Bell
state $\ket{\Psi^{-}}$, again, no matter how many steps the walkers have
already moved, in the following two cases: 1. ACS where the coins are being
post-selected in one of the triplet outcomes and 2. SCS where the coins are
being post-selected in the singlet outcome. As a consequence, the spatial
entanglement between the two walkers in these two cases remain constant at the
maximum value at all steps. These results are very interesting and maybe
useful for some applications in quantum technology. It should also be noted
that, since the probability of yielding such a result for the ACS case is 3
times more than that for the SCS case, it should be more efficient to opt for
ACS if it is possible to do so. However, in some situations, we may be limited
to perform only local measurements. In such circumstances, we show that we can
still get the maximum entanglement if we post-select the state corresponding
to $\hat{M}_{\uparrow\uparrow}$ or $\hat{M}_{\downarrow\downarrow}$, but only
for the ACS case. This, again, suggests an advantage of preparing the system
with ACS over SCS. For the SCS case, the state of the two walkers after post-
selection on the local coin states is not always equivalent to any of the Bell
states and hence the entanglement is not constant. Rather, it oscillates
similar to a damped oscillator as can be seen from our numerical results. We
discover that similar damping behaviour also shows up in the non-post-
selection case of both ACS and SCS. Even though we do not yet fully understand
what is the mechanism behind this damped oscillation, we observe that the
period per repeated pattern depends on the angle parameter in the coin
operators. To be more precise, the relation between the period per repeated
pattern ($T$) and the angle parameter of the coin operators ($\theta$) is
$T=n\pi/\theta$, where $n$ is the number of cycles per pattern.

##  5 Acknowledgements

This research has received funding support from the NSRF via the Program
Management Unit for Human Resources & Institutional Development, Research and
Innovation [grant number B05F640051]. The first author was supported by the
“Petchra Pra Jom Klao Ph.D. Research Scholarship from King Mongkut’s
University of Technology Thonburi" Contract No. 14/2561. The researchers would
like to thank Dr. Ekkarat Pongophas for inspiring discussions and useful
suggestions. The researchers also acknowledge TaCS and INNOSOFT for allowing
access to their high-performance computing resources.

## References

    * Shenvi et al. [2003] Neil Shenvi, Julia Kempe, and K Birgitta Whaley.  Quantum random-walk search algorithm.  _Physical Review A_ , 67(5):052307, 2003.  doi: 10.1103/PhysRevA.67.052307.
    * Santha [2008] Miklos Santha.  Quantum walk based search algorithms.  In _International Conference on Theory and Applications of Models of Computation_ , pages 31–46. Springer, 2008.  doi: 10.1007/978-3-540-79228-4_3.
    * Lovett et al. [2010] Neil B Lovett, Sally Cooper, Matthew Everitt, Matthew Trevers, and Viv Kendon.  Universal quantum computation using the discrete-time quantum walk.  _Physical Review A_ , 81(4):042330, 2010.  doi: 10.1103/PhysRevA.81.042330.
    * Childs [2009] Andrew M Childs.  Universal computation by quantum walk.  _Physical review letters_ , 102(18):180501, 2009\.  doi: 10.1103/PhysRevLett.102.180501.
    * Kendon [2020] Viv Kendon.  How to compute using quantum walks.  In _Proceedings 9th International Conference on Quantum Simulation and Quantum Walks_ , 2020.  doi: 10.4204/EPTCS.315.1.
    * Wang et al. [2017] Yu Wang, Yun Shang, and Peng Xue.  Generalized teleportation by quantum walks.  _Quantum Information Processing_ , 16(9):1–13, 2017.  doi: 10.1007/s11128-017-1675-y.
    * Aharonov et al. [1993] Yakir Aharonov, Luiz Davidovich, and Nicim Zagury.  Quantum random walks.  _Physical Review A_ , 48(2):1687, 1993.  doi: 10.1103/PhysRevA.48.1687.
    * Dadras et al. [2018] Siamak Dadras, Alexander Gresch, Caspar Groiseau, Sandro Wimberger, and Gil S Summy.  Quantum walk in momentum space with a bose-einstein condensate.  _Physical review letters_ , 121(7):070402, 2018\.  doi: 10.1103/PhysRevLett.121.070402.
    * Chen et al. [2019] Xiu-Bo Chen, Ya-Lan Wang, Gang Xu, and Yi-Xian Yang.  Quantum network communication with a novel discrete-time quantum walk.  _IEEE Access_ , 7:13634–13642, 2019.  doi: 10.1109/ACCESS.2018.2890719.
    * Giordani et al. [2021] Taira Giordani, Luca Innocenti, Alessia Suprano, Emanuele Polino, Mauro Paternostro, Nicolò Spagnolo, Fabio Sciarrino, and Alessandro Ferraro.  Entanglement transfer, accumulation and retrieval via quantum-walk-based qubit–qudit dynamics.  _New Journal of Physics_ , 23(2):023012, 2021\.  doi: 10.1088/1367-2630/abdbe1.
    * Schmitz et al. [2009] Hector Schmitz, Robert Matjeschk, Ch Schneider, Jan Glueckert, Martin Enderlein, Thomas Huber, and Tobias Schaetz.  Quantum walk of a trapped ion in phase space.  _Physical review letters_ , 103(9):090504, 2009\.  doi: 10.1103/PhysRevLett.103.090504.
    * Zähringer et al. [2010] Franziska Zähringer, Gerhard Kirchmair, Rene Gerritsma, Eenrique Solano, Rainer Blatt, and Christian F Roos.  Realization of a quantum walk with one and two trapped ions.  _Physical review letters_ , 104(10):100503, 2010\.  doi: 10.1103/PhysRevLett.104.100503.
    * Ryan et al. [2005] Colm A Ryan, Martin Laforest, Jean-Christian Boileau, and Raymond Laflamme.  Experimental implementation of a discrete-time quantum random walk on an nmr quantum-information processor.  _Physical Review A_ , 72(6):062317, 2005.  doi: 10.1103/PhysRevA.72.062317.
    * Preiss et al. [2015] Philipp M Preiss, Ruichao Ma, M Eric Tai, Alexander Lukin, Matthew Rispoli, Philip Zupancic, Yoav Lahini, Rajibul Islam, and Markus Greiner.  Strongly correlated quantum walks in optical lattices.  _Science_ , 347(6227):1229–1233, 2015.  doi: 10.1126/science.1260364.
    * Mugel et al. [2016] Samuel Mugel, Alessio Celi, Pietro Massignan, János K Asbóth, Maciej Lewenstein, and Carlos Lobo.  Topological bound states of a quantum walk with cold atoms.  _Physical Review A_ , 94(2):023631, 2016.  doi: 10.1103/PhysRevA.94.023631.
    * Schreiber et al. [2010] Andreas Schreiber, Katiuscia N Cassemiro, V Potoček, Aurél Gábris, Peter James Mosley, Erika Andersson, Igor Jex, and Ch Silberhorn.  Photons walking the line: a quantum walk with adjustable coin operations.  _Physical review letters_ , 104(5):050502, 2010\.  doi: 10.1103/PhysRevLett.104.050502.
    * Peruzzo et al. [2010] Alberto Peruzzo, Mirko Lobino, Jonathan CF Matthews, Nobuyuki Matsuda, Alberto Politi, Konstantinos Poulios, Xiao-Qi Zhou, Yoav Lahini, Nur Ismail, Kerstin Wörhoff, et al.  Quantum walks of correlated photons.  _Science_ , 329(5998):1500–1503, 2010.  doi: 10.1126/science.1193515.
    * Flurin et al. [2017] Emmanuel Flurin, Vinay V Ramasesh, Shay Hacohen-Gourgy, Leigh S Martin, Norman Y Yao, and Irfan Siddiqi.  Observing topological invariants using quantum walks in superconducting circuits.  _Physical Review X_ , 7(3):031023, 2017.  doi: 10.1103/PhysRevX.7.031023.
    * Zhou et al. [2019] Jia-Qi Zhou, Ling Cai, Qi-Ping Su, and Chui-Ping Yang.  Protocol of a quantum walk in circuit qed.  _Physical Review A_ , 100(1):012343, 2019.  doi: 10.1103/PhysRevA.100.012343.
    * Kempe [2003] Julia Kempe.  Quantum random walks: an introductory overview.  _Contemporary Physics_ , 44(4):307–327, 2003\.  doi: 10.1080/00107151031000110776.
    * Venegas-Andraca [2012] Salvador Elías Venegas-Andraca.  Quantum walks: a comprehensive review.  _Quantum Information Processing_ , 11(5):1015–1106, 2012.  doi: 10.1007/s11128-012-0432-5.
    * Carneiro et al. [2005] Ivens Carneiro, Meng Loo, Xibai Xu, Mathieu Girerd, Viv Kendon, and Peter L Knight.  Entanglement in coined quantum walks on regular graphs.  _New Journal of Physics_ , 7(1):156, 2005.  doi: 10.1088/1367-2630/7/1/156.
    * Abal et al. [2006] G Abal, R Siri, A Romanelli, and R Donangelo.  Quantum walk on the line: Entanglement and nonlocal initial conditions.  _Physical Review A_ , 73(4):042302, 2006.  doi: 10.1103/PhysRevA.73.042302.
    * Omar et al. [2006] Y Omar, N Paunković, L Sheridan, and S Bose.  Quantum walk on a line with two entangled particles.  _Physical Review A_ , 74(4):042304, 2006.  doi: 10.1103/PhysRevA.74.042304.
    * Berry and Wang [2011] Scott D Berry and Jingbo B Wang.  Two-particle quantum walks: Entanglement and graph isomorphism testing.  _Physical Review A_ , 83(4):042317, 2011.  doi: 10.1103/PhysRevA.83.042317.
    * Carson et al. [2015] GR Carson, Thomas Loke, and Jingbo B Wang.  Entanglement dynamics of two-particle quantum walks.  _Quantum Information Processing_ , 14(9):3193–3210, 2015.  doi: 10.1007/s11128-015-1047-4.
    * Štefanák et al. [2006] M Štefanák, T Kiss, I Jex, and B Mohring.  The meeting problem in the quantum walk.  _Journal of Physics A: Mathematical and General_ , 39(48):14965, 2006.  doi: 10.1088/0305-4470/39/48/009.
    * Pathak and Agarwal [2007] PK Pathak and GS Agarwal.  Quantum random walk of two photons in separable and entangled states.  _Physical Review A_ , 75(3):032351, 2007.  doi: 10.1103/PhysRevA.75.032351.
    * Chandrashekar et al. [2012] CM Chandrashekar, Sandeep K Goyal, and Subhashish Banerjee.  Entanglement generation in spatially separated systems using quantum walk.  _Journal of Quantum Information Science_ , 2(2):15–22, 2012.  doi: 10.4236/jqis.2012.22004.
    * Singh et al. [2019] Shivani Singh, Radhakrishnan Balu, Raymond Laflamme, and CM Chandrashekar.  Accelerated quantum walk, two-particle entanglement generation and localization.  _Journal of Physics Communications_ , 3(5):055008, 2019.  doi: 10.1088/2399-6528/ab1c6e.
    * Goyal and Chandrashekar [2010] Sandeep K Goyal and CM Chandrashekar.  Spatial entanglement using a quantum walk on a many-body system.  _Journal of Physics A: Mathematical and Theoretical_ , 43(23):235303, 2010.  doi: 10.1088/1751-8113/43/23/235303.
    * Venegas-Andraca and Bose [2009] Salvador E Venegas-Andraca and Sougato Bose.  Quantum walk-based generation of entanglement between two walkers.  2009\.  URL https://arxiv.org/abs/0901.3946.
    * Allés et al. [2012] B Allés, Semra Gündüç, and Yigit Gündüç.  Maximal entanglement from quantum random walks.  _Quantum Information Processing_ , 11(1):211–227, 2012.  doi: 10.1007/s11128-011-0240-3.