# Mesosome Avoidance

Robert Cummings, Jeffrey Shallit, and Paul Staadecker
School of Computer Science
University of Waterloo
Waterloo, ON N2L 3G1
Canada
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract

We consider avoiding mesosomes—that is, words of the form $xx^{\prime}$ with
$x^{\prime}$ a conjugate of $x$ that is different from $x$—over a binary
alphabet. We give a structure theorem for mesosome-avoiding words, count how
many there are, characterize all the infinite mesosome-avoiding words, and
determine the minimal forbidden words.

##  1 Introduction

Since the early 20th century, with the work of Axel Thue [11, 12], pattern
avoidance in words has been a topic of interest. Thue proved that there exists
an infinite word over a $3$-letter alphabet having no factor (i.e., a
contiguous sub-block) of the form $xx$, where $x$ is a nonempty word. We say
that such a word avoids squares. It is easy to see that every binary word of
length $\geq 4$ has a square, so one cannot avoid squares over a $2$-letter
alphabet. Thue also proved that there exists an infinite word over a
$2$-letter alphabet avoiding overlaps, that is, factors of the form $axaxa$,
where $a$ is a single letter and $x$ is a possibly empty word.

Since Thue’s pioneering work, many similar avoidance problems have been
studied. For example, Erdős [2] posed the problem of avoiding abelian squares
in words—i.e., words of the form $xx^{\prime}$ where $x^{\prime}$ is a
permutation of $x$—and Keränen [5] showed that it is possible to avoid abelian
squares over a $4$-letter alphabet; the alphabet size is optimal. In [6], the
authors studied words avoiding $x\sigma(x)$, where $\sigma$ is a cyclic shift
of the underlying alphabet. In [7], the authors studied words avoiding
$xh(x)$, where $h$ is an arbitrary nonerasing morphism. In [8], the authors
studied words avoiding $xx^{\prime}$ where $x^{\prime}$ is “nearly” identical
to $x$. A classic problem, due independently to Justin [4], Brown and Freedman
[1, Conjecture, pp. 595–596], Pirillo and Varricchio [9], and Halbeisen and
Hungerbühler [3] and still unsolved, asks if it is possible to avoid additive
squares (words of the form $xx^{\prime}$ where $|x|=|x^{\prime}|$ and $\sum
x=\sum x^{\prime}$) over some finite subset of $\mathbb{N}$, the natural
numbers.

A natural pattern to consider is $xx^{\prime}$, where $x^{\prime}$ is a
conjugate (cyclic shift) of $x$. For example, the English words enlist and
listen are conjugates. However, since $x$ and $x^{\prime}$ are conjugate if
and only if there exist words $u,v$ with $x=uv$ and $x^{\prime}=vu$, we see
that a word contains this kind of pattern if and only if it contains a square.
Thus, it is impossible to avoid such a pattern over a binary alphabet,
although it can be avoided over a ternary alphabet.

Instead, in this note, we consider a minor variation of this pattern. We say a
finite nonempty word $w$ is a mesosome if it is of the form $xx^{\prime}$,
with $x^{\prime}$ a conjugate of $x$, and $x\not=x^{\prime}$. The word
mesosome itself is a mesosome, as some is a cyclic shift of meso. Every
squarefree word, of course, avoids mesosomes, so mesosomes can certainly be
avoided over a $3$-letter alphabet. Our goal is to consider mesosome avoidance
over a binary alphabet.

There are four principal results. First, we characterize all finite binary
words avoiding mesosomes. Second, we count how many such words there are of
length $n$, and show this number is a cubic function of $n$. Third, we
characterize all infinite binary words avoiding mesosomes. Finally, we
characterize the minimal forbidden words for mesosome-avoiding words.

##  2 Characterizing the finite mesosome-avoiding words

We define $\overline{0}=1$ and $\overline{1}=0$, and extend this to finite and
infinite words in the obvious way. Clearly a binary word $x$ has a mesosome
iff $\overline{x}$ has a mesosome. Without loss of generality, then, in our
characterization we can restrict our attention to nonempty words that begin
with $0$. We make this assumption in what follows.

The basic idea is to classify mesosome-avoiding words starting with $0$ by the
number of runs they contain. A run is a maximal block of contiguous identical
symbols. With the notation $x\sim x^{\prime}$, we mean that $x$ and
$x^{\prime}$ are conjugates (possibly equal).

One run: Clearly $0^{i}$ avoids mesosomes for all $i\geq 1$.

Two runs: Clearly $0^{i}1^{j}$ avoids mesosomes for all $i,j\geq 1$.

Three runs:

######  Lemma 1.

A word of the form $0^{i}1^{j}0^{k}$ (for $i,j,k\geq 1$) avoids mesosomes iff
$j$ is odd.

###### Proof.

If $w=0^{i}1^{j}0^{k}$ is mesosome-free, then $j$ must be odd. For otherwise
$j=2r$ and $w$ contains a mesosome factor of the form $01^{r}1^{r}0$. For the
converse, suppose $j$ is odd and $w=0^{i}1^{j}0^{k}$ contains a mesosome
$xx^{\prime}$. Then $x$ must start with $0$ and end with $1$ and $x^{\prime}$
must start with $1$ and end with $0$. But then $j$ would be even, a
contradiction. ∎

Four runs:

######  Lemma 2.

The word $0^{i}1^{j}0^{k}1^{\ell}$ (for $i,j,k,\ell\geq 1$) avoids mesosomes
iff

  * (a)

$j=k=1$ or

  * (b)

$i<k$ and $j>\ell$ and $j,k$ are odd.

###### Proof.

Let us show that the strings in Cases (a) and (b) avoid mesosomes.

Case (a):  $w=0^{i}101^{\ell}$. Suppose $w$ has a mesosome. Then
$w=uxx^{\prime}v$ with $x\sim x^{\prime}$ and $x\neq x^{\prime}$. Suppose $x$
begins inside the first group of $0$’s in $w$. If it ends inside the first
group of $0$’s, then either $x^{\prime}=x$ or $x^{\prime}$ contains a $1$, a
contradiction. So $x$ contains a $1$. But then either $x=0^{s}1$, forcing
$x^{\prime}=x$, or $x=0^{s}10$, forcing $x^{\prime}$ to have no $0$’s.

So $x$ begins with the first $1$. But then there is no possible choice for
$x^{\prime}$.

So $x$ begins at a position $\geq i+2$ in $w$. But then either $x$ starts with
$0$ and $x^{\prime}$ doesn’t, or $x=1^{t}$, forcing $x^{\prime}=x$. In all
cases we get a contradiction.

Case (b): $w=0^{i}1^{j}0^{k}1^{\ell}$, with $i<k$ and $j>\ell$ and $j,k$ are
odd.

Suppose $w$ has a mesosome. Then again, $w=uxx^{\prime}v$ with $x\sim
x^{\prime}$ and $x\neq x^{\prime}$. Suppose $x$ begins inside the first group
of $0$’s in $w$. Then as in the previous case, $x$ cannot end in the first
group of $0$’s. Suppose $x$ ends inside the first group of $1$’s in $w$. Then
since $j$ is odd, $x^{\prime}$ must contain some $1$’s from the second group
of $1$’s. This means that $x^{\prime}$ has $k$ $0$’s. Since $k>i$, we see that
$x^{\prime}$ has more $0$’s than $x$ does, a contradiction. Suppose that $x$
ends after the first group of $1$’s. Then $x$ has at least $j$ $1$’s, and
$x^{\prime}$ has fewer than $j$ $1$’s, a contradiction.

