# Counterfactual universal quantum computation

Zhu Cao<EMAIL_ADDRESS>Key Laboratory of Advanced Control and
Optimization for Chemical Processes of Ministry of Education, East China
University of Science and Technology, Shanghai 200237, China  Shanghai
Institute of Intelligent Science and Technology, Tongji University, Shanghai
200092, China

###### Abstract

Universal quantum computation is usually associated with interaction among
two-level quantum subsystems, as this interaction is commonly viewed as a
necessity to achieve universal quantum computation. In this work, we show
that, contrary to this intuition, universal quantum computation can be
achieved without interaction among initially independent two-level quantum
subsystems. We call it counterfactual universal quantum computation. As
special cases, we show how to achieve counterfactual communication of quantum
states, counterfactual quantum swapping, and counterfactual quantum erasure
codes. To ease practical implementation, we analyze counterfactual universal
quantum computation with realistic devices, including the effects of finite
execution time, photon loss, and atom missing. Besides the theoretical
interest of illustrating the mysterious and counterintuitive nature of quantum
physics, our work has practical applications to color imaging of ancient arts,
upon which light is forbidden to shine.

##  I Introduction

The term “counterfactual” was first coined to describe the phenomenon of
interaction-free measurement, where an object is determined to be present or
absent without interaction with any probing particle. The first interaction-
free measurement scheme Dicke (1981); Elitzur and Vaidman (1993) had a limited
efficiency of 50% and was subsequently improved to 100% efficiency Kwiat  _et
al._ (1995) by the quantum Zeno effect Misra and Sudarshan (1977); Peres
(1980); Agarwal and Tewari (1994), an effect where a particle is frequently
weakly measured so that the state of the particle stays unchanged with a high
probability. The scheme was later extended to the scenario of quantum
cryptography Noh  _et al._ (2009); Ren  _et al._ (2011); Brida  _et al._
(2012); Liu  _et al._ (2012), quantum interrogation Kwiat  _et al._ (1999),
and entanglement distribution Elitzur and Cohen (2015); Aharonov  _et al._
(2018).

In this work we develop a counterfactual universal quantum computation (CUQC)
scheme that has the following counterfactual property: it can accomplish
universal quantum computation with no interaction among initially independent
two-level quantum subsystems throughout the computation process. This is
counterintuitive as it seems impossible for such a scheme to realize
entanglement among two-level quantum subsystems, which is a necessary
condition for universal quantum computation. In addition, so far, there has
been no scheme that can fulfill this counterfactual property. Note that the
term “counterfactual quantum computation” has had a different meaning Hosten
_et al._ (2006); Kong  _et al._ (2015), which is that the quantum computation
itself is in a superposition of “run” and “not run,” although the two-level
quantum subsystems have notable interactions. The correct outcome of the
quantum computation can be obtained with high probability even when the
quantum computation runs with negligible probability. The basic ingredient is
also the interaction-free measurement.

The CUQC scheme was motivated by the recent development of counterfactual
communication protocols, which starts with the Salih et al. protocol for
counterfactual communication of a classical bit Salih  _et al._ (2013), which
was later experimentally demonstrated Cao  _et al._ (2017). The
counterfactuality of this pioneering scheme is however debatable Vaidman
(2014); Salih  _et al._ (2014, 2018). The main opposing argument is that,
according to a stricter counterfactuality definition Vaidman (2013), the
scheme fails to be counterfactual. Recently, Aharonov and Vaidman Aharonov and
Vaidman (2019) provided another scheme for the same task which is
counterfactual even under the stricter counterfactuality definition Vaidman
(2013). Their scheme can be seen as a modification of the Salih et al. scheme,
with the difference that an additional double-sided mirror is added to the
setup.

As special cases of the CUQC scheme, we can achieve counterfactual
communication of a quantum state, counterfactual quantum swapping, and
counterfactual quantum erasure codes. In counterfactual communication of a
quantum state, a quantum state is transmitted counterfactually from one party
to another party. Note that a debatable scheme for counterfactual
communication of a quantum state was previously proposed Li  _et al._ (2015);
Vaidman (2016). The opposing argument is also that the scheme is not
counterfactual under the stricter counterfactuality definition Vaidman (2013).
Our result is counterfactual even under the stricter counterfactuality
definition Vaidman (2013), and can be seen as a quantum generalization of
Aharonov and Vaidman’s scheme Aharonov and Vaidman (2019). In counterfactual
quantum swapping, two quantum states are counterfactually swapped. This
special case recovers a recent result of Li et al. Li  _et al._ (2019). In
counterfactual quantum erasure code, a highly entangled erasure code is
prepared from separable states counterfactually. The code ensures that even if
some of the qubits are erased, the correct logical quantum state can still be
recovered through error correction.

For experimental implementations, we consider practical aspects such as finite
size and loss. In particular, we find that the fidelity of the computation
remains high under finite execution time, but the efficiency of the
computation has a notable change under finite execution time. We also find
that the fidelity and the efficiency are both sensitive to a small probability
of photon loss but insensitive to a small probability of atom missing. Here
photons and atoms are media that are utilized in our CUQC scheme. We also
discuss the dependence of the efficiency and the fidelity on the size of the
quantum computation circuit. In particular, we show in detail how the fidelity
deteriorates with an increase of the quantum circuit size if no error
correction is performed. From an orthogonal perspective, we analyze the
performance of the CUQC scheme between using a single atom and multiple atoms,
and find that multiple atoms can significantly speed up the computation
process in certain cases.

The road map for the rest of the paper is as follows. In Sec. II we review
some definitions and theorems that will be needed later in the paper. In Sec.
III we present the CUQC scheme. In Sec. IV we give three examples of the CUQC
scheme. In Sec. V we consider practical aspects of the CUQC scheme. In Sec. VI
we provide a summary and show some promising future research directions.

##  II Preliminaries

The following is the definition of universal quantum computation.

######  Definition 1 (Universal Quantum Computation Deutsch (1989)).

A universal quantum computation is an arbitrary unitary transformation on a
discrete Hilbert space spanned by the set of all quantum states of a
collection of qubits.

We will use the following important property of universal quantum computation.

######  Theorem 1 (One-qubit gates and CNOT gates are universal DiVincenzo
(1995)).

A universal quantum computation can be realized by a set of one-qubit gates
and CNOT gates.

Next is the definition of the presence of a quantum particle.

######  Definition 2 (Presence for a quantum particle Vaidman (2013)).

A quantum particle is said to be present at a point $P$ if the weak value of
the particle at $P$, measured by a weak measurement, is nonzero. Otherwise,
the particle is said to be absent at $P$.

A simple method, called two-state vector formalism, can be used to test
whether the weak value is nonzero. It can be stated as follows.

######  Theorem 2 (Two-state vector formalism Vaidman (2013)).

The weak value of a quantum particle is nonzero at a point $P$ if and only if
both the forward- and backward-evolving wave functions of the quantum particle
do not vanish at $P$.

As an example to illustrate this method and the concepts of forward- and
backward-evolving wave functions, consider the quantum optical setup in Fig.
1(a), which is essentially an interferometer. The transmission channel is
depicted as the region between two parallel blue lines. Alice is on the left
side of the channel and Bob is on the right side of the channel. Given a
source and a detector, the forward- and backward-evolving wave functions can
be defined as follows. The forward-evolving wave function is defined as the
wave function that starts with the source and is depicted by green dashed
lines. In this setup, it starts with the light source L and splits into two
paths at the first beam splitter BS1. The right path hits Bob’s shutter S. The
left path is reflected by the single-sided mirror SM1 and then splits into two
paths at BS2. The backward-evolving wave function is defined as the wave
function that starts with the detector and is depicted by red solid lines. In
the current setup, it starts with the detector T and splits into two paths at
BS2. The right path is first reflected by the single-sided mirror SM2 and then
hits Bob’s shutter S. The left path is first reflected by the single-sided
mirror SM1 and then splits into two paths at BS1. It can be seen that the
forward- and backward-evolving wave functions do not overlap in the
transmission channel, as shown in Figs. 1(c) and 1(d), indicating there is no
photon in the transmission channel.

Figure 1: Illustration of the two-state vector formalism. Consider a photon
that is emitted from a light source L and received by a detector T. The
forward-evolving (backward-evolving) wave function of this photon is depicted
by green dashed (red solid) lines. The region between two parallel blue lines
is the transmission channel. Alice (Bob) is on the left (right) of the
channel. Two cases are considered: (a) Bob has a shutter S and (b) Bob has no
shutter. (c) and (d) The forward- and backward-evolving wave functions do not
overlap. (e) and (f) The forward- and backward-evolving wave functions
overlap. Here L denotes the light source, BS1 and BS2 are beam splitters, SM1
and SM2 are single-sided mirrors, T is a single-photon detector, and S is a
shutter.