So $x$ must begin within the first group of $1$’s or after. But then
$x^{\prime}$ must end in the second group of $1$’s. Since $k$ is odd and
$j>\ell$, we can apply the argument above to $\overline{w^{R}}$.

Now we show that these are the only mesosome-avoiding binary words with four
runs.

Suppose $w=0^{i}1^{j}0^{k}1^{\ell}$ with $i,j,k,\ell\geq 1$. Considering the
factor $0^{i}1^{j}0^{k}$ gives us that $j$ is odd, by Lemma 1, and considering
the factor $1^{j}0^{k}1^{\ell}$ gives us that $k$ is odd, also by Lemma 1.

There are four cases to consider:

Case 1: $i\geq k$, $j>1$: Write $w=0^{i-k}xx^{\prime}1^{\ell-1}$, with
$x=0^{k}1^{(j+1)/2}$ and $x^{\prime}=1^{(j-1)/2}0^{k}1$. Note that $x\sim
x^{\prime}$ and $x\not=x^{\prime}$, a contradiction.

Case 2: $i\geq k$, $j=1$, $k>1$: Write $w=0^{i-1}xx^{\prime}1^{\ell-1}$, with
$x=010^{(k-1)/2}$ and $x^{\prime}=0^{(k+1)/2}1$. Note that $x\sim x^{\prime}$
and $x\not=x^{\prime}$, a contradiction.

Case 3: $j\leq\ell$, $k>1$.
Case 4: $j\leq\ell$, $k=1$, $j>1$. Cases 3 and 4 are completely parallel to
Cases 1 and 2, by considering $\overline{w^{R}}$ instead of $w$. ∎

Five runs:

######  Lemma 3.

If $x$ is mesosome-free and has 5 runs, then $x=01010$.

###### Proof.

Let $x=0^{i}1^{j}0^{k}1^{\ell}0^{m}$. We can now apply Lemma 2 to the first
four and last four runs. This gives four possibilities:

Case 1: $j=k=\ell=1$. If $i\geq 2$, then $w=0^{i-2}xx^{\prime}0^{m-1}$, with
$x=001$ and $x^{\prime}=010$. So $x\sim x^{\prime}$ and $x\not=x^{\prime}$.
The case $m\geq 2$ follows analogously by considering $\overline{w^{R}}$. So
$i=m=1$. In this case $w=01010$, which has no mesosome.

Case 2: $j=k=1$ and $j<\ell$ and $k>m$. But then $k=1>m\geq 1$, a
contradiction.

Case 3: $i<k$ and $j>\ell$ and $k=\ell=1$. But then $i<k=1$, a contradiction.

Case 4: $i<k$ and $j>\ell$ and $j<\ell$ and $k>m$. But then $j>\ell$ and
$j<\ell$, a contradiction. ∎

More than $5$ runs: By applying Lemma 3 to $w$, we see that the first five
runs must be $01010$. We can then apply the same lemma to each consecutive
group of $5$ runs and conclude that $w=(01)^{n/2}$ or $w=(01)^{(n-1)/2}0$.

For the converse, we need to see that these words are mesosome-free. But this
is clear, since any factor of the form $yy^{\prime}$ with $|y|=|y^{\prime}|$
either satisfies $y=y^{\prime}$ if $|y|$ is even, or $y=\overline{y^{\prime}}$
if $|y|$ is odd. In this latter case, $y^{\prime}$ contains one more copy of
one letter than $y$ does.

Thus we have proved the following result:

######  Theorem 1.

The finite binary word $x$ is mesosome-free iff $x$ or $\overline{x}$ has one
of the following forms:

  * (a)

$0^{i}$, $i\geq 1$;

  * (b)

$0^{i}1^{j}$, $i,j\geq 1$;

  * (c)

$0^{i}1^{j}0^{k}$ for $i,j,k\geq 1$ and $j$ odd;

  * (d)

$0^{i}101^{j}$ for $i,j\geq 1$;

  * (e)

$0^{i}1^{j}0^{k}1^{\ell}$ for $i,j,k,\ell\geq 1$ and $j,k$ odd, $i<k$ and
$j>l$;

  * (f)

$(01)^{i}$ or $(01)^{i}0$ for $i\geq 1$.

##  3 Counting the mesosome-avoiding words

Based on the characterization of Section 2, we can now count the mesosome-
avoiding binary words of length $n$. The following table gives the number
$m_{n}$ of such words of length $n$ for the first few values of $n$:

$n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$m_{n}$ | 1 | 2 | 4 | 8 | 14 | 24 | 32 | 42 | 54 | 68 | 82 | 98 | 118 | 140 | 162 | 186 | 216 | 248

It is sequence A341277 in the On-Line Encyclopedia of Integer Sequences [10].

######  Theorem 2.

Let $m(n)$ denote the number of mesosome-avoiding binary words of length $n$.
Write $n=4k+i$ for $i=0,1,2,3$ and $n\geq 5$. Then

$\displaystyle m(4k)$ $\displaystyle=(4k^{3}+15k^{2}+41k-12)/3;$
$\displaystyle m(4k+1)$ $\displaystyle=(4k^{3}+18k^{2}+50k)/3;$ (1)
$\displaystyle m(4k+2)$ $\displaystyle=(4k^{3}+21k^{2}+59k+12)/3;$
$\displaystyle m(4k+3)$ $\displaystyle=(4k^{3}+24k^{2}+68k+30)/3.$

###### Proof.

In what follows we only consider the words that begin with $0$; to get the
total of all such words, as provided in the statement of the the theorem, it
is necessary to multiply the intermediate results below by $2$.

Words with one run: There is only one, namely $0^{n}$.

Words with two runs: We must count the words of the form $0^{i}1^{j}$ for
$i,j\geq 1$ and $i+j=n$. Clearly there are $n-1$ such words.

Words with three runs: We must count words of the form $0^{i}1^{j}0^{k}$ for
$i,j,k\geq 1$ and $j$ odd. Once $j$ is fixed, there are clearly $n-j-1$ such
words, so letting $j=2j^{\prime}-1$, we see that the total is

$\sum_{1\leq
j^{\prime}\leq(n-1)/2}n-2j^{\prime}=\begin{cases}n(n-2)/4,&\text{if $n$ is
even};\\\ (n-1)^{2}/4,&\text{if $n$ is odd}.\end{cases}$

Words with four runs: Here there are two cases. Either $w=0^{i}101^{j}$ for
$i,j\geq 1$, or $w=0^{i}1^{j}0^{k}1^{\ell}$ with $i,j,k,\ell\geq 1$, $i<k$,
$j>\ell$, and $j,k$ odd.

In the former case there are clearly $n-3$ such words.

To count the second case, let $f(r)$ denote the number of ways to write $r$ as
the sum $r=i+k$ with $i,k\geq 1$ and $i<k$ and $k$ odd. Then it is easy to see
that $f(r)=\lfloor r/4\rfloor$. Then the second case is clearly
$g(n)=\sum_{0\leq r\leq n}f(r)f(n-r)$. To compute $g(n)$, rewrite
$f(r)=\lfloor r/4\rfloor$ as

$r/4-3/8+(-1)^{r}/8+(1-i)i^{r}/8+(1+i)(-i)^{r}/8,$

and then sum $g$ in the standard way (or use Maple). We get

$g(n)={{n-3}\over
96}(n^{2}-6n+3(-1)^{n}/2+1/2)+{1\over{192}}((6in-18i+6(-1)^{n})(-i)^{n}+(-6in+18i+6(-1)^{n})i^{n}).$

Considering the possibilities mod 4, this gives