Next we examine the opposite situation, as shown in Fig. 1(b). The optical
setup is almost the same as the previous setup, except that Bob’s shutter S is
removed. The forward-evolving wave function still starts at L and splits into
two paths at BS1. The left path is the same as the previous situation. The
right path is reflected by SM2 and splits into two paths at BS2. The backward-
evolving wave function still starts at the detector T and splits into two
paths at BS2. The left path remains the same as the previous situation. The
right path is reflected by SM2 and then splits at BS1 into two paths. It can
be seen that the forward- and backward-evolving wave functions overlap in the
transmission channel, as shown in Figs. 1(e) and 1(f); hence the photon is
present in the channel.

##  III Counterfactual universal quantum computation scheme

In this section we present our CUQC scheme. We begin with the definition of
counterfactuality for universal quantum computation in Sec. III.1. Then we
build the CUQC scheme in two steps. In the first step, we design a
counterfactual special CNOT gate. The exact definition of “special” is given
in Sec. III.2. For now, we content ourselves by viewing a special CNOT gate as
a weakened version of a CNOT gate. In the second step, given in Sec. III.3, we
show how to achieve the CUQC scheme through the combination of single-qubit
operations and counterfactual special CNOT gates.

###  III.1 Definition of CUQC

A CUQC scheme has the following three properties.

  1. 1.

It can achieve universal quantum computation.

  2. 2.

Initially, the two-level quantum subsystems are independent.

  3. 3.

There is no interaction among the two-level quantum subsystems during the
quantum computation.

Figure 2: Illustration of CUQC where there is no interaction among the two-
level quantum subsystems. Each two-level quantum subsystem is confined in an
isolated chamber (pink polygon). In addition, no physical particles are
present at any point out of the chamber (white region) at any time during the
computation.

The first two conditions are quite straightforward, but the third condition
has a few subtleties. As depicted in Fig. 2, _no interaction_ in this context
means that every two-level quantum subsystem is restricted in its isolated
chamber and away from other two-level quantum subsystems. In addition, there
is no physical particle, such as a photon or a phonon, that can potentially
carry information from one two-level quantum subsystem to another two-level
quantum subsystem, present at any point outside the chambers during the
computation. The presence of a physical particle is defined by Definition 2.

###  III.2 Counterfactual special CNOT gate

In this section we design a counterfactual special CNOT gate. This CNOT gate
is special in that there is a constraint on which qubit can be the control
qubit and which qubit can be the target qubit. More precisely, only qubits
that are realized by atoms can be the control qubits and only qubits that are
realized by photons can be the target qubits. This CNOT gate is counterfactual
in that there is no interaction between the photon and the atom during this
gate operation.

Our counterfactual special CNOT gate is inspired by a recent scheme that
counterfactually communicates a classical bit Aharonov and Vaidman (2019),
which we now review. Counterfactuality here means that no particle is present
in the transmission channel during the communication under Definition 2. This
in particular implies that the probability that a photon is detected by a
photon detector in the transmission channel at any time should be zero. The
scheme consists of three ingredients.

The first ingredient is the quantum Zeno effect. It is realized by a tandem
interferometer with $M$ beam splitters (BSs) of reflectivity
$\cos^{2}(\pi/2M)$, as shown in Fig. 3(a). The transmission channel cuts the
interferometer into two halves. Alice is on the left side and Bob is on the
right side. Bob aims to communicate a classical bit to Alice. All beam
splitters are on Alice’s side. Bob has a switch SW to determine whether the
upper arms of the cycles in the tandem interferometer are blocked. Alice’s two
detectors D0 and D1 are placed after the last BS. Initially, a photon comes
from the upper left side of the first BS, as the arrow in Fig. 3(a) shows. If
the upper arms of the tandem interferometer are blocked, for each cycle only
the reflected component [with proportion $\cos^{2}(\pi/2M)$ according to the
property of the BS] survives to the next cycle, and hence the photon goes to
detector D0 with probability

$\textsf{Prob}(\textrm{D}_{0})=(\cos^{2}(\frac{\pi}{2M}))^{M}\approx(1-(\frac{\pi}{2M})^{2}/2)^{2M}\approx
e^{-\pi^{2}/4M}.$ (1)

When $M$ goes to infinity, this probability goes to 1. Consequently, D0 always
clicks while D1 never clicks. If the upper arms are not blocked, the
probability that the photon goes across the transmission channel is
$\sin^{2}(i\pi/2M)$ for the $i$th cycle, and hence the photon goes to detector
D1 with probability

$\textsf{Prob}(\textrm{D}_{1})=\sin^{2}(\frac{M\pi}{2M})=1.$ (2)

Hence, the block status of the upper arms (block or pass), a classical bit of
Bob, is transmitted to the click status of the detectors (D0 clicks or D1
clicks), a classical bit of Alice. If this communication is also
counterfactual, then Bob’s goal is achieved. However, when the upper arms are
not blocked, it can be shown that for the last cycle, the probability of the
photon to be detected in the transmission channel is
$\sin^{2}[(M-1)\pi/2M]\approx 1$ for large $M$. Hence, the communication is
unfortunately not counterfactual.

Figure 3: (a) Quantum Zeno effect. For large $M$, if the upper arms are
blocked (unblocked), the photon always goes to D0 (D1). (b) Chained quantum
Zeno effect. The photon has zero probability to be detected in the
transmission channel for both the block and unblock cases. (c) A double-sided
mirror is added to eliminate the presence of the photon in the transmission
channel. Here BS denotes a beam splitter, SM is a single-sided mirror, DM is a
double-sided mirror, D0 and D1 are single-photon detectors, and SW is Bob’s
switch.

To avoid a nonzero probability of photon detection in the transmission
channel, the second ingredient, the chained quantum Zeno effect, is
introduced. It is realized by nesting a tandem interferometer inside each
cycle of the outer tandem interferometer (_outer cycle_ for short), as shown
in Fig. 3(b). Each nested inner tandem interferometer consists of $N$ beam
splitters with reflectivity $\cos^{2}(\pi/2N)$. Again, we assume $N$ goes to
infinity. If the upper arms of all cycles of an inner tandem interferometer
(_inner cycles_ for short) are blocked (unblocked), the photon goes to the
left (right) of the last BS of the inner tandem interferometer, which is
equivalent to a pass (block) status of an outer cycle, and hence D1 (D0) will
click. The overall effect is that the block status of the inner cycles (block
or pass) corresponds to the click status of the detectors (D1 clicks or D0
clicks) and therefore a classical bit is communicated from Bob to Alice. For
the block case, the probability of photon detection in the transmission
channel is bounded by $\sin^{2}(\pi/2N)$, and for the non-block case, it is
bounded by $\sin^{2}(\pi/2M)$. Therefore, the probabilities of the photon
passing through the channel for both the block case and the nonblock case go
to zero as $M$ and $N$ go to infinity. However, for the nonblock case, the
photon is still present in the transmission channel and hence
counterfactuality is not achieved. This can be seen through Fig. 4(a), which
depicts one outer cycle, in which the forward- and backward-evolving wave
functions overlap in the transmission channel, indicating that the photon is
present.

The critical idea of Ref. Aharonov and Vaidman (2019) is the third ingredient,
which joins two old outer cycles by a double-sided mirror to form a new outer
cycle, as shown in Fig. 3(c). A new outer cycle now contains $2(N-1)$ inner
cycles and there are in total $M-1$ new outer cycles. Note that this new setup
still maintains the property that the block status of the inner cycles (block
or pass) corresponds to the click status of the detectors (D1 clicks or D0
clicks). It remains to be shown that counterfactuality holds for both the
block case and the pass case. The forward- and backward-evolving wave
functions of one outer cycle are shown in Figs. 4(b) and (c). In Fig. 4(b),
the upper arms are not blocked, while in Fig. 4(c), the upper arms are
blocked. It can be seen that for both cases, the forward- and backward-
evolving wave functions do not overlap in the transmission channel, so the
photon is not present by Theorem 2. Hence, this scheme achieves counterfactual
communication of a classical bit.

Figure 4: Forward- and backward-evolving wave functions of one outer cycle (a)
without Bob’s shutter or a double mirror, (b) without Bob’s shutter but with a
double mirror, and (c) with both Bob’s shutter and a double mirror. The
forward-evolving wave function is represented by green dashed lines and the
backward-evolving wave function is shown by red solid lines. Here SM denotes a
single-sided mirror and DM a double-sided mirror.

Our counterfactual special CNOT gate modifies the above scheme in two aspects.
The first modification replaces Bob’s classical switch with a quantum switch.
The quantum switch can be realized by an atom that contains three energy
levels ${\left|{e}\right\rangle}$, ${\left|{g}\right\rangle}$, and
${\left|{s}\right\rangle}$ Li  _et al._ (2015), as shown in the right panel of
Fig. 5(a). When the atom is in the ground state ${\left|{g}\right\rangle}$, it
absorbs any passing photon, changes its state to the second excited state
${\left|{s}\right\rangle}$, and stays there. When the atom is in the first
excited state ${\left|{e}\right\rangle}$, it is unable to absorb photons.
Hence, the ground state ${\left|{g}\right\rangle}$ acts as the block status
and the first excited state ${\left|{e}\right\rangle}$ acts as the pass
status. The second modification replaces the beam splitters by polarization
beam splitters and uses the polarization encoding for the photons. The
horizontal polarization ${\left|{H}\right\rangle}$ and the vertical
polarization ${\left|{V}\right\rangle}$ stand for logical
${\left|{0}\right\rangle}$ and logical ${\left|{1}\right\rangle}$,
respectively.

Figure 5: (a) Optical setup of a counterfactual special CNOT gate (the
detailed protocol is explained in the text): D, single-photon detector; SM,
switchable mirror; SPR, switchable polarization rotator; MR, mirror; OD,
optical delay; PBS, polarizing beam splitter; QSW, quantum switch; and
${\left|{g}\right\rangle}$, ${\left|{e}\right\rangle}$, and
${\left|{s}\right\rangle}$, quantum states of an atom qubit. (b) On-off states
of switchable components. Here 0 denotes the off state and 1 denotes the on
state.

The complete setup is shown in Fig. 5(a). Initially, all switchable components
are turned off. A switchable component becomes a normal component when it is
in the on state and disappears when it is in the off state. After an input
photon with polarization ${\left|{H}\right\rangle}$ passes a switchable mirror
SM1, SM1 is turned on for $M-1$ outer cycles.

At the start of each outer cycle, a switchable polarization rotator SPR1 is
turned on, which rotates the polarization of the photon with an angle
$\beta_{1}=\pi/2M$. Here a rotation with an angle $\beta_{1}$ means that the
quantum state of the photon evolves as

$\left(\begin{array}[]{c}X\\\ Y\\\
\end{array}\right)\rightarrow\left(\begin{array}[]{cc}\cos\beta_{1}&\sin\beta_{1}\\\
-\sin\beta_{1}&\cos\beta_{1}\\\ \end{array}\right)\left(\begin{array}[]{c}X\\\
Y\\\ \end{array}\right)\equiv\left(\begin{array}[]{c}X^{\prime}\\\
Y^{\prime}\\\ \end{array}\right),$ (3)

where $(X,Y)^{T}$ denotes the quantum state
$X{\left|{H}\right\rangle}+Y{\left|{V}\right\rangle}$. Then SPR1 is turned off
and remains off for the rest of this outer cycle. The photon then splits into
two components by a polarization beam splitter PBS1, of which the vertical
component passes a switchable mirror SM2 and the horizontal component is
reflected by a mirror MR1. An optical delay OD1 is put on the horizontal
component so that both components return to PBS1 at the same time. The
switchable mirror SM2 is turned on for $N-1$ inner cycles. At the start of
each inner cycle, a switchable polarization rotator SPR2 is turned on, rotates
the polarization of the photon by an angle of $\beta_{2}=\pi/2N$, and is then
turned off. The photon then splits into two components at a polarization beam
splitter PBS2, of which the horizontal component passes the transmission
channel and the vertical component is reflected by a mirror MR2. An optical
delay OD2 is put on the vertical component so that both components return to
PBS2 at the same time. After passing the transmission channel, the photon is
either blocked by Bob’s atom or reflected by a mirror MRB. After $N-1$ inner
cycles, SM2 is turned off to allow the photon to exit the inner cycle. The
switchable mirror SM1 then reflects the photon, with SPR1 remaining off this
time so that no polarization rotation is applied to the photon, mimicking the
function of a double mirror. After another $N-1$ inner cycles, one outer cycle
is finished.

After $M-1$ such outer cycles, SM1 is turned off so that the output photon
passes $SM_{1}$. Figure 5(b) summarizes the on-off states of SM1, SM2, SPR1,
and SPR2. It is easy to show that this optical setup is equivalent to Fig. 6,
which, compared to Fig. 3(c), replaces each biased BS by a polarization beam
splitter (PBS) together with two polarization rotators (PRs) and each
classical switch is replaced by a quantum switch.

Figure 6: Equivalent optical setup of a counterfactual special CNOT gate: SM,
single-sided mirror; DM, double-sided mirror; PBS, polarization beam splitter;
PR, polarization rotator; and QSW, quantum switch.

Suppose the quantum switch is initially in the pure state
$C_{g}{\left|{g}\right\rangle}+C_{e}{\left|{e}\right\rangle}$, and hence the
overall initial state is
${\left|{\psi_{0}}\right\rangle}={\left|{H}\right\rangle}(C_{g}{\left|{g}\right\rangle}+C_{e}{\left|{e}\right\rangle}$).
After the first PBS, the overall state becomes

${\left|{\psi_{1}}\right\rangle}=(\cos\beta_{1}{\left|{H}\right\rangle}+\sin\beta_{1}{\left|{V}\right\rangle})(C_{g}{\left|{g}\right\rangle}+C_{e}{\left|{e}\right\rangle}).$
(4)

At the end of the first outer cycle but before the second PBS and its two
preceding PRs, the overall state conditioned on the photon not being absorbed
by Bob’s atom becomes

${\left|{\psi_{1}^{\prime}}\right\rangle}=C_{g}(\cos\beta_{1}{\left|{H}\right\rangle}+\sin\beta_{1}\cos^{2N}\beta_{2}{\left|{V}\right\rangle}){\left|{g}\right\rangle}+C_{e}\cos\beta_{1}{\left|{H}\right\rangle}{\left|{e}\right\rangle}.$
(5)

When $N$ goes to infinity, we have $\cos^{2N}\beta_{2}=1$, and hence the
overall state can be simplified to
$C_{g}(\cos\beta_{1}{\left|{H}\right\rangle}+\sin\beta_{1}{\left|{V}\right\rangle}){\left|{g}\right\rangle}+C_{e}\cos\beta_{1}{\left|{H}\right\rangle}{\left|{e}\right\rangle}$.
After the second PBS, the overall state becomes

$\displaystyle{\left|{\psi_{2}}\right\rangle}$ $\displaystyle=$ $\displaystyle
C_{g}[\cos(2\beta_{1}){\left|{H}\right\rangle}+\sin(2\beta_{1}){\left|{V}\right\rangle}]{\left|{g}\right\rangle}$
(6)
$\displaystyle+C_{e}(\cos^{2}\beta_{1}{\left|{H}\right\rangle}+\cos\beta_{1}\sin\beta_{1}{\left|{V}\right\rangle}){\left|{e}\right\rangle}.$

After the $M$th PBS, the overall state becomes

$\displaystyle{\left|{\psi_{M}}\right\rangle}$ $\displaystyle=$ $\displaystyle
C_{g}[\cos(M\beta_{1}){\left|{H}\right\rangle}+\sin(M\beta_{1}){\left|{V}\right\rangle}]{\left|{g}\right\rangle}$
(7)
$\displaystyle+C_{e}(\cos^{M}\beta_{1}{\left|{H}\right\rangle}+\cos^{M-1}\beta_{1}\sin\beta_{1}{\left|{V}\right\rangle}){\left|{e}\right\rangle}.$

When $M$ goes to infinity, the state can be simplified to
$C_{g}{\left|{V}\right\rangle}{\left|{g}\right\rangle}+C_{e}{\left|{H}\right\rangle}{\left|{e}\right\rangle}$.
Note that since ${\left|{g}\right\rangle}$ flips the photon state and
${\left|{e}\right\rangle}$ keeps the photon state unchanged, we view
${\left|{g}\right\rangle}$ as logical ${\left|{1}\right\rangle}$ and
${\left|{e}\right\rangle}$ as logical ${\left|{0}\right\rangle}$. In summary,
a counterfactual special CNOT gate performs a quantum transformation

$\mathcal{P}:(C_{g}{\left|{g}\right\rangle}+C_{e}{\left|{e}\right\rangle}){\left|{H}\right\rangle}\rightarrow
C_{g}{\left|{g}\right\rangle}{\left|{V}\right\rangle}+C_{e}{\left|{e}\right\rangle}{\left|{H}\right\rangle}.$
(8)