$\displaystyle g(4n)$ $\displaystyle=2n^{3}/3-(3/2)n^{2}+5n/6$ $\displaystyle
g(4n+1)$ $\displaystyle=2n^{3}/3-n^{2}+n/3$ $\displaystyle g(4n+2)$
$\displaystyle=2n^{3}/3-n^{2}/2-n/6$ $\displaystyle g(4n+3)$
$\displaystyle=2n^{3}/3-2n/3.$

Words with five or more runs: From Lemma 3 we see that for $n\geq 5$, there is
exactly one such word of length $n$.

Now, adding up all five cases, and multiplying by $2$, we get that the total
number $m(n)$ of mesosome-avoiding words of length $n\geq 5$ is given by Eqn.
(1).

∎

##  4 Infinite binary words avoiding mesosomes

Recall that by $x^{\omega}$, for a finite word $x$, we mean the infinite word
$xxx\cdots$.

######  Theorem 3.

Let $i,j\geq 1$. If $\bf x$ is an infinite binary mesosome-free word, then
$\bf x$ has one of the following forms (or their binary complement):

  * •

$0^{\omega}$

  * •

$0^{i}\,1^{\omega}$

  * •

$0^{i}\,1^{2j-1}\,0^{\omega}$

  * •

$0^{i}10\,1^{\omega}$

  * •

$(01)^{\omega}$

###### Proof.

First suppose that $\bf x$ is an infinite binary mesosome-free word. Let
$x_{n}$ denote the first $n$ letters of $\bf x$, for all $n\geq 1$. Note that
$x_{n}$ must be mesosome-free for all such $n$. This means that for all such
$n$, $x_{n}$ must be of the form described in Theorem 1.

Now suppose to the contrary that for some $n$, $x_{n}$ has the form
$0^{i}1^{j}0^{k}1^{\ell}$ for $j,k$ odd, $i<k$ and $j>\ell$. Then if we add
zeros at the end of $x_{n}$, we will have a word with five runs not of the
form $(01)^{i}$ or $(01)^{i}0$, and so we will have a mesosome. If we add ones
at the end of $x_{n}$, then eventually $\ell>j$ and our new word will have a
mesosome. Therefore, there is no way to add letters at the end of $x_{n}$
while ensuring that the new word is mesosome-free. Thus, $x$ must contain a
mesosome, a contradiction.

It follows that $x_{n}$ is of the form $0^{i}$, $0^{i}1^{j}$,
$0^{i}1^{2j-1}0^{\ell}$, $0^{i}101^{j}$, $(01)^{i}$, or $(01)^{i}0$ for all
$n$. It is easy to see by letting $n$ approach infinity that $x$ must be of
the required form.

Now suppose that $x$ is of the required form. Then clearly for all natural
$n$, $x_{n}$ is mesosome-free by Theorem 1, so $x$ is mesosome-free. ∎

##  5 Minimal forbidden words

A word is minimal forbidden if it is a mesosome, but no proper subword is a
mesosome. For example, the smallest minimal forbidden words are $0110$ and
$1001$. There are ten minimal forbidden words of length $6$, which are
$001010$, $010001$, $010100$, $011101$, $011110$, and their binary
complements. These are the only minimal forbidden words of length $\leq 7$.
Note that a minimal forbidden word is always of the form $xx^{\prime}$ for
$x\sim x^{\prime}$, so a minimal forbidden word always has even length.

Our first goal is to characterize the minimal forbidden words. We do this by
considering cases depending on the number of runs that the words contain.

One or two runs: All words with one or two runs are mesosome-free, so none are
minimal-forbidden.

Three runs: Let $w=0^{i}1^{j}0^{k}$ be minimal forbidden. Then $w$ is a
mesosome, so $j$ must be even by Lemma 1. Now, if $i>1$, we can write $w=0x$,
where $x=0^{i-1}1^{j}0^{k}$ is a mesosome, implying that $w$ is not minimal
forbidden. Similarly, if $k>1$, then $w$ is not minimal forbidden. Thus, we
must have $i=1=k$, and so $w=01^{n-2}0$ for even $n$.

Four runs:

######  Lemma 4.

A word of the form $0^{i}1^{j}0^{k}0^{\ell}$ is minimal forbidden iff $j$ and
$k$ are odd and either

  * (a)

$j>1$, $\ell=1$ and $i=k$ or

  * (b)

$k>1$, $i=1$ and $j=\ell$.

###### Proof.

Let $w=0^{i}1^{j}0^{k}1^{\ell}$ be minimal forbidden. Then $j$ and $k$ must be
odd, because otherwise either $01^{j}0$ or $10^{k}1$ would be a proper subword
and a mesosome. Having established that $j$ and $k$ are odd, we split into
four cases as follows:

Case 1: $j\leq\ell$ and $k\leq i$. If $j,k=1$ then $w=0^{i}101^{\ell}$ is
mesosome-free by Lemma 2, so is not minimal forbidden. Otherwise, suppose that
$j>1$. Then $\ell>1$, so we can write $w=x1^{\ell-1}$ where
$x=0^{i}1^{j}0^{k}1$ is a proper subword and (since $k\leq i$ and $j\neq 1$) a
mesosome by Lemma 2. A similar argument applied to $\overline{w^{R}}$ will
show that if $k>1$, then $w$ is still not minimal forbidden, a contradiction.

Case 2: $j>\ell$ and $k\leq i$. Note that if $x=0^{k}1^{(j+1)/2}$ and
$x^{\prime}=1^{(j-1)/2}0^{k}1$, then $xx^{\prime}$ is minimal forbidden and
$w=0^{i-k}xx^{\prime}1^{\ell-1}$. It follows that in this case, $w$ is minimal
forbidden iff $0^{i-k}$ and $1^{\ell-1}$ are empty; that is, if and only if
$i=k$ and $\ell=1$.

Case 3: $j\leq\ell$ and $k>i$. By considering $\overline{w^{R}}$, we see that
this case is symmetrical to case 2. It follows that in this case, $w$ is
minimal forbidden iff $\ell=j$ and $i=1$.

Case 4: $j>\ell$ and $k>i$. By Lemma 2, $w$ is mesosome-free, so cannot be
minimal forbidden. ∎

Five runs:

######  Lemma 5.

No word of length $n\geq 8$ of the form $0^{i}1^{j}0^{k}1^{\ell}0^{m}$ is
minimal forbidden.

###### Proof.

Suppose to the contrary that $w=0^{i}1^{j}0^{k}1^{\ell}0^{m}$ has length $\geq
8$ and is minimal forbidden. Then clearly at least one of $i$, $k$, $j$,
$\ell$, and $m$ must be greater than $1$. We split into two cases based on
this.

Case 1: $j,k,l=1$. Then $i>1$ or $m>1$. Suppose that $i>1$. Then we can write
$w=0^{i-2}xx^{\prime}0^{m-1}$, where $x=001$ and $x^{\prime}=010$. Note that
$xx^{\prime}$ is a mesosome of length $6$, and since $w$ has length $\geq 8$,
it must be that $xx^{\prime}$ is a proper subword of $w$, a contradiction. The
case where $m>1$ is symmetrical.

Case 2: at least one of $j$, $k$, and $l$ is different than one. Then as in
the proof of Lemma 3, it can be shown that either $0^{i}1^{j}0^{k}1^{\ell}$ or
$1^{j}0^{k}1^{\ell}0^{m}$ is a mesosome, implying that $w$ is not minimal
forbidden. ∎