During this transformation $\mathcal{P}$, there is no interaction between the
atom and the photon. The proof is as follows. First we note that the forward-
and backward-evolving wave functions of $\mathcal{P}$ are in a superposition
of the ones in Figs. 4(b) and 4(c). In addition, the forward- and backward-
evolving wave functions in Figs. 4(b) and 4(c) do not overlap in the
transmission channel. Hence, the forward- and backward-evolving wave functions
of $\mathcal{P}$ also do not overlap in the transmission channel. This implies
that the photon is not present in the channel, and hence there is no
interaction between the atom and the photon.

###  III.3 Reduction from a special CNOT gate to a generic CNOT gate

In this section we provide a CUQC scheme based on counterfactual special CNOT
gates. Here we restrict our attention to using one atom qubit and multiple
photon qubits. In Sec. V we will discuss the case of multiple atom qubits.

By Theorem 1, single-qubit operations and CNOT gates suffice for universal
quantum computation. Here the single-qubit operations are local and do not
involve interaction among two-level quantum subsystems. A normal CNOT gate,
however, requires two quantum subsystems to interact. One quantum subsystem
acts as the control qubit and the other acts as the target qubit. The control
qubit controls the target qubit. In addition, a normal CNOT gate can be
performed on any two qubits and the control qubit can be either of the two
qubits. However, a counterfactual special CNOT gate can only be between the
atom qubit and the photon qubit, where the atom qubit must be the control
qubit.

We show here that by several suitable transformations, any circuits with
normal CNOT gates can be transformed to an equivalent circuit with
counterfactual special CNOT gates where the control qubits are all atom qubits
and the target qubits are all photon qubits. There are three steps. In the
first step, we show that the control qubit and the target qubit can be
switched by adding four Hadamard gates. The transformation is illustrated by

$\textstyle{H}$$\textstyle{\bullet}$$\textstyle{H}$$\textstyle{=}$$\textstyle{\bullet}$$\textstyle{H}$
$\textstyle{H}$ (9)

In the second step, we show that if neither the control qubit nor the target
qubit is the atom qubit, we can transform the control qubit to the atom qubit
as follows (assume the top line is the atom qubit):

$\textstyle{{\left|{0}\right\rangle}}$$\textstyle{{\left|{0}\right\rangle}}$
$\textstyle{\bullet}$
$\textstyle{\bullet}$$\textstyle{=}$$\textstyle{\bullet}$$\textstyle{\bullet}$
(10)

The first CNOT gate and the third CNOT gate can be further transformed such
that the control qubit is switched to the first qubit.

In the third step, to ensure that the atom qubit always stays at the initial
state ${\left|{0}\right\rangle}$, we can add the atom qubit as an additional
qubit to the original circuit. Each time a CNOT gate needs to be performed,
the atom qubit goes through the second transformation (10) and returns to
${\left|{0}\right\rangle}$ at the end of the transformation, as shown by

$\textstyle{{\left|{0}\right\rangle}}$$\textstyle{{\left|{0}\right\rangle}}$
$\textstyle{\bullet}$
$\textstyle{{\left|{0}\right\rangle}}$$\textstyle{\bullet}$$\textstyle{\longrightarrow}$$\textstyle{\bullet}$$\textstyle{\longrightarrow}$$\textstyle{\bullet}$$\textstyle{\bullet}$
(11)

By these transformations, the control qubits of all CNOT gates can be
concentrated to one qubit. Implementing this qubit with an atom qubit and all
other qubits with photons and changing all CNOT gates to counterfactual
special CNOT gates, universal quantum computation can be realized by single-
qubit operations and counterfactual special CNOT gates. Since both single-
qubit operations and counterfactual special CNOT gates require no interaction
among two-level quantum subsystems, a CUQC scheme is achieved.

##  IV Examples

In this section we illustrate the power of the CUQC scheme through three
examples. All can be viewed as special cases of our CUQC scheme and may be of
independent interest. After presenting each example, we will partially
demonstrate it on the IBM Q platform ibm , which contains some small-scale
superconducting quantum computers. Note that a full demonstration is left as
future work and additionally requires faithful implementation of
counterfactual special CNOT gates. The IBM Q platform provides several
processor options, from which we choose ibmqx5 for our demonstration purpose.
The option ibmqx5 features a quantum computer with 16 qubits. The connectivity
of these 16 qubits is shown in Fig. 7. The symbol $a\rightarrow b$ means that
$a$ is the control qubit and $b$ is the target qubit. The quantum circuit
given by the user is compiled by the IBM Q compiler so that the circuit can be
simulated on IBM’s quantum computer.

Figure 7: Connectivity diagram of ibmqx5. Here $Q_{0},Q_{1},\cdots,Q_{15}$
denote the 16 qubits in ibmqx5. An arrow between two qubits shows that these
two qubits have control relations. The direction of each arrow is from the
control qubit to the target qubit.

###  IV.1 Example 1: Genuine counterfactual communication of a quantum state

In the first example, we present the protocol of genuine counterfactual
communication of a quantum state.

We start with counterfactually communicating a pure qubit. By applying the
counterfactual CNOT gate twice, together with some local operations, the
quantum state is transferred from the atom to the photon. The detailed quantum
circuit design is shown as follows:

$\centering\mathcal{C}=\lx@xy@svg{\hbox{\raise 0.0pt\hbox{\kern
0.0pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\kern
0.0pt\offinterlineskip\halign{\entry@#!@&&\entry@@#!@\cr&&&&&&\\\&&&&&&\crcr}}}\ignorespaces{\hbox{\kern
0.0pt\raise 0.0pt\hbox{\hbox{\kern-3.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern 17.87775pt\raise
0.0pt\hbox{\hbox{\kern-1.27777pt\raise-2.47217pt\hbox{$\textstyle{\bullet}$}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
38.19995pt\raise 0.0pt\hbox{\hbox{\kern
3.00003pt\raise-3.41666pt\hbox{$\textstyle{H}$}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
71.20273pt\raise
0.0pt\hbox{\hbox{\kern-1.27777pt\raise-2.47217pt\hbox{$\textstyle{\bullet}$}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
91.52493pt\raise 0.0pt\hbox{\hbox{\kern
3.00003pt\raise-3.41666pt\hbox{$\textstyle{H}$}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
121.64998pt\raise 0.0pt\hbox{\hbox{\kern-3.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise
0.0pt\hbox{$\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
136.65pt\raise 0.0pt\hbox{\hbox{\kern-3.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern
0.0pt\raise-40.51671pt\hbox{\hbox{\kern-3.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern
15.00002pt\raise-40.51671pt\hbox{\hbox{\kern 0.10002pt\raise
0.0pt\hbox{$\textstyle{\lx@xy@svgnested{\hbox{\raise 0.0pt\hbox{\kern
3.99994pt\hbox{\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx<EMAIL_ADDRESS>0.0pt\hbox{\hbox{\kern 0.0pt\raise-13.99997pt\hbox{\hbox{\vbox{\vskip
3.99994pt\hbox to7.99988pt{\hfill\lx@xy@buildcircle@\hfill}\vskip
3.99994pt}}}}}}}}}}}}$}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
38.19995pt\raise-40.51671pt\hbox{\hbox{\kern
3.00003pt\raise-3.41666pt\hbox{$\textstyle{H}$}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
68.325pt\raise-40.51671pt\hbox{\hbox{\kern 0.10002pt\raise
0.0pt\hbox{$\textstyle{\lx@xy@svgnested{\hbox{\raise 0.0pt\hbox{\kern
3.99994pt\hbox{\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx<EMAIL_ADDRESS>0.0pt\hbox{\hbox{\kern 0.0pt\raise-13.99997pt\hbox{\hbox{\vbox{\vskip
3.99994pt\hbox to7.99988pt{\hfill\lx@xy@buildcircle@\hfill}\vskip
3.99994pt}}}}}}}}}}}}$}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
91.52493pt\raise-40.51671pt\hbox{\hbox{\kern
3.00003pt\raise-3.41666pt\hbox{$\textstyle{H}$}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
121.64998pt\raise-40.51671pt\hbox{\hbox{\kern-3.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
136.65pt\raise-40.51671pt\hbox{\hbox{\kern-3.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise
0.0pt\hbox{$\textstyle{}$}}}}}}}\ignorespaces}}}}\ignorespaces\@add@centering$
(12)

Here, we note that although the goal of counterfactual communication of a
quantum state is similar to that of quantum teleportation, in that a quantum
state is transferred from one party to another, the two subjects also differ
in several important ways. First, in quantum teleportation, it is necessary
that the two parties share a Bell state for each qubit to be teleported, while
there is no such restriction in counterfactual communication of a quantum
state. Second, in quantum teleportation, the two parties need to perform
classical communication for a successful teleportation, while in our example,
such classical communication is not needed. Therefore, we avoid calling our
protocol counterfactual quantum teleportation to emphasize the difference. In
the Appendix, we extend our protocol to counterfactual communication of mixed
qubits and higher-dimensional quantum states.

We then partially demonstrate the protocol on the IBM Q platform. For
simplicity, we test the following quantum circuit, where we make the
assumption that this circuit is compiled into the circuit $\mathcal{C}$ in Eq.
(12) and the CNOT gates in this circuit are realized by counterfactual special
CNOT gates:

$\textstyle{\bullet}$ $\textstyle{\bullet}$

After inputting the states ${\left|{00}\right\rangle}$ and
${\left|{10}\right\rangle}$, the returned results of ibmqx5 are
${\left|{00}\right\rangle}$ and ${\left|{01}\right\rangle}$. This shows that
the first qubit is counterfactually communicated to the second qubit. This
example can enable grayscale imaging, by taking Bob’s state to be a mixed
quantum state.

###  IV.2 Example 2: Quantum swapping

In the second example, we consider quantum swapping, which transforms
${\left|{x}\right\rangle}{\left|{y}\right\rangle}$ to
${\left|{y}\right\rangle}{\left|{x}\right\rangle}$. We design the quantum swap
gate as follows:

$\textstyle{\bullet}$ $\textstyle{\bullet}$ $\textstyle{\bullet}$

Recall that by the definition of the quantum swap gate, it keeps
${\left|{00}\right\rangle}$ and ${\left|{11}\right\rangle}$ unchanged, and
swaps ${\left|{01}\right\rangle}$ and ${\left|{10}\right\rangle}$. After going
through the three CNOT gates shown above, the four states become

$\displaystyle{\left|{00}\right\rangle}\rightarrow{\left|{00}\right\rangle}\rightarrow{\left|{00}\right\rangle}\rightarrow{\left|{00}\right\rangle},$
$\displaystyle{\left|{01}\right\rangle}\rightarrow{\left|{11}\right\rangle}\rightarrow{\left|{10}\right\rangle}\rightarrow{\left|{10}\right\rangle},$
$\displaystyle{\left|{10}\right\rangle}\rightarrow{\left|{10}\right\rangle}\rightarrow{\left|{11}\right\rangle}\rightarrow{\left|{01}\right\rangle},$
(13)
$\displaystyle{\left|{11}\right\rangle}\rightarrow{\left|{01}\right\rangle}\rightarrow{\left|{01}\right\rangle}\rightarrow{\left|{11}\right\rangle}.$

Hence the circuit faithfully implements the quantum swap gate.

By switching the control qubit and the target qubit of the second CNOT gate,
the circuit can be transformed to

$\textstyle{\bullet}$$\textstyle{H}$$\textstyle{\bullet}$$\textstyle{H}$$\textstyle{\bullet}$
$\textstyle{H}$ $\textstyle{H}$

By viewing the first qubit as the atom qubit and the second qubit as the
photon qubit, such a circuit can be realized using counterfactual special CNOT
gates. This example recovers the result of a recent counterfactual protocol of
a quantum swap gate Li  _et al._ (2019).

We then partially demonstrate the above protocol on the IBM Q platform. We
again assume that each CNOT gate in the circuit is realized by a
counterfactual CNOT gate. After inputting the states
${\left|{00}\right\rangle}$,
${\left|{10}\right\rangle},{\left|{01}\right\rangle}$, and
${\left|{11}\right\rangle}$, the returned results are
${\left|{00}\right\rangle},{\left|{01}\right\rangle},{\left|{10}\right\rangle}$,
and ${\left|{11}\right\rangle}$, respectively. This verifies that such a
circuit can counterfactually swap two qubits.

###  IV.3 Example 3: Quantum error erasure code

In the third example, we consider quantum error erasure codes. A quantum error
erasure code is a type of error correction code that focuses on recovering
erasure errors. The smallest quantum error erasure code contains four qubits.
The encodings of logic 0 and logic 1 are

$\displaystyle{\left|{0_{L}}\right\rangle}$ $\displaystyle=$
$\displaystyle{\left|{0000}\right\rangle}+{\left|{1111}\right\rangle},$
$\displaystyle{\left|{1_{L}}\right\rangle}$ $\displaystyle=$
$\displaystyle{\left|{1001}\right\rangle}+{\left|{0110}\right\rangle}.$ (14)

To prove that this code can correct erasure errors, it suffices to prove that
it can correct bit flip errors in two bases that can be transformed by
Hadamard gates Steane (1996). The base that is transformed from the encoding
basis with Hadamard gates is

$\displaystyle\centering{\left|{0^{\bot}}\right\rangle}\@add@centering$
$\displaystyle=$
$\displaystyle{\left|{0000}\right\rangle}+{\left|{0011}\right\rangle}+{\left|{0101}\right\rangle}+{\left|{0110}\right\rangle}$
$\displaystyle+{\left|{1001}\right\rangle}+{\left|{1010}\right\rangle}+{\left|{1100}\right\rangle}+{\left|{1111}\right\rangle},$
$\displaystyle{\left|{1^{\bot}}\right\rangle}$ $\displaystyle=$
$\displaystyle{\left|{0000}\right\rangle}-{\left|{0011}\right\rangle}-{\left|{0101}\right\rangle}+{\left|{0110}\right\rangle}$
$\displaystyle+{\left|{1001}\right\rangle}-{\left|{1010}\right\rangle}-{\left|{1100}\right\rangle}+{\left|{1111}\right\rangle}.$

In the error erasure channel, the position of the error is known but the
correct value is unknown. Note that the parity is even in the logic encoding;
hence an odd encoding indicates an error and this error can be corrected by
properly choosing the bit value on the erroneous qubit so that the parity is
restored. In terms of quantum circuit design, one can design the following
circuit to encrypt
${\left|{\psi}\right\rangle}=\alpha{\left|{0}\right\rangle}+\beta{\left|{1}\right\rangle}$
to $\alpha{\left|{0_{L}}\right\rangle}+\beta{\left|{1_{L}}\right\rangle}$:

$\textstyle{{\left|{\psi}\right\rangle}}$$\textstyle{\bullet}$
$\textstyle{{\left|{0}\right\rangle}}$$\textstyle{H}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{{\left|{0}\right\rangle}}$
$\textstyle{{\left|{0}\right\rangle}}$

After the first gate, ${\left|{0}\right\rangle}$ becomes
${\left|{0000}\right\rangle}$ and ${\left|{1}\right\rangle}$ becomes
${\left|{1001}\right\rangle}$. After the second gate,
${\left|{0000}\right\rangle}$ becomes
${\left|{0}\right\rangle}\otimes({\left|{0}\right\rangle}+{\left|{1}\right\rangle})\otimes{\left|{00}\right\rangle}$
and ${\left|{1001}\right\rangle}$ becomes
${\left|{1}\right\rangle}\otimes({\left|{0}\right\rangle}+{\left|{1}\right\rangle})\otimes{\left|{01}\right\rangle}$.
After the third, fourth and fifth gates,
${\left|{0}\right\rangle}\otimes({\left|{0}\right\rangle}+{\left|{1}\right\rangle})\otimes{\left|{00}\right\rangle}$
becomes ${\left|{0000}\right\rangle}+{\left|{1111}\right\rangle}$ and
${\left|{1}\right\rangle}\otimes({\left|{0}\right\rangle}+{\left|{1}\right\rangle})\otimes{\left|{01}\right\rangle}$
becomes ${\left|{1001}\right\rangle}+{\left|{0110}\right\rangle}$. This shows
that the encoding by the circuit achieves the logic encoding.

By the second transformation (10) and taking the second qubit to be the atom
qubit, the circuit is turned into

$\textstyle{{\left|{\psi}\right\rangle}}$$\textstyle{\bullet}$$\textstyle{\bullet}$
$\textstyle{{\left|{0}\right\rangle}}$ $\textstyle{\bullet}$
$\textstyle{H}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{{\left|{0}\right\rangle}}$
$\textstyle{{\left|{0}\right\rangle}}$

The first and third CNOT gates can be further transformed using the first
transformation (9), after which all the control qubits are set to the second
qubit. Hence, the logic encoding of a quantum erasure code can be
counterfactually prepared.

We then partially demonstrate this example on the IBM Q platform. We make the
same assumption that the CNOT gates are realized by counterfactual special
CNOT gates. When inputting the states ${\left|{0000}\right\rangle}$ and
${\left|{1000}\right\rangle}$, the returned results are
${\left|{0000}\right\rangle}+{\left|{1111}\right\rangle}and{\left|{0110}\right\rangle}+{\left|{1001}\right\rangle}$.
This verifies that the encodings of the logical 0 and 1 are counterfactually
prepared.

##  V Practical issues

In this section we consider some practical aspects of the CUQC scheme. In
particular, we give some variants of CUQC that address practical issues such
as efficiency improvement and device imperfections. We first replace the
single atom in the standard CUQC by multiple atoms and show to what extent
such a modification improves the overall system efficiency. Next we show the
effect of device imperfections on the performance of the CUQC scheme. The
device imperfections include finite $M$, finite $N$, photon loss, and atom
missing.

###  V.1 CUQC with multiple atoms

In this section we show that multiple atoms can significantly reduce the
circuit depth in some cases.

Suppose a circuit contains $n$ qubits and these $n$ qubits are grouped into
$n/2$ pairs of qubits. For each pair of qubits, there is a CNOT gate from one
of the qubits to the other qubit in the circuit. In total, there are $n/2$
pairs of parallel CNOT gates in this circuit and there are no other gates.

Now, we consider the implementation of this circuit. In the case that there is
only one atom qubit, by the second transformation (10), this atom qubit needs
to process $3n/2$ CNOT gates and hence the circuit depth is $\Omega(n)$. In
contrast, if there are $n/2$ atom qubits, the circuit depth can be
significantly reduced to at most $3$ (each atom qubit handles one CNOT gate).

Note that the total gate number of the circuit remains similar regardless of
the number of atoms. This type of speedup is in the same vein as parallel
computing. The atom qubits here take the place of central processing units in
parallel computing architecture.

###  V.2 Error analysis

In previous sections, we have assumed ideal devices and infinite cycles. In
this section, we consider various practical aspects, including finite $M$,
finite $N$, photon loss, and atom missing.

We consider two figures of merits: the efficiency of the computation and the
fidelity of the computed result. Since these two figures depend strongly on
the number of counterfactual special CNOT gates in the circuit, we first
analyze the case where the circuit consists of a single counterfactual special
CNOT gate. After that, we discuss quantum circuits that contain multiple
counterfactual special CNOT gates.

For the first part, we consider a single counterfactual special CNOT gate in
the case of practical devices. Recall that in our setup, the outer cycle
rotates the polarization by $\beta_{1}=\pi/2M$ and the inner cycle rotates the
polarization by $\beta_{2}=\pi/2N$. There are $M-1$ outer cycles and for each
outer cycle there are $2(N-1)$ inner cycles.

Let $P_{D}$ denote the probability that the photon passes the transmission
channel. The efficiency is defined as $\textsf{E}=1-P_{D}$. The unnormalized
output state of the circuit is defined by

${\left|{\psi_{\footnotesize\textrm{final}}}\right\rangle}=C_{1}{\left|{H}\right\rangle}{\left|{g}\right\rangle}+C_{2}{\left|{V}\right\rangle}{\left|{g}\right\rangle}+C_{3}{\left|{H}\right\rangle}{\left|{e}\right\rangle}+C_{4}{\left|{V}\right\rangle}{\left|{e}\right\rangle}.$
(16)

The efficiency E can be represented as

$\textsf{E}=\sum_{i=1}^{4}|C_{i}|^{2}.$ (17)

Since the ideal output is
${\left|{\psi_{\footnotesize\textrm{ideal}}}\right\rangle}=C_{e}{\left|{H}\right\rangle}{\left|{e}\right\rangle}+C_{g}{\left|{V}\right\rangle}{\left|{g}\right\rangle}$,
the fidelity is

$\textsf{F}=|C_{e}^{*}C_{3}+C_{g}^{*}C_{2}|^{2}/\textsf{E}.$ (18)

We proceed by first analyzing the final state of the photon when the atom is
in the state ${\left|{e}\right\rangle}$ under finite $M$ and $N$. In this
case, the initial photon state ${\left|{H}\right\rangle}$ will become
$\cos^{M}\beta_{1}{\left|{H}\right\rangle}$ at the end. Now we analyze the
more complicated case that the atom is in the state
${\left|{g}\right\rangle}$. Let $(X,Y)^{T}$ denote the quantum state
$X{\left|{H}\right\rangle}+Y{\left|{V}\right\rangle}$. For each outer cycle,
the state of the photon evolves as

$\left(\begin{array}[]{c}X_{i}\\\ Y_{i}\\\
\end{array}\right)=\left(\begin{array}[]{cc}1&0\\\ 0&\cos^{2N}\beta_{2}\\\
\end{array}\right)\left(\begin{array}[]{cc}\cos\beta_{1}&\sin\beta_{1}\\\
-\sin\beta_{1}&\cos\beta_{1}\\\
\end{array}\right)\left(\begin{array}[]{c}X_{i-1}\\\ Y_{i-1}\\\
\end{array}\right)$ (19)

The initial conditions are $X_{0}=1$ and $Y_{0}=0$ since the initial photon
state is ${\left|{H}\right\rangle}$. Hence, for an initial state

${\left|{\psi_{\footnotesize\textrm{initial}}}\right\rangle}={\left|{H}\right\rangle}(C_{e}{\left|{e}\right\rangle}+C_{g}{\left|{g}\right\rangle}),$
(20)

the final state becomes

${\left|{\psi_{\footnotesize\textrm{final}}}\right\rangle}=C_{e}\cos^{M}\beta_{1}{\left|{H}\right\rangle}{\left|{e}\right\rangle}+C_{g}X_{M}{\left|{H}\right\rangle}{\left|{g}\right\rangle}+C_{g}Y_{M}{\left|{V}\right\rangle}{\left|{g}\right\rangle}.$
(21)

The efficiency and the fidelity are then calculated according to Eqs. (17) and
(18) .

Figure 8: (a) Efficiency of the circuit under various $M$ and $N$. The
efficiency is almost the same for the same ratio of $N$ to $M$ and becomes
higher when the ratio of $N$ to $M$ increases. However, for a $N/M$ ratio of
20, the efficiency is still low (below 0.9). (b) Fidelity of the circuit
output under various $M$ and $N$. The fidelity is approximately the same for
the same ratio of $N$ to $M$ and becomes higher when the ratio of $N$ to $M$
increases. When the $N/M$ ratio is above 5, the fidelity is close to unity.

For an initial atom state
$({\left|{g}\right\rangle}+{\left|{e}\right\rangle})/\sqrt{2}$, we plot the
efficiency against different $M$ and $N$ in Fig. 8(a) and the fidelity against
different $M$ and $N$ in Fig. 8(b). It can be seen that the fidelity
approaches one when $N$ is over five times $M$. The efficiency is more
stringent for the ratio of $N$ to $M$. Even when the ratio of $N$ to $M$ is
20, the efficiency is still below 0.9.

Hereafter, we set $M=10$ and $N=200$ and consider the effect of photon loss
and atom missing. We let $\gamma$ denote the probability of photon loss in the
transmission channel and let $\eta$ denote the probability of atom missing.

We first analyze the effect of photon loss and assume there is no atom
missing. If the atom is in the ground state, the transmission is always
blocked; hence whether the photon is lost in the transmission channel does not
make any difference. Therefore, we only need to consider the case that the
atom is in the state ${\left|{e}\right\rangle}$. After $N-1$ inner cycles,
some proportion of the vertical component will go into the next $N-1$ inner
cycles. The proportion is given by $W$, the first entry of the vector

$\left(\begin{array}[]{c}W\\\ \\\
\end{array}\right)=\left(\begin{array}[]{cc}\cos\beta_{2}&\sin\beta_{2}\\\
-(1-\gamma)\sin\beta_{2}&(1-\gamma)\cos\beta_{2}\\\
\end{array}\right)^{N}\left(\begin{array}[]{c}1\\\ 0\\\ \end{array}\right).$
(22)

After being reflected by the double-sided mirror, this vertical component goes
through another $N-1$ inner cycles before reaching the end of one outer cycle,
and hence the $W^{2}$ proportion of the vertical component remains after each
outer cycle. The state change for each outer cycle becomes

$\displaystyle\left(\begin{array}[]{c}U_{i}\\\ V_{i}\\\
\end{array}\right)=\left(\begin{array}[]{cc}1&0\\\ 0&W^{2}\\\
\end{array}\right)\left(\begin{array}[]{cc}\cos\beta_{1}&\sin\beta_{1}\\\
-\sin\beta_{1}&\cos\beta_{1}\\\
\end{array}\right)\left(\begin{array}[]{c}U_{i-1}\\\ V_{i-1}\\\
\end{array}\right).$ (31)

The initial conditions are $U_{0}=1$ and $V_{0}=0$. After $M-1$ outer cycles,
the final state becomes

${\left|{\psi_{\footnotesize\textrm{final}}}\right\rangle}=C_{e}U_{M}{\left|{H}\right\rangle}{\left|{e}\right\rangle}+C_{e}V_{M}{\left|{V}\right\rangle}{\left|{e}\right\rangle}+C_{g}X_{M}{\left|{H}\right\rangle}{\left|{g}\right\rangle}+C_{g}Y_{M}{\left|{V}\right\rangle}{\left|{g}\right\rangle}.$
(32)

We plot the efficiency and fidelity as a function of the photon loss
probability $\gamma$ in Fig. 9(a). It can be seen that the fidelity steadily
decreases, while the efficiency initially declines and then slowly increases.
When the photon loss is small, both the fidelity and the efficiency decrease
significantly as the photon loss increases.

Figure 9:  (a) Efficiency (blue solid line) and fidelity (red dashed line) vs
the photon loss probability $\gamma$. When $\gamma$ increases in the range
$0<\gamma<0.1$, the efficiency and the fidelity decrease rapidly. This shows
that the efficiency and the fidelity are quite sensitive to a small
probability of photon loss. (b) Efficiency and fidelity vs the atom missing
probability $\eta$. When $\eta$ increases in the region $0<\eta<0.1$, the
efficiency and the fidelity degrade slowly. This shows that the protocol is
resilient to infrequent block failure of the atom.

Now we analyze the effect of atom missing and assume that there is no photon
loss. In the atom missing case, the atom may fail to block the photon and let
the photon pass through. Apparently, if the atom is in the state
${\left|{e}\right\rangle}$, whether the atom blocks does not make any
difference. When the atom is in the state ${\left|{g}\right\rangle}$, the
vertical component no longer decays with a decay rate $\cos^{2N}\beta_{2}$ for
each outer cycle.

After $N-1$ inner cycles, the vertical component decays as the first entry $Z$
in the vector

$\left(\begin{array}[]{c}Z\\\ \\\
\end{array}\right)=\left(\begin{array}[]{cc}\cos\beta_{2}&\sin\beta_{2}\\\
-\eta\sin\beta_{2}&\eta\cos\beta_{2}\\\
\end{array}\right)^{N}\left(\begin{array}[]{c}1\\\ 0\\\ \end{array}\right).$
(33)

After being reflected by the double-sided mirror and going through another
$N-1$ inner cycles, the vertical component decays with the same proportion, so
the overall decay for one outer cycle is $Z^{2}$.

When $\eta=0$, this first entry is $Z=\cos^{N}\beta_{2}$, recovering the ideal
case. The state change for each outer cycle becomes

$\displaystyle\left(\begin{array}[]{c}X_{i}^{\prime}\\\ Y_{i}^{\prime}\\\
\end{array}\right)=\left(\begin{array}[]{cc}1&0\\\ 0&Z^{2}\\\
\end{array}\right)\left(\begin{array}[]{cc}\cos\beta_{1}&\sin\beta_{1}\\\
-\sin\beta_{1}&\cos\beta_{1}\\\
\end{array}\right)\left(\begin{array}[]{c}X_{i-1}^{\prime}\\\
Y_{i-1}^{\prime}\\\ \end{array}\right).$ (42)

The initial conditions are $X_{0}^{\prime}=1$ and $Y_{0}^{\prime}=0$. After
$M-1$ outer cycles, the final state becomes

${\left|{\psi_{\footnotesize\textrm{final}}}\right\rangle}=C_{e}\cos^{M}\beta_{1}{\left|{H}\right\rangle}{\left|{e}\right\rangle}+C_{g}X_{M}^{\prime}{\left|{H}\right\rangle}{\left|{g}\right\rangle}+C_{g}Y_{M}^{\prime}{\left|{V}\right\rangle}{\left|{g}\right\rangle}.$
(43)

We plot the efficiency and the fidelity as a function of the atom missing
probability $\eta$ in Fig. 9(b). It can be seen that the efficiency and the
fidelity both decrease slowly as $\eta$ increases in the range $0<\eta<0.1$.

For the second part, we show how the composition of the CNOT gates affects the
transfer efficiency and the fidelity of a circuit with multiple counterfactual
special CNOT gates. Suppose there are $K$ CNOT gates in a circuit Circ. The
transfer efficiency and the fidelity for a single CNOT gate are denoted by
$\textsf{E}(\textrm{CNOT})$ and $\textsf{F}(\textrm{CNOT})$, respectively.

Since Circ gets an output if and only if all CNOT gates in Circ succeed, the
efficiency of Circ is

$\textsf{E}(\textsc{Circ})=\textsf{E}(\textrm{CNOT})^{K}.$ (44)

For the fidelity part, we can view each quantum state as a vector and the
deviation can be characterized by the angle $\theta$ between the ideal vector
and the actual vector. By the definition of fidelity, we have

$\textsf{F}(\textrm{CNOT})=\cos^{2}\theta.$ (45)

In the worst case, the deviation happens in the same direction for all $K$
CNOT gates. In that case, the final vector deviates from the original vector
by an angle of $K\theta$. Combined with Eq. (45), the fidelity of Circ is
lower bounded by

$\textsf{F}(\textsc{Circ})\geq\cos^{2}[K\arccos\sqrt{\textsf{F}(\textrm{CNOT})}].$
(46)

##  VI Conclusion

In summary, we have shown a CUQC scheme of which the two-level quantum
subsystems have no interaction with each other during the computation. The
CUQC scheme is based on counterfactual special CNOT gates together with
appropriate circuit transformations. On a physical level, the scheme is based
on an atom qubit and an arbitrary number of photon qubits. As special cases,
we have shown counterfactual communication of a quantum state, counterfactual
quantum state swapping, and counterfactual quantum erasure code. The CUQC
scheme has been extended to the multiple atom qubit case, the case of a finite
round number, and the case of imperfect devices such as photon loss and atom
missing.

The CUQC scheme illustrates again the mysterious nature of quantum physics. In
addition to its theoretical interest, this scheme also has some practical
applications. In particular, the scheme enables grayscale imaging, by taking
the atom state in Sec. IV.1 to be
$p_{i}{\left|{0}\right\rangle}{\left\langle{0}\right|}+(1-p_{i}){\left|{1}\right\rangle}{\left\langle{1}\right|}$,
where $0\leq p_{i}\leq 1$ characterizes the grayness of the image. By
combining the grayscale images of three primary colors, we recover the full
color image. The imaging method we propose here has the notable feature that
no photon touches the image. This is especially important for the imaging of
ancient arts, to which even faint light can potentially cause significant
damage.

As future directions, it would be interesting to explore optical elements that
can split into more than two paths. In that case, a qutrit or a qudit, for
example, can be counterfactually transmitted with the same number of rounds as
a qubit. Another direction is to design passive substitutes for the switchable
components of a counterfactual special CNOT gate, as this part is quite
difficult to realize in laboratories. A third direction is to find other
physical platforms to realize the CUQC scheme, in addition to the hybrid
system of atoms and photons. For example, one can consider whether an all-
optical system can realize the CUQC scheme. As a fourth direction, a full
experimental realization of the CUQC scheme and its special cases presented in
this work is of great interest.

## Acknowledgements

This work was supported by the internal Grant No. SLH00202007 from East China
University of Science and Technology.

##  Appendix A Genuine counterfactual communication of mixed qubits and higher
dimensional quantum states

In this appendix, we generalize our counterfactual communication result first
to transmitting a mixed qubit and then to transmitting higher-dimensional
quantum states.

Note that a mixed qubit can be represented by
$\\{(p_{1},{\left|{\psi_{1A}}\right\rangle}),(p_{2},{\left|{\psi_{2A}}\right\rangle}),\cdots,(p_{k},{\left|{\psi_{kA}}\right\rangle})\\}$,
where $p_{i}$ is the probability of the state
${\left|{\psi_{iA}}\right\rangle}$ and the subscript $A$ means that this is an
atom qubit. During the protocol, the whole system evolves as

$\displaystyle\\{(p_{1},{\left|{\psi_{1A}}\right\rangle}),\cdots,(p_{k},{\left|{\psi_{kA}}\right\rangle})\\}{\left|{H}\right\rangle}$
(47) $\displaystyle=$
$\displaystyle\\{(p_{1},{\left|{\psi_{1A}}\right\rangle}{\left|{H}\right\rangle}),\cdots,(p_{k},{\left|{\psi_{kA}}\right\rangle}{\left|{H}\right\rangle})\\}$
$\displaystyle\stackrel{{\scriptstyle\mathcal{P}}}{{\rightarrow}}$
$\displaystyle\\{(p_{1},{\left|{e}\right\rangle}{\left|{\psi_{1P}}\right\rangle}),\cdots,(p_{k},{\left|{e}\right\rangle}{\left|{\psi_{kP}}\right\rangle})\\}$
$\displaystyle=$
$\displaystyle{\left|{e}\right\rangle}\\{(p_{1},{\left|{\psi_{1P}}\right\rangle}),\cdots,(p_{k},{\left|{\psi_{kP}}\right\rangle})\\},$

where ${\left|{\psi_{iA}}\right\rangle}={\left|{\psi_{iP}}\right\rangle}$,
$\mathcal{P}$ is the action of the protocol, and the subscript $P$ in
${\left|{\psi_{iP}}\right\rangle}$ means that this is a photon qubit. Hence,
by applying the quantum protocol, the state of the photon becomes
$\\{(p_{1},{\left|{\psi_{1P}}\right\rangle}),(p_{2},{\left|{\psi_{2P}}\right\rangle}),\cdots,(p_{k},{\left|{\psi_{kP}}\right\rangle})\\}$.
In other words, the mixed quantum state from the atom has transmitted to the
photon faithfully.

Next we generalize the qubit result to higher dimensions. We note that higher-
dimensional quantum states can be viewed as multiple qubit states that are
entangled. For simplicity, we show that two entangled qubits can be
counterfactually communicated. The case of more than two qubits is similar.
Two entangled qubits can be represented in the computational basis as

$C_{ee}{\left|{ee}\right\rangle}+C_{eg}{\left|{eg}\right\rangle}+C_{ge}{\left|{ge}\right\rangle}+C_{gg}{\left|{gg}\right\rangle}.$
(48)

During the protocol, the whole system evolves as

$\displaystyle(C_{ee}{\left|{ee}\right\rangle}+C_{eg}{\left|{eg}\right\rangle}+C_{ge}{\left|{ge}\right\rangle}+C_{gg}{\left|{gg}\right\rangle}){\left|{HH}\right\rangle}$
$\displaystyle=$ $\displaystyle
C_{ee}{\left|{ee}\right\rangle}{\left|{HH}\right\rangle}+C_{eg}{\left|{eg}\right\rangle}{\left|{HH}\right\rangle}+C_{ge}{\left|{ge}\right\rangle}{\left|{HH}\right\rangle}+C_{gg}{\left|{gg}\right\rangle}{\left|{HH}\right\rangle}$
$\displaystyle\stackrel{{\scriptstyle\mathcal{P}}}{{\rightarrow}}$
$\displaystyle
C_{ee}{\left|{ee}\right\rangle}{\left|{HH}\right\rangle}+C_{eg}{\left|{ee}\right\rangle}{\left|{HV}\right\rangle}+C_{ge}{\left|{ee}\right\rangle}{\left|{VH}\right\rangle}+C_{gg}{\left|{ee}\right\rangle}{\left|{VV}\right\rangle}$
$\displaystyle=$
$\displaystyle{\left|{ee}\right\rangle}(C_{ee}{\left|{HH}\right\rangle}+C_{eg}{\left|{HV}\right\rangle}+C_{ge}{\left|{VH}\right\rangle}+C_{gg}{\left|{VV}\right\rangle}),$

where $\mathcal{P}$ is the action of the protocol. In other words, after the
protocol, the state of the atoms is transferred to the photons faithfully and
turns the state of the photons to
$C_{ee}{\left|{HH}\right\rangle}+C_{eg}{\left|{HV}\right\rangle}+C_{ge}{\left|{VH}\right\rangle}+C_{gg}{\left|{VV}\right\rangle}$.
Similar to the previous analysis that extends pure qubits to mixed qubits, the
analysis of high-dimensional pure quantum states can also be extended to that
of high-dimensional mixed quantum states.

## References

  * Dicke (1981) R. H. Dicke, American Journal of Physics 49, 925 (1981).
  * Elitzur and Vaidman (1993) A. C. Elitzur and L. Vaidman, Foundations of Physics 23, 987 (1993).
  * Kwiat  _et al._ (1995) P. Kwiat, H. Weinfurter, T. Herzog, A. Zeilinger, and M. A. Kasevich, Physical Review Letters 74, 4763 (1995).
  * Misra and Sudarshan (1977) B. Misra and E. G. Sudarshan, Journal of Mathematical Physics 18, 756 (1977).
  * Peres (1980) A. Peres, American Journal of Physics 48, 931 (1980).
  * Agarwal and Tewari (1994) G. S. Agarwal and S. P. Tewari, Physics Letters A 185, 139 (1994).
  * Noh  _et al._ (2009) T.-G. Noh _et al._ , Physical Review Letters 103, 230501 (2009).
  * Ren  _et al._ (2011) M. Ren, G. Wu, E. Wu, and H. Zeng, Laser Physics 21, 755 (2011).
  * Brida  _et al._ (2012) G. Brida, A. Cavanna, I. P. Degiovanni, M. Genovese, and P. Traina, Laser Physics Letters 9, 247 (2012).
  * Liu  _et al._ (2012) Y. Liu, L. Ju, X.-L. Liang, S.-B. Tang, G.-L. S. Tu, L. Zhou, C.-Z. Peng, K. Chen, T.-Y. Chen, Z.-B. Chen, _et al._ , Physical Review Letters 109, 030501 (2012).
  * Kwiat  _et al._ (1999) P. G. Kwiat, A. White, J. Mitchell, O. Nairz, G. Weihs, H. Weinfurter, and A. Zeilinger, Physical Review Letters 83, 4725 (1999).
  * Elitzur and Cohen (2015) A. C. Elitzur and E. Cohen, International Journal of Quantum Information 12, 1560024 (2015).
  * Aharonov  _et al._ (2018) Y. Aharonov, E. Cohen, A. C. Elitzur, and L. Smolin, Foundations of Physics 48, 1 (2018).
  * Hosten  _et al._ (2006) O. Hosten, M. T. Rakher, J. T. Barreiro, N. A. Peters, and P. G. Kwiat, Nature 439, 949 (2006).
  * Kong  _et al._ (2015) F. Kong, C. Ju, P. Huang, P. Wang, X. Kong, F. Shi, L. Jiang, and J. Du, Physical Review Letters 115, 080501 (2015).
  * Salih  _et al._ (2013) H. Salih, Z.-H. Li, M. Al-Amri, and M. S. Zubairy, Physical Review Letters 110, 170502 (2013).
  * Cao  _et al._ (2017) Y. Cao, Y.-H. Li, Z. Cao, J. Yin, Y.-A. Chen, H.-L. Yin, T.-Y. Chen, X. Ma, C.-Z. Peng, and J.-W. Pan, Proceedings of the National Academy of Sciences 114, 4920 (2017).
  * Vaidman (2014) L. Vaidman, Physical Review Letters 112, 208901 (2014).
  * Salih  _et al._ (2014) H. Salih, Z.-H. Li, M. Al-Amri, and M. S. Zubairy, Physical Review Letters 112, 208902 (2014).
  * Salih  _et al._ (2018) H. Salih, W. McCutcheon, J. Hance, and J. Rarity, arXiv preprint arXiv:1806.01257 (2018).
  * Vaidman (2013) L. Vaidman, Physical Review A 87, 052104 (2013).
  * Aharonov and Vaidman (2019) Y. Aharonov and L. Vaidman, Physical Review A 99, 010103 (2019).
  * Li  _et al._ (2015) Z.-H. Li, M. Al-Amri, and M. S. Zubairy, Physical Review A 92, 052315 (2015).
  * Vaidman (2016) L. Vaidman, Physical Review A 93, 066301 (2016).
  * Li  _et al._ (2019) Z.-H. Li, M. Al-Amri, X.-H. Yang, and M. S. Zubairy, Physical Review A 100, 022110 (2019).
  * Deutsch (1989) D. E. Deutsch, Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences 425, 73 (1989).
  * DiVincenzo (1995) D. P. DiVincenzo, Physical Review A 51, 1015 (1995).
  * (28) https://quantum-computing.ibm.com .
  * Steane (1996) A. M. Steane, Physical Review Letters 77, 793 (1996).