Six runs or more: Suppose to the contrary that $w$ is minimal forbidden with
six runs or more. Then $w$ must have at least one run of length $>1$, because
otherwise $w$ would be mesosome-free by Theorem 1. Therefore, we can write
$w=uxv$, where $x$ has five runs, with one run of length $>1$. Note that $u$
and $v$ cannot both be empty, because $w$ needs to have at least six runs.
Thus, $x$ is a proper subword of $w$. Since $x$ has at least one run of length
$>1$, $x$ must also be a mesosome by Theorem 1, a contradiction. By
contradiction, we see that there are no minimal forbidden words with six runs
or more.

We have now proved the following result:

######  Theorem 4.

For $n\equiv 0$ (mod 4) and $n\geq 8$ there are $n-2$ minimal forbidden words
and they are as follows:

  * •

$0^{2i-1}1^{n-4i+1}0^{2i-1}1$ for $1\leq i\leq n/4-1$;

  * •

$0\,1^{2i-1}\,0^{n-4i+1}\,1^{2i-1}$ for $1\leq i\leq n/4-1$;

  * •

$0\,1^{n-2}\,0$,

and their binary complements.

For $n\equiv 2$ (mod 4) and $n\geq 10$ there are $n$ minimal forbidden words
and they are as follows:

  * •

$0^{2i-1}1^{n-4i+1}0^{2i-1}1$ for $1\leq i\leq(n-2)/4$;

  * •

$0\,1^{2i-1}\,0^{n-4i+1}\,1^{2i-1}$ for $1\leq i\leq(n-2)/4$;

  * •

$0\,1^{n-2}\,0$,

and their binary complements.

## References

  * [1] T. C. Brown and A. R. Freedman.  Arithmetic progressions in lacunary sets.  Rocky Mountain J. Math. 17 (1987), 587–596.
  * [2] P. Erdős.  Some unsolved problems.  Magyar Tud. Akad. Mat. Kutató Int. Közl. 6 (1961), 221–254.
  * [3] L. Halbeisen and N. Hungerbühler.  An application of Van der Waerden’s theorem in additive number theory.  INTEGERS—Elect. J. Combin. Number Theory 0 (2000), #A7.  http://www.integers-ejcnt.org/vol0.html.
  * [4] J. Justin.  Généralisation du théorème de van der Waerden sur les semi-groupes répétitifs.  J. Combin. Theory. Ser. A 12 (1972), 357–367.
  * [5] V. Keränen.  Abelian squares are avoidable on 4 letters.  In W. Kuich, editor, Proc. 19th Int’l Conf. on Automata, Languages, and Programming (ICALP), Vol. 623 of Lecture Notes in Computer Science, pp. 41–52. Springer-Verlag, 1992.
  * [6] J. Loftus, J. O. Shallit, and M.-w. Wang.  New problems of pattern avoidance.  In G. Rozenberg and W. Thomas, editors, Developments in Language Theory, 1999, pp. 185–199. World Scientific, 2000.
  * [7] T. Ng, P. Ochem, N. Rampersad, and J. Shallit.  New results on pseudosquare avoidance.  In R. Mercas and D. Reidenbach, editors, WORDS 2019, Vol. 11682 of Lecture Notes in Computer Science, pp. 264–274. Springer-Verlag, 2019\.
  * [8] P. Ochem, N. Rampersad, and J. Shallit.  Avoiding approximate squares.  Internat. J. Found. Comp. Sci. 19 (2008), 633–648.
  * [9] G. Pirillo and S. Varricchio.  On uniformly repetitive semigroups.  Semigroup Forum 49 (1994), 125–129.
  * [10] N. J. A. Sloane et al.  The On-Line Encyclopedia of Integer Sequences.  Web resource available at https://oeis.org, 2021.
  * [11] A. Thue.  Über unendliche Zeichenreihen.  Norske vid. Selsk. Skr. Mat. Nat. Kl. 7 (1906), 1–22.  Reprinted in Selected Mathematical Papers of Axel Thue, T. Nagell, editor, Universitetsforlaget, Oslo, 1977, pp. 139–158.
  * [12] A. Thue.  Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen.  Norske vid. Selsk. Skr. Mat. Nat. Kl. 1 (1912), 1–67.  Reprinted in Selected Mathematical Papers of Axel Thue, T. Nagell, editor, Universitetsforlaget, Oslo, 1977, pp. 413–478.


# Implementation of CU gates and its application in a remote-controlled
quantum operation

Byungjoo Kim  These authors contributed equally Center for Quantum
Information, Korea Institute of Science and Technology (KIST), Seoul, 02792,
Korea  Institute of Physics and Applied Physics, Yonsei University, Seoul
03722, Korea  Department of Laser & Electron Beam Technologies, Korea
Institute of Machinery and Materials (KIMM), Daejeon, 34103, Korea  Seongjin
Hong  These authors contributed equally Department of Physics, Chung-Ang
University, Seoul 06974, Korea  Yong-Su Kim  Center for Quantum Information,
Korea Institute of Science and Technology (KIST), Seoul, 02792, Korea
Division of Quantum Information, KIST School, University of Science and
Technology, Seoul, 02792, Korea  Kyunghwan Oh  Institute of Physics and
Applied Physics, Yonsei University, Seoul 03722, Korea  Hyang-Tag Lim
<EMAIL_ADDRESS>Center for Quantum Information, Korea Institute of
Science and Technology (KIST), Seoul, 02792, Korea  Division of Quantum
Information, KIST School, University of Science and Technology, Seoul, 02792,
Korea

###### Abstract

Recently, remote-controlled quantum information processing has been proposed
for its applications in secure quantum processing protocols and distributed
quantum networks. For remote-controlled quantum gates, the experimental
realization of controlled unitary (CU) gates between any quantum gates is an
essential task. Here, we propose and experimentally demonstrate a scheme for
implementing CU gates between arbitrary pairs of unitary gates using the
polarization and time-bin degrees of freedom of single-photons. Then, we
experimentally implement remote-controlled single-qubit unitary gates by
controlling either the state preparation or measurement of the control qubit
with high process fidelities. We believe that the proposed remote-controlled
quantum gate model can pave the way for secure and efficient quantum
information processing.

##  I Introduction

Quantum entanglement is a key concept in quantum physics and plays an
essential role in the field of quantum information processing Einstein1935 ;
Kimble2008 ; Horodeck2009 ; Giovannetti2011 . Among its various applications,
entangled operations, such as the controlled unitary (CU) gate including the
controlled-NOT gate, are of particular significance, serving as a cornerstone
for universal quantum computing Nielsen2000 ; Knill2011 ; Barz2015 . Due to
its importance, numerous efforts have been devoted to implement CU gates in
different physical platforms including trapped ion Schmidt2003 ; Leibfried2003
, superconducting Steffen2006 ; Plantenberg2007 , atomic Mandel2007 ;
Anderlini2007 , and photonic systems Obrien2003 ; Gasparoni2004 ; Bao2007 .
One distinguishing feature of CU gates in photonic systems is their intrinsic
ability for gate teleportation, enabling the realization of nonlocal quantum
gates Wan2019 ; Chou2018 ; Huang2004 . Hence, the implementation of CU gates
in a linear optical system is essential for quantum networks, including
distributed quantum computing and the quantum internet Kimble2008 ; Simon2017
; Humphreys2018 .

Recently, remote-controlled quantum computing (RCQC) has been proposed due to
its potential for secure quantum processing, blind quantum computing Barz2012
, distributed quantum network Humphreys2018 , and distributed quantum sensing
Kim2024 ; Liu2021 . In RCQC, the client has a control qubit, while the server
has a target qubit. The tasks of the client are remotely conducted as linear
combinations of quantum gates performed by the server. These tasks are encoded
as linear coefficients of arbitrary linear combinations of quantum gates.
These linear coefficients are decomposed and encoded into a control qubit,
enabling remote control of these operations by utilizing CU gates. The proof-
of-principle experiments of RCQC were demonstrated by controlling the linear
combination of two single-qubit gates using linear optics in the polarization
basis Wang2020 ; Qiang2017 . In addition, remote control of both the quantum
state and operations on the target qubit was realized through the
implementation of controlled gates using multiple degrees of freedom of
sinlge-photons Wang2020 . In previous studies, the quantum gates acting on the
target qubit are remotely controlled by only manipulating the quantum state of
control qubit. Moreover, in most cases, controlled gates are implemented by
using maximally entangled states (Bell states) as input states or ancillary
states Obrien2003 ; Gasparoni2004 ; Pittman2003 . Recently, it has been
reported that arbitrary entangled operations can be realized based on a
coherent superposition of local operations in unbalanced interferometers, and
arbitrary entangled operations can be acted on any quantum states including
separable two-qubit states Hong2020 .

In this work, we experimentally demonstrate two-qubit controlled unitary gates
and remote-controlled quantum gates on a single-qubit using the polarization
and time-bin degrees of freedom of single-photons using unbalanced
interferometers. We implement controlled-NOT (CNOT) and controlled-S (CS)
gates with high process fidelities and then experimentally demonstrate remote-
controlled single-qubit gates that realize a linear combination of Pauli
operators. The linear coefficients of the two single-qubit unitary gates
($\alpha$ and $\beta$) acting on the target qubit are encoded either in the
quantum state or in the projection operator of the control qubit. These linear
coefficients of unitary gates can then be remotely controlled with high
process fidelities through state preparation or measurement of the control
qubit. We believe that our scheme provides a useful platform for secure
quantum processing and distributed quantum networks.

##  II Theory

Figure 1: Quantum circuit diagram for a remote-controlled single-qubit
operation $U_{RC}=\alpha U_{0}+\beta U_{1}$ by exploting controlled unitary
gates. The linear coefficients $\alpha$ and $\beta$ can be remotely controlled
by manipulating either (a) the quantum state or (b) the projection operator of
the control qubit.

A CU gate is a two-qubit gate that operates on two-qubit in a way that the
first and second qubits serve as a control and a target, respectively
Nielsen2000 . A CU gate can be represented in the matrix form
$|0\rangle\langle 0|\otimes U_{0}+|1\rangle\langle 1|\otimes U_{1}$, which
acts on two-qubit states $|\psi_{{\rm C}}\rangle|\psi_{{\rm T}}\rangle$ where
$|\psi_{{\rm C}}\rangle$ and $|\psi_{{\rm T}}\rangle$ correspond to a control
qubit and a target qubit, respectively. Here, $U_{0}$ and $U_{1}$ denote the
arbitrary single-qubit unitary gates. The CU gate allows the control qubit
$|\psi_{{\rm C}}\rangle$ to compute a unitary operation either $U_{0}$ or
$U_{1}$, which operates on the target qubit $|\psi_{{\rm T}}\rangle$. In
detail, if the state of the control qubit is $|0\rangle$ ($|1\rangle$),
unitary operator $U_{0}$ ($U_{1}$) is applied to the target qubit $|\psi_{{\rm
T}}\rangle$.

Then we consider the concept of a remote-controlled quantum gate using the CU
gates. In the quantum circuit model, the control qubit enables remote control
of the application of an operation $U_{RC}$ on the target qubit. The $U_{RC}$
can be represented in a linear combination of two single-qubit unitary gates,
i.e. $U_{RC}=\alpha U_{0}+\beta U_{1}$, where $\alpha$ and $\beta$ are complex
numbers satisfying $|\alpha|^{2}+|\beta|^{2}=1$. The linear coefficients
$\alpha$ and $\beta$ can be then encoded in a quantum state or projection
operator of the control qubit. Here, we proposed two quantum circuit models of
remote-controlled single-qubit operation by manipulating either the quantum
state or projection operator of the control qubit as shown in Fig. 1.

At first, we consider a remote-controlled quantum gate by manipulating the
quantum state of the control qubit as shown in Fig. 1(a). The initial two-
qubit state is given as $|\Psi_{CT}\rangle=|\psi_{C}\rangle|\psi_{T}\rangle$
with $|\psi_{C}\rangle=\alpha|0\rangle+\beta|1\rangle$. After performing a CU
gate, the two-qubit state is transformed to
$|\Psi_{CT}\rangle=\alpha|0_{C}\rangle
U_{0}|\psi_{T}\rangle+\beta|1_{C}\rangle U_{1}|\psi_{T}\rangle$. When the
control qubit is projected onto
$|+^{M}_{C}\rangle=(|0_{C}\rangle+|1_{C}\rangle)\sqrt{2}$, the target qubit
state collapses onto

$\langle+^{M}_{C}|\Psi_{CT}\rangle=\frac{1}{\sqrt{2}}(\alpha
U_{0}|\psi_{T}\rangle+\beta U_{1}|\psi_{T}\rangle).$ (1)

Thus, a single qubit unitary gate $U_{RC}=\alpha U_{0}+\beta U_{1}$ is acted
on the target qubit $|\psi_{T}\rangle$. Note that $\alpha$ and $\beta$ can be
remotely-controlled by adjusting the quantum state of the control qubit
$|\psi_{C}\rangle$.

On the other hand, we now consider another quantum circuit model of a remote-
controlled quantum gate by adjusting the projection operator of the control
qubit as shown in Fig. 1(b). The initial state of control qubit is fixed as
$|+_{C}\rangle$, and a CU gate is performed on the initial two-qubit state
$|\Psi_{CT}\rangle=|+_{C}\rangle|\psi_{T}\rangle$, then $|\Psi_{CT}\rangle$ is
transformed to $(|0_{C}\rangle U_{0}|\psi_{T}\rangle+|1_{C}\rangle
U_{1}|\psi_{T}\rangle)\sqrt{2}$. Then, the control qubit is projected onto the
measurement basis
$|\psi^{M}_{C}\rangle=\alpha|0_{C}\rangle+\beta|1_{C}\rangle$ and the final
state of the target qubit is collapses onto

$\langle\psi^{M}_{C}|\Psi_{CT}\rangle=\frac{1}{\sqrt{2}}(\alpha
U_{0}|\psi_{T}\rangle+\beta U_{1}|\psi_{T}\rangle).$ (2)

One can find that the same form of the remote-controlled quantum gate
$U_{RC}=\alpha U_{0}+\beta U_{1}$ is applied on target qubit
$|\psi_{T}\rangle$, see Eq. (1). In this quantum circuit, the linear
coefficients of $\alpha$ and $\beta$ also can be remotely-controlled by
adjusting the projection operator of the control qubit when the initial state
of the control qubit is fixed with $|+_{C}\rangle$.

Figure 2: Experimental setup for implementing a remote-controlled quantum
operation using a CU gate. A CU gate acting on a two-qubit polarization state
of a down-converted photon pair is realized using an unbalanced Michelson
interferometer (control) and an unbalanced Mach-Zehnder interferometer
(target). With the implemented CU gate, a remote-controlled quantum operation
on the target qubit can be demonstrated by adjusting either the initial state
or the projection operator of the control qubit.

##  III Experiment

We implement a CU gate using polarization and time-bin degrees of freedom of
sinlge-photons Hong2020 . Our proposed experimental setup is shown in Fig. 2,
which is composed of two unbalanced interferometers. We use a mode-locked Ti-
sapphire laser with a center wavelength of 780 nm, a repetition rate of 80
MHz, and a pulse width of 140 fs as a pump laser to prepare a down-converted
photon pair. The initial pump beam is converted into 390 nm at a 1-mm-thick
lithium triborate (LBO) crystal via a second harmonic generation process, and
a pair of photons are generated from a 1-mm-thick beta-barium borate (BBO)
crystal with a degenerate type-II spontaneous parametric down conversion
(SPDC) process. Then, the signal photon is incident on the unbalanced
Michelson interferometer (UMI), which is composed of a polarizing beam
splitter (PBS), while the idler photon is incident on the unbalanced Mach-
Zehnder interferometer (UMZI), which is composed of two beam splitters (BSs).
Note that the signal (idler) photon refers to the control (target) qubit in
our experiment. To actively stabilize the relative phase of the unbalanced
interferometer, we attach a piezo actuator to one mirror of each
interferometer. The path length difference of the UMI is set to 1.875 m
($\Delta L=L-S$), which is half of the pulse period of the mode-locked pump
laser while the path length difference of the UMZI is set to 3.75 m ($2\Delta
L$). Thus, the photon pairs generated from consecutive pump laser pulses are
temporally overlapped. We use an interference filter of 3 nm full-width at
half-maximum (FWHM) bandwidth, and the expected coherence length of our down-
converted photon is $200~{}\mu$m.

Let us describe how we implement a CU gate $|0\rangle\langle 0|\otimes
U_{0}+|1\rangle\langle 1|\otimes U_{1}$. The operations $|0\rangle\langle 0|$
and $|1\rangle\langle 1|$ on the control qubit can be performed by passing the
PBS in the UMI, while $U_{0}$ and $U_{1}$ on the target qubit can be realized
by placing a combination of waveplates (WPs) at the short and long path arms
of the UMZI as shown in Fig. 2, respectively. The initial polarization-encoded
two-qubit state $|\Psi_{CT}\rangle$ can be described as
$|\Psi_{CT}\rangle|t_{C}^{0}t_{T}^{0}\rangle$ considering its time-bin mode,
where $|t_{C}^{0}\rangle$ ($|t_{T}^{0}\rangle$) denotes the initial time-bin
mode of the control (target) qubit.

The process of the proposed CU gate can be described as the following
transformation:

$\displaystyle|\Psi_{CT}\rangle|t_{C}^{0}t_{T}^{0}\rangle$
$\displaystyle\xrightarrow{{\rm UMI,UMZI}}$
$\displaystyle\frac{1}{2}[(|0\rangle\langle 0|\otimes
U_{0})|\Psi_{CT}\rangle|t_{C}^{s}t_{T}^{s}\rangle+(|0\rangle\langle 0|\otimes
U_{1})|\Psi_{CT}\rangle|t_{C}^{s}t_{T}^{l}\rangle$ (3)
$\displaystyle+(|1\rangle\langle 1|\otimes
U_{0})|\Psi_{CT}\rangle|t_{C}^{l}t_{T}^{s}\rangle+(|1\rangle\langle 1|\otimes
U_{1})|\Psi_{CT}\rangle|t_{C}^{l}t_{T}^{l}\rangle]$
$\displaystyle\xrightarrow{\text{Post-selection}}$
$\displaystyle\frac{1}{2}(|0\rangle\langle 0|\otimes U_{0}+|1\rangle\langle
1|\otimes U_{1})|\Psi_{CT}\rangle,$

where $|t_{T}^{l}\rangle$ ($|t_{C}^{s}\rangle$) denotes the time-bin mode of
the target (control) qubit passing through the long (short) path. The first
line of Eq. (3) is obtained after the initial two-qubit states passing through
the first BS and PBS in unbalanced interferometers. Then, the second line of
Eq. (3) is obtained after $|t^{s}_{C}t^{s}_{T}\rangle$ and
$|t^{l}_{C}t^{l}_{T}\rangle$ terms are post-selected with a time-bin
measurement operator as $|t^{s}_{C}t^{s}_{T}\rangle\langle
t^{s}_{C}t^{s}_{T}|+|t^{l}_{C}t^{l}_{T}\rangle\langle t^{l}_{C}t^{l}_{T}|$ by
set the coincidence window smaller than the time difference between long and
short path in unbalanced interferometers Hong2020 . Finally, we can obtain the
CU gate $|0\rangle\langle 0|\otimes U_{0}+|1\rangle\langle 1|\otimes U_{1}$ as
shown in Eq. (3). We apply this proposed arbitrary CU gate to the remote-
controlled quantum gate by controlling either the state preparation or
projection operator of the control qubit.

##  IV Results

###  IV.1 Controlled-unitary gates

Figure 3: Reconstructed process matrices of the experimentally reconstructed
(a) CNOT gate and (b) CS gate. Re$(\chi)$ and Im$(\chi)$ correspond to the
real and imaginary parts of the reconstructed process matrix $\chi$,
respectively. Note that the reconstructed process matrices are represented on
Pauli basis, for example, $I$, $X$, $Y$, and $Z$ correspond to $\sigma_{{I}}$,
$\sigma_{{X}}$, $\sigma_{{Y}}$, and $\sigma_{{Z}}$, respectively.

We demonstrated CNOT and CS gates with our proposed CU gates. The CNOT gate
can be realized by setting $U_{0}=I$, $U_{1}=X$. $I$ and $X$ operations are
realized by placing nothing and a half waveplate (HWP) with an angle of
$45^{\circ}$ at the short and long paths of the UMZI, respectively. In order
to evaluate the qualities of implemented operations, we perform quantum
process tomography (QPT). Figure 3(a) shows the experimentally reconstructed
process matrix $\chi_{CNOT}$. The process fidelity of the experimental process
matrix is obtained as 0.958$\pm$0.005. In order to evaluate the process
fidelity of the realized operation, we use the formula $F(\chi_{{\rm
exp}},\chi_{{\rm ideal}})=\left[{\rm tr}(\sqrt{\sqrt{\chi_{{\rm
exp}}}\chi_{{\rm ideal}}\sqrt{\chi_{{\rm exp}}}})\right]^{2}$ where
$\chi_{{\rm ideal}}$ $(\chi_{{\rm exp}})$ denotes the process matrix of the
ideal (experimentally realized) operation Hong2020 . The standard deviation of
the process fidelity is obtained by performing the Monte-Carlo simulation 100
times. In addition, the CS gate can be realized by setting $U_{0}=I$ and
$U_{1}=S=\left(\begin{array}[]{cc}1&0\\\ 0&i\\\ \end{array}\right)$
Schmidt2003 ; Garion2021 . $I$ and $S$ operations are implemented by placing
nothing on the short path and QWP at $45^{\circ}$, HWP at $45^{\circ}$, and
another QWP at $45^{\circ}$ on the long path in UMZI, respectively. Then, the
relative phase was precisely adjusted with a piezo actuator to obtain
coincidence counts corresponding to all state preparations and measurements.
The reconstructed process matrix $\chi_{CS}$ is also shown in Fig. 3(b) with a
process fidelity of 0.950$\pm$0.004. Note that the CS gate is a key two-qubit
quantum gate used for implementing the quantum Fourier transform Nielsen2000 .
The CS gate is theoretically decomposed into the universal quantum gates of a
$T$ gate, a $T^{-1}$ gate, and two CNOT gates, respectively Mastriani2021 .

###  IV.2 Remote-controlled linear coefficients of unitary operators

Figure 4: Experimentally reconstructed process matrices of remote-controlled
unitary operations $U_{RC}=\alpha I+\beta X$ acting on the target qubit. (a)
Remote-controlled operation by manipulating the state preparation of the
control qubit when the projection operator is fixed with $|+\rangle\ $. (b)
Remote-controlled operation by manipulating the projection operator of the
control qubit when the state preparation of the control qubit is fixed with
$|+\rangle\ $. Re$(\chi)$ and Im$(\chi)$ refer to the real and imaginary parts
of the reconstructed process matrix $\chi$, respectively.

We demonstrate a remote-controlled quantum gate on the target qubit by
controlling either the state preparation or projection operator of the control
qubit by applying our proposed CU gates. First, we implement a remote-
controlled quantum gate by manipulating the quantum state of the control
qubit. The control qubit can be prepared as
$|\psi_{C}\rangle=\alpha|0_{C}\rangle+\beta|1_{C}\rangle$. Note that the
amplitudes $\alpha$ and $\beta$ are set by adjusting the angles of HWP1 and a
quarter waveplate (QWP1), and the relative phase is set by adjusting the path
length of the UMI with a piezo actuator embedded in the mirror as shown in
Fig. 2. After applying the proposed CU gates as the final form of Eq. (3), the
two-qubit quantum state becomes as $(\alpha|0_{C}\rangle
U_{0}|\psi_{T}\rangle+\beta|1_{C}\rangle U_{1}|\psi_{T}\rangle)/\sqrt{2}$.
When the control qubit is projected onto
$|+_{C}^{M}\rangle=(|0\rangle+|1\rangle)/\sqrt{2}$ with HWP2, QWP2 and PBS
after the UMI, then the quantum state collapses onto $(\alpha U_{0}+\beta
U_{1})|\psi_{T}\rangle$. Thus, a remote-controlled quantum gate, which is
performed on the target qubit of $|\psi_{T}\rangle$, can be described as
$U_{RC}=\alpha U_{0}+\beta U_{1}$. The linear coefficients of $\alpha$ and
$\beta$ can be remotely controlled by preparing a quantum state of the control
qubit $|\psi_{C}\rangle$.

We experimentally demonstrate two remote-controlled quantum gates of
$U^{S}_{RC,A}=\sqrt{2/3}I+\sqrt{1/3}X$ and
$U^{S}_{RC,B}=\sqrt{1/2}I-\sqrt{1/2}X$ as examples. $I$ and $X$ single-qubit
unitary operations are realized by placing nothing and HWP at $45^{\circ}$ in
the short and long paths in the UMZI, respectively. To implement
$U^{S}_{RC,A}$ ($U^{S}_{RC,B}$), the quantum states of controlled qubit were
manipulated by setting the angles of HWP1 and QWP1 at $30^{\circ}$ and
$0^{\circ}$ ($-22.5^{\circ}$ and $45^{\circ}$), respectively. The projection
operator $|+_{C}^{M}\rangle\langle+_{C}^{M}|$ can be performed by setting the
angles of HWP2 and QWP2 at $22.5^{\circ}$ and $45^{\circ}$, respectively. In
order to estimate the quality of the implemented remote-controlled quantum
gates, we perform QPT and the experimentally reconstruced process metrics are
shown in Fig. 4(a). The corresponding process fidelities of the reconstructed
process matrices are 0.998$\pm$0.002 and 0.974$\pm$0.005, respectively.

Then, we demonstrate a remote-controlled quantum gate by adjusting the
projection operator of the control qubit when the quantum state of the control
qubit is fixed as $|+_{C}\rangle=(|0\rangle+|1\rangle)/\sqrt{2}$. To this end,
the control qubit is fixed as $|\psi_{C}\rangle=|+_{C}\rangle$, and the
projection operator $|\psi^{M}_{C}\rangle\langle\psi^{M}_{C}|$ with
$|\psi^{M}_{C}\rangle=\alpha|0\rangle+\beta|1\rangle$ is used for a control
qubit. In this scheme, the same remote-controlled quantum operation
$U_{RM}=\alpha U_{0}+\beta U_{1}$ can be performed on the target qubit, but
the linear coefficients $\alpha$ and $\beta$ are remotely controlled by the
projection operator of the control qubit,
$|\psi^{M}_{C}\rangle\langle\psi^{M}_{C}|$. $U_{0}=I$ and $U_{1}=X$ unitary
operations are realized in the same way as the above scheme. The quantum state
of the control qubit $|\psi_{C}\rangle=|+_{C}\rangle$ is prepared by setting
HWP1 at $22.5^{\circ}$ and QWP1 at $45^{\circ}$. Then, the projection operator
of the control qubit $|\psi^{M}_{C}\rangle\langle\psi^{M}_{C}|$ can be
prepared by adjusting the angles of HWP2 and QWP2. We demonstrate the same
gates of $U^{P}_{RC,A}=\sqrt{2/3}I+\sqrt{1/3}X$ and
$U^{P}_{RC,B}=\sqrt{1/2}I-\sqrt{1/2}X$ by adjusting the angles of HWP2 and
QWP2 when the control qubit is fixed as $|\psi_{C}\rangle=|+_{C}\rangle$. The
angles of HWP2 and QWP2 are set as $30^{\circ}$ and $0^{\circ}$
($-22.5^{\circ}$ and $45^{\circ}$) to implement $U^{P}_{RC,A}$
($U^{P}_{RC,B}$), respectively. The experimentally reconstructed process
matrices of $U^{P}_{RC,A}$ and $U^{P}_{RC,B}$ are shown in Fig. 4(b). The
corresponding process fidelities of the reconstructed process matrices are
0.974$\pm$0.005 and 0.973$\pm$0.004, respectively.

Our results show that by adjusting either the state preparation or projection
operator of the control qubit, the linear coefficients of the remote-
controlled quantum gates $U_{RC}$ applied to the target qubit can be remotely
controlled as desired. In particular, it is noteworthy that the linear
coefficients of unitary gates acting on a target qubit can be changed through
measurements even after the quantum operation consistent with the theoretical
prediction in Fig. 1(b). Note that the projection operator can be postponed
even after the unitary operation has been finished. It is an intriguing
direction to study the remote-controlled unitary operations with delayed-
choice in the quantum circuits model Peruzzo2012 ; Kaiser2012 .

##  V Conclusions

We experimentally demonstrate two-qubit CU gates by exploiting polarization
and time-bin degrees of freedom in a photonic system. Furthermore, we
experimentally demonstrated a remote-controlled quantum gate model by
controlling either the quantum state of the control qubit or the projection
operator of the control qubit. Since our scheme can be extended to multi-qubit
systems, it is intriguing to apply our proposed scheme to the controlled-
controlled-unitary gate Patel2016 ; Lanyon2009 . Moreover, we can consider the
controlled non-unitary operation by replacing a single-qubit unitary operation
with a projection operator or a generalized POVM Lim2014 ; Hong2022 ; Choi2020
. Note that this controlled non-unitary operation can be used for the
entanglement filter Okamoto2009 . A remote-controlled quantum gate model can
be directly applicable to the superposition of quantum gates Procopio2015 ;
Renner2022 , reducing query complexity Araujo2014 ; Wei2016 , quantum network
Kimble2008 ; Wehner2018 , and Hamiltonian simulations Childs2012 ; Berry2015 .
This quantum circuit model can provide insights to secure remote quantum
information processing, which is useful for clients concerned about
information exposure during quantum information processing.

## References

  * (1) A. Einstein, B. Podolsky, and N. Rosen, Can quantum-mechanical description of physical reality be considered complete? Phys. Rev. 47, 777–780 (1935).
  * (2) H. J. Kimble, The quantum internet, Nature 453, 1023–1030 (2008).
  * (3) R. Horodecki, P. Horodecki, M. Horodecki, and K. Horodecki, Quantum entanglement, Rev. Mod. Phys. 81, 865–942 (2009).
  * (4) V. Giovannetti, S. Lloyd, and L. Maccone, Advances in quantum metrology, Nat. Photon. 5, 222–229 (2011).
  * (5) M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, (Cambridge: Cambridge University Press) (2000).
  * (6) E. Knill, R. Laflamme, and G. J. Milburn, A scheme for efficient quantum computation with linear optics, Nature 409, 46–52 (2001).
  * (7) S. Barz, Quantum computing with photons: introduction to the circuit model, the one-way quantum computer, and the fundamental principles of photonic experiments, J. Phys. B: At. Mol. Phys. 48, 083001 (2015).
  * (8) F. Schmidt-Kaler et al., Realization of the Cirac-Zoller controlled-NOT quantum gate,  Nature 422, 408–411 (2003).
  * (9) D. Leibfried et al., Experimental demonstration of a robust and high-fidelity geometric two ion-qubit phase gate, Nature 422, 412–415 (2003).
  * (10) M. Steffen et al., Measurement of the Entanglement of Two Superconducting Qubits via State Tomography, Science 313, 1423–1425 (2006).
  * (11) J. H. Plantenberg, P. C. de Groot, C. J. P. M. Harmans, and J. E. Mooij, Demonstration of controlled-not quantum gates on a pair of superconducting quantum bits, Nature 447, 836–839 (2007).
  * (12) O. Mandel, M. Greiner, A. Widera, T. Rom, T. W. Hänsch, and I. Bloch, Controlled collisions for multi-particle entanglement of optically trapped atoms, Nature 425, 937–940 (2003).
  * (13) M. Anderlini, P. J. Lee, B. L. Brown, J. Sebby-Strabley, W. D. Phillips, and J. V. Porto, Controlled exchange interaction between pairs of neutral atoms in an optical lattice, Nature 448, 452–456 (2007).
  * (14) J. L. O’Brien, G. J. Pryde, A. G. White, T. C. Ralph, and D. Branning, Demonstration of an all-optical quantum controlled-NOT gate, Nature 426, 264–267 (2003).
  * (15) S. Gasparoni, J.-W. Pan, P. Walther, T. Rudolph, and A. Zeilinger, Realization of a photonic controlled-NOT gate sufficient for quantum computation, Phys. Rev. Lett. 93, 020504 (2004).
  * (16) X.-H. Bao et al., Optical nondestructive controlled-not gate without using entangled photons, Phys. Rev. Lett. 98, 170502 (2007).
  * (17) Y. Wanet al., Quantum gate teleportation between separated qubits in a trapped-ion processor, Science 364, 875–878 (2019).
  * (18) K. S. Chou et al., Deterministic teleportation of a quantum gate between two logical qubits, Nature 561, 368–373 (2018).
  * (19) Y.-F. Huang, X.-F. Ren, Y.-S. Zhang, L.-M. Duan, and G.-C. Guo, Experimental Teleportation of a Quantum Controlled-NOT Gate,  Phys. Rev. Lett. 93, 240501 (2004).
  * (20) C. Simon, Towards a global quantum network, Nat. Photon. 11, 678–680 (2017).
  * (21) P. C. Humphreys et al., Deterministic delivery of remote entanglement on a quantum network, Nature 558, 268–273 (2018).
  * (22) S. Barz, E. Kashefi, A. Broadbent, J. F. Fitzsimons, A. Zeilinger, and P. Walther, Demonstration of blind quantum computing, Science 335, 303–308 (2012).
  * (23) D.-H. Kim et al., Distributed quantum sensing of multiple phases with fewer photons, Nat. Commun. 15, 266 (2024).
  * (24) L. Z. Liu et al., Distributed quantum phase estimation with entangled photons, Nat. Photon. 15, 137–142 (2021).
  * (25) D. Wang et al., Remote-controlled quantum computing by quantum entanglement, Opt. Lett. 45, 6298–6301 (2020).
  * (26) X. Qiang, X. Zhou, K. Aungskunsiri, H. Cable and J. L. O’Brien, Quantum processing by remote quantum control, Quantum Sci. Technol. 2, 045002 (2017).
  * (27) T. B. Pittman, M. J. Fitch, B. C. Jacobs, and J. D. Franson, Experimental controlled-not logic gate for single photons in the coincidence basis, Phys. Rev. A 68, 032316 (2003).
  * (28) S. Hong et al., Experimental implementation of arbitrary entangled operations, New J. Phys. 22, 093070 (2020).
  * (29) S. Garion et al., Experimental implementation of non-Clifford interleaved randomized benchmarking with a controlled-S gate, Phys. Rev. Res. 3, 013204 (2021).
  * (30) M. Mastriani, Fourier’s quantum information processing, SN Comput. Sci. 2, 122 (2021).
  * (31) A. Peruzzo, P. Shadbolt, N. Brunner, S. Popescu, and J. L. O’Brien, A quantum delayed-choice experiment, Science 338, 634–637 (2012).
  * (32) F. Kaiser, T. Coudreau, P. Milman, D. B. Ostrowsky, and S. Tanzilli, Entanglement-enabled delayed-choice experiment, Science 338, 637–640 (2012).
  * (33) R. B. Patel, J. Ho, F. Ferreyrol, T. C. Ralph, and G. J. Pryde, A quantum Fredkin gate, Sci. Adv. 2, e1501531 (2016).
  * (34) B. P. Lanyon et al., Simplifying quantum logic using higher-dimensional Hilbert spaces, Nat. Phys. 5, 134-140 (2009).
  * (35) H.-T. Lim, Y.-S. Ra, K.-H. Hong, S.-W. Lee, and Y.-H. Kim, Fundamental Bounds in Measurements for Estimating Quantum States, Phys. Rev. Lett. 113, 020504 (2014).
  * (36) S. Hong, Y.-S. Kim, Y.-W. Cho, J. Kim, S.-W. Lee, and H.-T. Lim, Demonstration of complete information trade-off in quantum measurement, Phys. Rev. Lett. 128, 050401 (2022).
  * (37) Y.-H. Choi et al., Demonstration of simultaneous quantum steering by multiple observers via sequential weak measurements, Optica 7, 675–679 (2020).
  * (38) R. Okamoto, J. L. O’Brien, H. F. Hofmann, T. Nagata, K. Sasaki, and S. Takeuchi, An entanglement filter, Science 323, 483–485 (2009).
  * (39) L. M. Procopio et al., Experimental superposition of orders of quantum gates, Nat. Commun. 6, 7913 (2015).
  * (40) M. J. Renner and C. Brukner, Computational advantage from a quantum superposition of qubit gate orders, Phys. Rev. Lett. 128, 230503 (2022).
  * (41) M. Araújo, F. Costa, and C. Brukner, Computational advantage from quantum-controlled ordering of gates, Phys. Rev. Lett. 113, 250402 (2014).
  * (42) S. J. Wei, D. Ruan, and G.-L. Long, Duality quantum algorithm efficiently simulates open quantum systems, Sci. Rep. 6, 30727 (2016).
  * (43) S. Wehner, D. Elkouss, and R. Hanson, Quantum internet: A vision for the road ahead, Science 362, eaam9288 (2018).
  * (44) A. M. Childs and N. Wiebe, Hamiltonian simulation using linear combinations of unitary operations, arXiv:1202.5822 (2012).
  * (45) D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma, Simulating Hamiltonian dynamics with a truncated taylor series, Phys. Rev. Lett. 114, 090502 (2015).